## CryptoDB

### Giuseppe Persiano

#### Affiliation: Universita' di Salerno

#### Publications

**Year**

**Venue**

**Title**

2020

CRYPTO

Lower Bounds for Encrypted Multi-Maps and Searchable Encryption in the Leakage Cell Probe Model
📺
Abstract

Encrypted multi-maps (EMMs) enable clients to outsource the storage of a multi-map to a potentially untrusted server while maintaining the ability to perform operations in a privacy-preserving manner. EMMs are an important primitive as they are an integral building block for many practical applications such as searchable encryption and encrypted databases. In this work, we formally examine the tradeoffs between privacy and efficiency for EMMs.
Currently, all known dynamic EMMs with constant overhead reveal if two operations are performed on the same key or not that we denote as the global key-equality pattern. In our main result, we present strong evidence that the leakage of the global key-equality pattern is inherent for any dynamic EMM construction with $O(1)$ efficiency. In particular, we consider the slightly smaller leakage of decoupled key-equality pattern where leakage of key-equality between update and query operations is decoupled and the adversary only learns whether two operations of the same type are performed on the same key or not. We show that any EMM with at most decoupled key-equality pattern leakage incurs $\Omega(\log n)$ overhead in the leakage cell probe model. This is tight as there exist ORAM-based constructions of EMMs with logarithmic slowdown that leak no more than the decoupled key-equality pattern (and actually, much less). Furthermore, we present stronger lower bounds that encrypted multi-maps leaking at most the decoupled key-equality pattern but are able to perform one of either the update or query operations in the plaintext still require $\Omega(\log n)$ overhead. Finally, we extend our lower bounds to show that dynamic, response-hiding searchable encryption schemes must also incur $\Omega(log n)$ overhead even when one of either the document updates or searches may be performed in the plaintext.

2019

EUROCRYPT

Lower Bounds for Differentially Private RAMs
📺
Abstract

In this work, we study privacy-preserving storage primitives that are suitable for use in data analysis on outsourced databases within the differential privacy framework. The goal in differentially private data analysis is to disclose global properties of a group without compromising any individual’s privacy. Typically, differentially private adversaries only ever learn global properties. For the case of outsourced databases, the adversary also views the patterns of access to data. Oblivious RAM (ORAM) can be used to hide access patterns but ORAM might be excessive as in some settings it could be sufficient to be compatible with differential privacy and only protect the privacy of individual accesses.We consider $$(\epsilon ,\delta )$$(ϵ,δ)-Differentially Private RAM, a weakening of ORAM that only protects individual operations and seems better suited for use in data analysis on outsourced databases. As differentially private RAM has weaker security than ORAM, there is hope that we can bypass the $$\varOmega (\log (nb/c))$$Ω(log(nb/c)) bandwidth lower bounds for ORAM by Larsen and Nielsen [CRYPTO ’18] for storing an array of nb-bit entries and a client with c bits of memory. We answer in the negative and present an $$\varOmega (\log (nb/c))$$Ω(log(nb/c)) bandwidth lower bound for privacy budgets of $$\epsilon = O(1)$$ϵ=O(1) and $$\delta \le 1/3$$δ≤1/3.The information transfer technique used for ORAM lower bounds does not seem adaptable for use with the weaker security guarantees of differential privacy. Instead, we prove our lower bounds by adapting the chronogram technique to our setting. To our knowledge, this is the first work that uses the chronogram technique for lower bounds on privacy-preserving storage primitives.

2018

CRYPTO

Continuously Non-Malleable Codes in the Split-State Model from Minimal Assumptions
📺
Abstract

At ICS 2010, Dziembowski, Pietrzak and Wichs introduced the notion of non-malleable codes, a weaker form of error-correcting codes guaranteeing that the decoding of a tampered codeword either corresponds to the original message or to an unrelated value. The last few years established non-malleable codes as one of the recently invented cryptographic primitives with the highest impact and potential, with very challenging open problems and applications.In this work, we focus on so-called continuously non-malleable codes in the split-state model, as proposed by Faust et al. (TCC 2014), where a codeword is made of two shares and an adaptive adversary makes a polynomial number of attempts in order to tamper the target codeword, where each attempt is allowed to modify the two shares independently (yet arbitrarily). Achieving continuous non-malleability in the split-state model has been so far very hard. Indeed, the only known constructions require strong setup assumptions (i.e., the existence of a common reference string) and strong complexity-theoretic assumptions (i.e., the existence of non-interactive zero-knowledge proofs and collision-resistant hash functions).As our main result, we construct a continuously non-malleable code in the split-state model without setup assumptions, requiring only one-to-one one-way functions (i.e., essentially optimal computational assumptions). Our result introduces several new ideas that make progress towards understanding continuous non-malleability, and shows interesting connections with protocol-design and proof-approach techniques used in other contexts (e.g., look-ahead simulation in zero-knowledge proofs, non-malleable commitments, and leakage resilience).

2010

EPRINT

Fully Secure Anonymous HIBE and Secret-Key Anonymous IBE with Short Ciphertexts
Abstract

Lewko and Waters [Eurocrypt 2010] presented a fully secure HIBE
with short ciphertexts. In this paper we show how to modify
their construction to achieve anonymity.
We prove the security of our scheme under static (and generically secure)
assumptions formulated in composite order bilinear groups.
In addition, we present a
fully secure Anonymous IBE in the secret-key setting.
Secret-Key Anonymous IBE was implied by the work of
[Shen-Shi-Waters - TCC 2009] which can be shown secure
in the selective-id model.
No previous fully secure construction of secret-key Anonymous IBE is known.

2008

EPRINT

Constant-Round Concurrent Non-Malleable Commitments and Decommitments
Abstract

In this paper we consider commitment schemes that are secure against concurrent poly-time man-in-the-middle (cMiM) attacks. Under such attacks, two possible notions of security for commitment schemes have been proposed in the literature: concurrent non-malleability with respect to commitment and concurrent non-malleability with respect to decommitment (i.e., opening).
After the original notion of non-malleability introduced by [Dolev, Dwork and Naor STOC 91] that is based on the independence of the committed and decommitted message, a new and stronger notion of non-malleability has been given in [Pass and Rosen STOC 05] by requiring that for any man-in-the-middle adversary there is a stand-alone adversary that succeeds with the same probability.
Under this stronger security notion, a constant-round commitment scheme that is concurrent non-malleable only with respect to commitment has been given in [Pass and Rosen FOCS 05] for the plain model, thus leaving as an open problem the construction of a constant-round concurrent non-malleable commitments with respect to decommitment. In other words, in [Pass and Rosen FOCS 05] security against adversaries that mount concurrent man-in-the-middle attacks is guaranteed only during the commitment phase (under their stronger notion of non-malleability).
The main result of this paper is a commitment scheme that is concurrent non-malleable with respect to both commitment and
decommitment, under the stronger notion of [Pass and Rosen STOC 05].
This property protects against cMiM attacks mounted during both commitments and decommitments which is a crucial security requirement in several applications, as in some digital auctions, in which players have to perform both commitments and decommitments.
Our scheme uses a constant number of rounds of interaction in the
plain model and is the first scheme that enjoys all these properties
under the definitions of [Pass and Rosen FOCS 05].
We stress that, exactly as in [Pass and Rosen FOCS 05], we assume that commitments and decommitments are performed in two distinct phases that do not overlap in time.

2004

CRYPTO

2003

EPRINT

Public Key Encryption with keyword Search
Abstract

We study the problem of searching on data that is encrypted using a
public key system. Consider user Bob who sends email to user Alice
encrypted under Alice's public key. An email gateway wants to test
whether the email contains the keyword `urgent' so that it could
route the email accordingly. Alice, on the other hand does not wish
to give the gateway the ability to decrypt all her messages. We define
and construct a mechanism that enables Alice to provide a key to the
gateway that enables the gateway to test whether the word `urgent'
is a keyword in the email without learning anything else about the
email. We refer to this mechanism as <I>Public Key Encryption with
keyword Search</I>. As another example, consider a mail server that
stores various messages publicly encrypted for Alice by others. Using
our mechanism Alice can send the mail server a key that will enable
the server to identify all messages containing some specific keyword,
but learn nothing else. We define the concept of public key
encryption with keyword search and give several constructions.

1998

EPRINT

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof
Abstract

The input to the Graph Clustering Problem
consists of a sequence of integers $m_1,...,m_t$
and a sequence of $\sum_{i=1}^{t}m_i$ graphs.
The question is whether the equivalence classes,
under the graph isomorphism relation,
of the input graphs have sizes which match the input sequence of integers.
In this note we show that this problem has a (perfect) zero-knowledge
interactive proof system.
This result improves over <a href="http:../1996/96-14.html">record 96-14</a>,
where a parametrized (by the sequence of integers)
version of the problem was studied.

#### Program Committees

- Crypto 2019
- Asiacrypt 2018
- PKC 2016
- Crypto 2015
- Eurocrypt 2013
- Crypto 2010
- Eurocrypt 2007
- PKC 2006

#### Coauthors

- Joël Alwen (2)
- Dan Boneh (2)
- Angelo De Caro (2)
- Michele Ciampi (5)
- Giovanni Di Crescenzo (7)
- Oded Goldreich (1)
- Vincenzo Iovino (2)
- Abhishek Jain (1)
- Jonathan Katz (1)
- Yehuda Lindell (1)
- Silvio Micali (2)
- Adam O'Neill (1)
- Tatsuaki Okamoto (1)
- Rafail Ostrovsky (7)
- Omer Paneth (1)
- Sarvar Patel (1)
- Amit Sahai (1)
- Alfredo De Santis (8)
- Alessandra Scafuro (3)
- Abhi Shelat (1)
- Luisa Siniscalchi (5)
- Daniele Venturi (1)
- Ivan Visconti (13)
- Kevin Yeo (2)