「MPC-Mike Rosulek 」:Overview of Secure Computation and Yao's Protocol

「MPC-Mike Rosulek 」:Overview of Secure Computation and Yao's Protocol

本系列是总结Mike Rosulek教授在上海期智研究院的密码学学术讲座。

这是Mike教授的第一个分享:Overview of Secure Computation and Yao’s Protocol

Roadmap

  1. Secure computation: Concepts & definitions
  2. Yao’s protocol: semi-honest secure computation for boolean circuits

主要内容包括安全多方计算的整体介绍及其应用场景、如何定义安全多方计算的security、Yao的混淆电路协议 (garbled circuits protocol)。

(咕咕咕博客选手回来了,学长说:与其担心有没有学读,不如多学学密码学,泪目,我觉得他说的对!)

Secure computation

Concepts

什么是安全计算?

什么是安全多方计算
  • Mutually distrusting parties, each with a private input.

    【参与方之间互不信任,且都有一个隐私输入】

  • Learn the result of agreed-upon computation.

    【参与方希望能得到一个各方商定的计算结果】

安全计算能保证什么?

  • Privacy (“learn no more than” prescribed output)

    【隐私性:参与方除了得到商定的计算结果,其他都不能得到】

  • Input independence

    【各参与方的输入无关】

  • Output consistency

    【各参与方的输出是一个商定一致的计算结果】

以上性质及时在某些参与方勾结欺骗的情况下,也是成立的。

有恶意参与方的多方安全计算

scenarios

Example 1: Sugar Beets——甜菜定价

  • Farmers make bids (“at price X, I will produce Y amount”)

    【Farmers:会根据甜菜的定价决定产量,价格对产量的影响如上图蓝色的线】

  • Purchaser bids (“at price X, I will buy Y amount”)

    【Purchaser:会根据甜菜的定价觉得购买量,价格对购买量的影响如上图红色的线】

  • Market clearing price (MCP): price at which total supply = demand

    【双方希望甜菜价格能达到市场出清价,即产量=需求量】

但是双方不希望透露自己心中的定价,因为这会破坏经济市场的balabala

因此,在2009年,通过双方可以通过安全计算得到市场出请价。

Example 2: Ad conversion——广告投放

特斯拉存储了到店购买汽车的用户邮箱,而谷歌希望能个性化的投放汽车广告。

因此,如果双方公开数据库中的数据,就可以通过上图的SQL语句筛选出目标用户。

但这样会侵犯用户的用户的隐私,所以特斯拉和谷歌都不会直接公开用户的信息。由此,双方可以通过安全计算得到广告投放的目标用户。

Example 3: Wage Equity Study——薪资公平性研究

研究人员想研究Boston的薪资水平是否是性别平等的,但各企业不会愿意直接公开薪资。

而通过安全计算,可以在保护企业薪资隐私的情况下,得到相关研究结果。

Definitions

“securely” compute f ?

如何理解“安全地“计算f?

可以先从安全性需求/威胁来理解什么是不安全。

  • What if adversary learns more than f(x, y)?

    【如果攻击者学到了除商定计算结果f(x,y)以外的信息?】

  • What if adversary learns f(x, y) but then prevents honest party from learning it too?

    【如果攻击者能够得到计算结果,但是阻碍诚信的参与方得到正确的计算结果?】

  • What if adversary forces several parties to have inconsistent outputs?

    【如果攻击者通过某种手段使得一些参与方得到不一致的计算结果】

  • What if adversary’s choice of input depends on honest party’s input?

    【如果攻击者的输入会依赖一些诚信参与方的输入?】(不太理解这是一个什么样的情况?)

Security in ideal world

在理想情况下,假设有一个可信第三方,Alice和Bob把自己的输入x, y 告诉她,可信第三方计算f(x, y) ,再把计算结果分别分发给Alice和Bob。

在理想情况中,如果有一个恶意的参与方,结果会怎么样?(你看图,变坏的人变丑了2333

corrupt party’s view:

  1. 随意选择一个输入y
  2. 除了知道f(x, y) ,其他信息都不知道。
  3. 致使诚信参与方得到一致的f(x, y)

可见,在理想情况下,即使有恶意的参与方,也能达到之前提到的“安全地”计算f(x, y) 的要求。

Security goal: real protocol interaction is as secure as the ideal-world interaction

For every “attack” against real protocol, there is a way to achieve “same effect” in ideal world

【因此,现实情况的安全计算目标应该是达到和理想情况中的同等安全性。】

【对于每一个尝试攻击真实安全计算协议的攻击者来说,总有一种方式达到 和攻击理想情况的 相同影响。】

首先,先解释在real protocol中,恶意参与方会产生什么样的effect?

下图是一个现实的MPC协议交互图(有恶意参与方):

effect:

  • Something the adversary learns / can compute about honest party

    【恶意参与方通过MPC得到的计算结果,可能能计算一些关于可信参与方的信息】

  • Some influence on honest party’s output

    【恶意参与方能够影响可信参与方得到的计算结果】

Defining security

完整的安全定义: RanCanetti13

Universally Composable Security: A New Paradigm for Cryptographic Protocols

Security definition: For every real-world adversary $\mathcal{A}$, there exists an ideal adversary $\mathcal{A’}$ s.t. joint distribution (HonestOutput,AdvOutput) is indistinguishable.

【对于每一个真实协议交互下的攻击者 $\mathcal{A}$ ,都存在一个在理论协议情况下的攻击者 $\mathcal{A’}$ ,这两个攻击者产生的effect是相同的,两种情况下的诚信参与方的输出和恶意参与方的输出的 联合分布 是不可区分的。】

现在,来解释如何产生上文提到的:For every “attack” against real protocol, there is a way to achieve “same effect” in ideal world.

假设在理想情况中有一个simulator:simulates real-world interaction in ideal world

【可以在理想情况中模拟现实协议的交互。】

对于该模拟器来说,他可以扮演两种角色:

  1. Send protocol messages that look like they came from honest party

    • Demonstrates that honest party’s messages leak no more than f(x, y)

    【和恶意参与方交互,模拟现实协议中的诚信参与方:对模拟器来说,他除了知道计算结果f(x, y) 外】

  2. Extract an f-input by examining adversary’s protocol messages

    • “Explains” the effect on honest party’s output in terms of ideal world

    【在理想协议中,模拟器提取来自恶意参与方的输入信息,模拟理想情况中的参与方。】

    Q: yuyu老师问,这里的extract是什么意思?

    A:在现实安全计算的协议交互中,不管恶意参与方提交什么输入,总能商定一个结果。因此在理想情况中,也许恶意参与方只是上传了一些garbage bit,模拟器需要从这些garbage bits中提取一些信息,作为参与交互的输入。

Semi- Honest security

有一种特殊的情况,即攻击者是semi-honest:

  • Adversary assumed to follow the protocol on a given input

    【攻击者在给定输入下遵守协议】

  • Adversary may try to learn information based on what it sees

    【但攻击者会尝试从得到的信息中学到一些其他信息】

  • No need to extract, only simulate transcript given ideal input+output

    【因为攻击者会遵守协议,所以模拟器不需要extract来自半诚实的攻击者,只需要传送来自半诚实参与方的输入和可信第三方的计算输出结果。】

Yao’s protocol

Yao’s protocol : semi-honest secure computation for boolean circuits.

warm-up protocol: garbled truth table

Alice方:会计算一个混淆真值表(garbled truth table)

  1. Write truth table of function f

    【写下函数f的真值表,该函数对于Alice方有4种输入,对Bob方有4种输入】

  2. For each possible input, choose random cryptographic key

    【对于函数的每一种输入,Alice都选择一个随机的密钥(也叫label),对于Alice方的输入有4种密钥,对于Bob方的输入有4种密钥。】

  3. Encrypt each output with corresponding keys

    【再用对应的输入密钥加密每一个函数的输出】

  4. Randomly permute ciphertexts, send to Bob

    【对第三步的加密真值表随机置换,得到garbled truth table,再发给Bob。】

而对于Bob方:(先不考虑如何得到正确的密钥Ax和By)Bob得到了密钥Ax和By,对garbled truth table进行尝试性解密,就只能得到f(x, y)

对于Bob来说,是通过OT来得到正确的密钥Ax和By。后面会解释OT的简易版本和更为常用的做法。

Q:Bob如何判断这是正确的解密?

A:在对字符加密前,可以对字符加一些标记,比如前导0,或者特殊字符串之类。

在Bob收到garbled truth table和garbled input后,Bob的视角可以模拟成下图:

并且,对于distinguisher来说,只要密钥{A, B}中有一个不知道,那么 $\mathbb{E}{A, B}(C)\approx \mathbb{E}{A’, B’}(C’)$ ,(即和其他不知道的输入的加密是不可区分的)这样的模拟就是不可区分的。

Extending warm-up protocol

但这样的协议还存在一些问题:

  • Problem: Cost scales with the truth table size of f

    【对于复杂函数来说,真值表的大小会很大,计算开销和存储开销都会很大】

  • How does Bob magically learn “correct” Ax, By?

    【之前忽略的假设,Bob如何才能得到Alice制定的密钥Ax和By】

这里会先解决第一个问题,想法是把这个复杂函数拆分成多个garbled truth table,可以用一个garbled table 的garbled outputs作为另一个garbled table的keys,就像这样:

第二个问题,关于OT的部分,后文会继续解释。

Garbled circuit framework

对于garbled circuit framework的提出,出自姚期智院士86年的论文。

用boolean电路表示一个函数,电路由一些门组成:

(Alice) Garbling a circuit:

  1. Pick random labels W0, W1 on each wire

    【对于每一个wire,都会选择两个label来表示true和false,比如选择A0是true,A1是false,这里的label其实就是上文提到的加密密钥。】

  2. “Encrypt” truth table of each gate

    【然后,对每一个门,都用对应的label加密真值表】

  3. Garbled circuit = all encrypted gates

    Garbled encoding = one label per wire

    【这样就把一个混淆电路变成一些加密真值表,同样的,把混淆电路的编码变成了每个wire的一个label】

(Bob) Garbled evaluation:

Bob收到了混淆电路(garbled circuit)和混淆输入(garbled input),就可以进行garbled evaluation

  1. Only one ciphertext per gate is decryptable

    【对于Bob来说,他只有输入wire的单个label,因此对于每一个门,他都只能解密加密真值表中的一项】

  2. Result of decryption = value on outgoing wire

    【输出门的值就是最后的计算结果】

对于接受方Bob来说,它的任务就是用garbled input来evaluate garbled circuits。他只能学习到每个wire的一个label,计算上不可能的去猜测这个wire的另一个label是什么。而对于输出门的输出wire,即使揭露输出wire的两个label也只会泄漏电路的输出。

在BellareHoangRogaway12中有对gabled circuit做一些正式的符号定义:

  • Privacy: (F,X,d) reveals nothing beyond f and f(x)

  • Obliviousness: (F,X) reveals nothing beyond f

  • Authenticity: given (F, X), hard to find Y‘ that decodes $\notin$ {f(x), ⊥}

Oblivious transfer

回到之前说的第二个问题,对于evaluator,也就是Bob,如何才能得到garbled circuit的garbled input?

对于下图的garbled circuit,需要Alice输入A和B,需要Bob输入C和D。

Garbler’s input: Alice 作为garbler,她知道每个wire的两个label(比如A0, A1),也知道label对应的真值关系(比如A0是false,A1是true),那Alice只需要把她的输入的对应的那个label发送给Bob就好了。

Evaluator’s input: 我们需要用OT(oblivious transfer)来实现,让Bob从Alice手中获得他想要的label,但又不让Alice知道他想要的是哪一个label。


如何构造不经意传输(OT)?

下图是一种简单实现的OT,不是最优的协议,后面的文章会继续介绍常用的OT。

RRndIO.md.png

Alice有两个label:W0和W1,Bob想要得到其中一个,假设是Wc ( $c=0,1$ ) 。

Bob需要用KeyGen算法生成一对公私钥 $(sk_c, pk_c)$ ,同样还需要BlindKeyGen算法生成一个不知道(或者硕士无法知道)其对应私钥的公钥 $pk_{1-c}$ 。

  1. Bob将两个公钥 $pk_0, pk_1$ 发给Alice
  2. Alice用 $pk_0$ 加密W0,用 $pk_1$ 加密W1,把两个密文发送给Bob
  3. 因为Bob只知道Wc的私钥,而无法计算得到W1-c的私钥。所以Bob可以从Alice手中得到想要的label。

Need public-key encryption that supports blind key generation:

  • sample a public key without knowledge of secret key
  • E.g.: ElGamal (sample group element without knowing discrete log)

需要用一些支持blind key生成的公钥加密算法,比如ElGamal,群中的某些元素没有对应的离散对数,也就无法知道其对应的私钥。

Yao’s protocol: overview

Yao协议:

  1. Gabler生成每个wire的label,把garbled circuit f(加密的真值表)、garbled input x(Alice输入对应的labels)和output wire labels(输出wire对应的labels)发送给Evaluator
  2. Evaluator用n次OT,在和Alice交互中,得到Bob每一个输入wire的label,每一次OT,Alice都不知道Bob选择的输入是什么。
  3. 对于Evaluator来说:garbled f + garbled inputs + all output labels ⇒ Bob learns only f(x, y)

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×