## CryptoDB

### Ran Canetti

#### Publications

**Year**

**Venue**

**Title**

2021

TCC

Covert Learning: How to Learn with an Untrusted Intermediary
📺
Abstract

We consider the task of learning a function via oracle queries, where the queries and responses are monitored (and perhaps also modified) by an untrusted intermediary. Our goal is twofold: First, we would like to prevent the intermediary from gaining any information about either the function or the learner's intentions (e.g. the particular hypothesis class the learner is considering). Second, we would like to curb the intermediary's ability to meaningfully interfere with the learning process, even when it can modify the oracles' responses.
Inspired by the works of Ishai et al. (Crypto 2019) and Goldwasser et al. (ITCS 2021), we formalize two new learning models, called Covert Learning and Covert Verifiable Learning, that capture these goals. Then, assuming hardness of the Learning Parity with Noise (LPN) problem, we show:
1. Covert Learning algorithms in the agnostic setting for parity functions and decision trees, where a polynomial time eavesdropping adversary that observes all queries and responses learns nothing about either the function, or the learned hypothesis.
2. Covert Verifiable Learning algorithms that provide similar learning and privacy guarantees, even in the presence of a polynomial-time adversarial intermediary that can modify all oracle responses. Here the learner is granted additional random examples and is allowed to abort whenever the oracles responses are modified.
Aside theoretical interest, our study is motivated by applications to the secure outsourcing of automated scientific discovery in drug design and molecular biology. It also uncovers limitations of current techniques for defending against model extraction attacks.

2020

PKC

Blazing Fast OT for Three-Round UC OT Extension
📺
Abstract

Oblivious Transfer (OT) is an important building block for multi-party computation (MPC). Since OT requires expensive public-key operations, efficiency-conscious MPC protocols use an OT extension (OTE) mechanism [Beaver 96, Ishai et al. 03] to provide the functionality of many independent OT instances with the same sender and receiver, using only symmetric-key operations plus few instances of some base OT protocol. Consequently there is significant interest in constructing OTE friendly protocols, namely protocols that, when used as base-OT for OTE, result in extended OT that are both round-efficient and cost-efficient. We present the most efficient OTE-friendly protocol to date. Specifically: Our base protocol incurs only 3 exponentiations per instance. Our base protocol results in a 3 round extended OT protocol. The extended protocol is UC secure in the Observable Random Oracle Model (ROM) under the CDH assumption. For comparison, the state of the art for base OTs that result in 3-round OTE are proven only in the programmable ROM, and require 4 exponentiations under Interactive DDH or 6 exponentiations under DDH [Masney-Rindal 19]. We also implement our protocol and benchmark it against the Simplest OT protocol [Chou and Orlandi, Latincrypt 2015], which is the most efficient and widely used OT protocol but not known to suffice for OTE. The computation cost is roughly the same in both cases. Interestingly, our base OT is also 3 rounds. However, we slightly modify the extension mechanism (which normally adds a round) so as to preserve the number of rounds in our case.

2020

CRYPTO

Fully Deniable Interactive Encryption
📺
Abstract

Deniable encryption (Canetti \emph{et al.}, Crypto 1996) enhances secret communication over public channels, providing the additional guarantee that the secrecy of communication is protected even if the parties are later coerced (or willingly bribed) to expose their entire internal states: plaintexts, keys and randomness.
To date, constructions of deniable encryption --- and more generally, interactive deniable communication --- only address restricted cases where only {\em one} party is compromised (Sahai and Waters, STOC 2014). The main question --- whether deniable communication is at all possible if {\em both} parties are coerced at once --- has remained open.
We resolve this question in the affirmative, presenting a communication protocol that is {\em fully deniable} under coercion of both parties.
Our scheme has three rounds, assumes subexponentially secure indistinguishability obfuscation and one-way functions, and uses a short global reference string that is generated once at system set-up and suffices for an unbounded number of encryptions and decryptions.
Of independent interest, we introduce a new notion called \emph{off-the-record deniability}, which protects parties even when their claimed internal states are inconsistent (a case not covered by prior definitions). Our scheme satisfies both standard deniability and off-the-record deniability.

2020

TCC

Towards Multiparty Computation Withstanding Coercion of All Parties
📺
Abstract

Incoercible multi-party computation [Canetti-Gennaro ’96] allows parties to engage in secure computation with the additional guarantee that the public transcript of the computation cannot be used by a coercive external entity to verify representations made by the parties regarding their inputs to and outputs from the computation. That is, any deductions regarding the truthfulness of such representations made by the parties could be made even without access to the public transcript. To date, all incoercible secure computation protocols withstand coercion of only a fraction of the parties, or else assume that all parties use an execution environment that makes some crucial parts of their local states physically inaccessible even to themselves.
We consider, for the first time, the setting where all parties are coerced, and the coercer expects to see the entire history of the computation.In this setting we construct:
- A general multi-party computation protocol that withstands coercion of all parties, as long as none of the coerced parties cooperates with the coercer, namely they all use the prescribed ``faking algorithm'' upon coercion. We refer to this case as cooperative incoercibility.
The protocol uses deniable encryption and indistiguishability obfuscation, and takes 4 rounds of communication.
- A general two-party computation protocol that withstands even the ``mixed'' case where some of the coerced parties cooperate with the coercer and disclose their true local states. This protocol is limited to computing functions where the input of one of the parties is taken from a small (poly-size) domain. This protocol uses deniable encryption with public deniability for one of the parties; when instantiated using the deniable encryption of Canetti, Park, and Poburinnaya [Crypto'20], it takes 3 rounds of communication.
Finally, we show that protocols with certain communication pattern cannot be incoercible, even in a weaker setting where only some parties are coerced.

2020

TCC

Universal Composition with Global Subroutines: Capturing Global Setup within plain UC
📺
Abstract

The Global and Externalized UC frameworks [Canetti-Dodis-Pass-Walfish, TCC 07] extend the plain UC framework to additionally handle protocols that use a ``global setup'', namely a mechanism that is also used by entities outside the protocol. These frameworks have broad applicability: Examples include public-key infrastructures, common reference strings, shared synchronization mechanisms, global blockchains, or even abstractions such as the random oracle. However, the need to work in a specialized framework has been a source of confusion, incompatibility, and an impediment to broader use.
We show how security in the presence of a global setup can be captured within the plain UC framework, thus significantly simplifying the treatment. This is done as follows:
- We extend UC-emulation to the case where both the emulating protocol $\pi$ and the emulated protocol $\phi$ make subroutine calls to protocol $\gamma$ that is accessible also outside $\pi$ and $\phi$. As usual, this notion considers only a single instance of $\phi$ or $\pi$ (alongside $\gamma$).
- We extend the UC theorem to hold even with respect to the new notion of UC emulation. That is, we show that if $\pi$ UC-emulates $\phi$ in the presence of $\gamma$, then $\rho^{\phi\rightarrow\pi}$ UC-emulates $\rho$ for any protocol $\rho$, even when $\rho$ uses $\gamma$ directly, and in addition calls many instances of $\phi$, all of which use the same instance of $\gamma$. We prove this extension using the existing UC theorem as a black box, thus further simplifying the treatment.
We also exemplify how our treatment can be used to streamline, within the plain UC model, proofs of security of systems that involve global set-up, thus providing greater simplicity and flexibility.

2020

ASIACRYPT

Efficient and Round-Optimal Oblivious Transfer and Commitment with Adaptive Security
📺
Abstract

We construct the most efficient two-round adaptively secure bit-OT in the Common Random String (CRS) model. The scheme is UC secure under the Decisional Diffie-Hellman (DDH) assumption. It incurs O(1) exponentiations and sends O(1) group elements, whereas the state of the art requires O(k^2) exponentiations and communicates poly(k) bits, where k is the computational security parameter. Along the way, we obtain several other efficient UC-secure OT protocols under DDH :
- The most efficient yet two-round adaptive string-OT protocol assuming global programmable random oracle. Furthermore, the protocol can be made non-interactive in the simultaneous message setting, assuming random inputs for the sender.
- The first two-round string-OT with amortized constant exponentiations and communication overhead which is secure in the global observable random oracle model.
- The first two-round receiver equivocal string-OT in the CRS model that incurs constant computation and communication overhead.
We also obtain the first non-interactive adaptive string UC-commitment in the CRS model which incurs a sublinear communication overhead in the security parameter. Specically, we commit to polylog(k) bits while communicating O(k) bits. Moreover, it is additively homomorphic.
We can also extend our results to the single CRS model where multiple
sessions share the same CRS. As a corollary, we obtain a two-round
adaptively secure MPC protocol in this model.

2020

JOFC

Reusable Fuzzy Extractors for Low-Entropy Distributions
Abstract

Fuzzy extractors (Dodis et al., in Advances in cryptology—EUROCRYPT 2014, Springer, Berlin, 2014, pp 93–110) convert repeated noisy readings of a secret into the same uniformly distributed key. To eliminate noise, they require an initial enrollment phase that takes the first noisy reading of the secret and produces a nonsecret helper string to be used in subsequent readings. Reusable fuzzy extractors (Boyen, in Proceedings of the 11th ACM conference on computer and communications security, CCS, ACM, New York, 2004, pp 82–91) remain secure even when this initial enrollment phase is repeated multiple times with noisy versions of the same secret, producing multiple helper strings (for example, when a single person’s biometric is enrolled with multiple unrelated organizations). We construct the first reusable fuzzy extractor that makes no assumptions about how multiple readings of the source are correlated. The extractor works for binary strings with Hamming noise; it achieves computational security under the existence of digital lockers (Canetti and Dakdouk, in Advances in cryptology—EUROCRYPT 2008, Springer, Berlin, 2008, pp 489–508). It is simple and tolerates near-linear error rates. Our reusable extractor is secure for source distributions of linear min-entropy rate. The construction is also secure for sources with much lower entropy rates—lower than those supported by prior (nonreusable) constructions—assuming that the distribution has some additional structure, namely, that random subsequences of the source have sufficient minentropy. Structure beyond entropy is necessary to support distributions with low entropy rates. We then explore further how different structural properties of a noisy source can be used to construct fuzzy extractors when the error rates are high, building a computationally secure and an information-theoretically secure construction for large-alphabet sources.

2018

TCC

Certifying Trapdoor Permutations, Revisited
Abstract

The modeling of trapdoor permutations has evolved over the years. Indeed, finding an appropriate abstraction that bridges between the existing candidate constructions and the needs of applications has proved to be challenging. In particular, the notions of certifying permutations (Bellare and Yung, 96), enhanced and doubly enhanced trapdoor permutations (Goldreich, 04, 08, 11, Goldreich and Rothblum, 13) were added to bridge the gap between the modeling of trapdoor permutations and needs of applications. We identify an additional gap in the current abstraction of trapdoor permutations: Previous works implicitly assumed that it is easy to recognize elements in the domain, as well as uniformly sample from it, even for illegitimate function indices. We demonstrate this gap by using the (Bitansky-Paneth-Wichs, 16) doubly-enhanced trapdoor permutation family to instantiate the Feige-Lapidot-Shamir (FLS) paradigm for constructing non-interactive zero-knowledge (NIZK) protocols, and show that the resulting proof system is unsound. To close the gap, we propose a general notion of certifiably injective doubly enhanced trapdoor functions (DECITDFs), which provides a way of certifying that a given key defines an injective function over the domain defined by it, even when that domain is not efficiently recognizable and sampleable. We show that DECITDFs suffice for instantiating the FLS paradigm; more generally, we argue that certifiable injectivity is needed whenever the generation process of the function is not trusted. We then show two very different ways to construct DECITDFs: One is via the traditional method of RSA/Rabin with the Bellare-Yung certification mechanism, and the other using indistinguishability obfuscation and injective pseudorandom generators. In particular the latter is the first candidate injective trapdoor function, from assumptions other than factoring, that suffices for the FLS paradigm. Finally we observe that a similar gap appears also in other paths proposed in the literature for instantiating the FLS paradigm, specifically via verifiable pseudorandom generators and verifiable pseudorandom functions. Closing the gap there can be done in similar ways to the ones proposed here.

2015

CRYPTO

2014

CRYPTO

2006

TCC

2006

JOFC

2003

EUROCRYPT

1999

EUROCRYPT

#### Program Committees

- Crypto 2019
- TCC 2017
- Crypto 2017
- Eurocrypt 2016
- Crypto 2014
- Crypto 2013 (Program chair)
- Crypto 2012 (Program chair)
- Eurocrypt 2010
- TCC 2008 (Program chair)
- TCC 2007
- TCC 2004
- Crypto 2001
- Crypto 2000

#### Coauthors

- Gilad Asharov (2)
- Christian Badertscher (1)
- Boaz Barak (3)
- Mihir Bellare (1)
- Nir Bitansky (8)
- Yilei Chen (4)
- Alessandro Chiesa (1)
- Asaf Cohen (1)
- Henry Cohn (1)
- Dana Dachman-Soled (1)
- Ronny Ramzi Dakdouk (2)
- Ivan Damgård (2)
- Yevgeniy Dodis (2)
- Cynthia Dwork (1)
- Stefan Dziembowski (2)
- Marc Fischlin (1)
- Benjamin Fuller (2)
- Rosario Gennaro (1)
- Oded Goldreich (1)
- Shafi Goldwasser (5)
- Vipul Goyal (1)
- Shai Halevi (12)
- Carmit Hazay (2)
- Amir Herzberg (2)
- Jonathan Herzog (2)
- Julia Hesse (1)
- Justin Holmgren (2)
- Yuval Ishai (2)
- Abhishek Jain (2)
- Stanislaw Jarecki (1)
- Yael Tauman Kalai (6)
- Ari Karchmer (1)
- Jonathan Katz (5)
- Hugo Krawczyk (6)
- Eyal Kushilevitz (4)
- Amit Lichtenberg (1)
- Huijia Lin (3)
- Yehuda Lindell (6)
- Philip D. MacKenzie (1)
- Tal Malkin (3)
- Moni Naor (1)
- Jesper Buus Nielsen (1)
- Kobbi Nissim (1)
- Rafail Ostrovsky (2)
- Omer Paneth (9)
- Dimitrios Papadopoulos (1)
- Sunoo Park (1)
- Rafael Pass (3)
- Oxana Poburinnaya (5)
- Tal Rabin (4)
- Srinivasan Raghuraman (1)
- Mariana Raykova (2)
- Leonid Reyzin (4)
- Silas Richelson (2)
- Ronald L. Rivest (1)
- Alon Rosen (1)
- Adi Rosén (1)
- Ron D. Rothblum (1)
- Guy N. Rothblum (2)
- Aviad Rubinstein (1)
- Amit Sahai (2)
- Pratik Sarkar (2)
- Daniel Shahaf (1)
- Adam Smith (2)
- Michael Steiner (2)
- Madhu Sudan (1)
- Bjoern Tackmann (1)
- Stefano Tessaro (1)
- Luca Trevisan (1)
- Nikos Triandopoulos (1)
- Eran Tromer (1)
- Salil P. Vadhan (1)
- Vinod Vaikuntanathan (3)
- Margarita Vald (1)
- Mayank Varia (3)
- Muthuramakrishnan Venkitasubramaniam (1)
- Shabsi Walfish (1)
- Xiao Wang (2)
- Hoeteck Wee (2)
- Daniel Wichs (1)
- Vassilis Zikas (1)