26838 research outputs found
Sort by
Strong pseudorandom functions in AC0[2] in the bounded-query setting
Get PDFUnderstanding the minimal computational power needed to realize a pseudorandom function (PRF) is a long-standing question in cryptography. By the Razborov–Smolensky polynomial approximation method, it is known that cannot support strong pseudorandom functions with subexponential security, since any such function can be distinguished from random with quasipolynomially many samples. In this work, we initiate the study of low-complexity strong PRFs under a refined framework that separates adversary query complexity from running time, and observe that distinguishing algorithms for do not apply if the number of queries is below the threshold implied by the Razborov–Smolensky approximation bound. We propose the first candidate strong PRF in , which plausibly offers subexponential security against adversaries limited to a fixed quasipolynomial number of queries. We show that
our candidate lacks heavy Fourier coefficients, resists a natural class of adaptive attacks, has high rational degree, is non-sparse over F2 in expectation, and has low correlation with fixed function families. Finally, we show that if any strong PRF exists in (or a superclass), then we can construct a universal PRF, i.e., a single, fixed function which is guaranteed to be a strong PRF in the same class
Oblivious batch updates for bloom-filter-based outsourced cryptographic protocols
Get PDFIn this work, we initiate the formal study of oblivious batch updates over outsourced encrypted Bloom filters, focusing on scenarios where a storage-limited sender must insert or delete batches of elements in a Bloom filter maintained on an untrusted server. Our survey identifies only two prior approaches (CCS 2008 and CCS 2012) that can be adapted to this problem. However, they either fail to provide adequate security in dynamic scenarios or incur prohibitive update costs that scale with the filter’s maximum capacity rather than the actual batch size.
To address these limitations, we introduce a new cryptographic primitive, Oblivious Bloom Filter Insertion (OBFI), and propose novel constructions. At the core of our design is a novel building block, Oblivious Bucket Distribution (OBD), which enables a storage-limited sender to distribute a large array of elements, uniformly sampled from a finite domain, into small, fixed-size buckets in a data-oblivious manner determined by element order. The design of OBD is further supported by identifying and proving a new structural property of such arrays, which establishes tight and explicit probabilistic bounds on the number of elements falling within predefined subranges of the domain. Our OBFI constructions achieve adaptive data-obliviousness and ensure that batch update costs scale primarily with the batch size. Depending on the variant, the sender’s storage requirement ranges from O(λ), where λ is the security parameter, down to O(1). Finally, we demonstrate the practicality of OBFI by integrating it into representative Bloom-filterbased cryptographic protocols for Searchable Symmetric Encryption, Public-key Encryption with Keyword Search, and Outsourced Private Set Intersection, thereby obtaining batch-updatable counterparts with state-of-the-art security and performance
Dark haptics: Exploring manipulative haptic design in mobile user interfaces
No full textMobile user interfaces abundantly feature so-called 'dark patterns'. These deceptive design practices manipulate users’ decision making to profit online service providers. While past research on dark patterns mainly focus on visual design, other sensory modalities such as audio and touch remain largely unexplored. In this early work, we investigate the manipulative side of haptics, which we term as 'Dark Haptics', as a strategy to manipulate users. We designed a study to empirically showcase the potential of using a dark haptic pattern in a mobile device to manipulate user actions in a survey. Our findings indicate that our dark haptic design successfully influenced participants to forego their privacy after experiencing an alarming feedback for rejecting intrusive requests in the survey. As a first exploration of manipulative qualities of dark haptic designs, we attempt to lay the groundwork for future research and tools to mitigate harms and risks of dark haptics
Large deviations asymptotics for unbounded additive functionals of diffusion processes
No full textWe study large deviations asymptotics for a class of unbounded additive functionals, interpreted as normalized accumulated areas, of one-dimensional Langevin diffusions with sub-linear gradient drifts. Our results provide parametric insights on the speed and the rate functions in terms of the growth rate of the drift and the growth rate of the additive functional. We find a critical value in terms of these growth parameters that dictates regions of sub-linear speed for our large deviations asymptotics. Our approach is based upon various constructions of independent interest, including a decomposition of the diffusion process in terms of alternating renewal cycles and a detailed analysis of the paths during a cycle using suitable time and spatial scales. The key to the sub-linear behavior is a heavy-tailed large deviations phenomenon arising from the principle of a single big jump coupled with the result that at each regeneration cycle the upper-tail asymptotic behavior of the accumulated area of the diffusion process is proven to be semi-exponential (i.e., of heavy-tailed Weibull type)
Boekingssite voor Amsterdamse verpleeghuisbedden verkort wachttijden aanzienlijk - Zorgvisie - 08-05-2025
No full text
