A Pragmatic Introduction to Secure Multi-Party Computation (1)
A Pragmatic Introduction to Secure Multi-Party Computation Reading Notes
1 Introduction
Outsourced Computation
一方拥有数据,想知道对这些数据进行某种运算的结果;另一方接收数据并进行运算,返回结果。这期间第二方不应该知道任何关于输入、输出结果、中间量的任何信息。
同态加密(homomorphic encryption)允许对加密数据进行操作。分为部分同态加密(partially homomorphic encryption)和完全同态加密(FHE, fully homomorphic encryption)
Multi-Party Computation
持有数据的一些人想共同计算一个函数,但是他们不互相信任,也没有可信任的第三方。
A Pragmatic Introduction to Secure Multi-Party Computation (3) 基础MPC协议
3 Fundamental MPC Protocols
Yao’s Garbled Circuit Protocol (Yao’s GC)
混淆门的产生过程.
Parameters: Boolean circuit
implementing function , security parameter . GC generation:
- Wire Label Generation. For each wire
of , randomly choose wire labels,
, such that . - Garbled Circuit Construction. For each gate
of in topological order:
- Assume
is a -input Boolean gate implementing function : , where input labels are , and the output labels are .
- Create
’s garbled table. For each of possible combinations of ’s input values , set
Sort entries in the table by the input pointers, placing entry in position . - Output Decoding Table. For each circuit-output wire
(the output of gate ) with labels , create garbled output table for both possible wire values . Set
(Because we are xoring with a single bit, we just use the lowest bit of the output offor generating the above .) Sort entries in the table by the input pointers, placing entry ev in position . (There is no conflict, since .)
接下来是
Parameters: Parties
and with inputs and respectively. Boolean circuit implementing function . Protocol:
plays the role of GC generator and runs the algorithm of Figure 3.1. then sends the obtained GC (including the output decoding table) to . sends to active wire labels for the wires on which provides input. - For each wire
on which provides input, and execute an Oblivious Transfer (OT) where plays the role of the Sender, and plays the role of the Receiver:
’s two input secrets are the two labels for the wire, and ’s choice-bit input is its input on that wire. - Upon completion of the OT,
receives active wire label on the wire. evaluates received gate-by-gate, starting with the active labels on the input wires.
- For gate
with garbled table and active input labels , computes active output label : - Obtaining output using output decoding tables. Once all gates of
are evaluated, using “out” for the second key to decode the final output gates, obtains the final output labels which are equal to the plaintext output of the computation. sends the obtained output to , and they both output it.
GMW Protocol
Yao’s GC 只能支持只有两方的情况, 如果需要支持不少于三方, 则需要新的技术支持. 但是 GMW 协议 (Goldreich-Micali-Wigderson (GMW) Protocol) 天然支持这一点.
先讲只有两方的情况. 不失一般性地, 我们只考虑NOT, XOR 和 AND 三个门.
对于每根导线(即 wire, 表示某个门电路的输入或输出, 用
具体来说,
然后双方各自计算逻辑电路
遇到 XOR 门时, 也是直接将自己持有的两个输入的 share 取异或, 因为
遇到 AND 门时, 就需要双方进行交流了.
A Pragmatic Introduction to Secure Multi-Party Computation (2) 定义
A Pragmatic Introduction to Secure Multi-Party Computation Reading Notes
2 Defining Multi-Party Computation
Secret Sharing
Let
be the domain of secrets and be the domain of shares. Let be a (possibly randomized) sharing algorithm, and be a reconstruction algorithm. A -secret sharing scheme is a pair of algorithms that satisfies these two properties:
- Correctness. Let
. Then, . - Perfect Privacy. Any set of shares of size less than
does not reveal anything about the secret in the information theoretic sense. More formally, for any two secrets and any possible vector of shares , such that , , where denotes appropriate projection on a subspace of elements.
Real-Ideal Paradigm
在 Ideal World
中,每一方都和一个可信方
在 Real World 中,每一方都有一个
如果攻击者在 Ideal World 和 Real
World 中能做的事一样,称该协议
Semi-Honest Security
A semi-honest adversary is one who corrupts parties but follows the protocol as specified.
Circuit PSI
明天组会讲Circuit PSI,事先预习一下前置知识
参考资料:
【知乎专栏】隐私集合求交(Private Set Intersection)问题综述
PSI
隐私求交(Private Set Intersection, PSI)可能是被研究最多的具体的多方安全计算(Secure Multiparty Computation, MPC)协议。PSI本质上是一种特殊的多方安全计算协议:计算双方各自有一个集合,要求双方协作共同计算出两者集合的交集,计算过程中(除了交集部分)不泄露任何和各自集合相关的信息。
标准的PSI分为几大类:基于密钥交换(Diffie-Hellman key exchange based)、基于透明传输 (oblivious transfer based, OT-based)、基于透明键-值(oblivious key-value stores based, OKVS-based)、基于透明向量线性估值(Vector Oblivious Linear Evaluation, VOLE-based)、基于多项式操作(polynomial manipulation)、基于分支程序(Branching Program, BP)。
除此之外还有隐私求交集基数(Private Intersection Cardinality)、阈值隐私求交(Threshold Private Set Intersection)、电路隐私求交(Circuit-PSI)、模糊隐私求交(Fuzzy-PSI)等变体。
电路隐私求交(Circuit-PSI)
Circuit-PSI 的开篇之作:Private set intersection: Are garbled circuits better than custom protocols?
Yao’s Garbled Circuits
Proofs, Arguments, and Zero-Knowledge (4)
Proofs, Arguments, and Zero-Knowledge Reading Notes
11 Zero-Knowledge Proofs and Arguments
什么是“零知识”
(Informal definition of zero-knowledge). A proof or argument system with prescribed prover
and prescribed verifier for a language is said to be zero-knowledge if for any probabilistic polynomial time verifier strategy , there exists a probabilistic polynomial time algorithm (which can depend on ), called the simulator, such that for all , the distribution of the output of the simulator is “indistinguishable” from . Here, denotes the distribution over transcripts generated by the interaction of prover strategy and verifier strategy within the proof or argument system.
主要针对 prover,也就是说就算换一个 verifier 来,无论怎么做都无法从 prover 那里套出其他的信息。
- perfect zero knowledge:
和 产生的分布完全一样。 - statistical zero knowledge: 两者产生的分布只有可忽略的 “statistical
distance”,即
它等价于 - computational zero-knowledge: 对于多项式时间算法
无法区分两个分布。
statiscial zero knowledge 比较弱,尽管人们相信它能解决一些
BPP(Bounded-error Probalistic Polynomial-time)
以外的问题,但是并不认为它能解决 NPC 问题。(突然有个疑问,如果问题
需要注意,一个诚实的
statistical zero-knowledge proof with a polynomial time verifier
能处理的语言在复杂度集
Proofs, Arguments, and Zero-Knowledge (3)
Proofs, Arguments, and Zero-Knowledge Reading Notes
8 MIPs and Succinct Arguments
Multi-prover interactive proofs (MIPs) 允许验证者
MIP 定义
一个关于
- (Completeness) There exists a tuple of prover strategies
such that for every : - (Soundness) For every
and every tuple of prover strategies ,
如果
MIP 和 IP 的主要区别在于,MIP 是 non-adaptive 的,也就是说,在 IP 中证明者可以根据之前的 challenge 作出临时应对,但在 MIP 中就不行。从这一观点出发,我们可以证明 MIP 等价于 PPT oracle Turing Machine 能接受的 language。
设
为一个 language, 为一个 PPT oracle Turing Mahine, 表示 可以访问 oracle 。如果对于任意 ,都存在一个 使得 以概率 接受 ;对于任意 都存在一个 使得 至少以概率 拒绝 ,那么就存在关于 的 2-prover MIP。
至于构造方法,简单地说,
Proofs, Arguments, and Zero-Knowledge (2)
Proofs, Arguments, and Zero-Knowledge Reading Notes
5 Fiat-Shamir 变换
Fiat-Shamir transformation 可以将任意 public-coin protocol
The Random Oracle Model
随机函数
ROM 假设证明者和验证者可以访问一个黑盒随机函数
实际中使用真正的 ROM 是不现实的,一般会使用一些具体的哈希函数(如 SHA-3 等)来代替。
The Fiat-Shamir Transformation
Security of the Transformation
Proofs, Arguments, and Zero-Knowledge (1)
Proofs, Arguments, and Zero-Knowledge Reading Notes
3 定义和技术准备工作
Interactive Proofs
给定一个函数
整个消息序列
用
An interactive proof system
is said to have completeness error and soundness error if the following two properties hold.
- (Completeness) For every
, - (Soundness) For every
and every deterministic prover strategy , if sends a value at the start of the protocol, then An interactive proof system is valid if
.
除了
对于任何 IP 满足
Introduction to Modern Cryptography(13)
Introduction to Modern Cryptography Reading Notes
13 Digital Signature Schemes
定义
A (digital) signature scheme consists of three probabilistic polynomial-time algorithms
such that:
- The key-generation algorithm
takes as input a security parameter and outputs a pair of keys . These are called the public key and the private key, respectively. We assume that and each has length at least , and that can be determined from or . - The signing algorithm
takes as input a private key and a message from some message space (that may depend on ). It outputs a signature , and we write this as . - The deterministic verification algorithm
takes as input a public key , a message , and a signature . It outputs a bit , with meaning valid and meaning invalid. We write this as . It is required that except with negligible probability over
output by , it holds that for every (legal) message . If there is a function
such that for every output by the message space is , then we say that is a signature scheme for messages of length .
The signature experiment
:
is run to obtain keys . - Adversary
is given and access to an oracle . The adversary then outputs . Let denote the set of all queries that asked its oracle. succeeds if and only if (1) and (2) . In this case the output of the experiment is defined to be .
A signature scheme
is existentially unforgeable under an adaptive chosen-message attack, or just secure, if for all probabilistic polynomial-time adversaries , there is a negligible function such that:
与 MAC 同理,可以定义强安全。
Hash-and-Sign
对于任意长度的消息,可以先对它用哈希映射到一个固定长度的串,然后对其进行数字签证。(和 Hash-and-MAC 差不多)