Thephi-hiding assumption orΦ-hiding assumption is an assumption about the difficulty of finding smallfactors of φ(m) wherem is a number whosefactorization is unknown, and φ isEuler's totient function. The security of many moderncryptosystems comes from the perceived difficulty of certain problems. SinceP vs. NP problem is still unresolved, cryptographers cannot be sure computationally intractable problems exist. Cryptographers thus make assumptions as to which problems arehard. It is commonly believed that ifm is the product of two largeprimes, then calculating φ(m) is currently computationally infeasible; this assumption is required for the security of theRSA cryptosystem. The Φ-hiding assumption is a stronger assumption, namely that ifp₁ andp₂ are small primes exactly one of which divides φ(m), there is nopolynomial-time algorithm which can distinguish which of the primesp₁ andp₂ divides φ(m) with probability significantly greater than one-half.

This assumption was first stated in the 1999 paper titledComputationally Private Information Retrieval with Polylogarithmic Communication,^[1] where it was used in aprivate information retrieval scheme.

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)

• Computational number theory
• Computational hardness assumptions
• Theory of cryptography