New lattice based cryptographic constructions

DOI10.1145/780542.780603MaRDI QIDQ3581301zbMATH OpenOpenAlexWikidataFDO

Authors Oded Regev

Publication date 16 August 2010

Published in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0309051

Mathematics Subject Classification ID

Quantum computation (81P68) Cryptography (94A60)

Abstract: We introduce the use of Fourier analysis on lattices as an integral part of a lattice based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two cryptographic constructions which are based on the worst-case hardness of the unique shortest vector problem. The main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results ($O(n^{1.5})$ instead of $O(n^7)$). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a family of collision resistant hash functions which, apart from improving the security in terms of the unique shortest vector problem, is also the first example of an analysis which is not based on Ajtai's iterative step. Surprisingly, both results are derived from one theorem which presents two indistinguishable distributions on the segment $[0,1)$. It seems that this theorem can have further applications and as an example we mention how it can be used to solve an open problem related to quantum computation.

Recommendations

• New lattice-based cryptographic constructions
• A lattice-based public-key cryptosystem
• scientific article; zbMATH DE number 1304121
• scientific article; zbMATH DE number 1559544
• Public-key cryptosystems from the worst-case shortest vector problem

Cited in

(27)

• The hunting of the SNARK
• Quantum key search for ternary LWE
• How to meet ternary LWE keys
• Improved broadcast attacks against subset sum problems via lattice oracle
• Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
• LARA: a design concept for lattice-based encryption
• Collision-free hashing from lattice problems
• Public-Key Cryptographic Primitives Provably as Secure as Subset Sum
• Trapdoors for hard lattices and new cryptographic constructions
• Some Recent Progress in Lattice-Based Cryptography
• Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor
• scientific article; zbMATH DE number 1361466 (Why is no real title available?)
• Using quantum key distribution for cryptographic purposes: a survey
• Parameterized intractability of even set and shortest vector problem from Gap-ETH
• The Complexity of Public-Key Cryptography
• Cryptographic functions from worst-case complexity assumptions
• scientific article; zbMATH DE number 7174175 (Why is no real title available?)
• New lattice-based cryptographic constructions
• Lattice-Based Identification Schemes Secure Under Active Attacks
• Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party
• scientific article; zbMATH DE number 7746256 (Why is no real title available?)
• Efficient NIZKs from LWE via polynomial reconstruction and ``MPC in the head
• Quantum collision search for ternary LWE keys
• Super-quadratic quantum speed-ups and guessing many likely keys
• Diagonally dominant matrices for cryptography
• Chosen ciphertext attacks on lattice-based public key encryption and modern (non-quantum) cryptography in a quantum environment
• A new method of constructing a lattice basis and its applications to cryptanalyse short exponent RSA

This page was built for publication: New lattice based cryptographic constructions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581301)