## CryptoDB

### Shai Halevi

#### Publications

**Year**

**Venue**

**Title**

2021

CRYPTO

MPC-Friendly Symmetric Cryptography from Alternating Moduli: Candidates, Protocols, and Applications
📺
Abstract

We study new candidates for symmetric cryptographic primitives that leverage alternation between linear functions over $\mathbb{Z}_2$ and $\mathbb{Z}_3$ to support fast protocols for secure multiparty computation (MPC). This continues the study of weak pseudorandom functions of this kind initiated by Boneh et al. (TCC 2018) and Cheon et al. (PKC 2021).
We make the following contributions.
(Candidates). We propose new designs of symmetric primitives based on alternating moduli. These include candidate one-way functions, pseudorandom generators, and weak pseudorandom functions. We propose concrete parameters based on cryptanalysis.
(Protocols). We provide a unified approach for securely evaluating modulus-alternating primitives in different MPC models. For the original candidate of Boneh et al., our protocols obtain at least 2x improvement in all performance measures. We report efficiency benchmarks of an optimized implementation.
(Applications). We showcase the usefulness of our candidates for a variety of applications. This includes short ``Picnic-style'' signature schemes, as well as protocols for oblivious pseudorandom functions, hierarchical key derivation, and distributed key generation for function secret sharing.

2021

CRYPTO

You Only Speak Once: Secure MPC with Stateless Ephemeral Roles
📺
Abstract

The inherent difficulty of maintaining stateful environments over long periods of time gave rise to the paradigm of serverless computing, where mostly-stateless components are deployed on demand to handle computation tasks, and are teared down once their task is complete. Serverless architecture could offer the added benefit of improved resistance to targeted denial-of-service attacks, by hiding from the attacker the physical machines involved in the protocol until after they complete their work. Realizing such protection, however, requires that the protocol only uses stateless parties, where each party sends only one message and never needs to speaks again. Perhaps the most famous example of this style of protocols is the Nakamoto consensus protocol used in Bitcoin: A peer can win the right to produce the next block by running a local lottery (mining), all while staying covert. Once the right has been won, it is executed by sending a single message. After that, the physical entity never needs to send more messages.
We refer to this as the You-Only-Speak-Once (YOSO) property, and initiate the formal study of it within a new model that we call the YOSO model. Our model is centered around the notion of roles, which are stateless parties that can only send a single message. Crucially, our modelling separates the protocol design, that only uses roles, from the role-assignment mechanism, that assigns roles to actual physical entities. This separation enables studying these two aspects separately, and our YOSO model in this work only deals with the protocol-design aspect.
We describe several techniques for achieving YOSO MPC; both computational and information theoretic. Our protocols are synchronous and provide guaranteed output delivery (which is important for application domains such as blockchains), assuming honest majority of roles in every time step. We describe a practically efficient computationally-secure protocol, as well as a proof-of-concept information theoretically secure protocol.

2021

TCC

Random-Index PIR and Applications
📺
Abstract

Private information retrieval (PIR) lets a client retrieve an entry from a database without the server learning which entry was retrieved. Here we study a weaker variant that we call random-index PIR (RPIR), where the retrieved index is an output rather than an input of the protocol, and is chosen at random. RPIR is clearly weaker than PIR, but it suffices for some interesting applications and may be realized more efficiently than full-blown PIR.
We report here on two lines of work, both tied to RPIR but otherwise largely unrelated. The first line of work studies RPIR as a primitive on its own. Perhaps surprisingly, we show that RPIR is in fact equivalent to PIR when there are no restrictions on the number of communication rounds. On the other hand, RPIR can be implemented in a “noninteractive” setting (with preprocessing), which is clearly impossible for PIR. For two-server RPIR we show a truly noninteractive solution, offering information-theoretic security without any pre-processing.
The other line of work, which was the original motivation for our work, uses RPIR to improve on the recent work of Benhamouda et al. (TCC’20) for maintaining secret values on public blockchains. Their solution depends on a method for selecting many random public keys from a PKI while hiding most of the selected keys from an adversary. However, the method they proposed is vulnerable to a double-dipping attack, limiting its resilience. Here we observe that an RPIR protocol, where the client is implemented via secure MPC, can eliminate that vulnerability. We thus get a secrets-on-blockchain protocol (and more generally large-scale MPC), resilient to any fraction f < 1/2 of corrupted parties, resolving the main open problem left from the work of Benhamouda et al.
As the client in this solution is implemented via secure MPC, it really brings home the need to make it as efficient as possible. We thus strive to explore whatever efficiency gains we can get by using RPIR rather than PIR. We achieve more gains by using batch RPIR where multiple indexes are retrieved at once. Lastly, we observe that this application can make do with a weaker security guarantee than full RPIR, and show that this weaker variant can be realized even more efficiently. We discuss one protocol in particular, that may be attractive for practical implementations.

2021

TCC

Generalized Pseudorandom Secret Sharing and Efficient Straggler-Resilient Secure Computation
📺
Abstract

Secure multiparty computation (MPC) enables $n$ parties, of which up to $t$ may be corrupted, to perform joint computations on their private inputs while revealing only the outputs. Optimizing the asymptotic and concrete costs of MPC protocols has become an important line of research. Much of this research focuses on the setting of an honest majority, where $n \ge 2t+1$, which gives rise to concretely efficient protocols that are either information-theoretic or make a black-box use of symmetric cryptography. Efficiency can be further improved in the case of a {\em strong} honest majority, where $n>2t+1$.
Motivated by the goal of minimizing the communication and latency costs of MPC with a strong honest majority, we make two related contributions.
\begin{itemize}[leftmargin=*]
\item {\bf Generalized pseudorandom secret sharing (PRSS).}
Linear correlations serve as an important resource for MPC protocols and beyond. PRSS enables secure generation of many pseudorandom instances of such correlations without interaction, given replicated seeds of a pseudorandom function.
We extend the PRSS technique of Cramer et al.\ (TCC 2015) for sharing degree-$d$ polynomials to new constructions leveraging a particular class of combinatorial designs. Our constructions yield a dramatic efficiency improvement when the degree $d$ is higher than the security threshold $t$, not only for standard degree-$d$ correlations but also for several useful generalizations. In particular, correlations for locally converting between slot configurations in ``share packing'' enable us to avoid the concrete overhead of prior works.
\item {\bf Cheap straggler resilience.}
In reality, communication is not fully synchronous: protocol executions suffer from variance in communication delays and occasional node or message-delivery failures. We explore the benefits of PRSS-based MPC with a strong honest majority toward robustness against such failures, in turn yielding improved latency delays. In doing so we develop a novel technique for defending against a subtle ``double-dipping'' attack, which applies to the best existing protocols, with almost no extra cost in communication or rounds.
\end{itemize}
Combining the above tools requires further work, including new methods for batch verification via distributed zero-knowledge proofs (Boneh et al., CRYPTO 2019) that apply to packed secret sharing.
Overall, our work demonstrates new advantages of the strong honest majority setting, and introduces new tools---in particular, generalized PRSS---that we believe will be of independent use within other cryptographic applications.

2021

JOFC

Round-Optimal Secure Multi-party Computation
Abstract

Secure multi-party computation (MPC) is a central cryptographic task that allows a set of mutually distrustful parties to jointly compute some function of their private inputs where security should hold in the presence of an active (i.e. malicious) adversary that can corrupt any number of parties. Despite extensive research, the precise round complexity of this “standard-bearer” cryptographic primitive, under polynomial-time hardness assumptions, is unknown. Recently, Garg, Mukherjee, Pandey and Polychroniadou, in Eurocrypt 2016 demonstrated that the round complexity of any MPC protocol relying on black-box proofs of security in the plain model must be at least four. Following this work, independently Ananth, Choudhuri and Jain, CRYPTO 2017 and Brakerski, Halevi, and Polychroniadou, TCC 2017 made progress towards solving this question and constructed four-round protocols based on the DDH and LWE assumptions, respectively, albeit with super-polynomial hardness. More recently, Ciampi, Ostrovsky, Siniscalchi and Visconti in TCC 2017 closed the gap for two-party protocols by constructing a four-round protocol from polynomial-time assumptions, concretely, trapdoor permutations. In another work, Ciampi, Ostrovsky, Siniscalchi and Visconti TCC 2017 showed how to design a four-round multi-party protocol for the specific case of multi-party coin-tossing based on one-way functions. In this work, we resolve this question by designing a four-round actively secure multi-party (two or more parties) protocol for general functionalities under standard polynomial-time hardness assumptions with a black-box proof of security, specifically, under the assumptions LWE, DDH, QR and DCR.

2021

JOFC

Bootstrapping for HElib
Abstract

Gentry’s bootstrapping technique is still the only known method of obtaining fully homomorphic encryption where the system’s parameters do not depend on the complexity of the evaluated functions. Bootstrapping involves a recryption procedure where the scheme’s decryption algorithm is evaluated homomorphically. Prior to this work, there were very few implementations of recryption and fewer still that can handle “packed ciphertexts” that encrypt vectors of elements. In the current work, we report on an implementation of recryption of fully packed ciphertexts using the HElib library for somewhat homomorphic encryption. This implementation required extending previous recryption algorithms from the literature, as well as many aspects of the HElib library. Our implementation supports bootstrapping of packed ciphertexts over many extension fields/rings. One example that we tested involves ciphertexts that encrypt vectors of 1024 elements from $${\text {GF}}(2^{16})$$ GF ( 2 16 ) . In that setting, the recryption procedure takes under 3 min (at security level $$\approx 80$$ ≈ 80 ) on a single core and allows a multiplicative depth-11 computation before the next recryption is needed. This report updates the results that we reported in Eurocrypt 2015 in several ways. Most importantly, it includes a much more robust method for deriving the parameters, ensuring that recryption errors only occur with negligible probability. Many aspects of this analysis are proved, and for the few well-specified heuristics that we made, we report on thorough experimentation to validate them. The procedure that we describe here is also significantly more efficient than in the previous version, incorporating many optimizations that were reported elsewhere (such as more efficient linear transformations) and adding a few new ones. Finally, our implementation now also incorporates Chen and Han’s techniques from Eurocrypt 2018 for more efficient digit extraction (for some parameters), as well as for “thin bootstrapping” when the ciphertext is only sparsely packed.

2020

TCC

Can a Blockchain Keep a Secret?
📺
Abstract

Blockchains are gaining traction and acceptance, not just for cryptocurrencies, but increasingly as an architecture for distributed computing.
In this work we seek solutions that allow a \emph{public} blockchain to act as a trusted long-term repository of secret information:
Our goal is to deposit a secret with the blockchain, specify how it is to be used (e.g., the conditions under which it is released), and have the blockchain keep the secret and use it only in the specified manner (e.g., release only it once the conditions are met).
This simple functionality enables many powerful applications, including signing statements on behalf of the blockchain, using it as the control plane for a storage system, performing decentralized program-obfuscation-as-a-service, and many more.
Using proactive secret sharing techniques, we present a scalable solution for implementing this functionality on a public blockchain, in the presence of a mobile adversary controlling a small minority of the participants.
The main challenge is that, on the one hand, scalability requires that we use small committees to represent the entire system, but, on the other hand, a mobile adversary may be able to corrupt the entire committee if it is small.
For this reason, existing proactive secret sharing solutions are either non-scalable or insecure in our setting.
We approach this challenge via "player replaceability", which ensures the committee is anonymous until after it performs its actions.
Our main technical contribution is a system that allows sharing and re-sharing of secrets among the members of small dynamic committees, without knowing who they are until after they perform their actions and erase their secrets. Our solution handles a fully mobile adversary corrupting roughly 1/4 of the participants at any time, and is scalable in terms of both the number of parties and the number of time intervals.

2019

TCC

On Fully Secure MPC with Solitary Output
Abstract

We study the possibility of achieving full security, with guaranteed output delivery, for secure multiparty computation of functionalities where only one party receives output, to which we refer as solitary functionalities. In the standard setting where all parties receive an output, full security typically requires an honest majority; otherwise even just achieving fairness is impossible. However, for solitary functionalities, fairness is clearly not an issue. This raises the following question: Is full security with no honest majority possible for all solitary functionalities?We give a negative answer to this question, by showing the existence of solitary functionalities that cannot be computed with full security. While such a result cannot be proved using fairness-based arguments, our proof builds on the classical proof technique of Cleve (STOC 1986) for ruling out fair coin-tossing and extends it in a nontrivial way.On the positive side, we show that full security against any number of malicious parties is achievable for many natural and useful solitary functionalities, including ones for which the multi-output version cannot be realized with full security.

2019

TCC

Compressible FHE with Applications to PIR
Abstract

Homomorphic encryption (HE) is often viewed as impractical, both in communication and computation. Here we provide an additively homomorphic encryption scheme based on (ring) LWE with nearly optimal rate ($$1-\epsilon $$ for any $$\epsilon >0$$). Moreover, we describe how to compress many Gentry-Sahai-Waters (GSW) ciphertexts (e.g., ciphertexts that may have come from a homomorphic evaluation) into (fewer) high-rate ciphertexts.Using our high-rate HE scheme, we are able for the first time to describe a single-server private information retrieval (PIR) scheme with sufficiently low computational overhead so as to be practical for large databases. Single-server PIR inherently requires the server to perform at least one bit operation per database bit, and we describe a rate-(4/9) scheme with computation which is not so much worse than this inherent lower bound. In fact it is probably less than whole-database AES encryption – specifically about 2.3 mod-q multiplication per database byte, where q is about 50 to 60 bits. Asymptotically, the computational overhead of our PIR scheme is $$\tilde{O}(\log \log \mathsf {\lambda }+ \log \log \log N)$$, where $$\mathsf {\lambda }$$ is the security parameter and N is the number of database files, which are assumed to be sufficiently large.

2019

ASIACRYPT

Homomorphic Encryption for Finite Automata
Abstract

We describe a somewhat homomorphic GSW-like encryption scheme, natively encrypting matrices rather than just single elements. This scheme offers much better performance than existing homomorphic encryption schemes for evaluating encrypted (nondeterministic) finite automata (NFAs). Differently from GSW, we do not know how to reduce the security of this scheme from LWE, instead we reduce it from a stronger assumption, that can be thought of as an inhomogeneous variant of the NTRU assumption. This assumption (that we term iNTRU) may be useful and interesting in its own right, and we examine a few of its properties. We also examine methods to encode regular expressions as NFAs, and in particular explore a new optimization problem, motivated by our application to encrypted NFA evaluation. In this problem, we seek to minimize the number of states in an NFA for a given expression, subject to the constraint on the ambiguity of the NFA.

2018

CRYPTO

Round-Optimal Secure Multi-Party Computation
📺
Abstract

Secure multi-party computation (MPC) is a central cryptographic task that allows a set of mutually distrustful parties to jointly compute some function of their private inputs where security should hold in the presence of a malicious adversary that can corrupt any number of parties. Despite extensive research, the precise round complexity of this “standard-bearer” cryptographic primitive is unknown. Recently, Garg, Mukherjee, Pandey and Polychroniadou, in EUROCRYPT 2016 demonstrated that the round complexity of any MPC protocol relying on black-box proofs of security in the plain model must be at least four. Following this work, independently Ananth, Choudhuri and Jain, CRYPTO 2017 and Brakerski, Halevi, and Polychroniadou, TCC 2017 made progress towards solving this question and constructed four-round protocols based on non-polynomial time assumptions. More recently, Ciampi, Ostrovsky, Siniscalchi and Visconti in TCC 2017 closed the gap for two-party protocols by constructing a four-round protocol from polynomial-time assumptions. In another work, Ciampi, Ostrovsky, Siniscalchi and Visconti TCC 2017 showed how to design a four-round multi-party protocol for the specific case of multi-party coin-tossing.In this work, we resolve this question by designing a four-round actively secure multi-party (two or more parties) protocol for general functionalities under standard polynomial-time hardness assumptions with a black-box proof of security.

2018

CRYPTO

Faster Homomorphic Linear Transformations in HElib
📺
Abstract

HElib is a software library that implements homomorphic encryption (HE), with a focus on effective use of “packed” ciphertexts. An important operation is applying a known linear map to a vector of encrypted data. In this paper, we describe several algorithmic improvements that significantly speed up this operation: in our experiments, our new algorithms are 30–75 times faster than those previously implemented in HElib for typical parameters.One application that can benefit from faster linear transformations is bootstrapping (in particular, “thin bootstrapping” as described in [Chen and Han, Eurocrypt 2018]). In some settings, our new algorithms for linear transformations result in a $$6{\times }$$6× speedup for the entire thin bootstrapping operation.Our techniques also reduce the size of the large public evaluation key, often using 33%–50% less space than the previous HElib implementation. We also implemented a new tradeoff that enables a drastic reduction in size, resulting in a $$25{\times }$$25× factor or more for some parameters, paying only a penalty of a 2–$$4{\times }$$4× times slowdown in running time (and giving up some parallelization opportunities).

2018

TCC

Best Possible Information-Theoretic MPC
Abstract

We reconsider the security guarantee that can be achieved by general protocols for secure multiparty computation in the most basic of settings: information-theoretic security against a semi-honest adversary. Since the 1980s, we have elegant solutions to this problem that offer full security, as long as the adversary controls a minority of the parties, but fail completely when that threshold is crossed. In this work, we revisit this problem, questioning the optimality of the standard notion of security. We put forward a new notion of information-theoretic security which is strictly stronger than the standard one, and which we argue to be “best possible.” This notion still requires full security against dishonest minority in the usual sense, and adds a meaningful notion of information-theoretic security even against dishonest majority.We present protocols for useful classes of functions that satisfy this new notion of security. Our protocols have the unique feature of combining the efficiency benefits of protocols for an honest majority and (most of) the security benefits of protocols for dishonest majority. We further extend some of the solutions to the malicious setting.

2014

CRYPTO

2014

EUROCRYPT

#### Program Committees

- Eurocrypt 2019
- Eurocrypt 2016
- TCC 2015
- Crypto 2013
- PKC 2013
- TCC 2011
- Asiacrypt 2009
- Crypto 2009 (Program chair)
- Crypto 2009
- Eurocrypt 2008
- Asiacrypt 2007
- Eurocrypt 2007
- TCC 2006 (Program chair)
- Crypto 2005
- Eurocrypt 2005
- PKC 2002
- Eurocrypt 2001
- Crypto 2000

#### Coauthors

- Shweta Agrawal (1)
- Mihir Bellare (1)
- Fabrice Benhamouda (2)
- Nir Bitansky (2)
- John Black (1)
- Dan Boneh (3)
- Elette Boyle (1)
- Zvika Brakerski (2)
- Ran Canetti (12)
- Dario Catalano (1)
- Yilei Chen (1)
- Don Coppersmith (3)
- Jean-Sébastien Coron (2)
- Itai Dinur (1)
- Yevgeniy Dodis (3)
- Sanjam Garg (5)
- Nicholas Genise (1)
- Rosario Gennaro (3)
- Craig Gentry (25)
- Niv Gilboa (1)
- Steven Goldfeder (1)
- Oded Goldreich (3)
- Shafi Goldwasser (3)
- Sergey Gorbunov (3)
- François Grieu (1)
- Mike Hamburg (1)
- Carmit Hazay (2)
- Amir Herzberg (1)
- Nick Howgrave-Graham (1)
- Yuval Ishai (5)
- Abhishek Jain (1)
- Charanjit S. Jutla (3)
- Yael Tauman Kalai (1)
- Jonathan Katz (5)
- Mahimna Kelkar (1)
- Ilan Komargodski (1)
- Hugo Krawczyk (7)
- Ted Krovetz (1)
- Eyal Kushilevitz (3)
- Tancrède Lepoint (1)
- Baiyu Li (1)
- Chengyu Lin (1)
- Huijia Lin (1)
- Yehuda Lindell (2)
- Steve Lu (1)
- Philip D. MacKenzie (1)
- Bernardo Magri (2)
- Hemanta K. Maji (1)
- Nikolaos Makriyannis (1)
- Silvio Micali (1)
- Daniele Micciancio (1)
- Eric Miles (1)
- Steven Myers (1)
- David Naccache (1)
- Jesper Buus Nielsen (2)
- Valeria Nikolaenko (1)
- Ariel Nof (1)
- Rafail Ostrovsky (2)
- Benny Pinkas (1)
- Antigoni Polychroniadou (3)
- Tal Rabin (9)
- Charles Rackoff (1)
- Mariana Raykova (3)
- Leonid Reyzin (1)
- Phillip Rogaway (2)
- Ron D. Rothblum (1)
- Guy N. Rothblum (1)
- Amit Sahai (6)
- Gil Segev (1)
- Vivek Sharma (1)
- Victor Shoup (4)
- Nigel P. Smart (3)
- Michael Steiner (2)
- Julien P. Stern (1)
- Mehdi Tibouchi (1)
- Salil P. Vadhan (1)
- Vinod Vaikuntanathan (4)
- Marten van Dijk (1)
- Muthuramakrishnan Venkitasubramaniam (2)
- Dhinakaran Vinayagamurthy (1)
- Brent Waters (1)
- Daniel Wichs (3)
- Sophia Yakoubov (2)
- Eylon Yogev (1)
- Greg Zaverucha (1)
- Mark Zhandry (1)