I am interested in creating and cracking hard math problems. In many cases, the problems can be used in the design and analysis of cryptographic protocols. The published papers focus on pseudorandom functions, program obfuscation, and cryptographic multilinear maps.
Publications
Traitor-tracing made simple and attribute-based [ TCC 2018 ]
GGH15 beyond permutation branching programs [ Crypto 2018 ]
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 ]
Traitor-tracing made simple and attribute-based [ TCC 2018 ]
GGH15 beyond permutation branching programs [ Crypto 2018 ]
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 from simpler assumptions
Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum
[ eprint ]
Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum
[ eprint ]
Abstract: We present two new protocols:
(1) A succinct publicly verifiable non-interactive argument system for log-space uniform NC computations, under the assumption that any one of a broad class of fully homomorphic encryption (FHE) schemes has almost optimal security against polynomial-time adversaries. The class includes all FHE schemes in the literature that are based on the learning with errors (LWE) problem.
(2) A non-interactive zero-knowledge argument system for NP in the common random string model, assuming almost optimal hardness of search-LWE against polynomial-time adversaries.
Both results are obtained by applying the Fiat-Shamir transform with explicit, efficiently computable functions (specifically, correlation intractable functions) to certain classes of interactive proofs. We improve over prior work by reducing the security of these protocols to qualitatively weaker computational hardness assumptions. Along the way, we also show that the Fiat-Shamir transform can be soundly applied (in the plain model) to a richer class of protocols than was previously known.
(1) A succinct publicly verifiable non-interactive argument system for log-space uniform NC computations, under the assumption that any one of a broad class of fully homomorphic encryption (FHE) schemes has almost optimal security against polynomial-time adversaries. The class includes all FHE schemes in the literature that are based on the learning with errors (LWE) problem.
(2) A non-interactive zero-knowledge argument system for NP in the common random string model, assuming almost optimal hardness of search-LWE against polynomial-time adversaries.
Both results are obtained by applying the Fiat-Shamir transform with explicit, efficiently computable functions (specifically, correlation intractable functions) to certain classes of interactive proofs. We improve over prior work by reducing the security of these protocols to qualitatively weaker computational hardness assumptions. Along the way, we also show that the Fiat-Shamir transform can be soundly applied (in the plain model) to a richer class of protocols than was previously known.
Abstract: Motivated by the potential cryptographic application of building a directed transitive signature scheme, the search for a group with infeasible inversion was initiated in the theses of Hohenberger and Molnar in 2003. Later it was also shown to provide a broadcast encryption scheme by Irrer et al. (2004). However, to date the only case of a group with infeasible inversion is implied by the much stronger primitive of self-bilinear map constructed by Yamakawa et al. (2014) based on the hardness of factoring and indistinguishability obfuscation (iO).
We propose a candidate trapdoor group with infeasible inversion without using the heavy machinery of iO. The underlying group is isomorphic to the ideal class group of an imaginary quadratic order, and is represented by the elliptic curve isogeny graph. The hardness of group inversion relies on the conjectured hardness of several problems on the isogeny graphs defined over composite moduli with unknown factorization.
We propose a candidate trapdoor group with infeasible inversion without using the heavy machinery of iO. The underlying group is isomorphic to the ideal class group of an imaginary quadratic order, and is represented by the elliptic curve isogeny graph. The hardness of group inversion relies on the conjectured hardness of several problems on the isogeny graphs defined over composite moduli with unknown factorization.
Traitor-Tracing from LWE Made Simple and Attribute-Based
Yilei Chen, Vinod Vaikuntanathan, Brent Waters, Hoeteck Wee, Daniel Wichs
@16th Theory of Cryptography Conference [ TCC 2018 || eprint ]
Yilei Chen, Vinod Vaikuntanathan, Brent Waters, Hoeteck Wee, Daniel Wichs
@16th Theory of Cryptography Conference [ TCC 2018 || eprint ]
Alternative abstract: In [GKW 18], the authors propose a traitor-tracing scheme. The scheme is built upon a special type of secret-key function encryption called mixed-FE, where the ciphertexts that always decrypt to 1 can be produced without using the secret key. They then construct mixed-FE from LWE. The construction and security analysis of the mixed-FE take around 70 pages.
In this paper we show 2 simpler constructions of mixed-FE. The first one is from lockable obfuscation and any normal SKFE (2 pages); the second one is from key-homomorphic private-constrained PRFs (7 pages).
Btw, it doesn't mean you should skip [GKW 18]. [GKW 18] is a nice read. I recommend to read pages 7-11, and try to reconstruct the security analysis by yourself.
In this paper we show 2 simpler constructions of mixed-FE. The first one is from lockable obfuscation and any normal SKFE (2 pages); the second one is from key-homomorphic private-constrained PRFs (7 pages).
Btw, it doesn't mean you should skip [GKW 18]. [GKW 18] is a nice read. I recommend to read pages 7-11, and try to reconstruct the security analysis by yourself.
GGH15 Beyond Permutation Branching Programs: Proofs, Attacks and Candidates
Yilei Chen, Vinod Vaikuntanathan, Hoeteck Wee
@38th Crypto [ CRYPTO 2018 || sage || eprint || Kuleshov effect || slides & video@crypto ]
Yilei Chen, Vinod Vaikuntanathan, Hoeteck Wee
@38th Crypto [ CRYPTO 2018 || sage || eprint || Kuleshov effect || slides & video@crypto ]
Alternative abstract: Life cannot be exciting every day. Life is also about cleaning shoes. The time of cleaning shoes can be unforgettable.
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@MIT || slides@TLV ]
Ran Canetti, Yilei Chen, Leonid Reyzin, Ron D. Rothblum
@37th Eurocrypt [ EUROCRYPT 2018 || eprint || slides@MIT || slides@TLV ]
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}.
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 ]
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].
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 ]
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 ]
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 function)
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 function)
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 ]
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 were no specific "cryptographic applications". The main result is subsumed in a follow-up work that builds private constrained PRF (which implies more primitives e.g. reusable garbled circuits) from an extension of the safe mode of GGH15. Other than crypto-eprint, the manuscript was not submitted to anywhere.
------------------------------------------------------
Abstract: The capability of hiding secrets in the code of a program is powerful, yields advanced cryptographic applications such as computing on encrypted data and software watermarking. My research studies how to privately embed messages or functions in the code of a cryptographic key. Along the way we develop techniques and make new connections in pseudorandom functions (PRF), lattices, multilinear maps and program obfuscation.
In this talk I will focus on two contributions. I will start from the notion of a private constrained PRF. In a private constrained PRF, the master secret key holder is able to publish a modified key without being detected. Our main contribution is in building private constrained PRFs from standard hardness assumptions over lattice problems. Private constrained PRFs are expressive enough to imply simple constructions of deniable encryption, watermarking and functional encryption. I will then talk about correlation intractable hash functions. Correlation intractability captures the property needed for Fiat-Shamir heuristics and proof-of-work of Bitcoin hash functions. We propose two constructions of correlation intractable functions inspired by the private constrained PRF and the obfuscation literature.
In this talk I will focus on two contributions. I will start from the notion of a private constrained PRF. In a private constrained PRF, the master secret key holder is able to publish a modified key without being detected. Our main contribution is in building private constrained PRFs from standard hardness assumptions over lattice problems. Private constrained PRFs are expressive enough to imply simple constructions of deniable encryption, watermarking and functional encryption. I will then talk about correlation intractable hash functions. Correlation intractability captures the property needed for Fiat-Shamir heuristics and proof-of-work of Bitcoin hash functions. We propose two constructions of correlation intractable functions inspired by the private constrained PRF and the obfuscation literature.
Studies in Integer Factorization Algorithms
Senior thesis @ Shanghai Jiao Tong University
Senior thesis @ Shanghai Jiao Tong University