Publications
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 ]
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 ]
------------------------------------------------------
Constraint-hiding Constrained PRFs for NC1 from LWE
Ran Canetti, Yilei Chen
@36th Eurocrypt [ EUROCRYPT 2017 || humor || eprint || slides ]
Ran Canetti, Yilei Chen
@36th Eurocrypt [ EUROCRYPT 2017 || humor || eprint || slides ]
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].
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 ]
Yilei Chen, Craig Gentry, Shai Halevi
@36th Eurocrypt [ EUROCRYPT 2017 || sage || eprint || slides ]
Abstract: We describe new cryptanalytic attacks on the candidate branching program obfuscator proposed by Garg, Gentry, Halevi, Raykova, Sahai and Waters (GGHRSW) using the GGH13 graded encoding, and its variant using the GGH15 graded encoding as specified by Gentry, Gorbunov and Halevi. All our attacks require very specific structure of the branching programs being obfuscated, which in particular must have some input-partitioning property. Common to all our attacks are techniques to extract information about the "multiplicative bundling'' scalars that are used in the GGHRSW construction.
For GGHRSW over GGH13, we show how to recover the ideal generating the plaintext space when the branching program has input partitioning. Combined with the information that we extract about the "multiplicative bundling'' scalars, we get a distinguishing attack by an extension of the annihilation attack of Miles, Sahai and Zhandry. Alternatively, once we have the ideal we can solve the principle-ideal problem (PIP) in classical subexponential time or quantum polynomial time, hence obtaining a total break.
For the variant over GGH15, we show how to use the left-kernel technique of Coron, Lee, Lepoint and Tibouchi to recover ratios of the bundling scalars. Once we have the ratios of the scalar products, we can use factoring and PIP solvers (in classical subexponential time or quantum polynomial time) to find the scalars themselves, then run mixed-input attacks to break the obfuscation.
For GGHRSW over GGH13, we show how to recover the ideal generating the plaintext space when the branching program has input partitioning. Combined with the information that we extract about the "multiplicative bundling'' scalars, we get a distinguishing attack by an extension of the annihilation attack of Miles, Sahai and Zhandry. Alternatively, once we have the ideal we can solve the principle-ideal problem (PIP) in classical subexponential time or quantum polynomial time, hence obtaining a total break.
For the variant over GGH15, we show how to use the left-kernel technique of Coron, Lee, Lepoint and Tibouchi to recover ratios of the bundling scalars. Once we have the ratios of the scalar products, we can use factoring and PIP solvers (in classical subexponential time or quantum polynomial time) to find the scalars themselves, then run mixed-input attacks to break the obfuscation.
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 ]
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.
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
(a.k.a. the foundation of Bitcoin hash functions)
Ran Canetti, Yilei Chen, Leonid Reyzin.
@13th Theory of Cryptography Conference [ TCC 2016-A || proof-by-animation || eprint || slides ]
(a.k.a. the foundation of Bitcoin hash 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].
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 ]
Yilei Chen
Manuscript [ Abstract-in-one-word || eprint ]
Abstract: In this paper, we view multilinear maps through the lens of homomorphic obfuscation. In specific, we show how to homomorphically obfuscate the kernel-test and affine subspace-test functionalities of high dimensional matrices. Namely, the evaluator is able to perform additions and multiplications over the obfuscated matrices, and test subspace memberships on the resulting code. The homomorphic operations are constrained by the prescribed data structure, e.g. a tree or a graph, where the matrices are stored. The security properties of all the constructions are based on the hardness of Learning with errors problem (LWE). The technical heart is to "control" the "chain reactions'' over a sequence of LWE instances.
Viewing the homomorphic obfuscation scheme from a different angle, it coincides with the graph-induced multilinear maps proposed by Gentry, Gorbunov and Halevi (GGH15). Our proof technique recognizes several "safe modes" of GGH15 that are not known before, including a simple special case: if the graph is acyclic and the matrices are sampled independently from binary or error distributions, then the encodings of the matrices are pseudorandom.
Viewing the homomorphic obfuscation scheme from a different angle, it coincides with the graph-induced multilinear maps proposed by Gentry, Gorbunov and Halevi (GGH15). Our proof technique recognizes several "safe modes" of GGH15 that are not known before, including a simple special case: if the graph is acyclic and the matrices are sampled independently from binary or error distributions, then the encodings of the matrices are pseudorandom.
Studies in Integer Factorization Algorithms
Senior thesis @ Shanghai Jiao Tong University
Senior thesis @ Shanghai Jiao Tong University
