はまやんはまやんはまやん

hamayanhamayan's blog

CTFのCryptoにおける高機能暗号まとめ [秘密分散, ゼロ知識証明, ZKP, 準同型暗号]

Security

CTFにおけるCrypto入門とまとめの1つです。

高機能暗号

  • 高機能暗号: 暗号化・復号化以上のことができる暗号方式の総称
    • 秘密計算: ある暗号文から別の暗号文が作成可能であり、暗号化された平文に対する演算を暗号文のまま行える
      • 準同型暗号
    • ゼロ知識証明
    • 秘密分散
    • グループ証明
      • ユースケース: プライバシー観点から、ある権限を所有しているｋとおのみを証明できれば十分な時に使える
    • IDベース暗号
      • PKIを使った鍵運用はコストが高いので、個人の公開性の高い識別子ID（メールアドレスやユーザー名）を利用した公開鍵暗号方式
      • 楕円曲線上のペアリングが使えるらしい
      • Boneh-Franklin IDベース暗号
    • 検索可能暗号
      • NICTによるESKS(:Encrypted System with Keyword Search)
    • 低遅延暗号、ハイスループット暗号: 高速なリアルタイム通信の世界で暗号処理がボトルネックにならないように
    • 視覚的・物理的暗号技術: 産総研を中心とした研究グループが開発しているもので、視覚的に物理的に高機能暗号を示すことでアルゴリズムの「分かりやすさ」を知ってもらうための暗号（つまり、実用性を求めたものではない?）
      • カードベース暗号
    • IETF(:Internet Engineering Task Force)でも高機能暗号の標準化について議論がなされている
      • Crypto Forum, Privacy Pass WG, Privacy Preserving Measurement WGなど
    • 秘匿検索: 検索クエリは隠したまま、検索結果のみを得る
  • TEE: CPUの標準機能を使用して作成されたセキュア領域で安全に処理する仕組み
  • EAGLYSさんのQiitaに日本語解説が大量にあって助かる

秘密計算

  • 秘密計算: Secure Computation、各自の入力データは秘密にしたまま、必要な情報のみを得る技術
    • 秘密分散方式、秘密分散＋MPCベース
    • 準同型暗号方式、完全準同型暗号ベース
      • 加法準同型暗号 Enc(m) + Enc(n) = Enc(m + n)
      • 乗法準同型暗号 Enc(m) * Enc(n) = Enc(m * n)
      • 完全準同型暗号: 加法かつ乗法準同型暗号、かつ、この加法と乗法を任意の回数実行可能
  • マルチパーティ復号 / MPC: マルチパーティ計算
    • fのMPCプロトコル: n人の参加者（パーティ）P0, P1, ..., Pn-1がそれぞれ秘密情報xiを持ち、その情報の他のパーティに秘匿しながら全員で強調計算を行いf(x0, x1, ..., xn-1)を計算すること
    • 秘密計算の暗号学的なモデルのうち、一般的なもの
    • MPCにおける安全性
      • 正当性：パーティがプロトコルに正しく従った際には結果が正しく出力される
      • 秘匿性：条件Xの元で（攻撃者のシナリオらしい）攻撃者が攻撃を行った際に、プロトコルの実行によって、攻撃者でないパーティの情報が関数の出力を超えて漏れない
    • 攻撃者のシナリオについて
      • 計算能力観点：計算量的な攻撃者と情報理論歴な攻撃者に大別され、秘匿性を評価できる
        • 計算量的安全性：計算に凄い時間がかかることを前提とした安全性
        • 情報理論的安全性：無限の計算能力を持っていると仮定しても、攻撃者が得られる情報と秘密情報の確率的独立性（つまり、1/2で正解だし、1/2で不正解的なことだと思う）をもって安全性を保証できる。無条件安全性とも呼ばれる
      • 攻撃者の振る舞い：受動的な攻撃者、能動的な攻撃者
      • 攻撃者の人数：正直者多数、不正者多数
        • 正直者多数であれば、任意の関数fを情報理論的安全に構築可能であることが証明されている
        • 逆に、不正者多数だと、ある関数fは情報理論的安全に構築できない（こっちは「ある」であることに注意。一部は作れる）
    • MPCプロトコルの評価軸
      • 通信量：必要なデータ通信量
      • ラウンド数：必要な通信の回数。MPCでは「各パーティでのローカルでの計算→パーティ間の通信」の1ステップを何ラウンドか行う
      • 計算量：必要なローカルでの計算量
  • ブラインド署名 / 部分ブラインド署名

秘匿共通集合計算 PSI : Private Set Intersection

  • あるデータの2つの集合に対して、お互いに何を持っているのか秘密にしたまま共通する要素を特定する
  • ブラインド署名によって実現するアルゴリズムがある

https://qiita.com/SenK/items/a4b6191e44d2226844ec

紛失通信: Oblivious Transfer

https://qiita.com/SenK/items/f8249193d335e78d3333 https://hackmd.io/@theoldmoon0602/BJ3qRgRz_

  • OT: Oblivious Transfer, 紛失通信
    • 送信者が送信したデータのうち、受信者がどれを受信したのか、送信者が知ることができない
  • Rabin-OT
    • ラビン暗号を使い、紛失通信路をシミュレートするもので、1/2の確率で相手にメッセージが届き、残りの1/2の確率でメッセージが一切届かない
  • 1-out of-2 OT
    • 送信者が2つのメッセージを送信し、受信者はその片方のみを受信できる。送信者は、受信者がどちらのメッセージを受信したか分からないタイプのOT
    • これを拡張することでn個のメッセージのうちk個を受信するk-out of-n OTが構成できる
  • GC: Garbled Circuit

カードベース暗号

  • カードベース暗号: トランプカードのような物理的なカード組を使って秘密計算する
    • コミットメント: とある1bitの変数xを♣と♡のカードの組で表現したときこの2枚をxのコミットメントと呼ぶ
      • ♣♡ -> 0, ♡♣ -> 1
    • 形式的に表現する際の操作
      • turn i: i番目のカードをひっくり返す
      • perm (a1, a2,...): 与えられた巡回行列に従ってカードを入れ替える
        • ランダムカット: 1列に並んだカードを巡回的にシャッフルする。perm (1 2 3 ... n)
      • shuf {a, b, ..}: 与えられた巡回行列のいずれかをランダムに選択してカードを入れ替える
  • ファイブカードトリック: ANDの秘密計算
    1. 秘密にしたい入力a,bのコミットメントを裏にして2組用意して♡で挟んだa♡b、つまり??♡??を用意する
    2. 左側のコミットメントを逆にする
    3. 中央の♡を裏返す?????になる
    4. ランダムカットする
    5. 全部のカードを表にしたときに、3枚の♡が巡回的に並んでいれば結果はa and b=1であり、それ以外はa and b=0である
  • コミット型プロトコル: カードベース暗号による計算の結果がコミットメントとして得られる
    • つまり、and(a,b) = cのようにaとbのコミットメントを与えると、cのコミットメントが得られる。これにより出力されたコミットメントをまた次の計算の引数に使うことができ、コミットメントをIFとした連鎖的な計算が行える
    • コミット型ANDプロトコル
    • コミット型XORプロトコル
    • コピープロトコル: とあるコミットメントxを2つに複製可能
    • コミット型NOTプロトコル
    • コミット型ORプロトコル
  • 金持ち比べプロトコル（大小比較を秘密計算する）
    • （カードベース暗号ではないが）Yaoの金持ち比べ
    • カードベースの金持ち比べ
  • 考察
    • カードベース暗号ってどのくらい実用的なんだろう。数式を使わない（計算機がいらず、物理的に計算可能）という点で有意性はありそうだが、bit数に対して必要なカードが多そうで物理的なカードを使った実用性はあまりなさそうで、これをモデルとして計算機でやらせるとうまくいくということがある？
  • 参考

準同型暗号

  • https://nindanaoto.github.io/
  • スキームの核
    • 鍵生成
    • 暗号化
    • 評価: 暗号文に対する直接計算（暗号文のまま計算）
    • 復号
  • スキーム
    • PHE: 部分準同型暗号。足し算か掛け算のどちらかをサポート
      • 乗法準同型暗号: RSA、ElGamal
      • 加法準同型暗号: Paillier暗号、岡本・内山暗号
    • SHE: サムホワット型準同型暗号。加法ができ、乗法のみ演算回数に制限がある
      • 例：Boneh–Goh–Nissim暗号、格子暗号の一部
    • Leveled FHE: Leveled完全準同型暗号。鍵生成時に決定される一定数のオペレーションをサポート
    • FHE: 完全準同型暗号。無制限の加算と乗算をサポート
      • 秘匿マルチパーティ計算（SMPC）を促進
      • 例：Gentryによる格子暗号ベースの完全準同型暗号
  • TenSEAL: 準同型のまま計算するライブラリ

FHE: Fully Homomorphic Encryption 完全準同型暗号

  • FHE: Fully Homomorphic Encryption 完全準同型暗号
    • 暗号化されたまま無劣化で（つまり何度も）計算が可能
    • FHEは、暗号に基づく暗号と多項式演算の数学的原理に基づく
  • 「ノイズ」暗号化されたメッセージに意図的に導入されたランダムな要素
    • ノイズにより、セキュリティが保証される
    • ノイズは暗号化された値に対して計算が行われるたびに増加（加算よりも乗算の方が顕著）し、ノイズが大きくなりすぎると、平文を破損してしまう
    • ブートストラッピング: 暗号文のノイズを大幅に低減することで、FHEにおいて無限に計算できるようにするもの
      • 種類: ゲートブートストラップ、ファンクショナルブートストラップ、プログラマブルブートストラップ

  • FHEスキーム

    • 多項式の環を使う方式: RLWE: Ring Learning With Errors。R=Z[x]/(xn+1)を使う。主流
      • 現代の実装（SEAL, HElib, PALISADE など）は、ほぼ全てRLWE系を使っています
      • R=Z[x]/(xn-1)というのは、xn=-1とすることで、多項式を折り返した多項式の環のこと
      • BGV/BFV: 正確な算術演算に適した、高精度な方式
        • BFV: 整数用のFHE方式。多項式の次数、平文の法、暗号文の法を暗号化パラメタとして持つ
      • CKKS: 近似演算に最適化
        • CKKSノイズ（暗号演算に含まれる微小な丸め誤差）
        • m0leCon CTF 2026 Teaser - One More Bit
          • CKKSノイズの影響を統計的に見ることでサイドチャネル的に平文の情報が漏えいする。
    • LWE系が別であるらしい
    • 整数ベース, 初期のGentryのFHE。イデアル格子を使う。非常に遅いので使わない。
    • TFHE: Boolean circuitや小さなデータ項目に対するルックアップテーブルとして表現可能な関数に対して効率的

  • 資料

TFHE

https://qiita.com/dkawabe/items/06195c94c434106f8cc5

  • TFHE: Torus上のFHE(完全準同型暗号)
  • Torus: 0以上1未満の実数の集合、ただし、整数部分は無視する（1の加法減法は無視する）
    • 厳密には、実数体を整数環で割った商加群らしい
    • 0.1 = 1.1 = 2.1 = ... みたいな感じ
    • 0.3 + 0.8 = 1.1 = 0.1 みたいな感じ
    • 加法・減法は作れるが、乗法除法は定義できない
  • TFHEでは、f: T -> T を任意の一次関数として変換する暗号

秘密分散

https://qiita.com/SenK/items/33ce4cbf2fee23df95ec https://www.jstage.jst.go.jp/article/isciesci/63/2/63_71/_pdf

SSS: シャミアのしきい値法, Shamir's Secret Sharing

秘密分散ベースのMPC

  • BGW方式: Shamirの秘密分散に基づくMPC
    • 正確には線形秘密分散であるShamirの秘密分散に対して乗算を実現する方式
    • また、BGW方式を簡略化したGRR方式もあり、現在においてはBGW-typeと呼ばれる方式はGRRを指すことが多い
    • あまりちゃんと読めていないが、Bootstrapping（特定の復号回路を準同型演算でシミュレートするｋとおで、別の鍵の暗号文に乗り換える）というテクを使うらしい
  • 複製型秘密分散に基づく方法
    • 3パーティでしか使えないっぽい？
  • Beaver Tripleに基づく方法
    • multiplication tripleと呼ばれる事前計算されたデータを用いるほうほう
    • SPDZフレームワークを用いる方法: 加法型秘密分散に基づくMalicious安全な秘密計算手法で、準同型暗号を用いてmultiplication tripleを事前計算する
    • 補助クライアントを用いる方法: クライアントが秘密情報をn台のサーバに秘密分散して入力し、結果のシェアだけを受け取り、クライアント上で結果を復元する？

ゼロ知識証明 ZKP: Zero-Knowledge Proof

zk-SNARK, zk-STARK

  • STARK: Scalable Transparent ARguments-of-Knowledge, 以下を満たすような証明システム
    • Scalable: 証明時間がほぼ線形で、検証時間が対数の多項式時間
    • Transparet: トラステッドセットアップが存在しない（シークレットや認証局のようなtrust anchorなどが不要）
    • Arguments of Knowledge, Lean Cryptography?: 証明者の能力が確率的多項式時間チューリングマシンで実行可能
      • 安全な暗号と衝突体制のあるハッシュ関数の存在という、最小限の暗号的仮定のもと動く
        • ここに量子耐性が求められる？
    • STARKが多くのSNARK実装と比べて優れている点として、ハッシュ関数の存在以外には暗号学的な仮定を必要としないという点がある。
    • arithmetization 算術化
      • STARKプロトコルの最初のステップで、計算の検証の問題を「多項式が低次であることを確認する問題」に変換する。縮約とも言う
      • 更に2つの要素に分かれる
        • 実行トレース: 検証するのに必要な計算過程のこと
        • 多項式制約: 実行トレースが満たすべき制約を方程式の形で書き下したもの
        • つまり、実行トレース全てが多項式制約にのっとっていることを確認することで検証を行う
      • ちなみに実行トレースが複数の列になる場合は多項式制約が増えることになるが、その場合も最終的には単一の多項式に集約して、低次チェックを行うことになる
  • 分かりやすい資料

FRIプロトコル

  • FRI(Fast Reed-Solomon IOP)プロトコル、低次テスト（多項式が指定された次数以下であることを証明する）のための効率的な暗号学的プロトコル
    • 証明者: 多項式f(x)の次数がd以下である多項式を所有していることを証明したい
    • 検証者: 多項式が分からない状態で、証明者に点の値を要求することで、d以下の多項式を持っていることを証明したい
  • naiveな方法（FRIプロトコルではない）
    • 行えるクエリを「検証者が証明者にランダムな点を要求する」と定義する
    • クエリをd+2回行い、それを元に（多分ラグランジュ補間とかで）多項式を復元したときに、d次以下の多項式があるかを確認する
      • d+1次のものがあれば、d以下を満たさない
    • この方法だとクエリ複雑性はd+2
    • クエリの方法を工夫して、より効率的な方法はないだろうか
  • FRIプロトコル
    • クエリの方法をd+2からlog(d)程度に減らすために、分割統治法とクエリの工夫を行う
      • 分割統治法 -> 1つの多項式の次数がd以下である証明 → 2つの多項式の次数がd/2以下である証明 に変換
      • クエリの工夫 -> 複数の多項式の次数チェックを1度に行えるようにする。証明者支援型で低次テストするタイプ
  • 分割統治法: d未満の次数を持つ1つの多項式を、d/2未満の次数を持つ2つの多項式に変換する
    • f(x)をd未満の字図うの多項式として、dを偶数とする（奇数でもいい感じにできるっぽい）
    • f(x)=g(x2)+x・h(x2)と分割する。g(x)はf(x)の偶数係数から得られる多項式で、h(x)は奇数係数から得られる多項式
      • 具体的にはf(x)=a + bx + cx2 + dx3 + ex4 + fx5であれば以下のように分割する
        • g(x) = a + cx + ex2
        • h(x) = b + dx + fx2
  • クエリの工夫: 2つの多項式f,gがあり、両方の次数がd未満であることをテストする
    1. 検証者 -> 証明者: 体からランダムな値αを取って送る
    2. 証明者: クエリ処理の際に、h(x)=f(x)+αg(x)を結果として返すことにする（ここでMerkle木が出てくるらしい）
    3. このクエリを使って、h(x)の次数がd未満であると判定できれば、f(x)もg(x)も次数はd未満
      • 2つの多項式を足すと結果の次数は2つのうち大きいものになるので直感的には正しそう
      • αでかけて足すことで次数が最も高いxnの係数が足してゼロになる可能性があるが、これは体が十分に大きい場合は確率的に無視できるほど小さくできる
      • 他にも観点があるが、確率的には小さくできて実用上は問題無さそう
      • また、悪意ある証明者の考察もされているが、サンプル数を増やすことで見破れるらしい
  • 参考

PLONKプロトコル

Fiat-Shamir変換 フィアット・シャミール変換