Acompany 技術ブログ/技術ブログ記事一覧/📝完全準同型暗号①（格子暗暗号）
📝

完全準同型暗号①（格子暗暗号）

完全準同型暗号と格子暗号

Acompanyでは秘密計算技術を活用したセキュアなデータ活用サービスを提供しています。
データを暗号化したまま演算のできる秘密計算には完全準同型暗号、マルチパーティ計算（MPC）、TEEの3種類の手法があります。本記事では完全準同型暗号がどのような技術なのかを紹介します。
現在主流な完全準同型暗号は格子暗号を基に実現されます。
そこで今回は格子暗号について解説します。

格子暗号の概要

前述の通り完全準同型暗号では格子暗号を用いる場合が多くあります。格子暗号は完全準同型暗号以外にも量子コンピュータに対応するという点でも注目を集めている暗号です。
近年量子コンピュータという言葉を耳にする機会が多くなってきています。量子コンピュータを用いると従来のコンピュータでは難しいとされる計算が、容易に行える可能性があります。
計算が簡単にできることには良い面もありますが、それによって悪い影響が出ることもあります。その悪い影響のうちの一つが、現在広く利用されているRSA暗号や楕円曲線暗号が使えなくなってしまうことです。これらの暗号の安全性を担保している素因数分解問題、楕円曲線離散体数問題が量子コンピュータを用いると容易に解かれてしまうからです。
既存暗号の危機に備え、米国技術標準研究所（NIST）は量子コンピュータに耐性がある耐量子計算機暗号（Post-Quantum Cryptography, PQC）の標準化計画を発表しました。その有力候補として注目されているのが格子暗号です。
RSA暗号での素因数分解問題や楕円曲線暗号での楕円離散対数問題のように、格子暗号も数学的に解くのが難しいとされる問題を基に構成します。格子暗号で使用する問題が格子問題です。
 

格子とは

格子暗号を構成する前にまずは格子を定義します。
個の一次独立な基底ベクトルを とします。
この時格子 は次のように定義されます。
つまり基底を整数倍し、すべて足したベクトルによって格子は構成されます。また、この格子上にある点を格子点と呼びます。

格子問題

前述の通り格子暗号は格子問題を基に構成します。ここでは特に重要かつ有名な三つの格子問題(Lattice Problem)を紹介します。

1. 最短ベクトル問題（Shortest Vector Problem, SVP）

格子 が与えられた時、その格子点上で最も短い非零なベクトルを求める問題

2. 最近ベクトル問題（Closest Vector Problem, CVP）

格子 と 次元ベクトル空間上の点 が与えられた時、 に最も近い格子点を求める問題
SVPはNP困難な問題であり、SVPはNP困難なです。またCVPはSVPを含むため、SVP以上に計算が困難な問題として知られています。

3. LWE（Learning with Error）問題

、を奇素数とし、平均 、標準偏差 の離散正規分布をとする。 を固定し、}を一様ランダムに選ぶ。離散正規分布 からサンプルした に対して
となる の組がの確率で出力されるとする。
確率分布 からある の組がサンプルされたとき、を求める問題
 
具体的な数値例でLWE問題を考えてみます。
、微小なエラーベクトルを とし、以下のような連立近似方程式が与えられたとします。
ここで
とおくと連立近似方程式は
の各成分は素数 を法とする有限体 からランダムに選んだ整数になります。
ここで が基底行列と考えると は格子点と考えることができます。そこに微小なエラーベクトルを加えたものが です。
を基底ベクトル、任意の格子点 としたときの二次元のLWE問題のイメージ図です。
LWE問題は機械学習の理論から派生したものでSVP、CVPに帰着することができます。そのためLWE問題を解く際にはこれらの問題に帰着してから解を求めることで比較的容易に問題が解ける場合があります。またLWE問題は厳密には判定LWE問題（Decision-LWE）と探索LWE問題（Serch-LWE）の２種類があり、ここでは探索LWE問題を紹介しています。
準同型暗号にはこのLWE問題を使用するものが多くあります。詳しくは次回以降の記事で説明します。
 
これらの格子問題を解くにあたり「良い格子」と「悪い格子」が存在します。「良い格子」は問題が解きにくく、「悪い格子」の場合は既存のアルゴリズムを用いて容易に解くことができてしまいます。その二つの違いは基底同士の交わる角度です。角度が直交に近ければ近いほど解くのが簡単になります。そのため格子問題を暗号に用いる場合には、基底の設定に注意する必要があります。

格子問題から暗号を構成する

次にLWE問題から1bitの平文を暗号化する方法を紹介します。

共通パラメータの設定

  1. 受信者は鍵を作成する前に、全ての人に公開できる次元数 とパラメータ を定める。はじめに素数を選び、この先に設定する全てのパラメータが 以下になるように選ぶ。格子の次元  、全てが互いに直行しない 個の基底 を定める(各基底は 行列)。基底のそれぞれの成分も 以下にする。また任意の実数 を定める。
  1. を全ての利用者に公開する。
この暗号の安全性はパラメータの取り方にも関係します。例えば、次元数 は３桁以上の正整数、素数   は４桁以上など安全な暗号となるための条件が研究されています。

鍵の設定の準備

  1. 受信者は各成分を 以下の整数とする 行列 を設定する
  1. 各成分を確率分布 に基づいてランダムに選んだ整数とする 行列を とする
  1. 格子点 に を足した点を とする。 を計算する。

公開鍵と秘密鍵の設定

公開鍵：
秘密鍵：
と設定する
LWE方式では秘密鍵の設定の３工程目での「ある確率分布 」とは、平均 、標準偏差 の離散ガウス分布を指します。離散ガウス分布は 0 に近い整数が選択される確率の高い分布で、事前に定めたパラメータ  を用いて具体的な確率を決定します。
次に暗号化と復号の処理を説明します。これらの処理には様々な方法がありますが、今回は2008年にPeikertらによって提案された1bitの処理を行う最も簡単なアルゴリズムを紹介します。

暗号化

  1. ある確率分布に従って各成分を定めた 行列 を選ぶ。
  1. を計算する
  1. 平文が のとき：
　　平文が のとき：
　　と定める。
  1. を計算する
  1. を暗号文とする

復号

  1. を計算する。
  1. の値から平文を確認する。　
　　
これは  が高い確率で  になるからです。場合によっては復号に失敗してしまうこともあります。
以上の方法で１bitの平文の暗号処理、復号を行うことができます。
 

まとめ

  • 準同型暗号は格子暗号を基に構成されるものが主流
  • 格子暗号は格子問題を使用した次世代暗号である
 
参考文献
  • 量子コンピュータに耐性のある暗号技術の標準化動向:米国政府標準暗号について, 四方順司Discussion Paper No. 2019-J-4
  • 格子暗号の解読のための数学的基礎知識, 青野良範, 安田雅也
  • Peikert, Chris, Vinod Vaikuntanathan, and Brent Waters, “A Framework for Efficient and Composable Oblivious Transfer,” Proceedings of CRYPTO, LNCS 5157, Springer-Verlag, 2008, pp.554-571.
 
Xでポスト