LWE暗号の利用

【 LWE暗号の利用 】

Mahadevの論文を読む準備をしています。

Mahadevの量子計算の古典的検証では、古典コンピュータ上で実装可能で、しかし、量子コンピュータでも解読できない暗号、ポスト量子暗号のLWE暗号を利用します。今回のセッションでは、そのことを見ていきます。

基本的には、前回見た Trapdoor Claw-Free Functions (TCF) をLWEを使って定義します。こうして再定義された TCFを Noisy Trapdoor Claw-Free Functions (NTCF) といいます。それについては、セッションのスライドとビデオを参照ください。

ここでは、参考にした 2021年のMahadev達の論文の「はじめに」の部分が、よくまとまっていたので、それを紹介したいと思います。

「この論文では、純粋に古典的な検証者が、多項式時間に制限された一つの量子マシンと相互作用する新しいモデルを考察する。」

「量子デバイスの計算を多項式時間に制限することで、検証者は、ポスト量子暗号、すなわち、古典コンピュータ上で効率的に実装可能であるが、量子コンピュータでも解読できない暗号の基本技術を活用することができる。」

「このモデルでは、「信頼できない量子デバイスが “本当に ”量子的であることを効率的に検証する方法」と「信頼できない量子デバイスから検証可能な乱数文字列を生成する方法」という2つの基本的問題に対する解決策を提案する。」

「一つ目の課題は「量子優越性の証明問題」とも呼ばれ、既存のプロトコルでは、古典的スーパーコンピュータを用いて指数関数的な時間をかけて検証する必要がある。それに対し、本論文のqubit検証テストは、古典的検証者が多項式時間で検証可能な量子性の証明を提供する。」

「信頼できない量子デバイスを扱う難しさの中核には、デバイスの操作を通じて、量子デバイスの内部にあるqubitの構造を持たせることを強制することにある。すなわち、量子デバイスに実際にこの量子ビットを保持させ、また、検証者の要求に応えて、qubitの計測を実行することの難しさにある。」

この最後の部分をどう実現するかが、ポイントになります。

前回のセッションの最後の式、それは、今回のセッションの最後の式とも同じなのですが、claw (x0, x1) に対して、clawの値の重ね合わせである次の状態を量子コンピュータ内に作ることが鍵になります。

     ( |0>|x0> + |1>|x1> ) /√2

--------------------------------

「 Noisy Trapdoor Claw-Free Functions using LWE  」 を公開しました。
https://youtu.be/r5hGyMuwMVw?list=PLQIrJ0f9gMcOQHQ6KmWuUxuRZkHT-2gZ-

スライドのpdf
https://drive.google.com/file/d/1Pbce8wXMYeOQ-ihQcorBvK3UgkMIjink/view?usp=sharing

blog:「LWE暗号の利用 」
https://maruyama097.blogspot.com/2022/11/lwe.html

まとめページ「量子計算の古典的検証 」 

セミナーへの申し込み

参考資料
Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, Thomas Vidick
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
2021/05/04 ver.4 




コメント

このブログの人気の投稿

マルレク・ネット「エントロピーと情報理論」公開しました。

初めにことばありき

人間は、善と悪との重ね合わせというモデルの失敗について