The security of many modern cryptosystems comes from the perceived difficulty of certain problems.
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 titled Computationally Private Information Retrieval with Polylogarithmic Communication,[1] where it was used in a private information retrieval scheme.
The phi-hiding assumption has found applications in the construction of a few cryptographic primitives.