Phi-hiding assumption
Encyclopedia
The phi-hiding assumption or Φ-hiding assumption is an assumption about the difficulty of finding small factors
of φ(m) where m is a number whose factorization
is unknown, and φ is Euler's totient function
. The security of many modern cryptosystem
s comes from the perceived difficulty of certain problems. Since P vs. NP problem is still unresolved, cryptographers cannot be sure computationally intractable problems exist. Cryptographers thus make assumptions as to which problems are hard. It is commonly believed that if m is the product of two large primes
, then calculating φ(m) is currently computationally infeasible, this assumption is required for the security of the RSA Cryptosystem. The Φ-Hiding assumption is a stronger assumption, namely that if p1 and p2 are small primes exactly one of which divides φ(m), there is no polynomial-time algorithm which can distinguish which of the primes p1 and p2 divides φ(m) with probability significantly greater than one-half.
This assumption was first stated in the 1999 paper Computationally Private Information Retrieval with Polylogarithmic Communication.
Factorization
In mathematics, factorization or factoring is the decomposition of an object into a product of other objects, or factors, which when multiplied together give the original...
of φ(m) where m is a number whose factorization
Factorization
In mathematics, factorization or factoring is the decomposition of an object into a product of other objects, or factors, which when multiplied together give the original...
is unknown, and φ is Euler's totient function
Euler's totient function
In number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...
. The security of many modern cryptosystem
Cryptosystem
There are two different meanings of the word cryptosystem. One is used by the cryptographic community, while the other is the meaning understood by the public.- General meaning :...
s comes from the perceived difficulty of certain problems. Since P vs. NP problem is still unresolved, cryptographers cannot be sure computationally intractable problems exist. Cryptographers thus make assumptions as to which problems are hard. It is commonly believed that if m is the product of two large primes
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
, then calculating φ(m) is currently computationally infeasible, this assumption is required for the security of the RSA Cryptosystem. The Φ-Hiding assumption is a stronger assumption, namely that if p1 and p2 are small primes exactly one of which divides φ(m), there is no polynomial-time algorithm which can distinguish which of the primes p1 and p2 divides φ(m) with probability significantly greater than one-half.
This assumption was first stated in the 1999 paper Computationally Private Information Retrieval with Polylogarithmic Communication.
Applications
The Phi-hiding assumption has found applications in the construction of a few cryptographic primitives. Some of the constructions include:- Computationally Private Information Retrieval with Polylogarithmic Communication (1999)
- Efficient Private Bidding and Auctions with an Oblivious Third Party (1999)
- Single-Database Private Information Retrieval with Constant Communication Rate (2005)
- Password authenticated key exchange using hidden smooth subgroups (2005)