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 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,{{cite book |last1=Cachin |first1=Christian |last2=Micali |first2=Silvio|last3=Stadler|first3=Markus|title=Advances in Cryptology — EUROCRYPT '99 |chapter=Computationally Private Information Retrieval with Polylogarithmic Communication |series=Lecture Notes in Computer Science |year=1999|publisher=Springer|volume= 1592|pages=402–414|doi=10.1007/3-540-48910-X_28|editor1-last=Stern |editor1-first=Jacques|isbn=978-3-540-65889-4 |s2cid=29690672 }} where it was used in a private information retrieval scheme.
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)
- 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)
References
{{reflist}}
{{Computational hardness assumptions}}
Category:Computational number theory