Source author record

Brice Minaud

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Cryptography and Security Data Structures and Algorithms

Catalog footprint

Research overview

2works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Dynamic Local Searchable Symmetric Encryption

In this article, we tackle for the first time the problem of dynamic memory-efficient Searchable Symmetric Encryption (SSE). In the term "memory-efficient" SSE, we encompass both the goals of local SSE, and page-efficient SSE. The centerpiece of our approach is a novel connection between those two goals. We introduce a map, called the Generic Local Transform, which takes as input a page-efficient SSE scheme with certain special features, and outputs an SSE scheme with strong locality properties. We obtain several results. (1) First, for page-efficient SSE, we build a dynamic scheme with page efficiency $O(\log \log N)$ and storage efficiency $O(1)$ , called LayeredSSE. The main technical innovation behind LayeredSSE is a new weighted extension of the two-choice allocation process, of independent interest. (2) Second, we introduce the Generic Local Transform, and combine it with LayeredSSE to build a dynamic SSE scheme with storage efficiency $O(1)$ , locality $O(1)$ , and read efficiency $O(\log\log N)$ , under the condition that the longest list is of size $O(N^{1-1/\log \log λ})$ . This matches, in every respect, the purely static construction of Asharov et al. presented at STOC 2016: dynamism comes at no extra cost. (3) Finally, by applying the Generic Local Transform to a variant of the Tethys scheme by Bossuat et al. from Crypto 2021, we build an unconditional static SSE with storage efficiency $O(1)$ , locality $O(1)$ , and read efficiency $O(\log^\varepsilon N)$ , for an arbitrarily small constant $\varepsilon > 0$ . To our knowledge, this is the construction that comes closest to the lower bound presented by Cash and Tessaro at Eurocrypt 2014.

preprint2022arXiv

Generalized Cuckoo Hashing with a Stash, Revisited

Cuckoo hashing is a common hashing technique, guaranteeing constant-time lookups in the worst case. Adding a stash was proposed by Kirsch, Mitzenmacher, and Wieder at SICOMP 2010, as a way to reduce the probability of failure (i.e., the probability that a valid Cuckoo assignment fails to exist). It has since become a standard technique in areas such as cryptography, where a negligible probability of failure is often required. We focus on an extension of Cuckoo hashing that allows multiple items per bucket, which improves the load factor. That extension was also analyzed by Kirsch \emph{et al.} in the presence of a stash. In particular, letting $d$ be the number of items per bucket, and $s$ be the stash size, Kirsch \emph{et al.} showed that, for constant $d$ and $s$ , the failure probability is $\mathcal{O}(n^{(s+1)(1-d)})$ . In this paper, we first report a bug in the analysis by Kirsch \emph{et al.} by showing a counter-example leading to an asymptotically-larger probability of failure $Ω(n^{-d-s-1})$ . Then we provide a general analysis and upper bound of the failure probability for (almost) arbitrary $d$ and $s$ , instead of just constant, which is useful for applications in cryptography. We finally deduce from the general analysis a tight bound $Θ(n^{-d-s})$ for the probability of failure, for constants $d$ and $s$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.