Phi-hiding assumption

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 "p"₁ and "p"₂ are small primes exactly one of which divides φ("m"), there is no polynomial-time algorithm which can distinguish which of the primes "p"₁ and "p"₂ divides φ("m") with probability significantly greater than one-half.

This assumption was first stated in a paper by Cachin Micali and Stadler [http://citeseer.ist.psu.edu/cachin99computationally.html] in 1999.

Applications

The Phi-hiding assumption has found applications in the construction of a few cryptographic primitives. Some of the constructions include:
* [http://citeseer.ist.psu.edu/cachin99computationally.html Computationally Private Information Retrieval with Polylogarithmic Communication] (1999)
* [http://citeseer.ist.psu.edu/cachin99efficient.html Efficient Private Bidding and Auctions with an Oblivious Third Party] (1999)
* [http://www.springerlink.com/content/80959djt41b8l6rc/ Single-Database Private Information Retrieval with Constant Communication Rate] (2005)
* [http://portal.acm.org/citation.cfm?id=1102160&dl=acm&coll=&CFID=15151515&CFTOKEN=6184618 Password authenticated key exchange using hidden smooth subgroups] (2005)

ee also

* computational hardness assumptions