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 Computationally Private Information Retrieval with Polylogarithmic Communication,[1] 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:

References
  1. Cachin, Christian; Micali, Silvio; Stadler, Markus (1999). Stern, Jacques (ed.). "Computationally Private Information Retrieval with Polylogarithmic Communication". Lecture Notes in Computer Science. Springer. 1592: 402–414. doi:10.1007/3-540-48910-X. ISBN 978-3-540-65889-4. S2CID 29690672.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.