|
GGH Encryption Scheme
The Goldreich–Goldwasser–Halevi (GGH) lattice-based cryptosystem is an asymmetric cryptosystem based on lattices. There is also a GGH signature scheme. 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 GGH involves a ''private key'' and a ''pub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 are currently important candidates for 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. History In 1996, Miklós Ajtai introduced the first lattice-based cryptographic construction whose security could be based on the hardness of well-studied lattice problems, and Cynthia Dwork showed that a certain average-cas ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cryptosystem
In cryptography, a cryptosystem is a suite of cryptographic algorithms needed to implement a particular security service, such as confidentiality (encryption). Typically, a cryptosystem consists of three algorithms: one for key generation, one for encryption, and one for decryption. The term ''cipher'' (sometimes ''cypher'') is often used to refer to a pair of algorithms, one for encryption and one for decryption. Therefore, the term ''cryptosystem'' is most often used when the key generation algorithm is important. For this reason, the term ''cryptosystem'' is commonly used to refer to public key techniques; however both "cipher" and "cryptosystem" are used for symmetric key techniques. Formal definition Mathematically, a cryptosystem or encryption scheme can be defined as a tuple (\mathcal,\mathcal,\mathcal,\mathcal,\mathcal) with the following properties. # \mathcal is a set called the "plaintext space". Its elements are called plaintexts. # \mathcal is a set called th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Public-key Cryptography
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic algorithms based on mathematical problems termed one-way functions. Security of public-key cryptography depends on keeping the private key secret; the public key can be openly distributed without compromising security. In a public-key encryption system, anyone with a public key can encrypt a message, yielding a ciphertext, but only those who know the corresponding private key can decrypt the ciphertext to obtain the original message. For example, a journalist can publish the public key of an encryption key pair on a web site so that sources can send secret messages to the news organization in ciphertext. Only the journalist who knows the corresponding private key can decrypt the ciphertexts to obtain the sources' messages—an eavesdropp ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 regula ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
GGH Signature Scheme
The Goldreich-Goldwasser-Halevi (GGH) signature scheme is a digital signature scheme proposed in 1995 and published in 1997, based on solving the closest vector problem (CVP) in a lattice. The signer demonstrates knowledge of a good basis for the lattice by using it to solve CVP on a point representing the message; the verifier uses a bad basis for the same lattice to verify that the signature under consideration is actually a lattice point and is sufficiently close to the message point. The idea was not developed in detail in the original paper, which focussed more on the associated encryption algorithm. GGH signatures form the basis for the NTRUSign NTRUSign, also known as the NTRU Signature Algorithm, is an NTRU public-key cryptography digital signature algorithm based on the GGH signature scheme. The original version of NTRUSign was Polynomial Authentication and Signature Scheme (PASS), an ... signature algorithm. and Oded Regev had cryptanalyzed ( broken) the original GG ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lattice Problems
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 space (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 norm usuall ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Oded Goldreich
Oded Goldreich ( he, עודד גולדרייך; b. 1957) is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. His research interests lie within the theory of computation and are, specifically, the interplay of randomness and computation, the foundations of cryptography, and computational complexity theory. He won the Knuth Prize in 2017 and was selected in 2021 to receive the Israel Prize in mathematics. Biography Goldreich received a DSc in Computer Science at Technion in 1983 under Shimon Even. Goldreich has contributed to the development of pseudorandomness, zero knowledge proofs, secure function evaluation, property testing,Oded Goldreich, Shafi Goldwasser, and Dana Ron. 1998 Property Testing and its connection to Learning and Approximation. ''Journal of the ACM'', pages 653-750. and other areas in cryptography and computational complexity. Goldreich has also authored several books including: ''Fou ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Shafi Goldwasser
en, Shafrira Goldwasser , name = Shafi Goldwasser , image = Shafi Goldwasser.JPG , caption = Shafi Goldwasser in 2010 , birth_place = New York City, New York, U.S. , birth_date = , death_date = , death_place = , nationality = Israeli American , field = Computer science, cryptography , work_institution = , alma_mater = , doctoral_advisor = Manuel Blum , thesis_title = Probabilistic Encryption: Theory and Applications , thesis_url = http://search.proquest.com/docview/303337869 , thesis_year = 1984 , doctoral_students = , known_for = , prizes = , website = Shafrira Goldwasser ( he, שפרירה גולדווסר; born 1959) is an Israeli-American computer scientist and winner of the Turing Award in 2012. She is the RSA Professor of Electrical Engineering and Computer Science at MIT, a professor of mathematical sciences at th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Shai Halevi
Shai Halevi ( he, שי הלוי; born 1966) is a computer scientist who works on cryptography research at Algorand Foundation, a blockchain startup founded by Silvio Micali. Born in Israel in 1966, Halevi received a B.A. and M.Sc. in computer science from the Technion, Israel Institute of Technology in 1991 and 1993. He received his Ph.D. in computer science from MIT in 1997, and then joined IBM's Thomas J. Watson Research Center, where he was a principal research staff member until 2019. Since 2019, he has been a research fellow at Algorand Foundation. Research Shai Halevi's research interests are in cryptography and security. He has published numerous original technical research papers, three of which were awarded the IBM Pat Goldberg memorial best-paper award (in 2004, 2012, and 2013). Notable contributions by Shai Halevi include: * Obfuscation. Halevi is a co-inventor of the first candidate general-purpose indistinguishability obfuscation schemes, with security based on a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Trapdoor Function
In theoretical computer science and cryptography, a trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor". Trapdoor functions are a special case of one-way functions and are widely used in public-key cryptography. In mathematical terms, if ''f'' is a trapdoor function, then there exists some secret information ''t'', such that given ''f''(''x'') and ''t'', it is easy to compute ''x''. Consider a padlock and its key. It is trivial to change the padlock from open to closed without using the key, by pushing the shackle into the lock mechanism. Opening the padlock easily, however, requires the key to be used. Here the key ''t'' is the trapdoor and the padlock is the trapdoor function. An example of a simple mathematical trapdoor is "6895601 is the product of two prime numbers. What are those numbers?" A typical " brute-force" solution wou ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lattice Reduction
In mathematics, the goal of lattice basis reduction is to find a basis with short, nearly orthogonal vectors when given an integer lattice basis as input. This is realized using different algorithms, whose running time is usually at least exponential in the dimension of the lattice. Nearly orthogonal One measure of ''nearly orthogonal'' is the orthogonality defect. This compares the product of the lengths of the basis vectors with the volume of the parallelepiped they define. For perfectly orthogonal basis vectors, these quantities would be the same. Any particular basis of n vectors may be represented by a matrix B, whose columns are the basis vectors b_i, i = 1, \ldots, n. In the fully dimensional case where the number of basis vectors is equal to the dimension of the space they occupy, this matrix is square, and the volume of the fundamental parallelepiped is simply the absolute value of the determinant of this matrix \det(B). If the number of vectors is less than the dimension ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Oded Regev (computer Scientist)
Oded Regev (Hebrew: עודד רגב) 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 theoretical side, LWE has serv ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
