Phi-hiding assumption
From Wikipedia, the free 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 cryptosystems 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 a paper by Cachin Micali and Stadler [1] in 1999.
[edit] 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)
