## CryptoDB

### Ran Canetti

#### Publications

**Year**

**Venue**

**Title**

2022

EUROCRYPT

COA-Secure Obfuscation and Applications
📺
Abstract

We put forth a new paradigm for program obfuscation, where obfuscated programs are endowed with proofs of ``well formedness.'' In addition to asserting existence of an underlying plaintext program with an attested structure, these proofs also prevent mauling attacks, whereby an adversary surreptitiously creates an obfuscated program based on secrets which are embedded in other obfuscated programs. We call this new guarantee Chosen Obfuscation Attacks (COA) security.
We show how to enhance a large class of obfuscation mechanisms to be COA-secure, assuming subexponentially secure IO for circuits and subexponentially secure one-way functions.To demonstrate the power of the new notion, we also use it to realize:
- A new form of software watermarking, which provides significantly broader protection than current schemes against counterfeits that pass a keyless, public verification process.
- Completely CCA encryption, which is a strengthening of completely non-malleable encryption.

2022

EUROCRYPT

Unclonable Polymers and Their Cryptographic Applications
📺
Abstract

We propose a mechanism for generating and manipulating protein polymers to obtain a new type of *consumable storage* that exhibits intriguing cryptographic "self-destruct" properties, assuming the hardness of certain polymer-sequencing problems.
To demonstrate the cryptographic potential of this technology, we first develop a formalism that captures (in a minimalistic way) the functionality and security properties provided by the technology. Next, using this technology, we construct and prove security of two cryptographic applications that are currently obtainable only via trusted hardware that implements logical circuitry (either classical or quantum). The first application is a password-controlled *secure vault* where the stored data is irrecoverably erased once a threshold of unsuccessful access attempts is reached. The second is (a somewhat relaxed version of) *one time programs*, namely a device that allows evaluating a secret function only a limited number of times before self-destructing, where each evaluation is made on a fresh user-chosen input.
Finally, while our constructions, modeling, and analysis are designed to capture the proposed polymer-based technology, they are sufficiently general to be of potential independent interest.

2022

CRYPTO

Universally Composable End-to-End Secure Messaging
📺
Abstract

We model and analyze the Signal end-to-end messaging protocol within the UC framework. In particular:
- We formulate an ideal functionality that captures end-to-end secure messaging, in a setting with PKI and an untrusted server, against an adversary that has full control over the network and can adaptively and momentarily compromise parties at any time and obtain their entire internal states. In particular our analysis captures the forward secrecy and recovery-of-security properties of Signal and the conditions under which they break.
- We model the main components of the Signal architecture (PKI and long-term keys, the backbone continuous-key-exchange or "asymmetric ratchet," epoch-level symmetric ratchets, authenticated encryption) as individual ideal functionalities that are realized and analyzed separately and then composed using the UC and Global-State UC theorems.
- We show how the ideal functionalities representing these components can be realized using standard cryptographic primitives under minimal hardness assumptions.
Our modeling introduces additional innovations that enable arguing about the security of Signal irrespective of the underlying communication medium, as well as secure composition of dynamically generated modules that share state. These features, together with the basic modularity of the UC framework, will hopefully facilitate the use of both Signal-as-a-whole and its individual components within cryptographic applications.
Two other features of our modeling are the treatment of fully adaptive corruptions, and making minimal use of random oracle abstractions. In particular, we show how to realize continuous key exchange in the plain model, while preserving security against adaptive corruptions.

2022

ASIACRYPT

Triply Adaptive UC NIZK
Abstract

Non-interactive zero knowledge (NIZK) enables a prover, to prove that a statement in an NP
language is valid, given an accepting witness, without leaking any information about the witness. We study universally composable (UC) NIZKs which are secure against adaptive corruption of parties and provides adaptive soundness, i.e. the statement is adaptively chosen by a malicious prover based on the setup string distribution. The only known adaptively secure NIZK protocols either fail to achieve full adaptive soundness or rely on non-falsifiable knowledge assumptions. We construct the first NIZK protocols which are triply adaptive - secure against adaptive corruptions, guarantees adaptive soundness and satisfies adaptive zero knowledge, from falsifiable assumptions. We do so using the following methodology:
- We define a new ideal functionality, denoted as F_NICOM, for non-interactive commitment schemes in the UC framework.
- We define and construct Sigma protocols which satisfy triply adaptive security in the F_NICOM model.
- By relying on correlation intractable (CI) hash functions, we compile a triply adaptively secure Sigma protocol (in F_NICOM model) into a triply adaptive UC-NIZK argument in the F_NICOM+common reference string (crs) model.
In addition to CI hash functions, our compiler requires standard cryptographic primitives - non-interactive equivocal commitments and public key encryption with obliviously samplable ciphertexts, for implementing F_NICOM in the crs model. We instantiate our framework by demonstrating that most statically secure Sigma protocols can be proven to be triply adaptively secure in the F_NICOM model, hence, bridging the gap between static and adaptive security for NIZKs. Our NIZK arguments can be concretely based on assumptions, like LWE, or LPN and DDH.

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 2021
- 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

- Ghada Almashaqbeh (1)
- N. Nalla Anandakumar (1)
- Gilad Asharov (2)
- Christian Badertscher (1)
- Boaz Barak (3)
- Mihir Bellare (1)
- Nir Bitansky (8)
- Suvradip Chakraborty (1)
- 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)
- Yaniv Erlich (1)
- Marc Fischlin (1)
- Benjamin Fuller (2)
- Rosario Gennaro (1)
- Jonathan Gershoni (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)
- Palak Jain (1)
- Stanislaw Jarecki (1)
- Yael Tauman Kalai (6)
- Ari Karchmer (1)
- Jonathan Katz (5)
- Dakshita Khurana (1)
- Hugo Krawczyk (6)
- Eyal Kushilevitz (4)
- Amit Lichtenberg (1)
- Huijia Lin (3)
- Yehuda Lindell (6)
- Philip D. MacKenzie (1)
- Tal Malkin (4)
- 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)
- Itsik Pe'er (1)
- Oxana Poburinnaya (6)
- Manoj Prabhakaran (1)
- Tal Rabin (4)
- Srinivasan Raghuraman (1)
- Mariana Raykova (2)
- Leonid Reyzin (4)
- Silas Richelson (2)
- Ronald L. Rivest (1)
- Anna Roitburd-Berman (1)
- Alon Rosen (1)
- Adi Rosén (1)
- Ron D. Rothblum (1)
- Guy N. Rothblum (2)
- Aviad Rubinstein (1)
- Amit Sahai (2)
- Pratik Sarkar (3)
- Daniel Shahaf (1)
- Adam Smith (2)
- Michael Steiner (2)
- Madhu Sudan (1)
- Marika Swanberg (1)
- Bjoern Tackmann (1)
- Stefano Tessaro (1)
- Luca Trevisan (1)
- Nikos Triandopoulos (1)
- Eran Tromer (2)
- Salil P. Vadhan (1)
- Vinod Vaikuntanathan (3)
- Margarita Vald (1)
- Mayank Varia (4)
- Muthuramakrishnan Venkitasubramaniam (1)
- Shabsi Walfish (1)
- Xiao Wang (3)
- Hoeteck Wee (2)
- Daniel Wichs (1)
- Vassilis Zikas (1)