2021-02-16

2/16日記

しばらく更新がなかったので、日記にします。

今日やったことは

新宿rsに参加しました。

forcia.connpass.com

ぶっちゃけlogの話以外は知識が弱くてRust以外のところはよく分からなかったのですが、設計思想とかRustのクレートの話が聞けて楽しかった！次も参加予定。いつかネタが出来たら登壇してみたい。あと、懇親会でのas usize面倒な問題に対する議論が楽しかった。Language Serverで解消するというのは全然発想がなかった。

ポートフォリオサイトのアプデ

５０００兆年 as 半年ぶりにアプデをしました。

senk8.github.io

加えたのは上のようなQiitaの投稿取得機能です。Vue.jsからaxios使ってAPIにリクエストさせてます。通信がボトルネックになって、ページを開いた瞬間にDOMの要素が配置されきらない問題が発生している。ページローダーを加える必要があるか？あと、ZennでもAPIが使えるようになったら嬉しい。

アイコン更新

久しぶりにイラストを書きました。

プロセカは小豆沢がナンバーワン、異論は認めない。ビビバスに情緒と財布を破壊されたオタクでした。

おわり

2020-10-22

対話証明系のモチベーション

ゼロ知識証明はもともと対話証明系というモデルから生まれた。この記事は基礎に立ち返って、対話証明系からゼロ知識証明の歴史を探ってみる。なお、ここで示している対話証明はゼロ知識ではないので、検証者に証拠などを提出してもよい。

NP証明系

対話証明（IP）というのはおおざっぱにいえばNPを確率的にした問題のクラスである。クラスNPに属する言語は以下のように定義されていた。

問題に対する証拠wが与えられたとき、その証拠wが本当に正しいかどうかを多項式時間で判定できる。

これを別の言葉で言い換えると、NPは「問題を多項式時間で解くことは出来ないが、その証拠wが与えられた時、多項式時間で検証できるような多項式時間検証器Vが存在する問題のクラス」と言い換えられる。

これを証明者Pと検証者Vから定義される証明に簡単に拡張できる。

まず、無限の計算能力を持つ証明者Pと多項式時間の検証者Vがいて、証明者Pが証拠wを持っている。証明者Pは検証者Vに証拠wがあることを納得させたい。
PはVに証拠を渡し、Vはそれを多項式時間で検証する。

NPの定義よりVは証拠があれば多項式時間で検証できる。ここで

証明者が無限の計算能力なのは、証明を見つけるのに時間がかかるから
検証者が多項式時間なのは、多項式時間でなければNP問題を解けてしまうから

有名なグラフ同型問題で考えてみよう。wikipediaだがグラフ同型問題について詳しく書いてある。

ja.wikipedia.org

対話証明では２つのグラフが同型であることを示したい場合、そのグラフの同型写像が存在すること示せばよい。ゼロ知識ではないので証拠を示せば証明は簡単に終わる。

f:id:ATen:20201022002227p:plain — グラフ同型問題

これを多項式時間検証器VがNP証明系を定義するという。これはNPというクラスを違う視点から見た結果にすぎない。

対話証明系

NP証明系は検証手順を

「証明者からもらった証拠で問題が正しいか検証する」という決定的なアルゴリズム

に限っている。これを確率的なアルゴリズムに拡張することで高い表現力が得られると思われる（ここで「思われる」とあるのはNPがIPの真部分集合か明らかではないから）。

NPを自然に確率的なアルゴリズムに拡張したものをIP(対話証明)という。

この対話証明では証明にコイン投げと対話を許すことで確率的な証明を行う。実際にグラフ非同型問題を $IP$ で受理できることを示す。

グラフ非同型問題のプロトコル

グラフ非同型問題はco-NP問題に属する問題である。co-NP問題は

NP問題の否定問題で、現状NP問題に属しているかどうかは明らかでない。そのco-NP問題であるグラフ非同型問題は、NPに含まれない（と予想されている）のでNP証明系で証明することはできない。

実際に「非同型である」ことを証拠一つで証明するのは難しそうである。同型問題あれば、同型写像を一つ示せばよかったのだが。

ここで対話証明が活躍する。対話証明は一回で証明を終えるのではなく、何回かの対話の中で検証者を納得させればよい。ここで証明者と検証者の共通入力をグラフ $G _ 0=(V _ 0,E _ 0)$ とグラフ $G _ 1=(V _ 1,E _ 1)$ とおく。

検証者は $a=0$ か $a=1$ を選ぶ。その後、 $G _ a$ と同型なグラフ $G'=(V',E')$ を証明者に送る。
証明者は $G'=(V',E')$ を受け取ったら、検証者が $(G _ 0,G _ 1)$ のどちらと同型なグラフを送ってきたか判定する。 $G _ 0$ なら $b=0$ を、 $G _ 1$ なら $b=1$ を送る。
検証者は $a=b$ なら、1を出力する。そうでなければ0を出力して停止する。

ここで以下の点に注意してほしい。

2で $(G _ 0,G _ 1)$ がもし非同型なら、どちらと同型なグラフを送ってきたか特定できる。
検証者はこの処理を十分な回数繰り返して、停止しなければ初めて証明を受理する。非同型でないのに受理される確率は、何度も繰り返せば限りなく低い確率になる。

なお、検証者は $a$ をランダムに選択しなければならない。ランダムでなければ、検証者の行動が予測可能になるからである。検証者が乱数を返すようにすれば証明者は多くとも1/2の確率でしか騙せない。

対話証明のポイント

以下は対話証明の２つのポイントである。

確率的にすると、決定性アルゴリズムと比べると表現力が上がる。しかし、検証者は確率的になるので必ず正しい結果を返すわけではない。
対話的にすると、確率的アルゴリズムの欠点である「検証者が必ず正しい結果を返すわけではないこと」を解消できる。検証者が必ず正しい結果を返さなくても1/2より高い確率で正しい返答をしていれば、いつか証明は限りなく正しいものになる。

IP(Interactive Proof)

そして、上の対話証明が可能な言語のクラスをIPという。IPは以下のように定義される。

次の条件を満たす多項式時間関数Vと関数Pが存在し、多項式回の対話で証明が可能なら言語LはIPに属する。

$x\in L$ の時に $Pr[V=1]\geq 2/3$
$x\notin L$ の時に $P[V=0]\geq 2/3$

ここで $2/3$ となっているが、究極には $1/2$ より大きければよい。IPはNPに含まれていないとされるグラフ非同型問題のようなco-NP問題の証明に利用できるほど強力であり、 $NP\subseteq IP$ であることが知られている。さらにIPにおける重要な事実として

$IP=PSPACE=CZK$

がある。ここでPSPACEは多項式領域で計算できる問題のクラスであり、CZKは計算量的ゼロ知識証明が存在する言語のクラスである。（計算量的ゼロ知識証明というのは後に解説する予定） $NP\subseteq IP$ であることから $NP\subseteq CZK$ でもある。これはNP問題には必ず（計算量的）ゼロ知識証明が必ず存在するという驚きの事実である。

まとめ

この記事ではIPについて説明した。次の記事ではゼロ知識証明そして、知識の証明について解説する予定である。

参考文献

Oded Goldreich (原著), 岡本龍明, 藤崎英一郎(訳)　現代暗号・確率的証明・擬似乱数 2001 シュプリンガー・フェアラーク東京
岡本龍明, 山本博資　現代暗号 1997 産業図書
岡本龍明、太田和夫　暗号・ゼロ知識証明・数論　1995 共立出版
Michael Sipser（原著）、太田和夫、田中圭介（監訳）、阿部正幸、植田広樹、藤岡淳、渡辺治（訳）　計算理論の基礎[原著第２版]　3.複雑さの理論 2008　共立出版

2020-10-09

検証可能な暗号、Camenish−Shoup暗号

Encryption Scheme

以下の記事で紹介した論文に登場したCamenish-Shoup暗号について紹介する記事です。

tenn.hateblo.jp

Camenish-Shoup暗号

検証可能な暗号化と復号が行える暗号方式であり、Crammer-Shoup暗号とPailier暗号を合わせたような形をしている。Crammer-Shoup暗号は検証可能な復号機能を持っており、適応的選択暗号文攻撃（IND-CCA2）である方式だが、暗号化は検証可能ではなかった。Camenish-Shoup暗号では暗号機能とは独立したΣプロトコルを用いることで暗号化の正当性を証明する。また、加法準同型性を持つ。

方式

鍵生成

ソフィージェルマン素数とは $2p'+1$ も素数であるような $p'$ のこと。このとき、 $2p'+1$ は安全素数という。

2つのソフィージェルマン素数 $p',q'$ をランダムに選ぶ。ここで $p'\neq q'$ である。
$p:=(2p'+1),q:=(2q'+1),n:=p\cdot q,n':=p'\cdot q'$ を計算する。
$x _ 1,x _ 2,x _ 3 \in _ R [n ^ 2 / 4$ ]、 $g'\in _ R \mathbb{Z} ^ * _{n ^ 2}$ をランダムに選ぶ。
$g=(g') ^ {2n},y _ 1=g ^ {x _ 1},y _ 2=g ^ {x _ 2},y _ 3=g ^ {x _ 3}$ を計算する。
ハッシュ関数 $\mathcal{H _ {hk}(\cdot)}$ の鍵 $hk$ を生成する。
$pk=(hk,n,g,y _ 1,y _ 2,y _ 3)$ , $sk=(hk,n,g,x _ 1,x _ 2,x _ 3)$ とする。
$h=(1+n\ mod\ n ^ 2)\in \mathbb{Z} ^ * _{n ^ 2}$ とする。

暗号化

$m\in[n$ ]とそのラベル $L\in \{0,1\}^*$ を公開鍵で暗号化し、 $(u,e,v)$ とする。この時、乱数 $r\in _ R [n ^ 2 / 4$ ]を生成して使用する。

$u:=g ^ r,e:=y ^ r _ 1 \cdot h ^ m, v:=abs((y _ 2 \cdot y _ 3 ^ {H _ {hk}(u,e,L)}) ^ r)$

復号

まず、 $abs(v)=v$ と $v ^ 2 := u^{2(x _ 2+H _ {hk}(u,e,L)\cdot x _ 3)}$ を計算する。これが成立してなければrejectする。
$t=2 ^ {-1} mod\ n$ と $\hat{m} := (e/u ^ {x _ 1}) ^ {2t}$ を計算する。 $\hat{m}:=h ^ m,m\in [n$ ]でなければrejectする。通過したら、 $m$ を得る。

性質

IND-CCA2安全性

DCR仮定とハッシュ関数 $\mathcal{H} _ {hk}(\cdot)$ の衝突困難性のもと、Camenish-Shoup暗号は適応的選択暗号文攻撃に対して安全である。

加法準同型

暗号文 $C=(u,e,v)$ は同じ公開鍵で暗号化された $C'=(u',e',v')$ と掛け算を行うと

$(u\cdot u',e \cdot e',v \cdot v')=(g ^ {r+r'} ,y _ 1 ^ {r+r'} \cdot h ^ {m+m'},(y _ 2 \cdot y _ 3 ^ {H _ hk (u,e,L)})^ {r+r'})$

これは $m+m'$ の暗号文なので、加法準同型性を持つ。

検証可能な暗号化

検証可能とは、復号や暗号化の時に暗号状態で不正かどうかチェックして計算を中止できる機能のこと。Crammer-Shoup暗号は検証可能な復号機能が暗号方式に組み込まれていた。

Camenish−Shoup暗号では検証可能な復号機能に加え暗号方式とは別にΣプロトコルを行い、暗号化が正しいことも証明する。このプロトコルはPがVに対して、暗号文が確かに公開鍵とラベルによって暗号化されていることを証明する。このプロトコルはstrong RSA仮定のもと、verifiable encryptionである。

まとめ

このCamenish-Shoup暗号は非常に複雑な暗号文をしているので、実際に最初に紹介した記事の論文ではMalicious Securityを保証するのにも活用されていまし、Σプロトコルでゼロ知識証明できる機能が提供されているのは応用がききそうですね。

原論文

link.springer.com

暗号勉強会

あまりコードが出てこない話