公開鍵暗号系の頑強性の定式化について

小森 康司 (0051040)

公開鍵暗号系の安全性に関する重要な性質として，頑強性と呼ばれるものがあ る．頑強性とは，復号鍵を知らない攻撃者が，与えられた暗号文 $y$ から 「$y$ の平文とは自明でない関係にある平文」の暗号文を作り出せないような 性質をいう．Bellare らは確率的チューリング機械の概念を用いることで，頑 強性の形式的な定義 (定式化という) NM-ATK を与えた．一方鈴木らは，頑強 性を「疎集合に対する頑強性」と「密集合に対する頑強性」に分類することを 提唱し，それぞれの定式化を与え，また，各種定式化の関係についても明らか にしている．しかし従来の研究はあくまでも形式的な枠組の中での議論が主体 であり，それらの結果を現実世界に還元して意味付けるような試みは十分行わ れていない．本研究では，各種の定式化やそこから導出される結果が，現実世 界においてどのような意味を持つのかを明らかにした．例えば，頑強性と NM-ATK を同一視すると，DES や AES 等の対称鍵暗号系も頑強性を有さないこ とになってしまうことを示した．これは暗号理論の世界における認識とは著し く異なるものであり，背理法的な議論より，NM-ATK は頑強性の定式化として 適切でないといえる．また，頑強性と暗号化関数の一方向性についても議論し, この方面からも NM-ATK の不自然さを明らかにした.