峰田 敏行

デジタル社会の進展に伴い，データの正当性を保証する技術の重要性が高まっている.特にブロックチェーンや匿名認証技術において，膨大なデータ集合を効率的に検証する手法は不可欠である.この基盤となる技術が暗号学的アキュミュレータである.これは大規模なデータ集合を短い値に圧縮し，特定の要素が集合に含まれることを効率的に証明する.アキュミュレータでは要素の追加や削除が頻繁に行われるため，ある要素が集合に含まれていないことを示す非メンバーシップ証明の機能も必要となる.このように，要素の追加と削除が行われる方式は動的アキュミュレータ，所属と非所属の両方を証明できる方式はユニバーサルアキュミュレータと呼ばれる.しかし，現在主流の方式は RSA 仮定や楕円曲線上の離散対数問題などに基づいており，量子計算機によって解読される恐れがある.既存の耐量子安全なアキュミュレータにも課題がある.要素の挿入，削除，および非メンバーシップ証明のすべてを要素数 N に対して対数時間 log N 以下で実行できる方式は，いまだ確立されていない.本研究では，初めて耐量子安全性を持つ動的ユニバーサルアキュミュレータを提案する.本方式は格子暗号で用いられる Short Integer Soulution (SIS) 問題の困難性に安全性を帰着する.本方式では，要素の追加，削除，メンバーシップ証明，非メンバーシップ証明の計算時間が要素数 N に対して対数時間 log N で実現するアキュミュレータを提案する.構造には Sparse Merkle Tree (SMT) を採用する.SMT は，要素が存在しないデフォルトノードを物理的に保持せず，計算によって代替する.これにより，メモリ使用量を抑えつつ，効率的な非メンバーシップ証明を可能とする. さらに提案手法 2 として，SMT の構成を改良した手法を提案する.証明書の生成時にデフォルト部分を省くことで，証明書のサイズを大幅に圧縮する.ユーザの数が230 (10億ユーザ)程度のシステムで，木の高さを 256 と設定し，NIST で推奨されている 128bit セキュリティを保証する方式の場合，メンバーシップ証明書のサイズは提案手法 1 で 192KB, 提案手法 2 で 23.5KB となる.提案研究 1 では，Libert らが提案した動的なメンバーシップ証明のみ可能な方式と同様の証明書サイズで非メンバーシップ証明を実現した. 提案手法 2 ではさらに 87% の証明書サイズの削減を実現した.