My research focuses on cryptography and cryptanalysis, namely making hard problems useful or breaking them. I'm especially interested in working on problems related to lattices, elliptic curves, and quantum computation.
Talks on "Lattice, Multilinear Maps, and Obfuscation"
This is a collection of talks about the recent progress on understanding the lattice theory behind the cryptographic multilinear maps and program obfuscators. Open problems are mentioned in the slides.
@Lattice Meeting at ENS, Lyon, July 2017 [ blackboard talk ]
@Cryptography Innovation School II: Lattice, Shanghai, December 2019 [ slides, video 1, 2 ]
@Simons Institute Workshop on Lattices -- Bootcamp, Berkeley, January 2020 [ slides, video ]
This is a collection of talks about the recent progress on understanding the lattice theory behind the cryptographic multilinear maps and program obfuscators. Open problems are mentioned in the slides.
@Lattice Meeting at ENS, Lyon, July 2017 [ blackboard talk ]
@Cryptography Innovation School II: Lattice, Shanghai, December 2019 [ slides, video 1, 2 ]
@Simons Institute Workshop on Lattices -- Bootcamp, Berkeley, January 2020 [ slides, video ]
@Simons Institute Workshop on Lattices -- Cryptanalysis of Candidate Program Obfuscators.
Abstract: In this talk I will first survey the cryptanalytic attacks on the candidate program obfuscators. I will then explain two attacks on the candidates obfuscators built on GGH15 multilinear maps, and mention two interesting open problems related to lattices and quantum algorithms. [ slides || video ]
Abstract: In this talk I will first survey the cryptanalytic attacks on the candidate program obfuscators. I will then explain two attacks on the candidates obfuscators built on GGH15 multilinear maps, and mention two interesting open problems related to lattices and quantum algorithms. [ slides || video ]
------------------------------------------------------
Publications
Fiat-Shamir: from practice to theory [ STOC 2019 ]
Traitor-tracing from LWE made simple and attribute-based [ TCC 2018 ]
Constraint-hiding constrained PRFs for NC1 from LWE [ Eurocrypt 2017 ]
Cryptanalyses of candidate branching program obfuscators [ Eurocrypt 2017 ]
Matrix PRFs: constructions, attacks, and applications to obfuscation [ TCC 2019 ]
Adaptive succinct garbled RAM, or: how to delegate your database [ TCC 2016-B ]
On the correlation intractability of obfuscated pseudorandom functions [ TCC 2016-A ]
Approximate trapdoors for lattices and smaller hash-and-sign signatures [ Asiacrypt 2019 ]
Fiat-Shamir & correlation intractability from strong KDM-secure encryption [ Eurocrypt 2018 ]
Continuous space-bounded non-malleable codes from stronger proof-of-space [ Crypto 2019 ]
Hard isogeny problems over RSA moduli and groups with infeasible inversion [ Asiacrypt 2019 ]
GGH15 beyond permutation branching programs: proofs, attacks, and candidates [ Crypto 2018 ]
------------------------------------------------------
Does Fiat-Shamir Require a Cryptographic Hash Function?
Yilei Chen, Alex Lombardi, Fermi Ma, Willy Quach
In submission [ eprint || video@Boston University ]
Yilei Chen, Alex Lombardi, Fermi Ma, Willy Quach
In submission [ eprint || video@Boston University ]
Answer: Not necessarily.
Hard Isogeny Problems over RSA Moduli and Groups with Infeasible Inversion
Salim Ali Altuğ, Yilei Chen
@25th Asiacrypt [ ASIACRYPT 2019 || eprint || video@KU Leuven || open problems 1, 2 ]
Salim Ali Altuğ, Yilei Chen
@25th Asiacrypt [ ASIACRYPT 2019 || eprint || video@KU Leuven || open problems 1, 2 ]
Abstract: We initiate the study of computational problems on elliptic curve isogeny graphs defined over RSA moduli. We conjecture that several variants of the neighbor-search problem over these graphs are hard, and provide a comprehensive list of cryptanalytic attempts on these problems. Moreover, based on the hardness of these problems, we provide a construction of groups with infeasible inversion, where the underlying groups are the ideal class groups of imaginary quadratic orders.
Recall that in a group with infeasible inversion, computing the inverse of a group element is required to be hard, while performing the group operation is easy. 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 (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). Our construction gives a candidate without using iO.
Recall that in a group with infeasible inversion, computing the inverse of a group element is required to be hard, while performing the group operation is easy. 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 (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). Our construction gives a candidate without using iO.
Approximate Trapdoors for Lattices and Smaller Hash-and-Sign Signatures
Yilei Chen, Nicholas Genise, Pratyay Mukherjee
@25th Asiacrypt [ ASIACRYPT 2019 || eprint || slides@NIST_PQC ]
Yilei Chen, Nicholas Genise, Pratyay Mukherjee
@25th Asiacrypt [ ASIACRYPT 2019 || eprint || slides@NIST_PQC ]
Abstract: We study a relaxed notion of lattice trapdoor called approximate trapdoor, which is defined to be able to invert Ajtai’s one-way function approximately instead of exactly. The primary motivation of our study is to improve the efficiency of the cryptosystems built from lattice trapdoors, including the hash-and-sign signatures.
Our main contribution is to construct an approximate trapdoor by modifying the gadget trapdoor proposed by Micciancio and Peikert [Eurocrypt 2012]. In particular, we show how to use the approximate gadget trapdoor to sample short preimages from a trapdoor-independent distribution. The analysis of the distribution uses a theorem (implicitly used in past works) regarding linear transformations of discrete Gaussians on lattices.
Our approximate gadget trapdoor can be used together with the existing optimization techniques to improve the concrete performance of the hash-and-sign signature in the random oracle model under (Ring-)LWE and (Ring-)SIS assumptions. Our implementation shows that the sizes of the public-key & signature are about half of those in schemes built from exact trapdoors.
Our main contribution is to construct an approximate trapdoor by modifying the gadget trapdoor proposed by Micciancio and Peikert [Eurocrypt 2012]. In particular, we show how to use the approximate gadget trapdoor to sample short preimages from a trapdoor-independent distribution. The analysis of the distribution uses a theorem (implicitly used in past works) regarding linear transformations of discrete Gaussians on lattices.
Our approximate gadget trapdoor can be used together with the existing optimization techniques to improve the concrete performance of the hash-and-sign signature in the random oracle model under (Ring-)LWE and (Ring-)SIS assumptions. Our implementation shows that the sizes of the public-key & signature are about half of those in schemes built from exact trapdoors.
Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation
Yilei Chen, Minki Hhan, Vinod Vaikuntanathan, Hoeteck Wee
@17th Theory of Cryptography Conference [ TCC 2019 || eprint ]
Yilei Chen, Minki Hhan, Vinod Vaikuntanathan, Hoeteck Wee
@17th Theory of Cryptography Conference [ TCC 2019 || eprint ]
Succinct abstract: We initiate a systematic study of pseudorandom functions (PRFs) that are computable by simple matrix branching programs; we refer to these objects as “matrix PRFs”. Matrix PRFs are attractive due to their simplicity, strong connections to complexity theory and group theory, and recent applications in program obfuscation.
Continuous Space-Bounded Non-Malleable Codes from Stronger Proof-of-Space
Binyi Chen, Yilei Chen, Kristina Hostáková, Pratyay Mukherjee
@39th Crypto [ CRYPTO 2019 || eprint ]
Binyi Chen, Yilei Chen, Kristina Hostáková, Pratyay Mukherjee
@39th Crypto [ CRYPTO 2019 || eprint ]
Abstract: Non-malleable codes are encoding schemes that provide protections against various classes of tampering attacks. Recently Faust et al. (CRYPTO 2017) initiated the study of space-bounded non-malleable codes that provide such protections against tampering within small-space devices. They put forward a construction based on any non-interactive proof-of-space (NIPOS). However, the scheme only protects against an a priori bounded number of tampering attacks.
We construct non-malleable codes that are resilient to an unbounded polynomial number of space-bounded tamperings. Towards that we introduce a stronger variant of NIPOS called proof-extractable NIPOS, and propose two approaches of constructing such a primitive.
Using a new proof strategy we show that the generic encoding scheme of Faust et al. achieves unbounded tamper-resilience when instantiated with a proof-extractable NIPOS.
We construct non-malleable codes that are resilient to an unbounded polynomial number of space-bounded tamperings. Towards that we introduce a stronger variant of NIPOS called proof-extractable NIPOS, and propose two approaches of constructing such a primitive.
Using a new proof strategy we show that the generic encoding scheme of Faust et al. achieves unbounded tamper-resilience when instantiated with a proof-extractable NIPOS.
Fiat-Shamir: From Practice to Theory
Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, Daniel Wichs
@51st ACM Symposium on the Theory of Computing [ STOC 2019 || Part 1 || Part 2 ]
Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, Daniel Wichs
@51st ACM Symposium on the Theory of Computing [ STOC 2019 || Part 1 || Part 2 ]
Abstract of Part 1: 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.
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 || slides ]
Yilei Chen, Vinod Vaikuntanathan, Brent Waters, Hoeteck Wee, Daniel Wichs
@16th Theory of Cryptography Conference [ TCC 2018 || eprint || slides ]
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 ]
Abstract: We carry out a systematic study of the GGH15 graded encoding scheme used with general branching programs. This is motivated by the fact that general branching programs are more efficient than permutation branching programs and also substantially more expressive in the read-once setting.
Our main results are as follows:
1. Proofs. We present new constructions of private constrained PRFs and lockable obfuscation, for constraints (resp. functions to be obfuscated) that are computable by general branching programs. Our constructions are secure under LWE with subexponential approximation factors. Previous constructions of this kind crucially rely on the permutation structure of the underlying branching programs. Using general branching programs allows us to obtain more efficient constructions for certain classes of constraints (resp. functions) while posing new challenges in the proof, which we overcome using new proof techniques.
2. Attacks. We extend the previous attacks on indistinguishability obfuscation (iO) candidates that use GGH15 encodings. The new attack uses the rank of a matrix as the distinguisher, so we call it a "rank attack." The rank attack breaks, among others, the iO candidate for general read-once branching programs by Halevi, Halevi, Shoup, and Stephens-Davidowitz (CCS 2017).
3. Candidates. Drawing upon insights from our proofs and attacks, we present simple candidates for witness encryption and iO that resist the existing attacks, using GGH15 encodings. Our candidate for witness encryption crucially exploits the fact that formulas in conjunctive normal form (CNFs) can be represented by general, read-once branching programs.
Our main results are as follows:
1. Proofs. We present new constructions of private constrained PRFs and lockable obfuscation, for constraints (resp. functions to be obfuscated) that are computable by general branching programs. Our constructions are secure under LWE with subexponential approximation factors. Previous constructions of this kind crucially rely on the permutation structure of the underlying branching programs. Using general branching programs allows us to obtain more efficient constructions for certain classes of constraints (resp. functions) while posing new challenges in the proof, which we overcome using new proof techniques.
2. Attacks. We extend the previous attacks on indistinguishability obfuscation (iO) candidates that use GGH15 encodings. The new attack uses the rank of a matrix as the distinguisher, so we call it a "rank attack." The rank attack breaks, among others, the iO candidate for general read-once branching programs by Halevi, Halevi, Shoup, and Stephens-Davidowitz (CCS 2017).
3. Candidates. Drawing upon insights from our proofs and attacks, we present simple candidates for witness encryption and iO that resist the existing attacks, using GGH15 encodings. Our candidate for witness encryption crucially exploits the fact that formulas in conjunctive normal form (CNFs) can be represented by general, read-once branching programs.
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@TLV ]
Ran Canetti, Yilei Chen, Leonid Reyzin, Ron D. Rothblum
@37th Eurocrypt [ EUROCRYPT 2018 || eprint || 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+video@Paris ]
Ran Canetti, Yilei Chen
@36th Eurocrypt [ EUROCRYPT 2017 || humor || eprint || 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 ]
Alternative abstract: We show how to outsource large databases to untrusted servers, and later query and update the database over time in a private and verifiable way. Our scheme extends the non-adaptive RAM garbling scheme of Canetti and Holmgren [ITCS 2016] to be secure against adaptively chosen queries. 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. The manuscript has not been submitted to anywhere.
------------------------------------------------------
Hiding Secrets in Public Random Functions
Ph.D. dissertation @ Boston University [ BU library open access ]
Ph.D. dissertation @ Boston University [ BU library open access ]
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