Enigma
分散型のoffchain hash tableをstorageとして持つ。blockchainにはそのstorageのhash valueだけを保持。（access controlはblockchain上で行う）
データはクライアント側で暗号化し格納
nodesには（secret sharing）shares, encrypted data, public dataが保持
privateな部分のみoffchainで実行
汎用MPCは大きく2つに分類
yao's garbaled circuits
circuitレベルで算術を秘匿化するもの（だったはず）。通常のcircuitよりも非効率。
secret sharing (enigmaはこちら）
SSSは線形写像で加法準同型写像
像においても元同士の演算は閉じており、単位元・逆元もそれぞれ移される
任意の演算（任意回数の和積演算）が可能になるのがFHE
sMPCが主体で個々nodeが持つdataを秘匿化しつつネットワーク全体でその秘匿化dataを元にした計算を行う。FHEはその計算の効率化のため。（FHE単体ではverifiableではないので）
sMPC
全員がデータを秘匿化したまま計算結果の統計情報のみを計算
SSSによる加算
乗算が遅いO(N^2) -> FHEによる実行速度の増加O(N)
blockchainによる検証可能性、新規参入の動的化
FHE (fully homomophic encryption)
Fully Homomorphic Encryption without Bootstrapping
Goal: データがpublicにされるあるいはされる恐れのあるサーバでデータを隠しながらデータ処理。
not verifiable?
A Verifiable Fully Homomorphic Encryption Scheme for Cloud Computing Security
Verifiable Decryption for Fully Homomorphic Encryption
Efficiently Verifiable Computation on Encrypted Data
計算を秘匿化することが目的。
comparing to verifiable computation: publicな計算を満たす秘匿データを知っていることをゼロ知識に証明することが目的。
BGV Scheme: bootstrapなし、Modulus Switching
bootstrap: ノイズのある暗号文を暗号化したまま復号する回路にいれてノイズのない暗号文にすることで演算回数制限のないFHEへする手法
LWE(Learning with Errors)問題
ノイズ加算による暗号化
秘密鍵を持っていないとノイズを除去できない
演算の繰り返しによるノイズ増大
正しい暗号化データを渡しているかの検証はzk （投票の選択肢など）
verifiable FHEには統合的な証明システムが必要
Our basic idea is to encrypt the data with a somewhat homomorphic encryption scheme (for privacy),
and to add an authentication mechanism on top of the ciphertexts (for security).
暗号化のためにはmodified BV暗号の使用
authenticationのためにはhomomorphic MACsを使用
秘密鍵を使ってmessageセット($ m_1,...,m_t)に対応するtagsセットを生成することによって認証する。
そして、後に秘密鍵なしに誰でもタグを生成することができ、そのタグは以前の認証済みinputに対する関数fのoutputである$ m=f(m_1,...,m_t)を認証することができる。
検証はoriginal messageを知らずに行うことができる。
要は、全てのciphertextのためにMACを生成し、そのhomomorphic特性を利用しBV homomorphicの評価認証を行う。
全射/単射
全射: 終域の元全てに逆像が存在する写像（対応する逆像がない場合は全射ではない）
単射: 終域の元に逆像がmax1個まで存在する写像。1対1対応の写像。
https://gyazo.com/fb73f3a71c550bdf7099d9279a9dd514
全単射: 全ての元が1対1に対応。
同型/準同型
同型: 演算子の振る舞いが同じで位数も同じ(全単射)
準同型: 演算子の振る舞いが同じで単射
SPDZ
SDPZ is an MPC protocol allowing joint computation of arithmetic circuits.
offlineのpreprocessing phaseで乗算を効率化するためのtriplesを生成するためにSHEを利用し、加えて乱数（partyがcircuitにinputとして加える）をtrustedなdealerにより生成。
partyのSHE validityのためにzkを利用
partyがinputのシェアを受け取りadditionとmultiplicationをローカル計算（+必要なcommunication）を行い計算結果をoutputし不正を検証。
inputは乱数rを用いて、$ x_1^i = r_1 + x^i - r
preprocessing computationの前にcircuit内の全てのdataに対するMACとsecret-shared valueに多雨するMACが存在し、このMACkeyもsecret shareされるのでそれぞれのpartyはMAC keyはわからない状態。で、circuit outputに対してMACがあっているかどうかを検証することでMPCで不正をしていないか検知する。
FHEを用いたsMPC
dataとHash(data)を暗号化
(Enc, Hash)を分散
Practical Covertly Secure MPC for Dishonest Majority – or: Breaking the SPDZ Limits
What is SPDZ? Part 1: MPC Circuit Evaluation Overview
The SPDZ Protocol, Part 1
https://www.youtube.com/watch?v=N80DV3Brds0
https://www.youtube.com/watch?v=Ce45hp24b2E
SPDZ denotes a multiparty computation scheme in the preprocessing model based on somewhat homomorphic encryption (SHE) in the form of BGV. At CCS ’16, Keller et al. presented MASCOT, a replacement of the preprocessing phase using oblivious transfer instead of SHE, improving by two orders of magnitude on the SPDZ implementation by Damgård et al.
MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer
sMPC
複数パーティーが互いのinputを明らかにすることなくそれらを結合したinputに対する関数を計算できること。
例えば互いの金額を明らかにせずにどっちがより多くの金額を持っているか計算できること
oblicious trasnsferもsMPCベースのアプリケーション
circuit garblingベースの場合はcircuit評価をエミュレートするためにkeyの暗号化と復号化を伴う。
secret sharingベースの場合は、circuit評価のために全てのパーティーのsecret sharesを利用する。
a=a_1 + a_2のようなadditiveスキームのMPCが適している。
それぞれのノードでローカルにKadmila DHTベースのoff-chainストレージにデータは保持されそのハッシュ値のみがオンチェーンに記録。
SPDZをベースに検証可能にし、計算するノードはstakingが必要。計算エラーや悪意によりoutputが誤っている場合は没収。
Refs
enigma paper
Enigma
Enigmaの解説
秘密分散DAO、 もう一つの暗号2.0
Enigma ホワイトペーパーの日本語訳及び解説 part1