強い漏洩耐性をもつ電子署名に対するモデルと方式

今年度は、帰着という暗号理論の土台としての安全性証明技術を研究し、その結果は査読付き国際会議EUROCRYPT 2018（暗号理論三大会議の一つ）に採録された（論文タイトル：Memory Lower Bounds of Reductions Revisited）。世の中の暗号要素技術の安全性は、基本的に帰着により証明されている。帰着によりある安全性を証明する場合、「安全性を破ることができる敵が存在すれば、仮定された計算問題を破ることができる敵も存在する」ということを示す必要がある。具体的にいうと、目標安全性を破ることができる敵にアクセスできる帰着アルゴリズムを構成し、構成されたアルゴリズムは、仮定された計算問題を破ることができることを証明できれば、目標安全性はその計算問題を基づいて成り立つと言える。ただし、現実世界で、仮定された計算問題も大きいメモリー量をもつ敵に対して成り立たないといけないので、証明された安全性は弱くなる。本研究では、”唯一性”を持つ署名方式とマルチユーザ暗号要素技術と、ほぼ全てのハッシュ関数のマルチチャレンジ安全性を広い範囲の計算問題を基づいて、帰着により証明する場合、構成された帰着アルゴリズムは、基本的に大きいメモリー量を使わないといけないことを証明した。この成果により、従来からに知られていた広い範囲の暗号要素技術についての安全性証明は、現実世界で、予想より弱い可能性が高いということが分かった。

今年度は、帰着という暗号理論の土台としての安全性証明技術を研究し、その結果は査読付き国際会議EUROCRYPT 2018（暗号理論三大会議の一つ）に採録された（論文タイトル：Memory Lower Bounds of Reductions Revisited）。世の中の暗号要素技術の安全性は、基本的に帰着により証明されている。帰着によりある安全性を証明する場合、「安全性を破ることができる敵が存在すれば、仮定された計算問題を破ることができる敵も存在する」ということを示す必要がある。具体的にいうと、目標安全性を破ることができる敵にアクセスできる帰着アルゴリズムを構成し、構成されたアルゴリズムは、仮定された計算問題を破ることができることを証明できれば、目標安全性はその計算問題を基づいて成り立つと言える。ただし、現実世界で、仮定された計算問題も大きいメモリー量をもつ敵に対して成り立たないといけないので、証明された安全性は弱くなる。本研究では、”唯一性”を持つ署名方式とマルチユーザ暗号要素技術と、ほぼ全てのハッシュ関数のマルチチャレンジ安全性を広い範囲の計算問題を基づいて、帰着により証明する場合、構成された帰着アルゴリズムは、基本的に大きいメモリー量を使わないといけないことを証明した。この成果により、従来からに知られていた広い範囲の暗号要素技術についての安全性証明は、現実世界で、予想より弱い可能性が高いということが分かった。