International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Brett Hemenway

Publications

Year
Venue
Title
2016
CRYPTO
2016
TCC
2016
ASIACRYPT
2015
EPRINT
2015
EPRINT
2015
TCC
2013
ASIACRYPT
2012
PKC
2012
PKC
2012
PKC
2011
ASIACRYPT
2010
EPRINT
Homomorphic Encryption Over Cyclic Groups Implies Chosen-Ciphertext Security
Brett Hemenway Rafail Ostrovsky
Chosen-Ciphertext (IND-CCA) security is generally considered the right notion of security for a cryptosystem. Because of its central importance much effort has been devoted to constructing IND-CCA secure cryptosystems. In this work, we consider the problem of constructing IND-CCA secure cryptosystems from (group) homomorphic encryption. Our main results are natural and efficient constructions of IND-CCA secure cryptosystems from any homomorphic encryption scheme that satisfies weak cyclic properties, either in the plaintext, ciphertext or randomness space. Our results have the added benefit of simple and elegant proofs.
2010
EPRINT
Correlated Product Security From Any One-Way Function and the New Notion of Decisional Correlated Product Security
Brett Hemenway Steve Lu Rafail Ostrovsky
It is well-known that the k-wise product of one-way functions remains one-way, but may no longer be when the k inputs are correlated. At TCC 2009, Rosen and Segev introduced a new notion known as Correlated Product secure functions. These functions have the property that a k-wise product of them remains one-way even under correlated inputs. Rosen and Segev gave a construction of injective trapdoor functions which were correlated product secure from the existence of Lossy Trapdoor Functions (introduced by Peikert and Waters in STOC 2008). The first main result of this work shows the surprising fact that a family of correlated product secure functions can be constructed from any one-way function. Because correlated product secure functions are trivially one-way, this shows an equivalence between the existence of these two cryptographic primitives. In the second main result of this work, we consider a natural decisional variant of correlated product security. Roughly, a family of functions are Decisional Correlated Product (DCP) secure if $f_1(x_1),\ldots,f_k(x_1)$ is indistinguishable from $f_1(x_1),\ldots,f_k(x_k)$ when $x_1,\ldots,x_k$ are chosen uniformly at random. We argue that the notion of Decisional Correlated Product security is a very natural one. To this end, we show a parallel from the Discrete Log Problem and Decision Diffie-Hellman Problem to Correlated Product security and its decisional variant. This intuition gives very simple constructions of PRGs and IND-CPA encryption from DCP secure functions. Furthermore, we strengthen our first result by showing that the existence of DCP secure one-way functions is also equivalent to the existence of any one-way function. When considering DCP secure functions with trapdoors, we give a construction based on Lossy Trapdoor Functions, and show that any DCP secure function family with trapdoor satisfy the security requirements for Deterministic Encryption as defined by Bellare, Boldyreva and O'Neill in CRYPTO 2007. In fact, we also show that definitionally, DCP secure functions with trapdoors are a strict subset of Deterministic Encryption functions by showing an example of a Deterministic Encryption function which according to the definition is not a DCP secure function.
2009
EPRINT
Re-randomizable Encryption implies Selective Opening Security
Brett Hemenway Rafail Ostrovsky
In this paper, we present new general constructions of commitments and encryptions secure against a Selective Opening Adversary (SOA). Although it was recognized almost twenty years ago that SOA security was important, it was not until the recent breakthrough works of Hofheinz (H08) and Bellare, Hofheinz and Yilek (BHY09) that any progress was made on this fundamental problem. The Selective Opening problem is as follows: suppose an adversary receives $n$ commitments (or encryptions) of (possibly) correlated messages, and now the adversary can choose $n/2$ of the messages, and receive decommitments (or decryptions \emph{and} the randomness used to encrypt them). Do the unopened commitments (encryptions) remain secure? A protocol which achieves this type of security is called \emph{secure against a Selective Opening Adversary (SOA)}. This question arises naturally in the context of Byzantine Agreement and Secure Multiparty Computation, where an active adversary is able to eavesdrop on all the wires, and then choose a subset of players to corrupt. Unfortunately, the traditional definitions of security (IND-CPA,IND-CCA) do not guarantee security in this setting. In this paper: We formally define re-randomizable encryption and show that every re-randomizable encryption scheme gives rise to efficient encryptions secure against a selective opening adversary. (Very informally, an encryption is re- We formally define e-randomizable one-way functions and show that every re-randomizable one-way function family gives rise to efficient commitments secure against a Selective Opening Adversary. Applying our constructions to the known cryptosystems of El-Gamal, Paillier, and Goldwasser and Micali, we obtain IND-SO secure commitments and encryptions from the Decisional Diffie-Hellman (DDH), Decisional Composite Residuosity (DCR) and Quadratic Residuosity (QR) assumptions, that are either simpler or more efficient than existing constructions of Bellare Hofheinz and Yilek. Applying our general results to the Paillier Cryptosystem we demonstrate the first cryptosystem to achieve Semantic Selective Opening security from the DCR assumption. We give black-box constructions of Perfectly Binding SOA secure commitments, which is surprising given the negative results of Bellare, Hofheinz and Yilek. We define the notion of adaptive chosen ciphertext security (CCA-2) in the selective opening setting, and describe the first encryption scheme which is CCA-2 secure (and simultaneously SOA-secure).
2008
CRYPTO
2007
EPRINT
Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code
Brett Hemenway Rafail Ostrovsky
In this paper, we introduce the notion of a Public-Key Encryption (PKE) Scheme that is also a Locally-Decodable Error-Correcting Code. In particular, our construction simultaneously satisfies all of the following properties: \begin{itemize} \item Our Public-Key Encryption is semantically secure under a certain number-theoretic hardness assumption (a specific variant of the $\Phi$-hiding assumption). \item Our Public-Key Encryption function has \emph{constant expansion}: it maps plaintexts of length $n$ (for any $n$ polynomial in $k$, where $k$ is a security parameter) to ciphertexts of size $\O(n+k)$. The size of our Public Key is also linear in $n$ and $k$. \item Our Public-Key Encryption is also a \emph{constant rate} binary error-correcting code against any polynomial-time Adversary. That is, we allow a polynomial-time Adversary to read the entire ciphertext, perform any polynomial-time computation and change an arbitrary (i.e. adversarially chosen) constant fraction of {\em all}\ bits of the ciphertext. The goal of the Adversary is to cause error in decoding any bit of the plaintext. Nevertheless, the decoding algorithm can decode {\bf all} bits of the plaintext (given the corrupted ciphertext) while making a mistake on \emph{any} bit of the plaintext with only a negligible in $k$ error probability. \item Our Decoding algorithm has a {\bf Local Decodability} property. That is, given a corrupted ciphertext of $E(x)$ the decryption algorithm, for any $1 \le i \le n$ can recover the $i$'th bit of $x$ (i.e., $x_i$) with overwhelming probability reading at most $\O(k^2)$ bits of the corrupted ciphertext and performing computation polynomial in $k$. Thus, for large plaintext messages, out Public Key Decryption algorithm can decode and error-correct any $x_i$ with sublinear (in $|x|$) computation. \end{itemize} We believe that the tools and techniques developed in this paper will be of independent interest in other settings.

Program Committees

Eurocrypt 2019