Publications

Fiat-Shamir & CI from strong KDM-secure encryption [ Eurocrypt 2018 ]

Constraint-hiding constrained PRFs for NC1 from LWE [ Eurocrypt 2017 ]

Cryptanalyses of candidate branching program obfuscators [ Eurocrypt 2017 ]

Adaptive succinct garbled RAM, or how to delegate your database [ TCC 2016-B ]

On the correlation intractability of obfuscated pseudorandom functions [ TCC 2016-A ]

Fiat-Shamir & CI from strong KDM-secure encryption [ Eurocrypt 2018 ]

Constraint-hiding constrained PRFs for NC1 from LWE [ Eurocrypt 2017 ]

Cryptanalyses of candidate branching program obfuscators [ Eurocrypt 2017 ]

Adaptive succinct garbled RAM, or how to delegate your database [ TCC 2016-B ]

On the correlation intractability of obfuscated pseudorandom functions [ TCC 2016-A ]

------------------------------------------------------

**Fiat-Shamir and correlation intractability from strong KDM-secure encryption**

Ran Canetti, Yilei Chen, Leonid Reyzin, Ron D. Rothblum

@37th Eurocrypt [ EUROCRYPT 2018 || eprint || slides ]

**Alternative abstract:**We show that the textbook discrete-log based hash function is correlation intractable (therefore suffices for Fiat-Shamir for proofs) under exponential hardness assumption on the underlying discrete-log problem. The hash function is defined as:

Let g be a generator of the group G. The public key is composed of A = g^a, B = g^b. H_{A, B}(x) = A^x B = g^{ax+b}.

**Constraint-hiding Constrained PRFs for NC1 from LWE**

Ran Canetti, Yilei Chen

@36th Eurocrypt [ EUROCRYPT 2017 || humor || eprint || slides@Aarhus || slides+video@Paris ]

**Abstract:**Constraint-hiding constrained PRFs (CHCPRFs), initially studied by Boneh, Lewi and Wu [PKC 2017], are constrained PRFs where the constrained key hides the description of the constraint. Envisioned with powerful applications such as searchable encryption, private-detectable watermarking and symmetric deniable encryption, the only known candidates of CHCPRFs are based on indistinguishability obfuscation or multilinear maps with strong security properties.

In this paper we construct CHCPRFs for all NC1 circuits from the Learning with Errors assumption. The construction draws heavily from the graph-induced multilinear maps by Gentry, Gorbunov and Halevi [TCC 2015], as well as the existing lattice-based PRFs. Our construction gives an instance of the GGH15 applications with a security reduction to LWE.

We also show how to build from CHCPRFs reusable garbled circuits (RGC), or equivalently private-key function-hiding functional encryptions with 1-key security. This provides a different approach of constructing RGC from that of Goldwasser et al. [STOC 2013].

**Cryptanalyses of Candidate Branching Program Obfuscators**

Yilei Chen, Craig Gentry, Shai Halevi

@36th Eurocrypt [ EUROCRYPT 2017 || sage || eprint || slides || video ]

**Alternative abstract:** Birds are creatures with an outside and an inside. When you remove the outside, you see the inside; when you remove the inside, you see the soul.

**Adaptive Succinct Garbled RAM or How to Delegate Your Database**

Ran Canetti, Yilei Chen, Justin Holmgren, Mariana Raykova

@14th Theory of Cryptography Conference [ TCC 2016-B || Матрёшка || eprint || slides ]

**Abstract:**We show how to garble a large persistent database and then garble, one by one, a sequence of adaptively and adversarially chosen RAM programs that query and modify the database in arbitrary ways. Still, it is guaranteed that the garbled database and programs reveal only the outputs of the programs when run in sequence on the database. The runtime, space requirements and description size of the garbled programs are proportional only to those of the plaintext programs and the security parameter. We assume indistinguishability obfuscation for circuits and poly-to-one collision-resistant hash functions. The latter can be constructed based on standard algebraic assumptions such as the hardness of discrete log or factoring. In contrast, all previous garbling schemes with persistent data were shown secure only in the static setting where all the programs are known in advance.

As an immediate application, our scheme is the first to provide a way to outsource large databases to untrusted servers, and later query and update the database over time in a private and verifiable way, with complexity and description size proportional to those of the unprotected queries.

Our scheme extends the non-adaptive RAM garbling scheme of Canetti and Holmgren [ITCS 2016]. We also define and use a new primitive, called adaptive accumulators, which is an adaptive alternative to the positional accumulators of Koppula et al [STOC 2015] and somewhere statistical binding hashing of Hubacek and Wichs [ITCS 2015]. This primitive might well be useful elsewhere.

**On the Correlation Intractability of Obfuscated Pseudorandom Functions**

Ran Canetti, Yilei Chen, Leonid Reyzin.

@13th Theory of Cryptography Conference [ TCC 2016-A || proof-by-animation || eprint || slides ]

**Abstract:**A family of hash functions is called "correlation intractable'' if it is hard to find, given a random function in the family, an input-output pair that satisfies any "sparse'' relation, namely any relation that is hard to satisfy for truly random functions. Correlation intractability captures a strong and natural Random Oracle-like property. However, it is widely considered to be unobtainable. Indeed, it was shown that correlation intractable functions do not exist for some length parameters [Canetti, Goldreich and Halevi, J.ACM 04]. Furthermore, no candidate constructions have been proposed in the literature for any setting of the parameters.

We construct a correlation intractable function ensemble that withstands all relations with a priori bounded polynomial complexity. We assume the existence of sub-exponentially secure indistinguishability obfuscators, puncturable pseudorandom functions, and input-hiding obfuscators for evasive circuits. The existence of the latter is implied by Virtual-Grey-Box obfuscation for evasive circuits [Bitansky et al, CRYPTO 14].

------------------------------------------------------

**An Alternative View of the Graph-Induced Multilinear Maps**

Yilei Chen

Manuscript [ Abstract-in-one-word || eprint ]

**Alternative abstract:**We show that the GGH15 candidate multilinear maps is as secure as LWE for some plaintext distribution for all DAG. At the time it was written there's no specific cryptographic application. The main result is subsumed in a follow-up work that builds private constrained PRF (which implies more things e.g. reusable garbled circuits) from an extension of the safe mode of GGH15.

------------------------------------------------------

**Studies in Integer Factorization Algorithms**

Senior thesis @ Shanghai Jiao Tong University