The Experts below are selected from a list of 24966 Experts worldwide ranked by ideXlab platform
Chris Peikert - One of the best experts on this subject based on the ideXlab platform.
-
CRYPTO (1) - Noninteractive Zero Knowledge for NP from (Plain) Learning with Errors
Advances in Cryptology – CRYPTO 2019, 2019Co-Authors: Chris Peikert, Sina ShiehianAbstract:We finally close the long-standing problem of constructing a noninteractive zero-knowledge (NIZK) proof system for any NP language with security based on the plain Learning With Errors (LWE) problem, and thereby on worst-Case lattice problems. Our proof system instantiates the framework recently developed by Canetti et al. [EUROCRYPT’18], Holmgren and Lombardi [FOCS’18], and Canetti et al. [STOC’19] for soundly applying the Fiat–Shamir transform using a hash function family that is correlation intractable for a suitable class of relations. Previously, such hash families were based either on “exotic” assumptions (e.g., indistinguishability obfuscation or optimal Hardness of certain LWE variants) or, more recently, on the existence of circularly secure fully homomorphic encryption (FHE). However, none of these assumptions are known to be implied by plain LWE or worst-Case Hardness.
-
Lossy Trapdoor Functions and Their Applications
SIAM Journal on Computing, 2011Co-Authors: Chris Peikert, Brent WatersAbstract:We propose a general cryptographic primitive called lossy trapdoor functions (lossy TDFs), and we use it to develop new approaches for constructing several important cryptographic tools, including (injective) trapdoor functions, collision-resistant hash functions, oblivious transfer, and chosen ciphertext-secure cryptosystems (in the standard model). All of these constructions are simple, efficient, and black-box. We realize lossy TDFs based on a variety of cryptographic assumptions, including the Hardness of the decisional Diffie-Hellman (DDH) problem and the Hardness of the “learning with errors” problem (which is implied by the worst-Case Hardness of various lattice problems). Taken together, our results resolve some long-standing open problems in cryptography. They give the first injective TDFs based on problems not directly related to integer factorization and provide the first chosen ciphertext-secure cryptosystem based solely on worst-Case complexity assumptions.
-
STOC - Public-key cryptosystems from the worst-Case shortest vector problem: extended abstract
Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09, 2009Co-Authors: Chris PeikertAbstract:We construct public-key cryptosystems that are secure assuming theworst-Case Hardness of approximating the minimum distance on n-dimensional lattices to within small Poly(n) factors. Prior cryptosystems with worst-Case connections were based either on the shortest vector problem for a special class of lattices (Ajtai and Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured Hardness of lattice problems for quantum algorithms (Regev, STOC 2005). Our main technical innovation is a reduction from variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. As an additional contribution, we construct a natural chosen ciphertext-secure cryptosystem having a much simpler description and tighter underlying worst-Case approximation factor than prior schemes.
-
Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem.
IACR Cryptology ePrint Archive, 2008Co-Authors: Chris PeikertAbstract:We construct public-key cryptosystems that are secure assuming the worst-Case Hardness of approximating the length of a shortest nonzero vector in ann-dimensional lattice to within a small poly(n) factor. Prior cryptosystems with worst-Case connections were based either on the shortest vector problem for a special class of lattices (Ajtai and Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured Hardness of lattice problems for quantum algorithms (Regev, STOC 2005). Our main technical innovation is a reduction from certain variants of the shortest vector problem to corresponding versions of the “learning with errors” (LWE) problem; previously, only a quantum reduction of this kind was known. In addition, we construct new cryptosystems based on the search version of LWE, including a very natural chosen ciphertext-secure system that has a much simpler description and tighter underlying worst-Case approximation factor than prior constructions.
Benjamin Wesolowski - One of the best experts on this subject based on the ideXlab platform.
-
EUROCRYPT (1) - Short Stickelberger Class Relations and Application to Ideal-SVP
Lecture Notes in Computer Science, 2017Co-Authors: Ronald Cramer, Leo Ducas, Benjamin WesolowskiAbstract:The worst-Case Hardness of finding short vectors in ideals of cyclotomic number fields (Ideal-SVP) is a central matter in lattice based cryptography. Assuming the worst-Case Hardness of Ideal-SVP allows to prove the Ring-LWE and Ring-SIS assumptions, and therefore to prove the security of numerous cryptographic schemes and protocols — including key-exchange, digital signatures, public-key encryption and fully-homomorphic encryption.
-
Short Stickelberger Class Relations and Application to Ideal-SVP
Advances in Cryptology – EUROCRYPT 2017, 2017Co-Authors: Rainer Cramer, Leo Ducas, Benjamin WesolowskiAbstract:The worst-Case Hardness of finding short vectors in ideals of cyclotomic number fields (Ideal-SVP) is a central matter in lattice based cryptography. Assuming the worst-Case Hardness of Ideal-SVP allows to prove the Ring-LWE and Ring-SIS assumptions, and therefore to prove the security of numerous cryptographic schemes and protocols — including key-exchange, digital signatures, public-key encryption and fully-homomorphic encryption.A series of recent works has shown that Principal Ideal-SVP is not always as hard as finding short vectors in general lattices, and some schemes were broken using quantum algorithms — the Soliloquy encryption scheme, Smart-Vercauteren fully homomorphic encryption scheme from PKC 2010, and Gentry-Garg-Halevi cryptographic multilinear-maps from Eurocrypt 2013.Those broken schemes were using a special class of principal ideals, but these works also showed how to solve SVP for principal ideals in the worst-Case in quantum polynomial time for an approximation factor of $$\exp (\tilde{O}(\sqrt{n}))$$ . This exposed an unexpected Hardness gap between general lattices and some structured ones, and called into question the Hardness of various problems over structured lattices, such as Ideal-SVP and Ring-LWE.In this work, we generalize the previous result to general ideals. Precisely, we show how to solve the close principal multiple problem (CPM) by exploiting the classical theorem that the class-group is annihilated by the (Galois-module action of) the so-called Stickelberger ideal. Under some plausible number-theoretical hypothesis, our approach provides a close principal multiple in quantum polynomial time. Combined with the previous results, this solves Ideal-SVP in the worst Case in quantum polynomial time for an approximation factor of $$\exp (\tilde{O}(\sqrt{n}))$$ .Although it does not seem that the security of Ring-LWE based cryptosystems is directly affected, we contribute novel ideas to the cryptanalysis of schemes based on structured lattices. Moreover, our result shows a deepening of the gap between general lattices and structured ones.
Jörg Rothe - One of the best experts on this subject based on the ideXlab platform.
-
The shield that never was: Societies with single-peaked preferences are more open to manipulation and control
Information and Computation, 2011Co-Authors: Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg RotheAbstract:AbstractMuch work has been devoted, during the past 20years, to using complexity to protect elections from manipulation and control. Many “complexity shield” results have been obtained—results showing that the attacker’s task can be made NP-hard. Recently there has been much focus on whether such worst-Case Hardness protections can be bypassed by frequently correct heuristics or by approximations. This paper takes a very different approach: We argue that when electorates follow the canonical political science model of societal preferences the complexity shield never existed in the first place. In particular, we show that for electorates having single-peaked preferences, many existing NP-Hardness results on manipulation and control evaporate
-
The Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control
arXiv: Computer Science and Game Theory, 2009Co-Authors: Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg RotheAbstract:Much work has been devoted, during the past twenty years, to using complexity to protect elections from manipulation and control. Many results have been obtained showing NP-Hardness shields, and recently there has been much focus on whether such worst-Case Hardness protections can be bypassed by frequently correct heuristics or by approximations. This paper takes a very different approach: We argue that when electorates follow the canonical political science model of societal preferences the complexity shield never existed in the first place. In particular, we show that for electorates having single-peaked preferences, many existing NP-Hardness results on manipulation and control evaporate.
Giulia Ferrini - One of the best experts on this subject based on the ideXlab platform.
-
Continuous-variable sampling from photon-added or photon-subtracted squeezed states
Physical Review A, 2017Co-Authors: Ulysse Chabaud, Tom Douce, Damian Markham, P. Van Loock, Elham Kashefi, Giulia FerriniAbstract:We introduce a family of quantum circuits in continuous variables and we show that, relying on the widely accepted conjecture that the polynomial hierarchy of complexity classes does not collapse, their output probability distribution cannot be efficiently simulated by a classical computer. These circuits are composed of input photon-subtracted (or photon-added) squeezed states, passive linear optics evolution, and eight-port homodyne detection. We address the proof of Hardness for the exact probability distribution of these quantum circuits by exploiting mappings onto different architectures of subuniversal quantum computers. We obtain both a worst-Case and an average-Case Hardness result. Hardness of boson sampling with eight-port homodyne detection is obtained as the zero squeezing limit of our model. We conclude with a discussion on the relevance and interest of the present model in connection to experimental applications and classical simulations.
-
Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
Physical Review A, 2017Co-Authors: Ulysse Chabaud, Tom Douce, Damian Markham, P. Van Loock, Elham Kashefi, Giulia FerriniAbstract:We introduce a new family of quantum circuits in Continuous Variables and we show that, relying on the widely accepted conjecture that the polynomial hierarchy of complexity classes does not collapse, their output probability distribution cannot be efficiently simulated by a classical computer. These circuits are composed of input photon-subtracted (or photon-added) squeezed states, passive linear optics evolution, and eight-port homodyne detection. We address the proof of Hardness for the exact probability distribution of these quantum circuits by exploiting mappings onto different architectures of sub-universal quantum computers. We obtain both a worst-Case and an average-Case Hardness result. Hardness of Boson Sampling with eight-port homodyne detection is obtained as the zero squeezing limit of our model. We conclude with a discussion on the relevance and interest of the present model in connection to experimental applications and classical simulations.
Vadim Lyubashevsky - One of the best experts on this subject based on the ideXlab platform.
-
worst Case Hardness for lpn and cryptographic hashing via code smoothing
Theory and Application of Cryptographic Techniques, 2019Co-Authors: Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel WichsAbstract:We present a worst Case decoding problem whose Hardness reduces to that of solving the Learning Parity with Noise (LPN) problem, in some parameter regime. Prior to this work, no worst Case Hardness result was known for LPN (as opposed to syntactically similar problems such as Learning with Errors). The caveat is that this worst Case problem is only mildly hard and in particular admits a quasi-polynomial time algorithm, whereas the LPN variant used in the reduction requires extremely high noise rate of \(1/2-1/\mathrm{poly}(n)\). Thus we can only show that “very hard” LPN is harder than some “very mildly hard” worst Case problem. We note that LPN with noise \(1/2-1/\mathrm{poly}(n)\) already implies symmetric cryptography.
-
EUROCRYPT (3) - Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing
Advances in Cryptology – EUROCRYPT 2019, 2019Co-Authors: Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel WichsAbstract:We present a worst Case decoding problem whose Hardness reduces to that of solving the Learning Parity with Noise (LPN) problem, in some parameter regime. Prior to this work, no worst Case Hardness result was known for LPN (as opposed to syntactically similar problems such as Learning with Errors). The caveat is that this worst Case problem is only mildly hard and in particular admits a quasi-polynomial time algorithm, whereas the LPN variant used in the reduction requires extremely high noise rate of \(1/2-1/\mathrm{poly}(n)\). Thus we can only show that “very hard” LPN is harder than some “very mildly hard” worst Case problem. We note that LPN with noise \(1/2-1/\mathrm{poly}(n)\) already implies symmetric cryptography.
-
Asymptotically Efficient Lattice-Based Digital Signatures
Journal of Cryptology, 2017Co-Authors: Vadim Lyubashevsky, Daniele MicciancioAbstract:We present a general framework that converts certain types of linear collision-resistant hash functions into one-time signatures. Our generic construction can be instantiated based on both general and ideal (e.g., cyclic) lattices, and the resulting signature schemes are provably secure based on the worst-Case Hardness of approximating the shortest vector (and other standard lattice problems) in the corresponding class of lattices to within a polynomial factor. When instantiated with ideal lattices, the time complexity of the signing and verification algorithms, as well as key and signature size, is almost linear (up to poly-logarithmic factors) in the dimension n of the underlying lattice. Since no sub-exponential (in n) time algorithm is known to solve lattice problems in the worst Case, even when restricted to ideal lattices, our construction gives a digital signature scheme with an essentially optimal performance/security trade-off.
-
Asymptotically Effi cient Lattice-Based Digital Signatures.
IACR Cryptology ePrint Archive, 2013Co-Authors: Vadim Lyubashevsky, Daniele MicciancioAbstract:We present a general framework that converts certain types of linear collision-resistant hash functions into one-time signatures. Our generic construction can be instantiated based on both general and ideal (e.g. cyclic) lattices, and the resulting signature schemes are provably secure based on the worst-Case Hardness of approximating the shortest vector (and other standard lattice problems) in the corresponding class of lattices to within a polynomial factor. When instantiated with ideal lattices, the time complexity of the signing and verication algorithms, as well as key and signature size is almost linear (up to poly-logarithmic factors) in the dimension n of the underlying lattice. Since no sub-exponential (in n) time algorithm is known to solve lattice problems in the worst Case, even when restricted to ideal lattices, our construction gives a digital signature scheme with an essentially optimal performance/security trade-o.
-
Lattice signatures without trapdoors
2012Co-Authors: Vadim LyubashevskyAbstract:We provide an alternative method for constructing lattice-based digital signatures which does not use the "hash-and-sign" methodology of Gentry, Peikert, and Vaikuntanathan (STOC 2008). Our resulting signature scheme is secure, in the random oracle model, based on the worst-Case Hardness of the Õ(n 1.5)-SIVP problem in general lattices. The secret key, public key, and the signature size of our scheme are smaller than in all previous instantiations of the hash-and-sign signature, and our signing algorithm is also quite simple, requiring just a few matrix-vector multiplications and rejection samplings. We then also show that by slightly changing the parameters, one can get even more efficient signatures that are based on the Hardness of the Learning With Errors problem. Our construction naturally transfers to the ring setting, where the size of the public and secret keys can be significantly shrunk, which results in the most practical to-date provably secure signature scheme based on lattices.