ファイ隠蔽仮定

ファイ隠蔽仮定またはΦ 隠蔽仮定は、 φ( m )の小さな因数を見つけることの難しさに関する仮定である。ここで、 mは因数分解が不明な数であり、 φ はオイラーのトーティエント関数である。多くの現代の暗号システムのセキュリティは、特定の問題の困難さから来ている。P 対 NP 問題はまだ解決されていないため、暗号学者は計算上解決不可能な問題が存在することを確信できない。そのため、暗号学者はどの問題が難しいかについて仮定を立てる。 mが 2 つの大きな素数の積である場合、 φ( m ) を計算することは現在計算上不可能であると一般に考えられており、この仮定はRSA 暗号システムのセキュリティに必須である。 Φ-Hiding仮定はより強い仮定であり、すなわち、p ₁とp ₂が小さな素数であり、そのうちの1つが φ( m ) を割り切る場合、素数p ₁とp _{2のどちらが φ(} m )を割り切るかを半分よりも大幅に高い確率で 区別できる多項式時間アルゴリズムは存在しないという仮定である。

この仮定は、1999年の論文「Computationally Private Information Retrieval with Polylogarithmic Communication」^{[1]で初めて述べられ、}プライベート情報検索スキームで使用されました。

Phi 隠蔽仮定は、いくつかの暗号プリミティブの構築に応用されています。その構築には次のようなものがあります。

• 多重対数通信による計算上プライベートな情報検索 (1999)
• 第三者の介入を気にしない効率的なプライベート入札とオークション (1999)
• 一定通信速度での単一データベースプライベート情報検索 (2005)
• 隠れた滑らかなサブグループを使用したパスワード認証鍵交換 (2005)