Předpoklad skrývání Phi - Phi-hiding assumption

The předpoklad phi-úkrytu nebo Φ -krytý předpoklad je předpoklad o obtížnosti hledání malého faktory z φ (m) kde m je číslo, jehož faktorizace je neznámý a φ je Eulerova totientová funkce. Zabezpečení mnoha moderních kryptosystémy pochází z vnímané obtížnosti určitých problémů. Od té doby Problém P vs. NP stále není vyřešen, kryptografové si nemohou být jisti, že existují výpočtově neřešitelné problémy. Kryptografové tak vytvářejí předpoklady o tom, jaké problémy jsou tvrdý. Obecně se věří, že pokud m je produktem dvou velkých připraví, pak výpočet φ (m) je v současné době výpočetně neproveditelné; tento předpoklad je vyžadován pro bezpečnost Kryptosystém RSA. Předpoklad Φ-úkrytu je silnější předpoklad, konkrétně pokud str₁ a str₂ jsou malá prvočísla, z nichž jedna dělí φ (m), tady není žádný polynomiální čas algoritmus, který dokáže rozlišit, která z prvočísel str₁ a str₂ dělí φ (m) s pravděpodobností významně vyšší než polovina.

Tento předpoklad byl poprvé uveden v dokumentu z roku 1999 Computationally Private Information Retrieval with Polylogarithmic Communication^[1], kde byl použit v a Načítání soukromých informací systém.

Aplikace

Předpoklad skrývání Phi našel uplatnění při konstrukci několika kryptografických primitiv. Mezi stavby patří:

• Výpočetně soukromé získávání informací s polylogaritmickou komunikací (1999)
• Efektivní soukromé nabídky a aukce s lhostejnou třetí stranou (1999)
• Načítání soukromých informací z jedné databáze s konstantní rychlostí komunikace (2005)
• Výměna klíčů s ověřeným heslem pomocí skrytých hladkých podskupin (2005)

Reference