【Crypto 2020イベントレポート】ゼロ知識証明~ΣプロトコルとBulletproofs ~ Centrum Wiskunde & Informatica

8月に開催されたCrypto 2020にて、entrum Wiskunde & Informatica (CWI)の暗号学者による特別公演がありました。

登壇者

Ronald Cramer

オランダのアムステルダムに位置するCentrum Wiskunde & Informatica (CWI)とUniversity of Leidenの教授を務めています。暗号方式の一つであるクレーマー シュープ暗号を発明した人物の1人で、暗号学界での功績を成し遂げています。

Compressed Sigma-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics

以下、講演の内容になります。

ゼロ知識証明とは、命題（条件づけなど）が真であるという情報以外を伝えずに他者へ命題が真であることを証明する方法です。

ゼロ知識証明に使われていたセオリーにΣ（シグマ）プロトコルセオリーがあります。シグマプロトコルセオリーではゼロ知識証明の際に必要なコミュニケーションの数がO(|C|)*kで定義され、コミュニケーションは一次関数で表されます。コミュニケーションが一次関数的に処理されるため、こちらはリニアーコミュニケーションと呼ばれます。

一方、のちに発明されたBulletproofsではコミュニケーションの数がO(log|C|)*kで定義され、コミュニケーションは対数関数で表されます。コミュニケーションが2次関数的に処理されるため、こちらはクアドラティックコミュニケーションと呼ばれます代入値が同じ（条件が同じ）である場合、Bulletproofsを用いたほうがコミュニケーション数が少なくなるため効率を重視してBulletproofsの使用が広まりました。結果、シグマプロトコルの使用は激減していきました。

Ronald Cramer氏の研究では、シグマプロトコルのリニアーサイズ（一次関数的）なメッセージに数学的/暗号的な処理を行うことで二次関数的なメッセージへ変換できることが証明しました。

これにより、シグマプロトコルをBulletproofsに置換するのではなく、シグマプロトコルを改良することによりBulletproofsに劣らないプロトコルを作り上げることができると説明しています。

最後に

Crypto 2020はInternational Association for Cryptologic Research (IACR)により運営される暗号資産とブロックチェーンに関するカンファレンスです。

今回の公演では、ゼロ知識認証に使われる2つのプロトコルの背景から、シグマプロトコルの新たな可能性まで知ることができました。