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.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

  • العربيةفاي الاختباء الافتراضي
  • EnglishPhi-hiding assumption

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 1 and p 2 are small primes exactly one of which divides φ(m), there is no polynomial-time algorithm which can distinguish which of the primes p 1 and p 2 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, 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: 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)

Text derived from https://en.wikipedia.org/w/index.php?oldid=1276235035 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001276235035 · captured 2025-02-17 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Phi-hiding assumption”, snapshot enwiki-001276235035. https://encyclopegia.org/a/phi-hiding-assumption

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.