Anonymous tokens are, essentially, digital signature schemes that enable issuers to provide users with signatures without learning the user inputs or the final signatures. These primitives allow applications to propagate trust while simultaneously protecting the user identity. They have become a core component for improving the privacy of several real-world applications including ad measurements, authorization protocols, spam detection, and VPNs. In certain applications, it is natural to associate signatures with specific public metadata, ensuring that trust is only propagated with respect to only a certain set of users and scenarios. To solve this, we study the notion of anonymous tokens with public metadata. We present a variant of RSA blind signatures with public metadata where issuers may only generate signatures that verify for a certain choice of public metadata that is a modification of a scheme by Abe and Fujisaki. Our protocol exclusively uses standard cryptography with widely available implementations. We prove security from the one-more RSA assumptions with multiple exponents that we introduce. Furthermore, we provide evidence that the concrete security bounds should be nearly identical to standard RSA blind signatures. We show that our protocol incurs minimal overhead over standard RSA blind signatures and report anonymous telemetry for a real-world deployment to showcase its scalability. Following our work, our protocol has been proposed as a technical specification in an IRTF internet draft.

Threshold secret sharing enables distributing a message to n parties such that no subset of fewer than t parties can learn the message, whereas any subset of at least t parties can recover the message. Despite being a fundamental primitive, secret sharing still suffers from one significant drawback, where its message reconstruction algorithm is computationally expensive for large privacy thresholds t. In this paper, we aim to address this significant drawback.

In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of $n$ points from a universe consisting of $m=n^{1+Ω(1)}$ points. A data structure is defined to be non-adaptive when the memory locations that are chosen to be accessed during a query depend only on the query inputs and not on the contents of memory. We prove an $Ω(\log m / \log (sw/n\log m))$ static cell probe complexity lower bound for non-adaptive data structures that solve the fundamental dictionary problem where $s$ denotes the space of the data structure in the number of cells and $w$ is the cell size in bits. Our lower bounds hold for all word sizes including the bit probe model ($w = 1$) and are matched by the upper bounds of Boninger et al. [FSTTCS'17]. Our results imply a sharp dichotomy between dictionary data structures with one round of adaptive and at least two rounds of adaptivity. We show that $O(1)$, or $O(\log^{1-ε}(m))$, overhead dictionary constructions are only achievable with at least two rounds of adaptivity. In particular, we show that many $O(1)$ dictionary constructions with two rounds of adaptivity such as cuckoo hashing are optimal in terms of adaptivity. On the other hand, non-adaptive dictionaries must use significantly more overhead. Finally, our results also imply static lower bounds for the non-adaptive predecessor problem. Our static lower bounds peak higher than the previous, best known lower bounds of $Ω(\log m / \log w)$ for the dynamic predecessor problem by Boninger et al. [FSTTCS'17] and Ramamoorthy and Rao [CCC'18] in the natural setting of linear space $s = Θ(n)$ where each point can fit in a single cell $w = Θ(\log m)$. Furthermore, our results are stronger as they apply to the static setting unlike the previous lower bounds that only applied in the dynamic setting.

We study the problem of differentially private (DP) mechanisms for representing sets of size $k$ from a large universe. Our first construction creates $(\epsilon,\delta)$-DP representations with error probability of $1/(e^\epsilon + 1)$ using space at most $1.05 k \epsilon \cdot \log(e)$ bits where the time to construct a representation is $O(k \log(1/\delta))$ while decoding time is $O(\log(1/\delta))$. We also present a second algorithm for pure $\epsilon$-DP representations with the same error using space at most $k \epsilon \cdot \log(e)$ bits, but requiring large decoding times. Our algorithms match the lower bounds on privacy-utility trade-offs (including constants but ignoring $\delta$ factors) and we also present a new space lower bound matching our constructions up to small constant factors. To obtain our results, we design a new approach embedding sets into random linear systems deviating from most prior approaches that inject noise into non-private solutions.

We study encrypted storage schemes where a client outsources data to an untrusted third-party server (such as a cloud storage provider) while maintaining the ability to privately query and dynamically update the data. We focus on encrypted multi-maps (EMMs), a structured encryption (STE) scheme that stores pairs of label and value tuples. EMMs allow queries on labels and return the associated value tuple. As responses are variable-length, EMMs are subject to volume leakage attacks introduced by Kellaris et al. [CCS'16]. To prevent these attacks, volume-hiding EMMs were introduced by Kamara and Moataz [Eurocrypt'19] that hide the label volumes (i.e., the value tuple lengths). As our main contribution, we present the first fully dynamic volume-hiding EMMs that are both asymptotically and concretely efficient. Furthermore, they are simultaneously forward and backward private which are the de-facto standard security notions for dynamic STE schemes. Additionally, we implement our schemes to showcase their concrete efficiency. Our experimental evaluations show that our constructions are able to add dynamicity with minimal to no additional cost compared to the prior best static volume-hiding schemes of Patel et al. [CCS'19].

We present lower bounds for the static cryptographic data structure problem of single-server private information retrieval (PIR). PIR considers the setting where a server holds a database of n entries and a client wishes to privately retrieve the i-th entry without revealing the index i to the server. In our work, we focus on PIR with preprocessing where an r-bit hint may be computed in a preprocessing stage and stored by the server to be used to perform private queries in expected time t. As our main result, we prove that for any single-server, computationally secure PIR with preprocessing, it must be that tr = Ω(n log n) when r = Ω(log n). If r = O(log n), then we show that t = Ω(n). Our lower bound holds even when the scheme errs with probability 1/n2 and the adversary's distinguishing advantage is 1/n. Our work improves upon the tr = Ω(n) lower bound of Beimel, Ishai and Malkin [JoC'04]. For information-theoretic security, we present a stronger lower bound of t + r = Ω(n) and show a matching construction. Both our lower bounds apply for public-key doubly-efficient PIRs of Boyle, Ishai, Pass and Wootters [TCC'17]. Additionally, our lower bound for information-theoretic security also applies for offline-online PIRs as defined by Corrigan-Gibbs and Kogan [Eurocrypt'20], where the hint is private and only viewed by the client. We prove our lower bounds in a variant of the cell probe model where only accesses to the database are charged cost and computation and accesses to the hint are free. Our main technical contribution is a novel use of the cell sampling technique (also known as the incompressibility technique) used to obtain lower bounds on data structures. In previous works, this technique only leveraged the correctness guarantees to prove lower bounds even when used for cryptographic primitives. Our work combines the cell sampling technique with the privacy guarantees of PIR to construct a powerful, polynomial-time adversary that is critical to proving our higher lower bounds.

The Web public key infrastructure is essential to providing secure communication on the Internet today, and certificate authorities play a crucial role in this ecosystem by issuing certificates. These authorities may misissue certificates or suffer misuse attacks, however, which has given rise to the Certificate Transparency (CT) project. The goal of CT is to store all issued certificates in public logs, which can then be checked for the presence of potentially misissued certificates. Thus, the requirement that a given certificate is indeed in one (or several) of these logs lies at the core of CT. In its current deployment, however, most individual clients do not check that the certificates they see are in logs, as requesting a proof of inclusion directly reveals the certificate and thus creates the clear potential for a violation of that client’s privacy. In this paper, we explore the techniques that have been proposed for privacy-preserving auditing of certificate inclusion, focusing on their effectiveness, efficiency, and suitability in a near-term deployment. In doing so, we also explore the parallels with related problems involving browser clients. Guided by a set of constraints that we develop, we ultimately observe several key limitations in many proposals, ranging from their privacy provisions to the fact that they focus on the interaction between a client and a log but leave open the question of how a client could privately report any certificates that are missing.

We prove an Ω(d lg n/(lg lg n)2) lower bound on the dynamic cell-probe complexity of statistically oblivious approximate-near-neighbor search (ANN) over the d-dimensional Hamming cube. For the natural setting of d = Θ(lg n), our result implies an lower bound, which is a quadratic improvement over the highest (non-oblivious) cell-probe lower bound for ANN. This is the first super-logarithmic unconditional lower bound for ANN against general (non black-box) data structures. We also show that any oblivious static data structure for decomposable search problems (like ANN) can be obliviously dynamized with O(lg n) overhead in update and query time, strengthening a classic result of Bentley and Saxe (Algorithmica, 1980).

Volume leakage has recently been identified as a major threat to the security of cryptographic cloud-based data structures by Kellaris \em et al. [CCS'16] (see also the attacks in Grubbs \em et al. [CCS'18] and Lacharité \em et al. [S&P'18]). In this work, we focus on volume-hiding implementations of \em encrypted multi-maps as first considered by Kamara and Moataz [Eurocrypt'19]. Encrypted multi-maps consist of outsourcing the storage of a multi-map to an untrusted server, such as a cloud storage system, while maintaining the ability to perform private queries. Volume-hiding encrypted multi-maps ensure that the number of responses (volume) for any query remains hidden from the adversarial server. As a result, volume-hiding schemes can prevent leakage attacks that leverage the adversary's knowledge of the number of query responses to compromise privacy. We present both conceptual and algorithmic contributions towards volume-hiding encrypted multi-maps. We introduce the first formal definition of volume-hiding leakage functions. In terms of design, we present the first volume-hiding encrypted multi-map dprfMM whose storage and query complexity are both asymptotically optimal. Furthermore, we experimentally show that our construction is practically efficient. Our server storage is smaller than the best previous construction while we improve query complexity by a factor of 10-16x. In addition, we introduce the notion of differentially private volume-hiding leakage functions which strikes a better, tunable balance between privacy and efficiency. To accompany our new notion, we present a differentially private volume-hiding encrypted multi-map dpMM whose query complexity is the volume of the queried key plus an additional logarithmic factor. This is a significant improvement compared to all previous volume-hiding schemes whose query overhead was the maximum volume of any key. In natural settings, our construction improves the average query overhead by a factor of 150-240x over the previous best volume-hiding construction even when considering small privacy budget of ε=0.2.

Oblivious RAM (ORAM) and private information retrieval (PIR) are classic cryptographic primitives used to hide the access pattern to data whose storage has been outsourced to an untrusted server. Unfortunately, both primitives require considerable overhead compared to plaintext access. For large-scale storage infrastructure with highly frequent access requests, the degradation in response time and the exorbitant increase in resource costs incurred by either ORAM or PIR prevent their usage. In an ideal scenario, a privacy-preserving storage protocols with small overhead would be implemented for these heavily trafficked storage systems to avoid negatively impacting either performance and/or costs. In this work, we study the problem of the best \em storage access privacy that is achievable with only \em small overhead over plaintext access. To answer this question, we consider \em differential privacy access which is a generalization of the \em oblivious access security notion that are considered by ORAM and PIR. Quite surprisingly, we present strong evidence that constant overhead storage schemes may only be achieved with privacy budgets of ε = Ømega(łog n)$. We present asymptotically optimal constructions for differentially private variants of both ORAM and PIR with privacy budgets ε = Θ(łog n)$ with only $O(1)$ overhead. In addition, we consider a more complex storage primitive called key-value storage in which data is indexed by keys from a large universe (as opposed to consecutive integers in ORAM and PIR). We present a differentially private key-value storage scheme with ε = Θ(łog n)$ and $O(łogłog n)$ overhead. This construction uses a new oblivious, two-choice hashing scheme that may be of independent interest.

Private information retrieval (PIR) is a fundamental tool for preserving query privacy when accessing outsourced data. All previous PIR constructions have significant costs preventing widespread use. In this work, we present private stateful information retrieval (PSIR), an extension of PIR, allowing clients to be stateful and maintain information between multiple queries. Our design of the PSIR primitive maintains three important properties of PIR: multiple clients may simultaneously query without complex concurrency primitives, query privacy should be maintained if the server colludes with other clients, and new clients should be able to enroll into the system by exclusively interacting with the server. We present a PSIR framework that reduces an online query to performing one single-server PIR on a sub-linear number of database records. All other operations beyond the single-server PIR consist of cryptographic hashes or plaintext operations. In practice, the dominating costs of resources occur due to the public-key operations involved with PIR. By reducing the input database to PIR, we are able to limit expensive computation and avoid transmitting large ciphertexts. We show that various instantiations of PSIR reduce server CPU by up to 10x and online network costs by up to 10x over the previous best PIR construction.

We present PanORAMa, the first Oblivious RAM construction that achieves communication overhead O(log N log log N) for database of N blocks and for any block size B = Ω(log N) while requiring client memory of only a constant number of memory blocks. Our scheme can be instantiated in the "balls and bins" model in which Goldreich and Ostrovsky [JACM 96] showed an Ω(log N) lower bound for ORAM communication. Our construction follows the hierarchical approach to ORAM design and relies on two main building blocks of independent interest: a new oblivious hash table construction with improved amortized O(log N + poly(log log λ)) communication overhead for security parameter λ and N = poly(λ), assuming its input is randomly shuffled; and a complementary new oblivious random multi-array shuffle construction, which shuffles N blocks of data with communication O(N log log λ + N log N/log λ) when the input has a certain level of entropy. We combine these two primitives to improve the shuffle time in our hierarchical ORAM construction by avoiding heavy oblivious shuffles and leveraging entropy remaining in the merged levels from previous shuffles. As a result, the amortized shuffle cost is asymptotically the same as the lookup complexity in our construction.

We consider Oblivious Shuffling and K-Oblivious Shuffling, a refinement thereof. We provide efficient algorithms for both and discuss their application to the design of Oblivious RAM. The task of K-Oblivious Shuffling is to obliviously shuffle N encrypted blocks that have been randomly allocated on the server in such a way that an adversary learns nothing about the new allocation of blocks. The security guarantee should hold also with respect to an adversary that has learned the initial position of K touched blocks out of the N blocks. The classical notion of Oblivious Shuffling is obtained for K = N. We present a family of algorithms for Oblivious Shuffling. Our first construction, CacheShuffleRoot, is tailored for clients with $O(\sqrt{N})$ blocks of memory and uses $(4+ε)N$ blocks of bandwidth, for every $ε> 0$. CacheShuffleRoot is a 4.5x improvement over previous best known results on practical sizes of N. We also present CacheShuffle that obliviously shuffles using O(S) blocks of client memory with $O(N\log_S N)$ blocks of bandwidth. We then turn to K-Oblivious Shuffling and give algorithms that require 2N + f(K) blocks of bandwidth, for some function f. That is, any extra bandwidth above the 2N lower bound depends solely on K. We present KCacheShuffleBasic that uses O(K) client storage and exactly 2N blocks of bandwidth. For smaller client storage requirements, we show KCacheShuffle, which uses O(S) client storage and requires $2N+(1+ε)O(K\log_S K)$ blocks of bandwidth. Finally, we consider the case in which, in addition to the N blocks, the server stores D dummy blocks whose content is is irrelevant but still their positions must be hidden by the shuffling. For this case, we design algorithm KCacheShuffleDummy that, for N + D blocks and K touched blocks, uses O(K) client storage and $D+(2+ε)N$ blocks of bandwidth.