Fractal Analysis for Subset Sum Problems and its Applications to Cryptography

点击翻译按钮获取中文摘要

本年度も引き続き、ナップザック暗号の安全性評価の基礎となる部分和問題の求解困難性、特に、低密度攻撃に関する数学的研究を推し進めた。低密度攻撃は部分和問題の解を格子ベクトルに対応させ、最短ベクトル問題などの格子問題に対応させて解くことである。昨年度までに組合せ論（加法的組合せ論や極値組合せ論など）を意識し、部分和問題の解に対応する格子ベクトルをこれより短い格子ベクトルでカモフラージュするために必要な条件をヒューリスティックとして与えた。密度がより大きい場合の低密度攻撃による攻撃可能範囲が広がった。ただし、攻撃の計算時間は多項式時間とは限らず、効率的ではない可能性があることに注意する。これを量子公開鍵暗号として有名なOTU暗号に適用したところ低密度攻撃に耐性のある構成方法がないことがわかった。本年度はこの結果を国際会議CECC2021で発表を行った。この結果は学術雑誌に投稿中で査読結果待ちである。この結果に至るまでには1990年のCameronとErdosによる組合せ論的整数論の論文が参考になった。この論文では様々な特定性質を持った正の整数の集合の個数評価がHausdorff次元というフラクタル次元で特徴付けられることが記されている。このような個数評価はナップザック暗号の公開鍵の個数評価に直結し得る。この論文の紹介とCECC2021で発表した内容は第4回金沢暗号理論勉強会でも発表を行った。ナップザック暗号が安全となるための低密度攻撃の真の限界は純粋数学を意識してはじめて理解されるものと研究代表者は予想している。