ナッカシェ・シュテルン・ナップザック暗号

ナッカッシュ・シュテルン・ナップザック暗号は、1997年にデイヴィッド・ナッカッシュとジャック・シュテルンによって開発された、非典型的な公開鍵暗号です。この暗号システムは決定論的であるため、意味的に安全ではありません。 現在まで破られていませんが、このシステムは証明可能な安全性も欠いています

システムの概要

このシステムは、ナップサック問題の一種に基づいています。具体的には、整数c、n、p、v ₀、…、v _nが与えられたとき、次のベクトルを求めるという問題です ${\displaystyle x\in \{0,1\}^{n}}$

${\displaystyle c\equiv \prod _{i=0}^{n}v_{i}^{x_{i}}\mod p}$

ここでの考え方は、v _{i が}互いに素で、法pよりもはるかに小さい場合、この問題は簡単に解けるというものです。この観察によって復号が可能になります。

鍵生成

公開鍵と秘密鍵のペアを生成するには

• 大きな素数係数pを選びます
• 正の整数nを選び、iが 0 からnまでの場合、p ₀ = 2 から始めて、 となるi番目の素数にp _iを設定します。${\displaystyle \prod _{i=0}^{n}p_{i}$
• gcd( p -1, s )=1となるような秘密の整数s < p -1を選択します。
• セット。${\displaystyle v_{i}={\sqrt[{s}]{p_{i}}}\mod p}$

公開鍵はp、n、v ₀、...、v _nです。秘密鍵はsです。

暗号化

nビット長のメッセージmを暗号化するには、次のように計算します

${\displaystyle c=\prod _{i=0}^{n}v_{i}^{m_{i}}\mod p}$

ここで、m _iはメッセージmのi番目のビットです。

復号

メッセージcを復号化するには、計算します

${\displaystyle m=\sum _{i=0}^{n}{\frac {2^{i}}{p_{i}-1}}\times \left(\gcd(p_{i},c^{s}\mod p)-1\right)}$

これは分数であるため機能します

${\displaystyle {\frac {\gcd(p_{i},c^{s}\mod p)-1}{p_{i}-1}}}$

p _{i が}c ^s mod pを割り切るかどうかによって 0 または 1 になります。

安全性

トラップドア関数の安全性は、次の乗法ナップサック問題の難しさに依存しています。与えられたものを復元します。マークル・ヘルマン暗号などの加法ナップサックベースの暗号システムとは異なり、ユークリッド格子縮約のような手法はこの問題には適用されません $${\displaystyle c=\prod _{i=0}^{n}v_{i}^{m_{i}}{\pmod {p}},}$$ ${\displaystyle m_{i}}$

最もよく知られている一般的な攻撃は、離散対数問題を解いてからを復元することであり、これは古典コンピュータでは困難であると考えられています。しかし、ショアの量子アルゴリズムはこの問題を効率的に解決します。さらに、現在（2023年）では、ナカッシュ＝シュテルン・ナップサックが離散対数問題に帰着するという証明はありません。 ${\displaystyle s}$ ${\displaystyle p,p_{i},v_{i}}$

最もよく知られている特定の攻撃（2018年）は、メッセージのハミング重みが非常に低いと仮定して、トラップドアを知らずに関数を部分的に反転する誕生日定理を使用するものである。^{[ 1 ]}

参考文献

1. Anastasiadis, M.; Chatzis, N.; Draziotis, KA (2018年10月). 「ナカチェ・シュテルン・ナップザック暗号システムに対する誕生日型攻撃」. Information Processing Letters . 138 : 39–43 . doi : 10.1016/ j.ipl.2018.06.002

• 原著論文
• 最近の帯域幅の改善

参照

• マークル・ヘルマン・ナップザック暗号
• グラハム・シャミア・ナップザック暗号