Information about Trapdoor Permutation
A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor". Trapdoor functions are widely used in cryptography.
In mathematical terms, if f is a trapdoor function there exists some secret information y, such that given f(x) and y it is easy to compute x. Consider taking an engine apart. It would not be very easy to put it together again unless of course you had the assembly instructions. These instructions would be the trapdoor that allow you to return the engine to its original state. A mathematical example would be the multiplication of two large prime numbers. Finding and verifying two large primes is easy, as is their multiplication. But factoring the resultant product can be very difficult.
Trapdoor functions came to prominence in cryptography in the mid-1970s with the publication of asymmetric encryption techniques by Diffie, Hellman, and Merkle. Indeed, Diffie and Hellman first coined the term (Diffie and Hellman, 1976). Several function classes have been proposed, and it soon became obvious that trapdoor functions are harder to find than was initially thought. For example, an early suggestion was to use schemes based on the subset sum problem. This turned out -- rather quickly -- to be unsuitable.
As of 2004, the best known trapdoor function (family) candidates are the RSA and Rabin families of functions. Both are written as exponentiation modulo a composite number, and both are related to the problem of prime factorisation.
Functions related to the hardness of the discrete logarithm problem (either modulo a prime or in a group defined over an elliptic curve) are not known to be trapdoor functions, because there is no known "trapdoor" information about the group that enables the efficient computation of discrete logs. However, the discrete logarithm problem can be used as the basis for a trapdoor when the related problems called the computational Diffie-Hellman problem (CDH) and/or its decisional variant are used. The semantically secure version of the ElGamal Cryptosystem relies on the Decision Diffie-Hellman problem (DDH). The Digital Signature Algorithm is based on CDH in a prime order subgroup.
A trapdoor in cryptography has the very specific aforementioned meaning and is not to be confused with a backdoor (these are frequently used interchangeably and this is incorrect). A backdoor is a deliberate mechanism that is added to a cryptographic algorithm (e.g., a key pair generation algorithm, digital signing algorithm, etc.) or operating system, for example, that permits one or more unauthorized parties to bypass or subvert the security of the system in some fashion. A one-way function is a function that is easy to compute but "hard to invert" (in the sense defined below). "Easy to compute" means that some algorithm can compute the function in polynomial time (in the input size).
..... Click the link for more information.
In mathematical terms, if f is a trapdoor function there exists some secret information y, such that given f(x) and y it is easy to compute x. Consider taking an engine apart. It would not be very easy to put it together again unless of course you had the assembly instructions. These instructions would be the trapdoor that allow you to return the engine to its original state. A mathematical example would be the multiplication of two large prime numbers. Finding and verifying two large primes is easy, as is their multiplication. But factoring the resultant product can be very difficult.
Trapdoor functions came to prominence in cryptography in the mid-1970s with the publication of asymmetric encryption techniques by Diffie, Hellman, and Merkle. Indeed, Diffie and Hellman first coined the term (Diffie and Hellman, 1976). Several function classes have been proposed, and it soon became obvious that trapdoor functions are harder to find than was initially thought. For example, an early suggestion was to use schemes based on the subset sum problem. This turned out -- rather quickly -- to be unsuitable.
As of 2004, the best known trapdoor function (family) candidates are the RSA and Rabin families of functions. Both are written as exponentiation modulo a composite number, and both are related to the problem of prime factorisation.
Functions related to the hardness of the discrete logarithm problem (either modulo a prime or in a group defined over an elliptic curve) are not known to be trapdoor functions, because there is no known "trapdoor" information about the group that enables the efficient computation of discrete logs. However, the discrete logarithm problem can be used as the basis for a trapdoor when the related problems called the computational Diffie-Hellman problem (CDH) and/or its decisional variant are used. The semantically secure version of the ElGamal Cryptosystem relies on the Decision Diffie-Hellman problem (DDH). The Digital Signature Algorithm is based on CDH in a prime order subgroup.
A trapdoor in cryptography has the very specific aforementioned meaning and is not to be confused with a backdoor (these are frequently used interchangeably and this is incorrect). A backdoor is a deliberate mechanism that is added to a cryptographic algorithm (e.g., a key pair generation algorithm, digital signing algorithm, etc.) or operating system, for example, that permits one or more unauthorized parties to bypass or subvert the security of the system in some fashion.
See also
References
- W. Diffie and M. Hellman. New Directions in Cryptography. IEEE Trans. Info. Theory 22(6), pp644–654 (1976). PDF version of the paper
function expresses dependence between two quantities, one of which is given (the independent variable, argument of the function, or its "input") and the other produced (the dependent variable, value of the function, or "output").
..... Click the link for more information.
..... Click the link for more information.
inverse function for ƒ, denoted by ƒ−1, is a function in the opposite direction, from B to A, with the property that a round trip (a composition) returns each element to itself.
..... Click the link for more information.
..... Click the link for more information.
Cryptography (or cryptology; derived from Greek κρυπτός kryptós "hidden," and the verb γράφω gráfo "write" or λεγειν legein
..... Click the link for more information.
..... Click the link for more information.
In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. An infinitude of prime numbers exists, as demonstrated by Euclid in about 300 BC.
..... Click the link for more information.
..... Click the link for more information.
Centuries: 19th century - 20th century - 21st century
1940s 1950s 1960s - 1970s - 1980s 1990s 2000s
1970 1971 1972 1973 1974
1975 1976 1977 1978 1979
- -
- The 1970s decade refers to the years from 1970 to 1979, also called
..... Click the link for more information.
1940s 1950s 1960s - 1970s - 1980s 1990s 2000s
1970 1971 1972 1973 1974
1975 1976 1977 1978 1979
- -
- The 1970s decade refers to the years from 1970 to 1979, also called
..... Click the link for more information.
Public-key cryptography, also known as asymmetric cryptography, is a form of cryptography in which a user has a pair of cryptographic keys - a public key and a private key. The private key is kept secret, while the public key may be widely distributed.
..... Click the link for more information.
..... Click the link for more information.
Bailey Whitfield 'Whit' Diffie (born June 5 1944) is a US cryptographer and one of the pioneers of public-key cryptography.
He received a Bachelor of Science degree in mathematics from the Massachusetts Institute of Technology in 1965.
..... Click the link for more information.
He received a Bachelor of Science degree in mathematics from the Massachusetts Institute of Technology in 1965.
..... Click the link for more information.
Martin Edward Hellman (born October 2, 1945) is a cryptologist, famous for his invention of public key cryptography in cooperation with Whitfield Diffie and Ralph Merkle.
Hellman graduated from the Bronx High School of Science.
..... Click the link for more information.
Hellman graduated from the Bronx High School of Science.
..... Click the link for more information.
Ralph Merkle
Born January 2 1952
Citizenship American
Nationality American
..... Click the link for more information.
Born January 2 1952
Citizenship American
Nationality American
..... Click the link for more information.
The subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set of integers, does the sum of some non-empty subset equal exactly zero? For example, given the set , the answer is YES because the subset sums to zero.
..... Click the link for more information.
..... Click the link for more information.
20th century - 21st century - 22nd century
1970s 1980s 1990s - 2000s - 2010s 2020s 2030s
2001 2002 2003 - 2004 - 2005 2006 2007
2004 by topic:
News by month
Jan - Feb - Mar - Apr - May - Jun
..... Click the link for more information.
1970s 1980s 1990s - 2000s - 2010s 2020s 2030s
2001 2002 2003 - 2004 - 2005 2006 2007
2004 by topic:
News by month
Jan - Feb - Mar - Apr - May - Jun
..... Click the link for more information.
RSA is an algorithm for public-key cryptography. It was the first algorithm known to be suitable for signing as well as encryption, and one of the first great advances in public key cryptography.
..... Click the link for more information.
..... Click the link for more information.
The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of factorization. However the Rabin cryptosystem has the advantage that the problem on which it relies has been proved to be as hard as integer
..... Click the link for more information.
..... Click the link for more information.
integer factorization is the process of breaking down a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer.
..... Click the link for more information.
..... Click the link for more information.
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. The problem of computing discrete logarithms is a sort of sibling to the problem of integer factorization, in that both problems are
..... Click the link for more information.
..... Click the link for more information.
Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz[1] and Victor S.
..... Click the link for more information.
..... Click the link for more information.
The Diffie-Hellman problem (DHP) is the name of a specific problem in cryptography which was first proposed by Whitfield Diffie and Martin Hellman. The DHP is a problem that is assumed to be difficult to do, hence some cryptography schemes are variants of the problem.
..... Click the link for more information.
..... Click the link for more information.
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie-Hellman key agreement. It was described by Taher Elgamal in 1984[1].
..... Click the link for more information.
..... Click the link for more information.
The Diffie-Hellman problem (DHP) is the name of a specific problem in cryptography which was first proposed by Whitfield Diffie and Martin Hellman. The DHP is a problem that is assumed to be difficult to do, hence some cryptography schemes are variants of the problem.
..... Click the link for more information.
..... Click the link for more information.
The Digital Signature Algorithm (DSA) is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature Standard (DSS)
..... Click the link for more information.
..... Click the link for more information.
A backdoor in a computer system (or cryptosystem or algorithm) is a method of bypassing normal authentication, securing remote access to a computer, obtaining covert access to plaintext, and so on, while attempting to remain undetected.
..... Click the link for more information.
..... Click the link for more information.
Do one-way functions exist?
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
