## CryptoDB

### Sarvar Patel

#### Affiliation: Bell Labs, Lucent Technologies

#### Publications

**Year**

**Venue**

**Title**

2020

CRYPTO

Two-Sided Malicious Security for Private Intersection-Sum with Cardinality
📺
Abstract

Private intersection-sum with cardinality allows two parties, where each party holds a private set and one of the parties additionally holds a private integer value associated with each element in her set, to jointly compute the cardinality of the intersection of the two sets as well as the sum of the associated integer values for all the elements in the intersection, and nothing beyond that.
We present a new construction for private intersection sum with cardinality that provides malicious security with abort and guarantees that both parties receive the output upon successful completion of the protocol. A central building block for our constructions is a primitive called shuffled distributed oblivious PRF (DOPRF), which is a PRF that offers oblivious evaluation using a secret key shared between two parties, and in addition to this allows obliviously permuting the PRF outputs of several parallel oblivious evaluations. We present the first construction for shuffled DOPRF with malicious security. We further present several new sigma proof protocols for relations across Pedersen commitments, ElGamal encryptions, and Camenisch-Shoup encryptions that we use in our main construction, for which we develop new batching techniques to reduce communication.
We implement and evaluate the efficiency of our protocol and show that we can achieve communication cost that is only 4-5x greater than the most efficient semi-honest protocol. When measuring monetary cost of executing the protocol in the cloud, our protocol is 25x more expensive than the semi-honest protocol. Our construction also allows for different parameter regimes that enable trade-offs between communication and computation.

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.

2001

EPRINT

An Efficient MAC for Short Messages
Abstract

HMAC is the internet standard for message authentication. What
distinguishes HMAC from other MAC algorithms is that it provides
proofs of security assuming that the underlying cryptographic hash
(e.g. SHA-1) has some reasonable properties. HMAC is efficient for
long messages, however, for short messages the nested construction
results in a significant inefficiency. For example to MAC a message
shorter than a block, HMAC requires at least two calls to the
compression function rather than one.
This inefficiency may be particularly high for some applications, like
message authentication of signaling messages, where the individual
messages may all fit within one or two blocks. Also for TCP/IP traffic
it is well known that large number of packets (e.g. acknowledgment)
have sizes around 40 bytes which fit within a block of most
cryptographic hashes. We propose an enhancement that allows both
short and long messages to be message authenticated more efficiently
than HMAC while also providing proofs of security. In particular, for
a message smaller than a block our MAC only requires one call to the
compression function.

2000

EPRINT

Provably Secure Password-Authenticated Key Exchange Using Diffie-Hellman
Abstract

When designing password-authenticated key exchange protocols (as
opposed to key exchange protocols authenticated using
cryptographically secure keys), one must not allow any information
to be leaked that would allow verification of the password (a weak
shared key), since an attacker who obtains this information may be
able to run an off-line dictionary attack to determine the
correct password. Of course, it may be extremely difficult to hide
all password information, especially if the attacker may pose as one
of the parties in the key exchange. Nevertheless, we present a new
protocol called PAK which is the first Diffie-Hellman-based
password-authenticated key exchange protocol to provide a formal
proof of security (in the random oracle model) against both passive
and active adversaries. In
addition to the PAK protocol that provides mutual explicit
authentication, we also show a more efficient protocol called PPK that
is provably secure in the implicit-authentication model. We then
extend PAK to a protocol called PAK-X, in which one side (the
client) stores a plaintext version of the password, while the other
side (the server) only stores a verifier for the password. We
formally prove security of PAK-X, even when the server is
compromised. Our formal model for password-authenticated key
exchange is new, and may be of independent interest.

#### Coauthors

- Daniel Bleichenbacher (1)
- Victor Boyko (2)
- Mark Etzel (1)
- Philip D. MacKenzie (3)
- Peihan Miao (1)
- Giuseppe Persiano (1)
- Zulfikar Ramzan (2)
- Mariana Raykova (1)
- Karn Seth (1)
- Ganapathy S. Sundaram (2)
- Ram Swaminathan (1)
- Kevin Yeo (1)
- Moti Yung (1)