耐量子計算機暗号・秘密計算のePrintウォッチング（2023年５月第２週）

@0917laplace です．

前回に続いて，暗号理論の中でも特に進展が早い（と思われる）耐量子計算機暗号と秘密計算の分野に絞って，週次単位でiacrに投稿されたePrintを整理します

Cryptology ePrint Archive

今回は2023年５月第２週（5/7-5/13）に投稿された（厳密にはapprovedされた）耐量子計算機暗号・秘密計算のePrint（2023/634-2023/673）を対象に整理します
まとめ方の雰囲気としては，前回の記事を参照してください

耐量子計算機暗号

分野の分類としては

• 格子

• 符号

• 多変数

• 同種

• ハッシュ

• 全般

• その他

とします
＊格子暗号を用いた準同型暗号方式は，こちらではなく次の秘密計算の章で集計します

↓読み込むまでに時間かかるかも？ですので，URL埋め込みもしておきます
PQCのまとめ表

今回注目したいのは number 663 です．
格子暗号と呼ばれる暗号方式の安全性の根拠となる問題は，大きく分けてLWE問題とNTRU問題の２つがあります．これらに基づく暗号方式はそれぞれ異なるものとなりますが，この論文で提案されているのはそれらのハイブリッド方式，ということになります．
LWE問題にはさまざまな派生がありますが，この論文では Module-LWE 問題を用いています．第３章の NTWE 問題の定式化を見ると，分布の構成を LWE 問題に寄せて，暗号文の構成を NTRU 問題に寄せているという印象です．
全体的に代数的整数論を仮定している（といっても代数体の整数環が分かれば十分）ですが，そこは読み飛ばしても影響はなさそうかなと思います．

秘密計算

分野の分類としては

• 準同型

• MPC

• GC（Garbled Circuit）

• TEE

• カード

• ハードウェア

• 全般

• その他

とします

↓同じくURL埋め込みをしておきます
秘密計算のまとめ表

こちらで注目すべきは number 664 です．
群作用が関わる同型問題は色々あります．3.1節で例示されていますが，グラフの同型問題やテンソル同型問題などです．また，耐量子計算機暗号の主要な４方式（格子暗号・符号ベース暗号・多変数多項式暗号・同種写像暗号）にもそれぞれ同型問題が存在します．
＊その中でも最初に多変数多項式暗号が出てくるあたり，この方は多変数多項式暗号が専門なのですかね・・・？
この論文では，一般の同型問題を用いた認証方式や署名方式を紹介しつつ，最後の第５章でMPC-in-the-head方式を提案しています．
＊MPC-in-the-head 方式とは，零知識証明を用いたプロトコルにMPCを組合せた方式のようです
↓原論文
Y. Ishai, E. Kushilevitz, R. Ostrovsky, A. Sahai: ``Zero-knowledge from secure multiparty computation.'',  In: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp.21-30, 2007.

今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！