永田 裕大
大規模なデータ集合の管理では, 要素が集合に含まれていることを証明するメンバーシップ証明が重要となる. メンバーシップ証明を実現する暗号プリミティブとして, Vector Commitment (VC) がある. VC はベクトルで表されるデータ集合全体に対する短いコミットメントを保持し, 各要素がデータ集合に含まれていることを証明することができる. VC において, 証明内容が改ざんできないことや, 多数の要素に対する証明の生成, 更新, 検証を効率的に行えることが不可欠である. Srinivasan らにより提案された Hyperproofsは,大規模ベクトルに対するメンバーシップ証明を効率的に生成, 集約できる VC である. Hyperproofs では証明書を木構造として管理し, 葉ノードにベクトルの要素が格納されている. それぞれの要素の証明書は木のパスをたどる設計のため, 証明書の一部は他の要素と共有されている. また, 更新時には変更が生じた要素に対応するパスのみを更新する設計が採用されている. しかし, 他の位置の要素を持った人がコミットメントや証明の更新を行うには, ベクトル中のどのインデックスに対応する要素が更新されたかを公開する必要がある. 更新位置の漏洩はアクセスパターンの露見につながり, プライバシーの観点から問題となり得る. 本研究では, Hyperproofs の更新位置秘匿性を実現するための拡張方式を提案する. 提案方式では, 1 回の更新を要素が含まれていない位置も更新(ダミー更新)を行うことで, 複数位置の同時更新として処理する. 実更新とダミー更新を同一形式で公開することにより, 観測者から実際の更新位置を識別できないようにする. このとき, ダミー更新の位置にランダムな更新量を適用することで, 更新パターンからの識別を防ぐ設計とした. また, 提案方式に対する安全性証明を行った.
