My research focuses on cryptography, and its connection to complexity theory and other disciplines in computer science and mathematics. My main interests are making hard mathematical problems useful for privacy protection, and showing that some conjectured hard problems are in fact easy.
Publications
Fiat-Shamir: from practice to theory [ STOC 2019 ]
Does Fiat-Shamir require a cryptographic hash function [ Crypto 2021 ]
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 ]
Cryptanalysis of candidate obfuscators for affine determinant programs [ Eurocrypt 2022 ]
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 ]
Quantum algorithms for variants of average-case lattice problems via filtering [ Eurocrypt 2022 ]
GGH15 beyond permutation branching programs: proofs, attacks, and candidates [ Crypto 2018 ]
Hardness of range avoidance and remote point for restricted circuits via cryptography [ STOC 2024 ]
------------------------------------------------------
Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix. See the updated version of eprint/2024/555 - Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today.
Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold. I leave the rest of the paper as it is (added a clarification of an operation in Step 8) as a hope that ideas like Complex Gaussian and windowed QFT may find other applications in quantum computation, or tackle LWE in other ways.
Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold. I leave the rest of the paper as it is (added a clarification of an operation in Step 8) as a hope that ideas like Complex Gaussian and windowed QFT may find other applications in quantum computation, or tackle LWE in other ways.
Original abstract: We show a polynomial time quantum algorithm for solving the learning with errors problem (LWE) with certain polynomial modulus-noise ratios. Combining with the reductions from lattice problems to LWE shown by Regev [J.ACM 2009], we obtain polynomial time quantum algorithms for solving the decisional shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP) for all n-dimensional lattices within approximation factors of Omega(n^{4.5}). Previously, no polynomial or even subexponential time quantum algorithms were known for solving GapSVP or SIVP for all lattices within any polynomial approximation factors.
To develop a quantum algorithm for solving LWE, we mainly introduce two new techniques. First, we introduce Gaussian functions with complex variances in the design of quantum algorithms. In particular, we exploit the feature of the Karst wave in the discrete Fourier transform of complex Gaussian functions. Second, we use windowed quantum Fourier transform with complex Gaussian windows, which allows us to combine the information from both time and frequency domains. Using those techniques, we first convert the LWE instance into quantum states with purely imaginary Gaussian amplitudes, then convert purely imaginary Gaussian states into classical linear equations over the LWE secret and error terms, and finally solve the linear system of equations using Gaussian elimination. This gives a polynomial time quantum algorithm for solving LWE.
To develop a quantum algorithm for solving LWE, we mainly introduce two new techniques. First, we introduce Gaussian functions with complex variances in the design of quantum algorithms. In particular, we exploit the feature of the Karst wave in the discrete Fourier transform of complex Gaussian functions. Second, we use windowed quantum Fourier transform with complex Gaussian windows, which allows us to combine the information from both time and frequency domains. Using those techniques, we first convert the LWE instance into quantum states with purely imaginary Gaussian amplitudes, then convert purely imaginary Gaussian states into classical linear equations over the LWE secret and error terms, and finally solve the linear system of equations using Gaussian elimination. This gives a polynomial time quantum algorithm for solving LWE.
Fiat-Shamir for Bounded-Depth Adversaries
Liyan Chen, Yilei Chen, Zikuan Huang, Nuozhou Sun, Tianqi Yang, Yiding Zhang
[ eprint ]
Liyan Chen, Yilei Chen, Zikuan Huang, Nuozhou Sun, Tianqi Yang, Yiding Zhang
[ eprint ]
Abstract: We study how to construct hash functions that can securely instantiate the Fiat-Shamir transformation against bounded-depth adversaries. The motivation is twofold. First, given the recent fruitful line of research of constructing cryptographic primitives against bounded-depth adversaries under worst-case complexity assumptions, and the rich applications of Fiat-Shamir, instantiating Fiat-Shamir hash functions against bounded-depth adversaries under worst-case complexity assumptions might lead to further applications (such as SNARG for P, showing the cryptographic hardness of PPAD, etc.) against bounded-depth adversaries. Second, we wonder whether it is possible to overcome the impossibility results of constructing Fiat-Shamir for arguments [Goldwasser, Kalai, FOCS ’03] in the setting where the depth of the adversary is bounded, given that the known impossibility results (against p.p.t. adversaries) are contrived.
Our main results give new insights for Fiat-Shamir against bounded-depth adversaries in both the positive and negative directions. On the positive side, for Fiat-Shamir for proofs with certain properties, we show that weak worst-case assumptions are enough for constructing explicit hash functions that give AC0[2]-soundness. In particular, we construct an AC0[2]-computable correlation-intractable hash family for constant-degree polynomials against AC0[2] adversaries. On the negative side, we show Fiat-Shamir for arguments is still impossible to achieve against adversaries within AC0[2].
Our main results give new insights for Fiat-Shamir against bounded-depth adversaries in both the positive and negative directions. On the positive side, for Fiat-Shamir for proofs with certain properties, we show that weak worst-case assumptions are enough for constructing explicit hash functions that give AC0[2]-soundness. In particular, we construct an AC0[2]-computable correlation-intractable hash family for constant-degree polynomials against AC0[2] adversaries. On the negative side, we show Fiat-Shamir for arguments is still impossible to achieve against adversaries within AC0[2].
Abstract: Universal computational extractors (UCEs), introduced by Bellare, Hoang, and Keelveedhi [BHK13], can securely replace random oracles in various applications, including KDM-secure encryption, deterministic encryption, RSA-OAEP, etc. Despite its usefulness, constructing UCE in the standard model is challenging. The only known positive result is given by Brzuska and Mittelbach [BM14], who construct UCE with strongly computationally unpredictable one-query source assuming indistinguishability obfuscation (iO) and the existence of point obfuscators with auxiliary input (AIPO); they also construct UCE with q-query sources assuming iO and composable AIPO. On the other hand, Brzuska, Farshim, and Mittelbach [BFM14] show that the most potent version of UCE does not exist, assuming the existence of iO.
In this paper, we construct UCE with strongly computationally unpredictable one-query sources from lattice assumptions based on the GGH15 encodings [GGH15], without using iO. Security is proven under the following assumptions: (1) LWE with subexponential hardness; (2) evasive LWE, which is a new assumption proposed by Wee [Wee22]; (3) the existence of AIPO in NC1. Our UCE directly implies a universal hardcore function that outputs a polynomial number of bits, giving the first lattice-based universal hardcore function without using iO. We also put forth a new primitive called obliviously programmable function as an intermediate abstraction; it makes our analysis more modularized and could be of independent interest
In this paper, we construct UCE with strongly computationally unpredictable one-query sources from lattice assumptions based on the GGH15 encodings [GGH15], without using iO. Security is proven under the following assumptions: (1) LWE with subexponential hardness; (2) evasive LWE, which is a new assumption proposed by Wee [Wee22]; (3) the existence of AIPO in NC1. Our UCE directly implies a universal hardcore function that outputs a polynomial number of bits, giving the first lattice-based universal hardcore function without using iO. We also put forth a new primitive called obliviously programmable function as an intermediate abstraction; it makes our analysis more modularized and could be of independent interest
Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography
Yilei Chen, Jiatu Li
@56th STOC [ STOC 2024 || eprint || eccc || video ]
Yilei Chen, Jiatu Li
@56th STOC [ STOC 2024 || eprint || eccc || video ]
Abstract: A recent line of research has introduced a systematic approach to explore the complexity of explicit construction problems through the use of meta problems, namely, the range avoidance problem (abbrev. Avoid) and the remote point problem (abbrev. RPP). The upper and lower bounds for these meta problems provide a unified perspective on the complexity of specific explicit construction problems that were previously studied independently. An interesting question largely unaddressed by previous works is whether Avoid and RPP are hard for simple circuits such as low-depth circuits.
In this paper, we demonstrate, under plausible cryptographic assumptions, that both the range avoidance problem and the remote point problem cannot be efficiently solved by nondeterministic search algorithms, even when the input circuits are as simple as constant-depth circuits. This extends a hardness result established by Ilango, Li, and Williams (STOC’23) against deterministic algorithms employing witness encryption for NP, where the inputs to Avoid are general Boolean circuits.
Our primary technical contribution is a novel construction of witness encryption inspired by public-key encryption for certain promise language in NP that is unlikely to be NP-complete. We introduce a generic approach to transform a public-key encryption scheme with particular properties into a witness encryption scheme for a promise language related to the initial public key encryption scheme. Based on this translation and variants of standard lattice-based or coding-based PKE schemes, we obtain, under plausible assumption, a provably secure witness encryption scheme for some promise language in NP\coNP/poly. Additionally, we show that our constructions of witness encryption are plausibly secure against nondeterministic adversaries under a generalized notion of security in the spirit of Rudich’s super-bits (RANDOM’97), which is crucial for demonstrating the hardness of Avoid and RPP against nondeterministic algorithms.
In this paper, we demonstrate, under plausible cryptographic assumptions, that both the range avoidance problem and the remote point problem cannot be efficiently solved by nondeterministic search algorithms, even when the input circuits are as simple as constant-depth circuits. This extends a hardness result established by Ilango, Li, and Williams (STOC’23) against deterministic algorithms employing witness encryption for NP, where the inputs to Avoid are general Boolean circuits.
Our primary technical contribution is a novel construction of witness encryption inspired by public-key encryption for certain promise language in NP that is unlikely to be NP-complete. We introduce a generic approach to transform a public-key encryption scheme with particular properties into a witness encryption scheme for a promise language related to the initial public key encryption scheme. Based on this translation and variants of standard lattice-based or coding-based PKE schemes, we obtain, under plausible assumption, a provably secure witness encryption scheme for some promise language in NP\coNP/poly. Additionally, we show that our constructions of witness encryption are plausibly secure against nondeterministic adversaries under a generalized notion of security in the spirit of Rudich’s super-bits (RANDOM’97), which is crucial for demonstrating the hardness of Avoid and RPP against nondeterministic algorithms.
LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling
Yilei Chen, Zihan Hu, Han Luo, Qipeng Liu, Yaxin Tu
[ eprint || arXiv ]
Yilei Chen, Zihan Hu, Han Luo, Qipeng Liu, Yaxin Tu
[ eprint || arXiv ]
Abstract: We show new algorithms, hardness results and applications for S|LWE> and C|LWE> with real Gaussian, Gaussian with linear or quadratic phase terms, and other related amplitudes. Let n be the dimension of LWE samples. Our main results are
1. There is a subexponential-time algorithm for S|LWE> with Gaussian amplitude with known phase, given subexponentially many quantum samples. The algorithm is modified from Kuperberg's sieve, and in fact works for more general amplitudes as long as the amplitudes and phases are completely known.
2. There is a polynomial time quantum algorithm for solving S|LWE> and C|LWE> for Gaussian with quadratic phase amplitudes, where the sample complexity is as small as quasi-linear in n. As an application, we give a quantum oblivious LWE sampler where the core quantum sampler requires only quasi-linear sample complexity. This improves upon the previous oblivious LWE sampler given by Debris-Alazard, Fallahpour, Stehlé [STOC 2024] in terms of the quantum sample complexity.
3. There exist polynomial time quantum reductions from standard LWE or worst-case GapSVP to S|LWE> with Gaussian amplitude with small unknown phase, and arbitrarily many samples. Compared to the first two items, the appearance of the unknown phase term places a barrier in designing efficient quantum algorithm for solving standard LWE via S|LWE>.
1. There is a subexponential-time algorithm for S|LWE> with Gaussian amplitude with known phase, given subexponentially many quantum samples. The algorithm is modified from Kuperberg's sieve, and in fact works for more general amplitudes as long as the amplitudes and phases are completely known.
2. There is a polynomial time quantum algorithm for solving S|LWE> and C|LWE> for Gaussian with quadratic phase amplitudes, where the sample complexity is as small as quasi-linear in n. As an application, we give a quantum oblivious LWE sampler where the core quantum sampler requires only quasi-linear sample complexity. This improves upon the previous oblivious LWE sampler given by Debris-Alazard, Fallahpour, Stehlé [STOC 2024] in terms of the quantum sample complexity.
3. There exist polynomial time quantum reductions from standard LWE or worst-case GapSVP to S|LWE> with Gaussian amplitude with small unknown phase, and arbitrarily many samples. Compared to the first two items, the appearance of the unknown phase term places a barrier in designing efficient quantum algorithm for solving standard LWE via S|LWE>.
QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, Florian Speelman
[ arXiv ]
Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, Florian Speelman
[ arXiv ]
Abstract: While seemingly undesirable, it is not a surprising fact that there are certain problems for which quantum computers offer no computational advantage over their respective classical counterparts. Moreover, there are problems for which there is no "useful" computational advantage possible with the current quantum hardware. This situation however can be beneficial if we don't want quantum computers to solve certain problems fast - say problems relevant to post-quantum cryptography. In such a situation, we would like to have evidence that it is difficult to solve those problems on quantum computers; but what is their exact complexity?
To do so one has to prove lower bounds, but proving unconditional time lower bounds has never been easy. As a result, resorting to conditional lower bounds has been quite popular in the classical community and is gaining momentum in the quantum community. In this paper, by the use of the QSETH framework [Buhrman, Patro, Speelman 2021], we are able to understand the quantum complexity of a few natural variants of CNFSAT, such as parity-CNFSAT or counting-CNFSAT, and also are able to comment on the non-trivial complexity of approximate-#CNFSAT; both of these have interesting implications about the complexity of (variations of) lattice problems, strong simulation and hitting set problem, and more. In the process, we explore the QSETH framework in greater detail than was (required and) discussed in the original paper, thus also serving as a useful guide on how to effectively use the QSETH framework.
To do so one has to prove lower bounds, but proving unconditional time lower bounds has never been easy. As a result, resorting to conditional lower bounds has been quite popular in the classical community and is gaining momentum in the quantum community. In this paper, by the use of the QSETH framework [Buhrman, Patro, Speelman 2021], we are able to understand the quantum complexity of a few natural variants of CNFSAT, such as parity-CNFSAT or counting-CNFSAT, and also are able to comment on the non-trivial complexity of approximate-#CNFSAT; both of these have interesting implications about the complexity of (variations of) lattice problems, strong simulation and hitting set problem, and more. In the process, we explore the QSETH framework in greater detail than was (required and) discussed in the original paper, thus also serving as a useful guide on how to effectively use the QSETH framework.
Practically Solving LPN in High Noise Regimes Faster Using Neural Networks
Haozhe Jiang, Kaiyue Wen, Yilei Chen
[ eprint || arXiv || code ]
Haozhe Jiang, Kaiyue Wen, Yilei Chen
[ eprint || arXiv || code ]
Abstract: We conduct a systematic study of solving the learning parity with noise problem (LPN) using neural networks. Our main contribution is designing families of two-layer neural networks that practically outperform classical algorithms in high-noise, low-dimension regimes. We consider three settings where the numbers of LPN samples are abundant, very limited, and in between. In each setting we provide neural network models that solve LPN as fast as possible. For some settings we are also able to provide theories that explain the rationale of the design of our models.
Comparing with the previous experiments of Esser, Kübler, and May (CRYPTO 2017), for dimension n = 26, noise rate τ = 0.498, the “Guess-then-Gaussian-elimination” algorithm takes 3.12 days on 64 CPU cores, whereas our neural network algorithm takes 66 minutes on 8 GPUs. Our algorithm can also be plugged into the hybrid algorithms for solving middle or large dimension LPN instances.
Comparing with the previous experiments of Esser, Kübler, and May (CRYPTO 2017), for dimension n = 26, noise rate τ = 0.498, the “Guess-then-Gaussian-elimination” algorithm takes 3.12 days on 64 CPU cores, whereas our neural network algorithm takes 66 minutes on 8 GPUs. Our algorithm can also be plugged into the hybrid algorithms for solving middle or large dimension LPN instances.
Cryptanalysis of Candidate Obfuscators for Affine Determinant Programs
Li Yao, Yilei Chen, Yu Yu
@41st Eurocrypt [ EUROCRYPT 2022 || eprint ]
Li Yao, Yilei Chen, Yu Yu
@41st Eurocrypt [ EUROCRYPT 2022 || eprint ]
Abstract: At ITCS 2020, Bartusek et al. proposed a candidate indistinguishability obfuscator (iO) for affine determinant programs (ADPs). The candidate is special since it directly applies specific randomization techniques to the underlying ADP, without relying on the hardness of traditional cryptographic assumptions like discrete-log or learning with errors. It is relatively efficient compared to the rest of the iO candidates. However, the obfuscation scheme requires further cryptanalysis since it was not known to be based on any well-formed mathematical assumptions.
In this paper, we show cryptanalytic attacks on the iO candidate provided by Bartusek et al. Our attack exploits the weakness of one of the randomization steps in the candidate. The attack applies to a fairly general class of programs. At the end of the paper we discuss plausible countermeasures to defend against our attacks.
In this paper, we show cryptanalytic attacks on the iO candidate provided by Bartusek et al. Our attack exploits the weakness of one of the randomization steps in the candidate. The attack applies to a fairly general class of programs. At the end of the paper we discuss plausible countermeasures to defend against our attacks.
Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering
Yilei Chen, Qipeng Liu, Mark Zhandry
@41st Eurocrypt [ EUROCRYPT 2022 || QIP || eprint || arXiv || eccc || sage ]
Yilei Chen, Qipeng Liu, Mark Zhandry
@41st Eurocrypt [ EUROCRYPT 2022 || QIP || eprint || arXiv || eccc || sage ]
Abstract: We show polynomial-time quantum algorithms for the following problems:
(*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant.
(*) Learning with errors (LWE) problem given LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions.
(*) Extrapolated dihedral coset problem (EDCP) with certain parameters.
The SIS, LWE, and EDCP problems in their standard forms are as hard as solving lattice problems in the worst case. However, the variants that we can solve are not in the parameter regimes known to be as hard as solving worst-case lattice problems. Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider. For EDCP, our quantum algorithm slightly extends the result of Ivanyos et al. (2018).
Our algorithms for variants of SIS and EDCP use the existing quantum reductions from those problems to LWE, or more precisely, to the problem of solving LWE given LWE-like quantum states. Our main contribution is solving LWE given LWE-like quantum states with interesting parameters using a filtering technique.
(*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant.
(*) Learning with errors (LWE) problem given LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions.
(*) Extrapolated dihedral coset problem (EDCP) with certain parameters.
The SIS, LWE, and EDCP problems in their standard forms are as hard as solving lattice problems in the worst case. However, the variants that we can solve are not in the parameter regimes known to be as hard as solving worst-case lattice problems. Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider. For EDCP, our quantum algorithm slightly extends the result of Ivanyos et al. (2018).
Our algorithms for variants of SIS and EDCP use the existing quantum reductions from those problems to LWE, or more precisely, to the problem of solving LWE given LWE-like quantum states. Our main contribution is solving LWE given LWE-like quantum states with interesting parameters using a filtering technique.
White-box Cryptography with Device Binding from Token-based Obfuscation and more
Shashank Agrawal, Estuardo Alpirez Bock, Yilei Chen, Gaven Watson
@14th COSADE [ COSADE 2023 || eprint ]
Shashank Agrawal, Estuardo Alpirez Bock, Yilei Chen, Gaven Watson
@14th COSADE [ COSADE 2023 || eprint ]
Abstract: White-box cryptography has been proposed as a software countermeasure technique for applications where limited or no hardware-based security is available. In recent years it has been crucial for enabling the security of mobile payment applications. In this paper we continue a recent line of research on device binding for white-box cryptography. Device binding ensures that a white-box program is only executable on one specific device and is unusable elsewhere. Building on this, we ask the following question: is it possible to design a global white-box program which is compiled once, but can be securely shared with multiple users and bound to each of their devices? Acknowledging this question, we provide two new types of provably-secure constructions for white-box programs.
First, we consider the use of Token-Based Obfuscation (TBO) and show that TBO can provide us a direct way to construct white-box programs with device-binding, as long as we can securely share a token generation key between the compiling entity and the device running the white-box program. This new feasibility result provides more general and efficient results than previously presented for white-box cryptography and demonstrates a new application of TBO not previously considered.
We then consider a stronger family of global white-boxes, where secrets don't need to be shared between users and providers. We show how to extend approaches used in practice based on message recoverable signatures and validate our proposed approach, by providing a construction based on puncturable PRFs and indistinguishability obfuscation.
First, we consider the use of Token-Based Obfuscation (TBO) and show that TBO can provide us a direct way to construct white-box programs with device-binding, as long as we can securely share a token generation key between the compiling entity and the device running the white-box program. This new feasibility result provides more general and efficient results than previously presented for white-box cryptography and demonstrates a new application of TBO not previously considered.
We then consider a stronger family of global white-boxes, where secrets don't need to be shared between users and providers. We show how to extend approaches used in practice based on message recoverable signatures and validate our proposed approach, by providing a construction based on puncturable PRFs and indistinguishability obfuscation.
Does Fiat-Shamir Require a Cryptographic Hash Function?
Yilei Chen, Alex Lombardi, Fermi Ma, Willy Quach
@41st Crypto [ CRYPTO 2021 || eprint || video@Boston University ]
Yilei Chen, Alex Lombardi, Fermi Ma, Willy Quach
@41st Crypto [ CRYPTO 2021 || eprint || video@Boston University ]
Answer: No.
On Removing Rejection Conditions in Practical Lattice-Based Signatures
Rouzbeh Behnia, Yilei Chen, Daniel Masny
@12th PQCrypto [ PQCrypto 2021 ]
Rouzbeh Behnia, Yilei Chen, Daniel Masny
@12th PQCrypto [ PQCrypto 2021 ]
Abstract: Digital signatures following the methodology of “Fiat-Shamir with Aborts”, proposed by Lyubashevsky, are capable of achieving the smallest public-key and signature sizes among all the existing lattice sig- nature schemes based on the hardness of the Ring-SIS and Ring-LWE problems. Since its introduction, several variants and optimizations have been proposed, and two of them (i.e., Dilithium and qTESLA) entered the second round of the NIST post-quantum cryptography standardiza- tion. This method of designing signatures relies on rejection sampling during the signing process. Rejection sampling is crucial for ensuring both the correctness and security of these signature schemes.
In this paper, we investigate the possibility of removing the two rejection conditions used both in Dilithium and qTESLA. First, we show that removing one of the rejection conditions is possible, and provide a variant of Lyubashevsky’s signature with comparable parameters with Dilithium and qTESLA. Second, we give evidence on the difficulty of removing the other rejection condition, by showing that two very general approaches do not yield a signature scheme with correctness or security.
In this paper, we investigate the possibility of removing the two rejection conditions used both in Dilithium and qTESLA. First, we show that removing one of the rejection conditions is possible, and provide a variant of Lyubashevsky’s signature with comparable parameters with Dilithium and qTESLA. Second, we give evidence on the difficulty of removing the other rejection condition, by showing that two very general approaches do not yield a signature scheme with correctness or security.
Hard Isogeny Problems over RSA Moduli and Groups with Infeasible Inversion
Salim Ali Altuğ, Yilei Chen
@25th Asiacrypt [ ASIACRYPT 2019 || eprint || video@KU Leuven || slides@Kobe || open problems 1, 2 ]
Salim Ali Altuğ, Yilei Chen
@25th Asiacrypt [ ASIACRYPT 2019 || eprint || video@KU Leuven || slides@Kobe || 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).
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).
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 || slides@MIT ]
Ran Canetti, Yilei Chen, Leonid Reyzin, Ron D. Rothblum
@37th Eurocrypt [ EUROCRYPT 2018 || eprint || slides@TLV || slides@MIT ]
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 || slides@Aarhus ]
Ran Canetti, Yilei Chen
@36th Eurocrypt [ EUROCRYPT 2017 || humor || eprint || slides+video@Paris || slides@Aarhus ]
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 ]
Succinct 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].
------------------------------------------------------
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 Workshop on Lattices -- Bootcamp, Berkeley, January 2020 [ slides, video ]
@Simons Workshop on Lattices -- Cryptanalysis of Program Obfuscators, Virtual, March 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 Workshop on Lattices -- Bootcamp, Berkeley, January 2020 [ slides, video ]
@Simons Workshop on Lattices -- Cryptanalysis of Program Obfuscators, Virtual, March 2020 [ slides || video ]
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 || slides ]
Ph.D. dissertation @ Boston University [ BU library open access || slides ]
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