Garbled Circuit

零碎知识

定律:是由实验得出的基本结论，由定律进行数学推导可以得到一些物理上的结论或者定理

定理: 由公理，原理，定律经过数学推导得出的结论

公理: 是没有经过证明，但被当作不证自明的一个命题

信息守恒定律: 物理学的绝对性定律,量子力学基石(幺正性:波函数归一化,全空间粒子总概率为1),指孤立物理系统中信息守恒(定律,不一定正确,如黑洞佯谬的挑战)

黑洞无毛: 黑洞只有质量、角动量以及电荷三个不能变为电磁辐射的守恒量，其他的信息全都丧失

黑洞佯谬: 广义相对论中对黑洞的计算得出黑洞无毛,黑洞层面信息不再守恒,这也是广义相对论和量子理论矛盾之处

同态：抽象代数中，同态是两个代数结构（例如群、环、或者向量空间）之间的保持结构不变的映射

同态加密: 对经过同态加密的数据进行处理得到一个输出，将这一输出进行解密，其结果与用同一方法处理未加密的原始数据得到的输出结果是一样的

可信计算(Trusted Computing，TC): 可信目的是保证系统和应用的完整性等，从而确定系统或软件运行在期望的可信状态。可信是安全的必要不充分条件,可信计算分为外包计算和多方计算,外包计算是甲方拥有数据和计算方法,使用乙方的算力获取结果,安全常用同态加密

差分隐私(differential privacy): 一种数据共享手段,为了应对差分攻击而生,原理就是给查询结果加噪声

多方安全计算（Secure Multi-Party Computation）：主要是针对无可信第三方的情况下，如何安全地计算一个约定函数的问题；安全多方计算（ Secure Multi-Party Computation，MPC）于1986 年由姚期智院士提出。安全多方计算协议允许多个数据所有者在互不信任的情况下进行协同计算，输出计算结果，并保证任何一方均无法得到除应得的计算结果之外的其他任何信息。换句话说，MPC技术可以获取数据使用价值，却不泄露原始数据内容

信息论安全：一个安全多方计算协议，如果对于拥有无限计算能力攻击者而言是安全的，则称作是信息论安全的或无条件安全的

密码学安全: 如果对于拥有多项式计算能力的攻击者是安全的，则称为是密码学安全的或条件安全的。在条件安全模型下，当且仅当恶意参与者的人数少于总人数的一半时，安全的方案才存在

敌手模型：

半诚实（Semi-Honest）模型：假设参与计算的各方都是半诚实的，即参与方可以保留交互时得到的信息。对于想要协作完成计算并得到正确结果的参与方来说，这样的模型符合实际情况。恶意（Malicious）模型、诚实模型不符合实际情况

多项式时间：在计算复杂度理论中，指的是一个问题的计算时间不大于问题大小的多项式倍数，可以在机器上以多项式时间求解的问题被称为P问题，可以在多项式时间验证答案的问题被称为NP，数学家有时把“如多项式时间长的算法”视为快速计算，相对应的是超多项式时间

密钥共享：密钥分享的基本思路是将每个数字拆散成多个数，并将这些数分发到多个参与方，如算工资，设置一个最大数值范围，每个人给别人一个数字，可以提前超支出，但是经过n次分发后进行相加

随机预言机Random OracleL：如果x和H(x)已经在表里记录过，就输出H(x)如果没有关于x的记录，则RO完全随机地在值域中选取一个0,1字符串（或者从其他希望映射到的元素集合中完全随机的选取）当作H(x)，把这个和x一起记录在表里，然后输出这个H(x)。

OT协议

1-out-of-2 OT

消息提供方Alice有两个消息M0和M1，只想提供给Bob其中一个，并且不会泄露另一个

消息接收方Bob想要获取其中一个消息(假设为M1),但不想让Alice知道自己想获取的是哪一个

流程演示

1-2OT假设Alice有两个消息M0、M1,Bob想获取M1

假设M1、M0长度相同，要求随机数r长度和两者相同

sequenceDiagram
 participant A as Alice(数据提供方，拥有消息M0和M1) 
 participant B as Bob(数据请求方，想要获取M1)
 A ->> A: Alice分别产生两个密钥对rsa0,rsa1
 A ->> B : 发送给Bob rsa0-pub,rsa1-pub公钥
 B ->> B : 生成一个随机数r
 B ->> B : Bob想要获取M1,使用rsa1-pub加密r成rsa1-context
 B ->> A : Bob将rsa1-context发送给Alice
 A->>A : Alice用rsa0-pri,rsa1-pri分别解密rsa1-context得到r'和r
 A->>A: Alice用r'与M0做xor得到xor(r',M0)、xor(r',M0),r与M1得到xor(r,M1)
 A ->>B : Alice把xor(r',M0)、xor(r,M1)发送给Bob
 B ->>B: xor(xor(r,M1),r)得到消息M1

sequenceDiagram participant A as Alice(数据提供方，拥有消息M0和M1) participant B as Bob(数据请求方，想要获取M1) A ->> A: Alice分别产生两个密钥对rsa0,rsa1 A ->> B : 发送给Bob rsa0-pub,rsa1-pub公钥 B ->> B : 生成一个随机数r B ->> B : Bob想要获取M1,使用rsa1-pub加密r成rsa1-context B ->> A : Bob将rsa1-context发送给Alice A->>A : Alice用rsa0-pri,rsa1-pri分别解密rsa1-context得到r'和r A->>A: Alice用r'与M0做xor得到xor(r',M0)、xor(r',M0),r与M1得到xor(r,M1) A ->>B : Alice把xor(r',M0)、xor(r,M1)发送给Bob B ->>B: xor(xor(r,M1),r)得到消息M1

混淆电路

所有可计算的函数问题都可转换为不同的电路，加法电路、乘法电路、移位电路、选择电路等。而电路本质上由门（gate）组成，逻辑门包括与门、非门、或门、与非门等。混淆电路把这些门的真值表进行加密和打乱来掩盖原本的逻辑信息信息。

基本步骤

1. 生成：Alice生成混淆电路
2. 传输：Bob获取Alice的输入和混淆电路，基于OT协议
3. 计算：Bob计算电路的到混淆结果，发送给Alice，Alice根据混淆结果得到最终结果发送给Bob

下面我们单看XOR门的混淆电路过程（可逆运算不能达到隐私计算效果）

XOR的真值表为

Alice	Bob	out
1	1	0
1	0	1
0	1	1
0	0	0

Alice首先使用字符串替换真值表，然后使用输入作为对称加密密钥加密输出

Alice	Bob	out
a1	b1	ENCa1b1(r0)
a1	b0	ENCa1b0(r1)
a0	b1	ENCa0b1(r1)
a0	b0	ENCa0b0(r0)

数据传递

1. Alice把自己的输入(假设为a1)和输出(ENCa1b1(r0)、ENCa1b0(r1)、 ENCa0b1(r1)、ENCa0b0(r0))发送给发送给Bob
2. Bob通过不经意传输获取自己的输出对应的字符串（假设是b0）

评估：对于单个逻辑门，显然没有达到隐私计算的目的，混淆电路一般用于不可逆的计算！