IL-003
A Public-key Encryption Scheme based on Non-linear Indeterminate Equations

○秋山浩一郎（東芝）・後藤泰宏（北海道教育大）・奥村伸也（阪大）・高木　剛・縫田光司（東大）・花岡悟一郎（産総研）

RSA暗号など現行の公開鍵暗号は大きな数の計算が可能な量子計算機ができると短時間で解読されてしまうことが知られている。量子計算機の開発はここ数年で急速に進んでおり、これに伴い米国国立標準技術研究所（ＮＩＳＴ）が量子計算機にも強い公開鍵暗号（耐量子公開鍵暗号）の標準化を開始するなど、耐量子公開鍵暗号に注目が集まっている。本論文に示す公開鍵暗号(Giophantus(TM))は量子計算機でも解くことが困難な不定方程式の求解問題に安全性の根拠をおく公開鍵暗号で、公開鍵に暗号解読に強い非線形な構造を持つという特長がある。本論文ではアルゴリズムの概要と安全性の理論解析並びに安全性を担保できるパラメータを具体的に示している。