隐私计算方法

零知识证明

零知识证明指：证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。

零知识证明系统包括两部分：宣称某一命题为真的示证者(prover)和确认该命题确实为真的验证者(verifier)。证明是通过这两部分之间的交互来执行的，其思想源于交互式证明系统。

零知识证明起源于最小泄漏证明，设P表示掌握某些信息，并希望证实这一事实的实体，设V是证明这一事实的实体。假如某个协议向V证明P的确掌握某些信息，但V无法推断出这些信息是什么，我们称P实现了最小泄露证明。不仅如此，如果V除了知道P能够证明某一事实外，不能够得到其他任何知识，我们称P实现了零知识证明，相应的协议称作零知识协议。

零知识证明的三个性质：

  1. 正确性。P无法欺骗V。换言之，若P不知道一个定理的证明方法，则P使V相信他会证明定理的概率很低。
  2. 完备性。V无法欺骗P。若P知道一个定理的证明方法，则P使V以绝对优势的概率相信他能证明。
  3. 零知识性。V无法获取任何额外的知识。

实例：

若A为验证者，B为示证者。其中A拥有B的公钥，B如何让A相信自己就是B且不泄露自己的私钥。

  1. B把自己的私钥给A，A用公钥对某个数据加密，然后用B的私钥解密，如果正确，则证明对方确实是B。
  2. A给出一个随机值，并使用B的公钥对其加密，然后将加密后的数据交给B，B用自己的私钥解密并展示给A，如果与A给出的随机值相同，则证明对方是B。

方法2就属于零知识证明，既没有出示自己的私钥，也能证明自己是B。

同态加密

同态加密是基于数学难题的计算复杂性理论的密码学技术。对经过同态加密的数据进行处理得到一个输出，将这一输出进行解密，其结果与用同一方法处理未加密的原始数据得到的输出结果是一样的。

本质上，同态加密是指这样一种加密函数，对明文进行环上的加法和乘法运算再加密，与加密后对密文进行相应的运算，结果是等价的。由于这个良好的性质，人们可以委托第三方对数据进行处理而不泄露信息。

全同态加密是指同时满足加同态和乘同态性质，可以进行任意多次加和乘运算的加密函数。

虽然其拥有很好性质，但是其效率低下，实际场景中难以应用。

差分隐私

差分隐私是密码学中的一种手段，旨在提供一种当从统计数据库查询时，最大化数据查询的准确性，同时最大限度减少识别其具体记录的机会。（可以查聚集数据，不给查具体的信息）

从隐私保护的角度来说，隐私的主体是单个用户，只有牵涉到某个特定用户的才叫隐私泄露，发布群体用户的信息（一般叫聚集信息）不算泄露隐私。

但是通过多个聚集数据之间的交集或差集推测出一些具体的隐私信息，这种攻击就是差分攻击。

如通过查询前100个人的情况和前99个人的情况进行对比，就能推测出第一百个人的信息。

为了防止差分攻击，差分隐私所作的就是找出一种方法，让攻击者用某种方法查询两个相近的数据集，查询到的概率非常接近。如此攻击者就无法通过两个数据集之间的差异推导出个体的隐私。

常见方式：通过加入随机性，使记录相似的两个数据集，查询获得相同值的概率非常相似。（加噪，使其查询结果随机化）

  • Laplace机制，在查询结果里加入Laplace分布的噪音，适用于数值型输出。
  • 指数机制，在查询结果里用指数分布来调整概率，适用于非数值型输出。

但是，使用差分隐私时，需要考虑隐私预算。究竟使用多大的噪声，允许误差在什么程度。都需要在精度和安全上做衡量。

多方安全计算

针对无可信第三方的情况下，如何安全地计算一个约定函数的问题。

多个参与方共同完成的一次安全计算，这里的安全是指，在一次计算中，所有的参与方都可以提供自己的隐私输入，并能从计算中得到计算结果，而无法获得其他参与方隐私输入的任何信息。

多方安全计算源于姚期智先生的“百万富翁问题”，是指两个百万富翁想知道谁更富有，而不希望别人知道自己资产的真实数额。

百万富翁问题的简单模型，是要求参与者『半诚实』的，有这样几个假定的：

  1. 两人富翁都是正人君子，不会虚报自己的财富的；
  2. 两人都希望诚实地比较出谁更有钱；
  3. 但是，两人又都希望知道对方财产到底是多少；
  4. 其他一切人都不值得信赖。

主要是启发我们在无可信第三方的情况下，如何安全的计算一个约定函数。

总结其一般性质为：

  1. 隐私性：任何一个参与方不能获得其他参与方的任何隐私输入数据，除去能从计算结果中推断出的信息。
  2. 正确性和可验证性：计算应能保证正确执行，并且这一过程的合法性和正确性应可被参与方或者第三方验证。
  3. 公平性和健壮性：参与计算的各方，如非提前约定，应能同时获得计算结果或者无法获得结果。

一般计算流程：

  1. 密钥生成：所有未来会参与到签名过程的参与方联合在一起，执行两件事情：
    • 为每一个参与方生成一个秘密的私钥；
    • 共同计算出一个公钥用于对应这一个私钥序列。
  2. 签名算法：参与某次签名的参与方分别将自己的私钥作为隐私输入，需要签名的信息作为公共输入，进行一次联合签名运算，得到签名。在这个过程中，安全多方计算的隐私性保证了参与方并不能获得其他方的私钥信息，但都可以得到签名。正确性和健壮性保证了签名的不可伪造。
  3. 验签算法：利用对应于本次交易参与方的公钥，按照传统签名算法的验签方式即可完成。因为在验签过程中，没有“秘密输入”，这意味着不需要一次安全多方计算就可以执行验签过程，这将成为利用安全多方计算执行分布式签名的优点之一。

门限签名/阈值签名

门限签名基于安全多方计算思想进行构造。

门限签名是普通数字签名的一个重要分支，是门限秘密共享技术和数字签名的一种结合。

(t,n)门限签名方案是指由 n个成员组成一个签名群体，该群体有一对公钥和私钥，群体内大于等于 t个合法、诚实的成员组合可以代表群体用群私钥进行签名，任何人可利用该群体的公钥进行签名验证。这里 t 是门限值，只有大于等于 t 个合法成员才能代表群体进行签名，群体中任何 t-1 个或更少的成员不能代表该群体进行签名，同时任何成员不能假冒其他成员进行签名。采用门限签名方式可以实现权力分配，避免滥用职权。

环签名

环签名是一个能够实现签名者无条件匿名的签名方案，是一种简化的群签名，环签名中只有环成员没有管理者，不需要环成员间的合作。

假设有N个用户，每个用户拥有公钥sk_i和公钥pk_i，其算法如下：

  1. 利用一个概率多项式时间算法(PPT)，输入安全参数K，输出公私钥对。（允许不同的签名算法）
  2. 利用PPT算法，对输入信息m和N个成员的公钥L = {pk_1,….,pk_n} + 一个成员的私钥sk进行签名，得到对m的签名R。
  3. 一个确定性算法，在输入(m,R)后验证R是否为m的环签名。

环签名因为其签名隐含的某个参数按照一定的规则组成环状而得名。而在之后提出的许多方案中不要求签名的构成结构成环形，只要签名的形成满足自发性、匿名性和群特性，也称之为环签名。