1. 同态加密

同态加密是具有同态性的一类加密算法，可以在密文上进行计算。其中，同态一词源于抽象代数，表示保持结构不变的映射。具体来说在同态加密中，同态意味着对密文进行计算可以映射到明文的计算上。比如，在Paillier加密系统中，我们用E(x)表示对明文x的加密，则E(x_1)×E(x_2)=E(x_1+x_2)。也就是说，在Paillier加密系统中，对密文进行乘法计算可以映射为对明文的加法计算。

同态加密可以分为部分同态加密和全同态加密。部分同态加密系统可以进行任意次的加法或者任意次的乘法。比如，在Paillier加密系统中，我们可以通过对密文进行任意次的乘法进而完成对明文任意次的求和，但是没有办法在不解密的情况下计算两个明文的乘积，我们称这种特征的加密系统为加性同态加密。相对应的，可以计算出加密明文任意次乘积的加密系统，我们称为乘性同态加密。

一些现有成熟的非对称加密系统本身具有加性同态或者乘性同态。因此在设计一个加性或者乘性同态加密系统时，往往选择适合的成熟算法而非设计一个全新的加密系统。在常见的加密系统中，椭圆曲线加密、Paillier加密系统是加性同态的；RSA加密是乘性同态的。一些特殊的算法[1]基于双线性映射可以在进行任意次的加法中额外执行一次乘法。

全同态加密指的是同时具有加性和乘性，进而可以在加密的明文上进行任意计算的加密。全同态加密的概念早在1978就被提出和讨论，直到2009年才由Craig Gentry提出了一个在理论上可行但是复杂度极高的方案，时至今日也没有可以实际应用的方案。
       
随着计算机网络与每个人的联系越来越紧密，使用同态加密来保证数据安全和隐私变得越来越重要。我们可以使用同态加密进行匿名投票[3]，云数据第三方审查[4],数据隐私保护等。下面我们通过一个例子说明如何在支付系统中通过同态加密保护隐私。

在一个常见的中心化信用卡支付系统中，用户每次消费都会生成一个交易信息，其中包括了这次交易消费的金额（甚至更多交易细节）。暴露大量的消费金额信息给服务器实际上侵犯了用户的隐私。比如，服务器可以基于大数据，推测用户买了什么商品，预测用户的消费习惯。如果交易中还包括了商家信息，服务器甚至可以准确知道用户在何处买了哪几款商品。服务器如果拥有一个用户长期的消费信息，那么就可以生成一个精确的用户画像并对用户的消费进行精准的诱导。如果用户是商业机构，还有暴露商业机密的风险。

那么怎么隐藏账单的细节进而保护用户的消费隐私呢？同态加密是这个答案中不可或缺的一部分。在每一次消费结束后，生成的账单中消费金额可以由用户加密。当积累多次账单之后，用户使用具有加法同态性的同态加密，计算出多个账单消费的总和，然后只解密总和给服务器并按照总和还款。这里使用到了Interger Commitment技术[2]，原理是先隐藏(Hide)一个数生成承诺(Commitment)，之后在想揭露(Reveal)这个秘密的时候进行揭露。具体参数的生成及算法细节请参考引用。

假设一次消费金额为x_1，(g_c,h_c,n)为系统参数，r_1为随机数。对于该消费的承诺C_1为：
C_1=g_c^(x_1 ) h_c^(r_1 ) modn.

假设用户共进行了2次消费，金额分别为{x_1,x_2}，则生成的两次消费的承诺为{C_1,C_2}。合并这两次消费并求和的方法为：



用户最终只要告诉服务器两次消费的和x_1+x_2及用于隐藏的随机数r_1+r_2即可。当合并的消费次数越多，单次消费隐私的暴露越少。比如，用户合并了100次消费的金额，那么服务器则不太可能推测出用户的消费习惯、消费水平的隐私信息，只能知道用户100次消费的总和。

信用卡需要用户签名来保证消费不可抵赖。那么怎么对一个加密的消费金额进行签名呢？信用卡对于每个用户都会有使用额度的限制。如果用户可以在一次消费中支付超出限度的金额，那么这个隐私保护系统对于任何信用卡服务商都是不可接受的。怎么保证用户消费的金额没有超出自己的可用额度呢？为了回答以上两个问题，我们需要引入零知识证明。


2. 零知识证明

零知识证明起源于1985年Goldwasser, Micali及Rackoff三位学者一篇交互式零知识证明的文章。但是随着科技的发展，零知识证明已经从一个具体的密码学算法发展成了更广泛、深刻的算法思想。实际上，任何NP陈述(NP-statement)均可以找到对应的零知识证明[5]。具体来讲，零知识证明可以通过证明加密数的性质、证明加密数的计算等途径用于身份认证、投票、鉴权、隐私保护等一系列应用，并且随着技术的演进，可以应用的场景将会越来越多。因此，很难从功能的角度对零知识证明进行全面、准确的划分。

从交互方式来说，零知识证明可以分为交互式的和非交互式的。最早期的零知识证明使用的就是交互式的，证明人要根据验证人提出的各种挑战(challenge)作出不同的证明。考虑到证明人预测到挑战，或者随机猜出一个可以被接受的证明，验证人需要不停的生成挑战来验证证明是否可信。因为需要多轮的挑战与证明，所以证明过程是交互式的。后来人们意识到只要挑战足够不可预测，并且让算法随机得出可接受证明的概率极低，那么不需要交互也可认为证明是可信的，进而成为非交互式的零知识证明。Fiat-Shamir heuristic[6]算法可以用于生成随机的挑战。随机的挑战可以通过把证明过程的各个参数作为输入，输入进一个公开的哈希函数来生成。保证证明人无法随机得出可验证通过的证明则要具体的设计。

零知识证明需要满足正确性、完备性、零知识性。前两个性质在大部分严密的证明中能满足，但是零知识性则是独特而又难以构造的。比如说在常见的椭圆曲线签名系统中，只有拥有私钥的人能够成功签名，通过私钥对应的公钥可以验证签名。通过让证明者签名一个随机的字符串可以证明一个人拥有私钥，同时没有暴露私钥。那么是否可以说这是一种零知识证明的身份认证呢？答案是否定的，因为公钥和签名本身也包含了信息，破坏了零知识性的原则。那么如何构建一个零知识证明呢？

回到刚才信用卡支付的例子。用户对每一次交易信息中的消费金额进行加密，此外，用户还要对消费金额进行数字签名同时证明消费金额（严格的说，所有未结清账单的消费总和）处于自己的支付额度以内。因此该用户需要进行以下两个零知识证明：



其中NIPK是Non-interactive Proof of Knowledge的缩写。〖"NIPK" 〗_1证明的是一个对x_1签名的CL签名[7]，其签名的内容与承诺中隐藏的内容相同。〖"NIPK" 〗_2证明的是承诺中隐藏的消费金额处在0与信用额度limit之间。在这种形式的公式中，希腊字母表示的是需要被证明的值，其余的英文字母表示的值验证人均是已知的。在〖"NIPK" 〗_1中，C_1即一次消费的承诺，为了符合参数命名标准，将{x,r}替换为{ξ,ρ_ξ}, pk是签名所对应的公钥并且该公钥是验证人已知的。证明的第一行"CLverify"(pk,ξ)=accept表示证明在已知公钥及签名的情况下，证明该签名验证通过并且该签名签的原文为ξ。证明的第二行表示证明知道C_1隐藏的值是ξ。这两行证明合在一起，就需要证明两行中的ξ是同一个值。也就是CL签名的内容与C_1中隐藏的内容相同。
由于篇幅所限，本文仅介绍〖"NIPK" 〗_1中一个子证明的证明过程。严谨详细的证明流程及参数含义可以参考[7][8]。下面是〖"NIPK" 〗_1的展开形式：



其中，前4个条款是"CLverify"(pk,ξ)=accept的展开，证明了一个CL签名的正确性。这个证明看似复杂，实际上只需要反复使用两个更加基础的证明：证明两个底不同的离散对数拥有相同的幂[9]以及范围证明[8]。这里我们进一步简化，仅介绍如何证明两个底不同的离散对数拥有相同的幂。

假设Alice有一个秘密x，她使用两组不同的参数{g_1,h_1}和{g_2,h_2}分别进行计算：E=g_1^x h_1^(r_1 ) modn，F=g_2^x h_2^(r_2 ) modn，其中r_1,r_2是两个随机数。Alice要向Bob证明E和F隐藏了相同的秘密，E和F对Bob是公开的。使用非交互式零知识证明流程可分为四步



结语：本文简单介绍了密码学中的同态加密与零知识证明并通过保护交易隐私的场景将两个算法联系起来。文中例子仅为了展示两种算法，并不意味着已经构建了一个完善的隐私保护的交易系统。如果您对带有隐私保护的交易系统感兴趣，可以参考[10]以及迅雷链后续发展。


引用

Citation:
[1]Boneh, Dan, Eu-Jin Goh, and Kobbi Nissim. "Evaluating 2-DNF formulas on ciphertexts." Theory of Cryptography Conference. Springer, Berlin, Heidelberg, 2005.
[2]Damgård I, Fujisaki E. A statistically-hiding integer commitment scheme based on groups with hidden order[C]//International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2002: 125-142.
[3]Hirt, Martin, and Kazue Sako. "Efficient receipt-free voting based on homomorphic encryption." International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2000.
[4]Wang, Cong, et al. "Privacy-preserving public auditing for data storage security in cloud computing." Infocom, 2010 proceedings ieee. Ieee, 2010.
[5]Goldreich, Oded, Silvio Micali, and Avi Wigderson. "Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems." Journal of the ACM (JACM)38.3 (1991): 690-728.
[6]Fiat A, Shamir A. How to prove yourself: Practical solutions to identification and signature problems[C]//Advances in Cryptology—CRYPTO’86. Springer, Berlin, Heidelberg, 1986: 186-194.
[7]Camenisch J, Lysyanskaya A. A signature scheme with efficient protocols[M]//Security in communication networks. Springer, Berlin, Heidelberg, 2002: 268-289.
[8]Bünz, Benedikt, et al. "Bulletproofs: Short proofs for confidential transactions and more." Bulletproofs: Short Proofs for Confidential Transactions and More. IEEE, 2018.
[9]Camenisch J, Michels M. A group signature scheme based on an RSA-variant[J]. BRICS Report Series, 1998, 5(27).
[10]Rial A, Danezis G. Privacy-preserving smart metering[C]//Proceedings of the 10th annual ACM workshop on Privacy in the electronic society. ACM, 2011: 49-60.

这篇居然不用话费金币，太好了，麻烦多一些