Lattice-based Cryptography
   HOME





Lattice-based Cryptography
Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions support important standards of post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently. In 2024 NIST announced the Module-Lattice-Based Digital Signature Standard for post-quantum cryptography. History In 1996, Miklós Ajtai introduced the first lattice-based cryptographic construction whose security could be ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Cryptographic Primitive
Cryptographic primitives are well-established, low-level cryptography, cryptographic algorithms that are frequently used to build cryptographic protocols for computer security systems. These routines include, but are not limited to, one-way hash functions and cipher, encryption functions. Rationale When creating cryptosystem, cryptographic systems, system designer, designers use cryptographic primitives as their most basic building blocks. Because of this, cryptographic primitives are designed to do one very specific task in a precisely defined and highly reliable fashion. Since cryptographic primitives are used as building blocks, they must be very reliable, i.e. perform according to their specification. For example, if an encryption routine claims to be only breakable with number of computer operations, and it is broken with significantly fewer than operations, then that cryptographic primitive has failed. If a cryptographic primitive is found to fail, almost every protocol t ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Jill Pipher
Jill Catherine Pipher (born December 14, 1955, in Harrisburg, Pennsylvania) is an American mathematician. She served as president of the American Mathematical Society (AMS, 2019–2020). and president of the Association for Women in Mathematics (AWM, 2011–2013). She was the first director of the Institute for Computational and Experimental Research in Mathematics (ICERM, 2011–2016), an NSF-funded mathematics institute based in Providence, Rhode Island. Contributions Pipher's research areas include harmonic analysis, Fourier analysis, partial differential equations, and cryptography. She has published more than 60 research articles and has coauthored with Jeffrey Hoffstein and Joseph Silverman a textbook titled ''An Introduction to Mathematical Cryptography''. Education and career Pipher is currently the Elisha Benjamin Andrews Professor of Mathematics at Brown University. She received a B.A. from the University of California, Los Angeles in 1979 and a PhD from UCLA in 1 ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


GGH Encryption Scheme
The Goldreich–Goldwasser–Halevi (GGH) lattice-based cryptosystem is a broken asymmetric cryptosystem based on lattices. There is also a GGH signature scheme which hasn't been broken as of 2024. The Goldreich–Goldwasser–Halevi (GGH) cryptosystem makes use of the fact that the closest vector problem can be a hard problem. This system was published in 1997 by Oded Goldreich, Shafi Goldwasser, and Shai Halevi, and uses a trapdoor one-way function which relies on the difficulty of lattice reduction. The idea included in this trapdoor function is that, given any basis for a lattice, it is easy to generate a vector which is close to a lattice point, for example taking a lattice point and adding a small error vector. But to return from this erroneous vector to the original lattice point a special basis is needed. The GGH encryption scheme was cryptanalyzed (broken) in 1999 by . Nguyen and Oded Regev had cryptanalyzed the related GGH signature scheme in 2006. Operation ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Shortest Vector Problem
In computer science, lattice problems are a class of optimization problems related to mathematical objects called '' lattices''. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: lattice problems are an example of NP-hard problems which have been shown to be average-case hard, providing a test case for the security of cryptographic algorithms. In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes. The use of worst-case hardness in such schemes makes them among the very few schemes that are very likely secure even against quantum computers. For applications in such cryptosystems, lattices over vector spaces (often \mathbb^n) or free modules (often \mathbb^n) are generally considered. For all the problems below, assume that we are given (in addition to other more specific inputs) a basis for the vector space ''V'' and a norm ''N''. The nor ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Standard Basis
In mathematics, the standard basis (also called natural basis or canonical basis) of a coordinate vector space (such as \mathbb^n or \mathbb^n) is the set of vectors, each of whose components are all zero, except one that equals 1. For example, in the case of the Euclidean plane \mathbb^2 formed by the pairs of real numbers, the standard basis is formed by the vectors \mathbf_x = (1,0),\quad \mathbf_y = (0,1). Similarly, the standard basis for the three-dimensional space \mathbb^3 is formed by vectors \mathbf_x = (1,0,0),\quad \mathbf_y = (0,1,0),\quad \mathbf_z=(0,0,1). Here the vector e''x'' points in the ''x'' direction, the vector e''y'' points in the ''y'' direction, and the vector e''z'' points in the ''z'' direction. There are several common notations for standard-basis vectors, including , , , and . These vectors are sometimes written with a hat to emphasize their status as unit vectors (standard unit vectors). These vectors are a basis in the sense that any othe ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Basis (algebra)
In mathematics, a Set (mathematics), set of elements of a vector space is called a basis (: bases) if every element of can be written in a unique way as a finite linear combination of elements of . The coefficients of this linear combination are referred to as components or coordinates of the vector with respect to . The elements of a basis are called . Equivalently, a set is a basis if its elements are linearly independent and every element of is a linear combination of elements of . In other words, a basis is a linearly independent spanning set. A vector space can have several bases; however all the bases have the same number of elements, called the dimension (vector space), dimension of the vector space. This article deals mainly with finite-dimensional vector spaces. However, many of the principles are also valid for infinite-dimensional vector spaces. Basis vectors find applications in the study of crystal structures and frame of reference, frames of reference. De ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Lattice (group)
In geometry and group theory, a lattice in the real coordinate space \mathbb^n is an infinite set of points in this space with the properties that coordinate-wise addition or subtraction of two points in the lattice produces another lattice point, that the lattice points are all separated by some minimum distance, and that every point in the space is within some maximum distance of a lattice point. Closure under addition and subtraction means that a lattice must be a subgroup of the additive group of the points in the space, and the requirements of minimum and maximum distance can be summarized by saying that a lattice is a Delone set. More abstractly, a lattice can be described as a free abelian group of dimension n which spans the vector space \mathbb^n. For any basis of \mathbb^n, the subgroup of all linear combinations with integer coefficients of the basis vectors forms a lattice, and every lattice can be formed from a basis in this way. A lattice may be viewed as a re ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Linear Algebra
Linear algebra is the branch of mathematics concerning linear equations such as :a_1x_1+\cdots +a_nx_n=b, linear maps such as :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrix (mathematics), matrices. Linear algebra is central to almost all areas of mathematics. For instance, linear algebra is fundamental in modern presentations of geometry, including for defining basic objects such as line (geometry), lines, plane (geometry), planes and rotation (mathematics), rotations. Also, functional analysis, a branch of mathematical analysis, may be viewed as the application of linear algebra to Space of functions, function spaces. Linear algebra is also used in most sciences and fields of engineering because it allows mathematical model, modeling many natural phenomena, and computing efficiently with such models. For nonlinear systems, which cannot be modeled with linear algebra, it is often used for dealing with first-order a ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Homomorphic Encryption
Homomorphic encryption is a form of encryption that allows computations to be performed on encrypted data without first having to decrypt it. The resulting computations are left in an encrypted form which, when decrypted, result in an output that is identical to that of the operations performed on the unencrypted data. While homomorphic encryption does not protect against side-channel attacks that observe behavior, it can be used for privacy-preserving outsourced storage and computation. This allows data to be encrypted and outsourced to commercial cloud environments for processing, all while encrypted. As an example of a practical application of homomorphic encryption: encrypted photographs can be scanned for points of interest, without revealing the contents of a photo. However, observation of side-channels can see a photograph being sent to a point-of-interest lookup service, revealing the fact that photographs were taken. Thus, homomorphic encryption eliminates the need ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Craig Gentry (computer Scientist)
Craig Gentry (born 1973) is an American computer scientist working as CTO of TripleBlind. He is best known for his work in cryptography, specifically fully homomorphic encryption.Craig GentryFully Homomorphic Encryption Using Ideal Lattices In ''the 41st ACM Symposium on Theory of Computing (STOC)'', 2009. Education In 1993, while studying at Duke University, he became a Putnam Fellow. In 2009, his dissertation, in which he constructed the first Fully Homomorphic Encryption scheme, won the ACM Doctoral Dissertation Award. Career In 2010, he won the ACM Grace Murray Hopper Award for the same work. In 2014, he won a MacArthur Fellowship. Previously, he was a research scientist at the Algorand Foundation and IBM Thomas J. Watson Research Center. In 2022, he won the Gödel Prize The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Learning With Errors
In cryptography, learning with errors (LWE) is a mathematical problem that is widely used to create secure encryption algorithms. It is based on the idea of representing secret information as a set of equations with errors. In other words, LWE is a way to hide the value of a secret by introducing noise to it. In more technical terms, it refers to the computational problem of inferring a linear n-ary function f over a finite Ring (mathematics), ring from given samples y_i = f(\mathbf_i) some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus to be useful in cryptography. More precisely, the LWE problem is defined as follows. Let \mathbb_q denote the ring of integers Modular arithmetic, modulo q and let \mathbb_q^n denote the set of n-Vector (mathematics and physics), vectors over \mathbb_q . There exists a certain unknown linear function f:\mathbb_q^n \rightarrow \mathbb_q, and the input to the LWE problem is a sample of pairs (\mathbf,y), wher ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Oded Regev (computer Scientist)
Oded Regev (Hebrew: עודד רגב; born 1980 or 1979) is an Israeli-American theoretical computer scientist and mathematician. He is a professor of computer science at the Courant institute at New York University. He is best known for his work in lattice-based cryptography, and in particular for introducing the learning with errors problem. Biography Oded Regev earned his B.Sc. in 1995, M.Sc. in 1997, and Ph.D. in 2001, all from Tel Aviv University. He completed his Ph.D. at the age of 21, advised by Yossi Azar, with a thesis titled "Scheduling and Load Balancing." He held faculty positions at Tel Aviv University and the École Normale Supérieure before joining the Courant institute. Work Regev has done extensive work on lattices. He is best known for introducing the learning with errors problem (LWE), for which he won the 2018 Gödel Prize. As the citation reads: Regev’s work has ushered in a revolution in cryptography, in both theory and practice. On the theoretic ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]