耐量子公開鍵暗号 CRYSTALS-KYBER の高速実装(導入編)

イントロダクション

Fixstarsでは 耐量子の公開鍵暗号である CRYSTALS-KYBER の高速な実装に取り組んでいます。この取り組みについてこちらのブログで紹介していきます。

今回は導入編として、CRYSTALS-KYBERの数理的な背景と公開鍵暗号の安全性の考え方について簡単に説明したいと思います。

CRYSTALS-KYBERとは？

公開鍵暗号は情報社会において重要なセキュリティ技術です。 公開鍵暗号は「コンピュータでも効率的に解くことが困難である（とされている）数学的な問題」に依拠しています。例えば、RSA暗号は桁数が大きい合成数の素因数分解が現実的な時間内では困難であることを安全性の根拠としています。公開鍵暗号はこのような「仮定」に基づいた計算量的安全性を満たす方式が用いられています。

しかし、量子計算機を用いることで素因数分解問題を多項式時間で解くアルゴリズムが Peter Shor によって発見されました。 Shorのアルゴリズムの量子計算機を用いた実装実験は次の記事が参考になると思います。
https://qiskit.org/textbook/ja/ch-algorithms/shor.html

こうした状況のなか、米国のNISTが中心となって次世代の公開鍵暗号-すなわち、量子計算機に耐性のある公開鍵暗号-を開発・標準化するプロジェクトが進められています。これが、Post Quantum Cryptography(PQC) と呼ばれるものです。

PQCのプロジェクトでは、“Selected Algorithms 2022”として公開鍵暗号1つとデジタル署名3つのアルゴリズムが選定されました。
https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022

選ばれた公開鍵暗号が CRYSTALS-KYBER です。
Algorithm Specifications And Supporting Documentationが公開されています。
https://pq-crystals.org/kyber/data/kyber-specification-round3-20210131.pdf

格子暗号

LWE(Learning-with-errors) 問題

CRYSTALS-KYBERはLWE問題と呼ばれる格子問題に依拠しています。 KYBERは比較的シンプルな構成になっていますが、いきなり仕様書を読んでも難しいかも知れません。今回はその元になったLWE問題について簡単に説明します。

ℝⁿ上のベクトル空間の基底 b に対してある整数ベクトル a を用いて表されるベクトルの集合を格子といいます。つまり、
$$L = \sum a_i {b_i} : a_i \in \mathbb{Z}$$
のような形であらわすことができます。

LWE問題はSLWEとDLWEに分けられます。以下のインスタンスに何回でもアクセスできる解読者が次の問題を解きます。

• Search-LWE : 秘密のベクトル ${s} \in \mathbb{Z}_q^n$ を特定する問題
• Decision-LWE : 下記のインスタンスで出力された組$({a},t)$とランダムサンプルされた組$({a’},b’)$を識別する問題

インスタンス

${a} \leftarrow \mathbb{Z}^n_q$ (ランダムサンプリング)

e ← ϕ ∈ 𝕋(ℝ/ℤ) (ランダムサンプリング)

$t = \left( \sum_{i = 1}^n a_is_i \right)/q + e$

組 $({a},t)$ を出力

Regev暗号

公開鍵暗号は一般に以下のアルゴリズム組から構成されます。

• (pk, sk) ← Gen(params)
• セキュリティパラメタを入力として秘密鍵skと公開鍵pkを出力する

• c ← Enc(pk, m)
• 公開鍵と平文mを入力として暗号文cを出力する

• m´ ← Dec(pk, sk, c)
• 公開鍵と秘密鍵と暗号文を入力として復号文m´を出力する
• 正当な復号が行われた場合m = m´となる

LWE問題に基づいた公開鍵暗号の構成方法をRegevが示しました。この暗号をRegev暗号と呼びます。Regev暗号の基本的なアルゴリズムを次の図に示します。

LWE 問題を利用した暗号にはいくつかバリエーションがあります。多項式環を利用したRing-LWE問題に基づく暗号、RLWE や LWE をさらに一般化したModule-LWE等が挙げられます。

CRYSTALS-KYBERはModule-LWEを用いたRegev暗号の1つです。

公開鍵暗号の安全性

ここからは公開鍵暗号の安全性の考え方について説明します。特に最近公開鍵暗号は技術的にホットな話題ですし「公開鍵暗号が安全とはどういうことか」を知っておくことは意義があると考えられます。すこし脇道にそれますが、ここで簡単に説明します。

公開鍵暗号は、一般に以下のアルゴリズム組から構成されます。

• (pk, sk) ← Gen(params)
• セキュリティパラメタを入力として秘密鍵skと公開鍵pkを出力する

• c ← Enc(pk, m)
• 公開鍵と平文mを入力として暗号文cを出力する

• m′ ← Dec(pk, sk, c)
• 公開鍵と秘密鍵と暗号文を入力として復号文m′を出力する
• 正当な復号が行われた場合m = m′となる

ここで Dec アルゴリズムは入力された情報を用いて平文を暗号文に復号する「問題」を解くことになります。ここでDec は、

• 秘密鍵skの情報を有していれば容易に実行できる
• sk を有していない場合容易に実行できない

という性質を持っていることが必要です。ここでいう「容易」とは、充分に高い確率で遂行できる多項式時間アルゴリズムが存在するくらいで考えます。

暗号を攻撃することを考えます。攻撃するエンティティは次の攻撃アルゴリズム𝒜を構成する必要があります。

公開鍵暗号はこの問題がチューリング機械において「困難」であるような問題を暗号化・復号化問題に落とし込んでいるというわけです。

公開鍵暗号の安全性は数理的なゲームに基づいたモデルによって定式化されています。色々な種類があるのですが一般的・代表的なものを紹介します。

攻撃モデル

• CPA : chosen plaintext attack ; 選択平文攻撃 ; 攻撃者は任意の平文を暗号化するオラクルにアクセスできる
• CCA : chosen ciphertext attack ; 選択暗号文攻撃 ;攻撃者は任意の暗号文を復号するオラクルにアクセスできる

さらに、これらの攻撃モデルは次の二種類に分けることができます。

• selective ; 過去にオラクルにアクセスした内容及びそれに対するレスポンスを利用できない（揮発性メモリ的な）
• adaptive ; 過去にオラクルにアクセスした内容及びそれに対するレスポンスを利用できる（不揮発性メモリ的な）

解読モデル

• OW : One-Way ; 暗号文から秘密情報全体が漏れてはいけない
• IND : Indistinguish ; 暗号文から秘密情報が1ビットも漏れてはいけない

たとえば挑戦者がIND-CCA-gameに勝利するには攻撃者の選択暗号文攻撃の下でチャレンジ暗号文から平文に関する情報を1ビットも漏らさないことが求められますが、OW- ゲームの場合は暗号文から平文を直接復号されなければよいわけです。IND 安全性のほうがより「強い」安全性であるということになります。ちなみにIND 安全性から　OW 安全性が導出できます。つまり、IND安全ならOW安全ということです。

CRYSTALS-KYBERはIND-CCA-adaptive安全の公開鍵暗号です。すなわち、「暗号文を復号するオラクルに任意回、復号結果を都度参照しながらアクセスすることが許されているなかで秘密鍵に関する情報を1ビットも漏らすことがない」ということになります。

尚、CRYSTALS-KYBERでは、IND-CPA安全な公開鍵暗号を構成して、藤崎-岡本変換によりIND-CCA-adaptive安全なKEM(Key Encapsulation Mechanism)に変換してIND-CCA2安全を確保しています。詳細なアルゴリズムがインターネット上に公開されています。

「1/2より有意に大きい」というのはより形式的には暗号文長などから定義される多項式等によって攻撃者のアドバンテージ（ゲームに勝利する確率）が「微小な」値で抑えられることを不等式を用いて評価します。攻撃者の勝利確率が“negligible”（日本語でいうと「無視できるほど小さい」）であるなどといいます。

暗号の構成においては、（１）暗号の正当性（アルゴリズムの入出力を数学的に示すことで主張する機能が実現されていること）の証明　および　（２）暗号の安全性（プロトコルの安全性定義とそれが成り立っていること）の証明　が求められます。

まとめ

次回は当プロジェクトで実際に KYBER の CPU 実装を評価しながら高速化に取り組んでいきます。

参考文献

• J. Bos et al., “CRYSTALS – Kyber: A CCA-Secure Module-Lattice-Based KEM,” 2018 IEEE European Symposium on Security and Privacy (EuroS&P), London, UK, 2018, pp. 353-367, doi: 10.1109/EuroSP.2018.00032.

• Avanzi, Roberto Maria, Joppe W. Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler and Damien Stehlé. “CRYSTALS-Kyber Algorithm Specifications And Supporting Documentation.” (2017).

• Moriyama,Nishimaki,Okamoto,“公開鍵暗号の数理”(2011),共立出版

本記事はインターン生の藤本さんと共同で記載しています。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。