HN 日本語サマリー

← 一覧へ戻る
セキュリティ

難読化: 暗号の最終ボスを構築する (パート I)

Obfuscation: Building the final boss of cryptography (Part I) (vitalik.eth.limo)

44 pointsby fbrusch3 コメント

要約

この記事は、プログラミングにおける難読化の概念と、その暗号学における重要性について解説しています。特に、「区別不能難読化(iO)」と呼ばれる強力な暗号プリミティブに焦点を当て、その理想的な実現が困難であること、そして現在のところ実行時間が膨大であるという課題を提示しています。しかし、将来的には効率化が進む可能性や、新たな暗号学的仮定に基づく研究の方向性についても触れられています。

全文翻訳

難読化:暗号学の最終ボスを構築する(パートI)

ダークモード切り替え

2026年6月29日 全投稿を見る

難読化:暗号学の最終ボスを構築する(パートI)

Sora Suegami、Janmajaya Mall、Aayush Jain、Fun Killerによるフィードバックとレビューに特別感謝します。

暗号学において考案された最も強力なプリミティブは難読化です。難読化は、プログラム (P) を「暗号化されたプログラム」(Obf(P)) に変換することを可能にします。これにより、(Obf(P)) を平文の入力で実行し、(P) と同じ平文の出力を得ることができますが、(P) の内部動作は隠蔽されます。一般的に使用される正確な形式化である不可識別性難読化(iO)は、同じ機能を持つ2つの異なるプログラムの難読化が与えられた場合、どちらがどちらであるかを区別できないと述べています。実質的には、コードを隠蔽するのであって、データを隠蔽するのではありません。

難読化は、理論上の理想的な「信頼できない信頼された第三者」に非常に近いものを提供するため、強力です。

[画像: Nick Szaboによる「The God Protocols」の引用]

*出典: The God Protocols (Nick Szabo), 1997

暗号プロトコルは、しばしば、すべてのメッセージを監視し正直に応答する信頼された第三者に依存するプロトコルを最初に想像し、その後、その同じことを信頼なしで行う方法を見つけることによって記述されます。

  • 暗号化は単純です。「信頼された第三者」は、効果的には「[受信者]に[メッセージ]を見せたい」という指示を受け付け、メッセージを受信者に渡す郵便システムのようなものです。
  • ゼロ知識証明は、データを受け取り、それを検証し、その後、データがある意味で正しいことを誰にでも確認する信頼された第三者を置き換えます。

難読化(技術的には、難読化とハッシュの組み合わせ)を使用すると、基本的にあらゆるプロトコルに対してシミュレートされた信頼された第三者を作成できるため、上記の両方や、さらに多くのものを置き換えることができます。唯一の大きな例外があります。難読化されたプログラムは、それ自体がコピーされるのを防ぐことができないため、お金のような「ステートフル」なことはできません。そして、まさにそのギャップをブロックチェーンが埋めるのに適しています。

したがって、難読化とブロックチェーンがあれば、非常に魔法のようなことができます。例えば、ほとんど信頼の仮定を必要としない、安全でプライベートかつ共謀に強い投票システムなどです。M-of-N閾値委員会は不要です。あるいは、2014年のこのリストにあるほとんどすべてのものを、M-of-Nの信頼仮定なしで実現できます。

User
Encryptto P.pub
Action
Publish
to chain
Obfuscate
Ask Obf(P) for its
internal public key
if op.type == INPUT:
    self.inputs.append(op.msg)
elif (op.type == OUTPUT
      and verifySig(op.msg, P.pub, op.sig)
      and is_valid(op.claimed_block_hash)):
          do_stuff(op.msg)
The program (eg. a voting
mechanism, a privacy-preserving
financial or social app...)
It should have an internal
private+public key, which it uses
both to accept encrypted inputs, and
to sign its outputs
Generate smart contract
that goes onchain
C
Publish
C...
C Tree
accumulates
encrypted messages
P.pub
Obf(P)
Run Obf(P) on
message tree and
proof of blockchain
consensus
Output: (action,claimed_block_hash,sig)
C verifies (action,claimed_block_hash, sig)
against P.pub (included in
C's code), if it passes, take
action
We may want to eventually re-add a
small amount of PoW to the protocol to
make extracting any extra information,
even by doing 51% attacks to create
chains with different histories, provably
expensive.

難読化とブロックチェーンを組み合わせて、「信頼できない信頼された第三者」に非常に近いものを作成するための、かなり汎用的な方法

では、問題は何でしょうか? 安全な形式の難読化を作成するのは、非常に非常に難しいことが判明しました。

数十年にわたる安全でない難読化の伝統があります。人々は、プログラムのロジックをシャッフルして何が起こっているのかを見えにくくしていましたが、これはしばしばゲームのようなプロプライエタリプログラムのユーザーによる改変を防ぐためでした。これは、暗号化におけるシーザー暗号のようなものと同等であり、シーザー暗号と同様に、定期的に破られています。

その結果、数学的に安全であることを証明できる難読化プロトコルの作成を試みる数十年にわたる伝統もありました。しかし、ほぼ最初から、これには問題がありました。2001年には、有名な結果が得られました。つまり、理想的な形式の難読化(プログラム (P) を、(Obf(P)) の実行が、任意のユーザー提供の (x) に対して (P(x)) を返すAPIをクエリすることから学べること以上の何も明らかにしないように難読化すること)を作成することは不可能であるということです。中心的な考え方は、(P) のコードインスタンス化は、常にユーザー提供の入力に対する出力以上の何かを明らかにすることです。少なくとも、それ自身のコードに(P) を適用することによって、物事を学ぶことができます。

その時点から、研究者は2番目に良いターゲットである不可識別性難読化(iO)の証明に移行しました。これは20年間のプロジェクトであり、多くの失敗した試み、まだ存在しない要素の上に構築されるプロトコルの多くの構築、その要素を構築しようとする多くの人々、そしてその失敗した試みなどがありました。しかし、過去数年間で、ついに良いニュースがありました。合理的なセキュリティ仮定の下でiOを達成する方法がわかったのです。

しかし、その良いニュースの中には悪いニュースもあります。実行時間は文字通り天文学的です。それは技術的には多項式ですが、多くの「完全準同型暗号にやや似たものに、その評価のための回路を別の完全準同型暗号に似たものに入れる、それを各ビットに対して一度だけ通常の完全準同型暗号で実行して中間的な数メガバイトの値を得る、そしてああ、その全体を別の完全準同型暗号に似たものに入れて、それらすべてを入力の各ビットに対して一度実行しなければならない」という層を積み重ねることを含みます。その結果、これらの「証明可能な安全なiOスキームのようなもの」の実行時間は、( ext{λ}^{10} )(ここで ( ext{λ} ) は「セキュリティパラメータ」、つまりスキームを破るのにかかる時間の対数です。( ext{λ} = 100 ) または ( 120 ) と言うのが標準です)よりも大きくなります。

ここには2つの希望のある物語があります。一つは、これがSNARKsが2010年頃にあった状況に似ており、可能であることがわかった今、賢い人々(とボット)が各ボトルネックに対して巧妙な回避策を考案し始め、実行時間から何桁も削り取っていき、最終的には「重いGPUで1日かかるだけ」のもの(それでも法外に聞こえるかもしれませんが、実際には多くの興味深いアプリケーションには十分です)に到達するだろうということです。もう一つは、同じ目標に向けた別の戦略で、より多くの作業が見られるということです。つまり、新しい暗号仮定の開発をより良く行い、どの新しい仮定が実際に安全である可能性が高いかをより良く判断することです。

ヒューリスティックなアプローチを加えると、これまでに約3つの(まだ死んでいない)難読化プロトコルのファミリがあり、それらを効率性とセキュリティ仮定に対する大胆さの「トレードオフフロンティア」に配置できます。

図: 難読化プロトコルのトレードオフフロンティア(Galactic, Planetary, Intensive, Consumer-friendly)

この投稿では、これまでで最も銀河系(Galactic)でありながら、最も厳密なファミリ、つまり上記の図の青色で示されたものを詳細に説明します。

警告:多くの数学が登場します。難読化は、過去20年間に暗号学者が発明したほぼすべてのプリミティブを積み重ねる必要があるため、困難です。ただし、ブロックチェーン開発者がすでに知っているプリミティブ(SNARKsやSTARKsなど)を除くものです。基盤となる数学も異なります。SNARKsやSTARKsは多項式、ハッシュ、楕円曲線が多く含まれる傾向がありますが、難読化は多くの格子(lattices)、ベクトル、行列を扱います。

[画像: 格子暗号の概念図]

表記に関する注意
  • この投稿の説明は、さまざまな論文のアプローチを組み合わせており、単一の論文に完全に従っているわけではありません。
  • 場合によっては、表記法と語彙の選択が個々の基盤となる投稿と異なる場合があります。
  • ベクトルは小文字、行列は大文字で表します。
  • 図では、灰色で表示されたテキストと点線は、非公式に「XはYに依存するが、Yを実際にXに渡す必要はないため、Xの(サイズ/実行時間)はYの(サイズ/実行時間)よりもはるかに小さくなる可能性がある」ことを意味します。
  • 「iO」は「不可識別性難読化」を意味し、「IO」は「入力/出力」とは対照的です。どちらも、.io TLDの名前の由来であるイギリス領インド洋領地とは異なります。

標準的なパイプライン

今日構築されている「合理的に証明可能な安全な」難読化プロトコルは、10年前の構築の塔の上に構築されています。それはAJ15 / BV15 / LPST15 / LPST16の系統です。

AJ15とBV15は、ほぼ同時に発表された2つの論文で、どちらも機能的暗号化と呼ばれるプリミティブの上に難読化を構築するほぼ同じ方法を発見しました。機能的暗号化では、「権威」が関数 (F) に紐付けられた鍵を公開し、それらの鍵が存在すると、暗号化鍵を持つ人は誰でも (x) を暗号化でき、復号鍵を持つ人は誰でも (F(x)) を復号できます。LPST15も同様のものを考案しました。しかし、必要とされる機能的暗号化は非常に強力な特性を持つ必要があり、それはまだ利用可能ではありませんでした。幸いなことに、1年後、LPST16は、サブ線形コンパクトランダム化エンコーディングと呼ばれるものの上に難読化を構築する方法を発見し、それを、すでに知られている「簡潔だが非コンパクトな」機能的暗号化スキームと、XiOと呼ばれる新しいプリミティブ(すべての可能な入力に対する出力のテーブルを公開するよりもわずかに小さいサイズの難読化)の上に構築しました。それ以降の作業の大部分は、XiOを実際に実装する方法を見つけることでした(ただし、一部のプロトコルは別のルートを取ります。例:JLS20)。

この説明を3つの部分に分けます。

  1. 簡潔なFEスキームとXiOスキームがあると仮定して、難読化プロトコルをどのように構築するか。
  2. 簡潔なFEスキームをどのように構築するか。
  3. XiOスキームをどのように構築するか。

簡潔なFEスキームとXiOスキームがあると仮定して、難読化プロトコルをどのように構築するか。

簡潔なFEとXiOの上に難読化プロトコルを構築する方法はいくつかあり、それらはすべて、高レベルの原則とプロパティにおいてほぼ同等です。そのため、LPST15デザインの簡略化されたバージョンに準拠します。

この投稿では、「関数」と「回路」を交換可能に使用します。回路は、AND、OR、NOTなどのゲートのセットであり、それらをリンクするワイヤがあり、関数を評価するために使用できます。回路の直感をより良く得るために、このガーブルドサーキットの説明投稿をお勧めします(これは後で必要になるプリミティブです)。

まず、簡潔なFEとXiOを定義して、これらのガジェットのプロパティを理解しましょう。

ここに簡潔なFEがあります。

権威は、回路に依存しない公開パラメータと、回路 (C) を持つ公開されている単一ビット出力関数に対する回路固有の復号鍵を生成します。

暗号化者は、暗号化鍵を使用して (x) を暗号化できます。このステップの実行時間は、(C) の回路サイズが増加しても(またはわずかに増加するだけで)増加しませんが、入力長に対しては線形にスケールします。

復号者は、復号鍵を使用して (C(x)) を学習でき、(x) についてそれ以上のことは何も学習できません。このステップの実行時間は、(C) の回路サイズに比例してスケールします。

言い換えれば、誰かが信頼されたセットアップを行い、私が (x) を暗号化し、あなたは (C(x)) を復号できる(完全準同型暗号とは異なります。FHEでは、(C(x)) を復号できる人は誰でも (x) や (x) の他の任意の関数も復号できます)ということです。

機能的暗号化だけでは難読化には十分ではありません。なぜなら、(i)関数を隠蔽しないこと、そして(ii)公開された各暗号化は1つの入力にバインドされており、その1つの入力で評価された関数のみを復号できるからです。しかし、それは目標の大部分を達成します。

注意点として、より一般的な簡潔なFEの定義は、高い回路サイズではなく、高い回路深度を許容することを要求します。しかし、ここでは高い深度を許容する必要があります。幸いなことに、深度に依存しない簡潔なFEは、深度に制限された簡潔なFEのかなり単純なラッパーです(後で説明します)。したがって、この投稿では、使用する簡潔なFEも深度に依存しないと仮定します。

次に、XiOです。

ジェネレーターは、単一ビット出力を持つ隠された関数(回路 (C))のパラメータを選択します。彼らはその関数のエンコーディングを生成します。このステップは、すべての可能な入力に対する (C) の評価、あるいはそれ以上の時間を許容されますが、出力は真理値表(すべての可能な入力に対する出力のセット)よりも小さくなければなりません。

評価者は、エンコーディングを評価して、任意の入力 (x) に対して (C(x)) を学習します。

XiOが設計されている関数のクラスは、ゼロ入力関数(別名「ソーク(thunk)」)として最もよく理解される関数であり、大きくて管理しやすいサイズの出力を生成します。ソーク (() \rightarrow X) が与えられた場合、それを関数 (i \rightarrow X[i]) として考えることができます。つまり、インデックス (i) を入力として受け取り、ソークのi番目の出力を返す関数です。これらは同じオブジェクトの2つの異なるビューです。この投稿では、これらのビューを定期的に行き来します。

例として、STARK(約128〜512KBサイズの暗号証明)を生成する関数を、インデックス (0 \le i \lt 2^{22}) を入力として受け取り、内部でSTARKを生成し、STARKのi番目のビットを出力する関数に変換することを想像できます。XiOの目標は、そのSTARKを生成することを可能にする、STARKよりも小さいガジェットであることです(ただし、STARK自体が既知のXiOプロトコルがそれを縮小するのを実際に許可するには小さすぎる可能性があることに注意してください)。

次に、簡潔なFEとXiOを組み合わせて、サブ線形コンパクトランダム化エンコーディングと呼ばれるプリミティブを作成します。

図: サブ線形コンパクトREの構築パイプライン

これを注意深く見ていきましょう。ここでの目標は、(P()) の「ランダム化エンコーディング」、つまり (P()) を実行可能にするガジェットを作成することです。これは、(P) の実行時間よりも漸近的に小さく、その出力よりも漸近的に小さく、かつ (P) を隠蔽するものです。

これは通常のランダム化エンコーディングの提示とは少し異なります。通常のものは (P(x)) 上で動作し、(x) を隠蔽しますが (P) は隠蔽しません(例:ガーブルドサーキットはこのように機能します)。しかし、これは私たちのユースケースに必要なものです。難読化は関数を隠蔽することがすべてです。

使用するプリミティブは関数を隠蔽しません。これを実現するために、これらのプリミティブが動作する「外側の」関数を仮想マシン(または「チューリングマシン」)にします。基本的に、回路を入力として受け取る関数 (VM) であり、(VM(P, X) = P(x)) となります。(VM) を評価する回路は、ユニバーサルサーキットと呼ばれます。このようにして、(P) は別の入力となり、プライベートにすることができます。

漸近的複雑性に関する1つのニュアンス:(VM) は回路としてインスタンス化される必要があり、回路のサイズは実行時間に比例する必要があります(回路はループを許可しないため)。したがって、(VM) 回路のサイズは、(P) の実行時間に比例する必要があります。幸いなことに、簡潔なFEは、回路が大きく深くても生成を高速にすることができます。しかし、出力は (P) のサイズにスケールするサイズと暗号化コストを持つ可能性があります。これが、(P) を回路以外の言語(チューリングマシンなど)で表現する必要がある理由です。そのサイズは、計算が大きくなっても固定される必要があります。

簡潔な機能的暗号化の信頼されたセットアップを行います。作成者は公開パラメータと (VM) の復号鍵を公開します。これにより、誰でも ((P, x)) を暗号化でき、他の誰でも (VM(P, x) = P(x)) を復号できますが、(P) や (x) を学習することはありません。

このランダム化エンコーディングを生成するために、作成者は言及した2つのプリミティブを内部でラップします。つまり、(VM(P, x)) の簡潔なFE暗号化のXiOを実行します。簡潔なFE暗号化は ((P, x)) を隠蔽し、(P) が実行に時間がかかる場合でも生成が高速です。しかし、簡潔なFEは出力圧縮ではありません。出力が大きい場合、簡潔なFE暗号化はさらに大きくなります(これはそのタイプの構築における避けられない制限です)。XiOはサイズを元に戻します。作成者は、簡潔なFE暗号化のi番目のビットを出力する回路 (C extsubscript{sfe}(i)) を作成し、それをXiOします。そのサイズは現在、プログラム (P) 自体よりも漸近的に小さく、生成時間も漸近的に高速です(「漸近的」に注意してください。小さいサイズでは、スキームのオーバーヘッドが支配的です。私たちが望む主な特性は、十分に大きい回路の場合、(xIO(sFE(VM(P, x))))) が ((P, x)) 自体よりもバイトサイズと生成時間の両方で小さくなるということです)。

ここで、難読化の最初のヒントが見えてきます。作成者自身が信頼されたセットアップを実行し、xIOを公開でき、他の人は実行されているプログラムを学習することなくそれを実行できます。しかし、大きな問題があります。これは1つの事前設定された入力に対してのみ機能します。

次に、最終的な難読化構築に進みます。

図: 難読化構築の再帰構造

基本的に、サブ線形コンパクトREプリミティブを取得し、それを再帰的に適用します。難読化しようとしている関数に入力されるビットの数で再帰します。ベースケース(ゼロ入力)では、サブ線形コンパクトREを上記のように使用します。1ビットを追加するために、2つの難読化を1レベル下で生成するプロセスをサブ線形コンパクトREでラップします。つまり、最初の入力ビットを (0) に固定して (P) を実行する関数 (P extsubscript{0}(x)) と、最初の入力ビットを (1) に固定して (P) を実行する関数 (P extsubscript{1}(x)) を難読化します。

サブ線形コンパクトREの2つのビルディングブロックの主要なプロパティを思い出してください。

  • XiOは、この難読化が生成する2つのサブ難読化よりも小さいことを保証します。
  • 簡潔なFEは、生成する2つのサブ難読化よりも生成が速いことを保証します。

両方のプロパティが必要であり、再帰が爆発しないことを保証します。

難読化されたプログラムを評価するには、トップレベルのREを評価して2つの新しい難読化(どちらも必要な入力ビットが1つ少ない)を取得し、入力の最初のビットに基づいて左または右を選択し、さらに再帰を続けます。最終的に、完全なパス (x) に対して (P(x)) を生成するソークに到達します。

ここで、何が起こっているのかを別の同等の方法で見ることができます。

図: 難読化のツリー構造

nビット入力を持つプログラムの場合、すべての可能な評価の深さn、サイズ (2^n) のツリーがあります。しかし、このツリーのほとんどの部分は決して評価されません。全体は「ソーク」のツリーであり、ツリーを作成する指数関数的なコストは、関心のある特定の入力へのパス上にないすべてのソークが決して実際にインスタンス化されないため、決して支払われません。インスタンス化される唯一のものは、各ステップでルートから入力へのパスに沿った難読化です。そして、非常に高レベルでは、それがすべてです。それがコアデザインです。

注意:元のLPST15およびLPST16の論文は、起こっていることを少し異なる(しかし同等の)方法で説明しています。それらは難読化自体を再帰させるのではなく、代わりに「ノードプログラム」を再帰させます。そのアプローチの1つの良い特性は、ノードプログラムが「これまでの入力ビット」をキャプチャするため、(P) 自体を操作またはラップする必要がないことです。彼らのバージョンでは、(P) はプロセス全体を通して変更されません。

上記の記述で省略されたもう1つの点は、難読化が安全であるためにはランダム化が必要であるということです。したがって、実際には (iO(P)) ではなく、(iO(P, seed)) です。ここで (seed) は、ガーブルドサーキットのようなプリミティブに必要な(疑似)ランダム性を生成するためにハッシュされる値です。ランダム化エンコーディング、XiO、および簡潔な機能的暗号化もすべて (seed) を引数として取ります。これらの関数が他の関数をサブルーチンとして呼び出す場合、サブルーチンのシードを自身のシードからのハッシュ経由で生成し、それぞれに一意の異なるシードを提供することに注意する必要があります。セキュリティ証明をクリーンにするために、ハッシュは技術的にはパンクチャブルPRFである必要がありますが、パンクチャされたバージョンを構築することは可能でありながら実際には実行されないという興味深い特性があります。

簡潔なFEスキームをどのように構築するか。

悪いニュース:簡潔なFEスキームは、互いに積み重ねられた複雑な構築の塔です。

良いニュース:これらの構築は比較的よく理解されており、非常に標準的な暗号学的仮定(「単なる」格子(lattices))を使用しており、簡潔なFEを構築するためのパイプラインは、おおよそ2014年から理解されています。

まず、図を示します。

図: 簡潔なFE構築のパイプライン

これらを一つずつ見ていきましょう。最も基本的な2つのビルディングブロックは、ガーブルドサーキットと完全準同型暗号です。

ガーブルドサーキット

ここでは、ガーブルドサーキットについてより詳細に説明しています。基本的な要約は次のとおりです。

  • サーキットの各ワイヤについて、0を表すラベルと1を表すラベルの2つのラベルを生成します。
  • 各ゲートについて、どの入力ラベルのペアがどの出力ラベルに対応するかを示すテーブルを公開します。このテーブルはラベルでソートされているため、どの入力ラベルがゼロに対応し、どれが1に対応するのかは不明です。
  • 出力ラベルは「クリア」では与えられません。代わりに、通常は入力のハッシュとXORされます。これにより、必要に応じて計算できますが、両方の入力ラベルを持っているブランチ以外のものについて何も学習することはできません。
  • 実行するには、入力に対応するラベルを取得し、サーキットを「たどって」最終的なワイヤの値(実際には値であり、単なるラベルではない)を決定する必要があります。

[画像: ガーブルドサーキットの概念図]

ガーブルドサーキットは安全に一度だけ実行できます。誰かに2つの入力のラベルを与えると、彼らは2つよりも多くの出力を計算できます。ガーブルドサーキットは、もともと2-of-2マルチパーティ計算プリミティブとして開発されました。私がサーキット (C) を持ち、あなたが (x) を知っている場合、私は (C) のガーブリングを送信し、各入力ワイヤについて、オブリビアス転送と呼ばれる技術を使用して、どちらのラベルがどちらであるかを知ることなく、2つの入力ラベルのうちの1つをあなたが学習するのを助けます。その後、あなたはサーキットをたどって出力 (C(x)) を計算します。

オブリビアス転送の基本的な大まかな説明:あなたは私に2つの公開鍵 (A) と (B) を送信します。これらはランダムなハッシュに合計される必要があり、1つだけが有効な秘密鍵を持つことができますが、私はどちらかわかりません。私は (A) で1つのラベルを、(B) で1つのラベルを暗号化します。あなたは私が秘密鍵を持っているラベルを復号しますが、私はどちらであるかを知ることはできません。

ここでは、2-of-2計算を行っているわけではありません。むしろ、ガーブルドサーキットを、簡潔なFEに必要なプロパティを取得するための構成要素として使用しています。ガーブルドサーキットには多くの有用なプロパティがあります。特に:

  • 入力に対するラベルを、入力を明らかにすることなく誰かに与えることができます。
  • ゲートごとの作業は並列であるため、(C) 自体が非常に深い場合でも、(C) のガーブリングを生成することは低深度です。

これらの両方のプロパティが重要になります。

ガーブリングはサーキットに関する一部の情報を隠蔽しますが、何かに意味のあるほど有用なほどではありません。関数を隠蔽する必要がある場合(例:2-of-2 MPCユースケース)、典型的な解決策はユニバーサルサーキット(または仮想マシン)をガーブルし、サーキットプロバイダーに実行したい実際のサーキット (C) を入力の一部となるラベルとして提供させることです。私たちのユースケースでは、関数に関する詳細をガーブルすることが漏洩しても気にしません。実際、まさにこの「VMでラップする」トリックを採用しているためです。

完全準同型暗号(FHE)

ここでは、FHEについてより詳細に説明します。詳細がこの投稿の他の構築にとって重要であるため、基本的な要約を提供します。

FHEは、学習誤差(learning with errors, LWE)と呼ばれる暗号学的仮定に基づいています。基本的に、ある数値を法とする線形方程式系(つまり、行列 (A)、ベクトル (s) と (b)、法 (q) で、(b = (As + e) % q) mod (q) となり、ここで (e) は「小さい」(つまり「低ノルム」)誤差ベクトルであり、(e) の各値は (q) よりもはるかに小さい)の近似解を持っている場合、(b) と (A) が与えられても (s) を抽出することはできません。正確な*方程式 (s * A = b) があれば、それは線形方程式系(mod (q))であり、ガウスの消去法で比較的安価に行うことができます。しかし、誤差が追加されると、この逆算は計算上実行不可能になります。

この仮定に基づいて構築された多くのFHEアルゴリズムがあり、それぞれ異なるプロパティを持っています。最も単純な考え方は、秘密鍵 (s) をランダムに選択し、ランダムな行列 (A) を生成し、単一ビット (m) の暗号化として (b = A * s + e + m * \frac{q}{2}) mod (q) を計算することです(ここで、ベクトルにビットを追加すると、その値がベクトルの各要素に追加されます)。

(A*s + e + m * q/2)

作成者はその後、この方法で計算された (0) と (1) の暗号文を公開できます。復号するには、(b - A * s) を計算できます。これは (e + m * \frac{q}{2}) に等しくなります。高位のビットがメッセージをエンコードし、低位のビットが誤差をエンコードしており、これは破棄できます。2つの暗号文 (b extsubscript{1}) と (b extsubscript{2}) がそれぞれ (x extsubscript{1}) と (x extsubscript{2}) の有効な暗号文である場合、(b extsubscript{1} + b extsubscript{2}) (ここでもすべて mod (q))は (x extsubscript{1} + x extsubscript{2}) の有効な暗号文です。

上記の設計では、メッセージスロットに単一ビットだけでなくベクトルのビットを暗号化できることがわかります。しかし、上記の設計では実際にはサポートされていない1つの重要なことがあります。乗算です。

乗算は加算よりもトリッキーです。いくつかの理由があります。第一に、2つのベクトルを互いに乗算してベクトルを得ることはできません。行列や多項式のような他の構造に対してのみ可能です。第二に、3項値 (A * s + e + m * \frac{q}{2}) を2つ加算すると別の3項値が得られますが、3項値を2つ乗算すると9項値が得られるため、形状の異なるものが得られます。第三に、最終的に「小さい」誤差を「大きい」他のものに掛け合わせることになり、1回の乗算ラウンド後に誤差が爆発します。

これに対する単一の簡単な解決策はありません。解決策のファミリがいくつかあり、すべて異なる欠点があります。多項式を使用するものは、Ring LWEと呼ばれるより強力な仮定に基づいています。一般的に使用されるスキームはBFVです。FHEの使用に最も便利なスキームは行列に基づき、GSWと呼ばれます。その仕組みを示すために、まず基本的な算術を機能させる単純化されたバージョンを示しますが、誤差の問題を処理しないため、誤差がゼロでない場合は破損します。

まず、秘密 (s) を生成します。値を暗号化するには (m)、まずランダムな行列 (A) を生成します。ここで (s * A) は「小さい」または「低ノルム」の誤差 (e) に等しくなります。これを実行する1つの方法は、両方を2つの部分に分けて生成することです。

  • ランダムな (s extsubscript{prefix}) を生成し、(s = (-s extsubscript{prefix} | 1)) ((|) は連結)と設定します。
  • ランダムな (A extsubscript{prefix}) とランダムな低ノルム誤差 (e) を生成し、(A = ({{A extsubscript{prefix}} \atop {s extsubscript{prefix} * A extsubscript{prefix} + e}})) (これは垂直連結です)と設定します。

図: GSWの行列構造

次に、(c = A + m * I) (ここで (I) は単位行列)を計算します。そして、暗号文を復号するには、((s * C)[-1]) (つまり、(s * C) の最後の値)を読み取ります。

図: GSWの復号プロセス

数学者であれば、(m) を (C) の固有値(正確には誤差付き固有値)に「隠して」いることに気づくかもしれません。(s) は固有ベクトルであり、(s * C \approx s * m) を満たします。それらは厳密な固有ベクトルと固有値ではありません。誤差付きの固有ベクトルと固有値です。しかし、まず誤差を脇に置いて、固有値が特別な理由となるいくつかのプロパティに注目しましょう。

暗号文の加算は再び簡単です。もし

(C extsubscript{1}) が ((s * C extsubscript{1})[-1] \approx m extsubscript{1}) を満たすなら

(C extsubscript{2}) が ((s * C extsubscript{2})[-1] \approx m extsubscript{2}) を満たすなら

(C extsubscript{1} + C extsubscript{2}) は ((s * (C extsubscript{1} + C extsubscript{2}))[-1] \approx (m extsubscript{1} + m extsubscript{2})) を満たします。

しかし、以前とは異なり、暗号文の乗算もできます。もし

(s * C extsubscript{1} \approx s * m extsubscript{1})

(s * C extsubscript{2} \approx s * m extsubscript{2})

ならば

(s * (C extsubscript{1} * C extsubscript{2}))

(= (s * C extsubscript{1}) * C extsubscript{2})

(\approx m extsubscript{1} * s * C extsubscript{2})

(\approx m extsubscript{1} * m extsubscript{2} * s)

固有値は、基本的に、このようにも加算および乗算プロパティを持つ行列の唯一の属性であり、そこでも同じ固有ベクトルを持つ行列に制限しています。

さて、誤差許容度を戻しましょう。上記の方法は、そのままでは致命的な欠陥があります。誤差を含む完全な方程式を書き出すと、誤差を行列 (C) と (s) の要素に掛け合わせることになり、これらは ([0, q-1]) の全範囲にわたる可能性があります。したがって、これはすぐに誤差を最大まで爆発させます。さらに、復号さえ誤差を許容できません。

最初の穴を塞ぐために(2番目の穴については最後に戻ります)、実際のGSWはガジェット行列メカニズムに依存します。

ガジェット行列の外観は次のとおりです。

図: ガジェット行列

これだけでは良さそうに見えますが、あまり意味がありません。しかし、それはキャンセルアウトする操作(行列ではない)とペアになることを意図しています。それが行列ビット分解操作です。

図: 行列ビット分解

この操作((G^{-1}) と呼びます)の出力の隣接する4つの値はそれぞれ、入力の対応する値の(最下位ビット優先)バイナリエンコーディング(つまり、ビット分解)です。

(G) と (G^{-1}) に関する最も重要な事実は次のとおりです。

  • (G^{-1}) の出力は「低ノルム」(すべて小さい値)です。
  • (G * G^{-1}(x) = x)、任意の (x) に対して。

後者は直感的に確認できます。例の2(0 1 0 0)のハイライトされたビット分解を計算全体で追跡すると、ガジェットの 1 2 4 8 に掛け合わされ、結果は ((0 * 1) + (1 * 2) + (0 * 4) + (0 * 8) = 2) になります。つまり、ガジェット行列をビット分解に適用すると、ビット分解を「評価」して元の値に戻します。

単純化された説明で単位行列((I))を使用した箇所では、実際のプロトコルでは (G) を使用します。つまり、暗号文は (A + m * G) の形式です。2つの暗号文を (C extsubscript{1} * G^{-1}(C extsubscript{2})) を計算することによって乗算します。メッセージは、もはや厳密には誤差付き固有値ではないものに隠されていますが、必要なプロパティは維持されています。代数は同じように機能しますが、誤差が大きな数に掛け合わされることはないため、乗算は実際に機能します。具体的には:

  • 暗号化:(C = A + m * G)
  • 復号:(\frac{(s * C)[-1]}{q / 2})
  • 加算:(C extsubscript{1} + C extsubscript{2}) (当然)
  • 乗算:(C extsubscript{1} * G^{-1}(C extsubscript{2}))

復号における1つの微妙な点に注意してください。(G) の最後の列には、唯一の非ゼロエントリとして (\frac{q}{2}) が含まれており、(G) を掛けると (m * \frac{q}{2} + e) ((m + e) ではない)を含むオブジェクトが得られます。これが復号における誤差許容度をもたらします。また、暗号化時に (\frac{q}{2}) で割っている理由もこれです。この方法では (q) が2のべき乗である必要があります。必要であれば、(q) を別の値にすることもできますが、これには復号手順のわずかな調整が必要です。

乗算の正しさを確認できます。まず代数から始めます。加算について:

(C extsubscript{1} = A extsubscript{1} + m extsubscript{1} * G)

(C extsubscript{2} = A extsubscript{2} + m extsubscript{2} * G)

次に乗算について:

(C extsubscript{1} * G^{-1}(C extsubscript{2}))

(= (A extsubscript{1} + m extsubscript{1} * G) * G^{-1}(C extsubscript{2}))

(= A extsubscript{1} * G^{-1}(C extsubscript{2}) + m extsubscript{1} * G * G^{-1}(C extsubscript{2}))

(= A extsubscript{1} * G^{-1}(C extsubscript{2}) + m extsubscript{1} * C extsubscript{2})

(= A extsubscript{1} * G^{-1}(C extsubscript{2}) + m extsubscript{1} * A extsubscript{2} + m extsubscript{1} * m extsubscript{2} * G)

ここで、最初の2つの項がどちらも元の (A extsubscript{1}) と (A extsubscript{2}) と同じように有効な「パディング」であることを示す必要があります。必要な中心的なプロパティは、(s * A) を掛けると、小さい低ノルム誤差のみが残ることです。

2番目の項は簡単です。(A extsubscript{2}) は有効なパディングです((s * A extsubscript{2}) は低ノルムです)。そしてそれを小さい (m extsubscript{1}) で掛け合わせるので、(m extsubscript{1} * A extsubscript{2}) も低ノルムであり、したがって有効なパディングです。

最初の項について、(s * A extsubscript{1} * G^{-1}(C extsubscript{2})) を展開してみましょう。(s * A extsubscript{1}) は「小さい」誤差を返します。(G^{-1}(C extsubscript{2})) は1と0の行列を返します。したがって、(s * A extsubscript{1} * G^{-1}(C extsubscript{2})) は、1と0の行列に掛け合わされた小さい誤差であり、依然として小さい誤差です。

2番目のパディングの誤差はメッセージ空間のサイズ(つまり、0または1)によって約爆発します。最初のパディングの誤差は行列のサイズによって爆発します。したがって、各乗算は誤差を定数倍だけ爆発させるため、誤差が高くなりすぎる前にFHEが耐えられる乗算回数を予測できます。その時点で、ブートストラップによって誤差をリセットする必要があります。つまり、FHE内でFHE復号回路を評価します。

最後に、もう1つのニュアンスがあります。誤差の爆発を制限するには、メッセージを小さく保つ必要があります。具体的には、0または1である必要があります(-1や2なども受け入れることができます)。加算と乗算はサイズの制限を尊重せず、BGVとは異なり、ここにはネイティブな「ラップアラウンド」モジュロ2がありません。したがって、上記アルゴリズムを安全にするには、次のように実装された「論理ゲート」を持つ回路を使用する必要があります。

  • (AND(a, b) = ab)
  • (OR(a, b) = a + b - ab)
  • (XOR(a, b) = a + b - 2ab)
  • (NOT(a) = E extsubscript{1} - a) ここで (E extsubscript{1}) は1の暗号文です。

これはその方法の1つにすぎません。最適ではありません。より効率的に行う方法があり、それがFHE最適化の技術の一部です。

ここに、このスタイルのGSWに沿ったPythonコードの一部があります。ただし、(A * R) が「パディング」であるという少し異なる技術を使用していることに注意してください(これは上記のすべてのプロパティに加えて、後で必要となる追加のプロパティを持っています)。https://gist.github.com/vbuterin/f0f8a9eb09633226ada20c21a98d537e

この種のFHEを試してみる価値があります。なぜなら、後で使う他のプリミティブのいくつかに直感を与えるのに役立つからです。

さて、次に進みましょう。

属性ベース暗号(ABE)

[画像: 属性ベース暗号の概念図]

このAbeではない。