MatRiCT: 基于格密码的匿名保密交易

Original 高尚安比技术社区 2020-11-09 14:21

收录于合集

本文作者高尚，来自安比技术社区的小伙伴，目前就职于香港理工大学，研究零知识证明的应用等方向。

在匿名加密货币中，在保障隐私的同时，如何高效地验证交易的合法性一直是比较热门的话题。而格密码具有的抵抗量子攻击的特性，也一直被认为是下一代密码学的研究热点。这两个热点问题结合，就碰撞出了19年CCS的MatRiCT——抗量子攻击的匿名保密交易协议。之前啃这篇文章的时候，对格密码不是很了解。在看完东泽大神的格密码科普系列后，再读这篇文章，很多问题感觉豁然开朗！这里我就尽量避免格密码里的复杂公式，跟大家来一起学习MatRiCT吧~

保密交易的验证

在加密货币中，为了保证每一条交易的合法性，需要允许任何人可以对所产生的交易进行验证。比如交易：，表示用户A通过两个账户，和，向账户（属于用户B）转账10元，我们需要验证：。这个验证对于公开的加密货币（如比特币）来说很简单，但是对于匿名加密货币中，如Zcash和门罗币，我们需要在保证每一笔交易都能被验证的同时，还要确保交易金额以及转账者的身份不被泄露。这样验证问题就有一点棘手，不过还是可以通过零知识证明来实现。比如在门罗币中，就是通过零知识证明实现了RingCT协议（匿名保密交易协议），进而达到了在保证隐私的同时，对保密交易提供了可验证性。

一个RingCT协议大致提供了以下两点安全，每种均采用一个零知识证明完成：

交易金额保密：通过区间证明（range proof）实现；
用户身份保密：通过环签名（linkable ring signature）实现。

目前，以上两种零知识证明，在离散对数的假设下，都有十分高效的实现，比如Bulletproofs [Oakland'18]就可以实现复杂度的区间证明。的环签名也有具体方案[ESORICS'15, EUROCRYPT'15]，但是离散对数问题在量子计算机眼里不是困难的。所以目前大家都在尝试找到能抵抗量子攻击的方案。其中格密码就是一个不错的方向。

格密码效率

虽然在格密码中，也已经有对于以上的区间证明和环签名的解决方案[CRYPTO'19]，但是相比离散对数假设下的方案，其效率是极低的。比如对于一个区间证明，Bulletproof仅需不到KB的空间，而[CRYPTO'19]需要花费约KB。

在格密码下低效的主要原因之一是承诺的大小远超其他元素的大小。这个问题是因为要保证格密码中的问题依然困难（M-SIS和M-LWE）被迫选择较大的安全参数造成的。此外在区间证明中，因为需要隐藏的交易金额并不一定是short的，所以没办法采用Hashed-Message Commitment（HMC）的承诺方法，而只能采用Unbounded-Message Commitment（UMC）。这里我们不去管HMC和UMC是如何实现的，简单对比下他们的优缺点：

	处理对象	承诺大小
HMC	小向量如二进制向量	固定
UMC	无限制	随处理对象长度增长

MatRiCT概述

MatRiCT就是匿名货币的基于格密码的高效RingCT协议[CCS'19]（这里容我插一句，其实效率相比传统方案并不高，只是提高了[CRYPTO'19]的性能）。其主要包括两个部分：

Balance Proof：替换传统区间证明并达到同样效果；
高效环签名：提高了传统环签名的拒绝采样的效率。

此外，MatRiCT针对匿名货币的场景还有通过其他小技术进行优化和扩展性能。这些小技术比较简单直接，所以这里就不具体介绍了。具体包括：

承诺组合：组合多个线性关系的承诺为一个承诺；
两组参数：对于二进制证明和其他部分采用两组参数，优化证明空间；
可验证承诺：基于HMC设计的有“迷你陷门”的承诺方式，审计员可以通过其私钥和陷门来逆向承诺，获得消息明文（这个需要根据应用场景选择是否采用）；
RingCT协议新模型：通过加入区块链状态等其他信息，扩展RingCT模型，并使之支持stealth addresses技术。

MatRiCT中Balance Proof

我们之前说过对于一个交易，首先保证以下两个要求：

输入、输出金额非负；
输入之和等于输出之和。

对于第一个要求，一般采用区间证明方式，证明金额属于一个非负区间。对于第二个要求，传统区间证明非常容易实现，因为同态承诺满足。但是这种区间证明在格密码下只能采用UMC，因为和不一定是short的。

为了采用HMC来减少承诺的大小，MatRiCT对金额的二进制表示做承诺，而非金额本身。比如的情况，假设HMC仅能处理二进制向量，我们无法使用。但是再把转化成后，我们可以使用。这样，对于之前的第一个要求，我们就可以采用一个二进制证明（Binary Proof）来实现，只要证明是二进制向量，就能保证所表示的金额是大于的。但是对于第二个要求就比较麻烦，因为（对应的承诺也不相等）。比如我们再最开始举的例子：Bits(3)+Bits(7)=(0,0,1,1)+(0,1,1,1,)=(0,1,2,2)≠（1,0,1,0）=Bits(10).那么对于第二个要求怎么办呢？下面有请“balance proof”~

Balance proof就是通过使用一些“纠正数” ，其中，来保证

。

个输入和个输出

纠正数的原理如下：

还是之前的例子，

，其中表示，

表示，

。

对于这个交易，。这样，我们就能通过

来验证第二个要求，从而替换区间证明，这也就是balance proof的原理。因为在balance proof中，我们可以放心地使用HMC，所以其空间大小要明显小于[CRYPTO'19]的区间证明。

MatRiCT中环签名

在大多数目前的环签名方案中[CRYPTO'19]，采用one-out-of-many proof来实现。主要思想是将公钥看作是一个对于的承诺，来提高效率（Mimblewimble 的idea）。比如对于个公钥的集合，签名者持有私钥以及其对应的公钥，。签名者通过产生一个克罗内克 (Kronecker's delta)序列，，来保证是的承诺（函数：当时，；其余情况）。因此，环签名问题可以转化为对于拥有的证明。进一步，我们可以通过将转化为二进制表达以及的特点来降低签名大小（若，可以从降至）。为了表述清楚，我们先不考虑这个对数证明体积的转化。

MatRiCT发现有一个特点：仅有一个元素是，其余均为。根据这个特点，可以设计一种高效的拒绝采样（rejection sampling）方式。下面先插播一段格密码中拒绝采样的原理，对于这个内容清楚的小伙伴们可以直接跳过~

在目前的格密码的-协议中，我们都需要通过一种拒绝采样的机制，来保证消息的隐秘性。假设对于消息，和一个隐藏值，在收到挑战后，我们的应答为。在格密码M-SIS的困难问题下，我们需要保证仍然是short的，所以无法像离散对数那样，从整个域采样。如果接受所有采样结果的话，会带来一个问题：攻击者可以通过的分布来获得的分布。简单的说，假设每次从固定区间进行采样（采样区间往往公开），我们可以通过收集多次的值，减去的平均值（一般为），乘以后计算平均值，来获得的大致范围。为了避免这个问题，通常采用拒绝采样的方式，即我们设定一个公开的分布为目标分布（如均值为的正态分布），采用一个系数使其（绝大部分）在的分布的下方，再拒绝在这个目标分布外的。这样，通过拒绝采样的分布不会泄露任何关于的分布的信息。
[CRYPTO'19]采用的是正态分布。为了更方便实现以及更有效地阻止旁道攻击，MatRiCT采用均匀分布。使用均匀分布的话，假设的采样空间是，挑战空间为（），对于二进制信息，我们需要保证，否则，需要重新采样，重复整个过程。举个非二进制的例子方便大家理解。假设，秘密消息的范围是，挑战范围是，很容易得知，对于任何消息，的范围一定会包括区间（注意，这个是包括的区间，即所有可能区间的交集，而不是属于的区间）。这样对于任意消息，我们只取作为合法结果，输出的也只能在这个区间内。因为是均匀采样，所以在这个区间内也是均匀分布，这样攻击者无法通过的分布获得的信息。
对于二进制信息使用均匀分布采样有一个提高采样效率的方法：如果，我们可以直接从来采样。这样的话始终不会被拒绝，是不是很酷！但是这种方法会带来一个弊端：对于这种序列，生成证明的时间会远高于这种序列，从而泄露了旁道信息……

根据仅有一个元素是的特点，MatRiCT发现如果直接使用在时，即使采用来采样，也不会造成旁道攻击的问题。这是因为对于不同的，其被拒绝的概率始终是相同的，也就导致了生成proof的时间是相同的。所以，我们可以直接采用这种高效的采样机制，从均匀分布的区间进行采样~把这个技术应用到one-out-of-many proof，再应用到环签名，就是MatRiCT的高效环签名方案啦！

MatRingCT

说了这么多，讲一讲MatRiCT是如何通过结合两个技术实现RingCT的吧！假设有个输入账户和个输出账户，用户通过引入个其他账户，来隐藏输入账户的身份。假设这些账户是用户真正的输入账户是，其余的是其他账户（用户不知道这些账户的余额，但是有）。所以针对每一个，用户可以计算：

还记得我们在balance proof里说的吗？当是，上面的式子是一个对于的承诺，

（（分别是对输出账户和输入账户的randomness，在MatRiCT里面称之为coin key）！而且看成公钥的话，私钥就是这个randomness！然后，只要根据环签名，证明是的承诺就可以啦！完美结束~

总结

最后做个总结，针对目前格密码中RingCT效率低的问题，MatRiCT进行改进与优化，包括基于HMC的balance proof来替代区间证明，和高效拒绝采样机制在环签名的应用。结合这两点，MatRiCT提出了高效的RingCT协议，来填补防量子攻击的RingCT的空缺。此外，MatRiCT还提出了其他小技术，来进一步提高效率。不过，相对于目前离散对数下的RingCT协议，MatRiCT的效率还是不够好。有机会可以给大家介绍新的高效方案~

参考文献

[Oakland'18] Bunz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., and Maxwell, G. Bulletproofs: Short Proofs for Confidential Transactions and More. In Proc. of the IEEE Symposium on Security and Privacy (Oakland'18), IEEE.
[ESORICS'15] Bootle, J., Cerulli, A., Chaidos, P., Ghadafi, E., Groth, J., andPetit, C. Short Accountable Ring Signatures Based on DDH. In Proc. of the European Symposium on Research in Computer Security (ESORICS'15), Springer.
[EUROCRYPT'15] Groth, J., and Kohlweiss, M. One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin. In Proc. of the Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'15), Springer
[CRYPTO'19] Esgin, M. F., Steinfeld, R., Liu, J. K., and Liu, D. Lattice-BasedZero-Knowledge Proofs: New Techniques for Shorter and Faster Constructions and Applications. In Proc. of the Annual Interna- tional Cryptology Conference (CRYPTO'19), Springer.
[CCS'19] Esgin, M. F., Zhao, R. K., Steinfeld, R., Liu, J. K., and Liu, D.MatRiCT: Efficient, Scalable and Post-Quantum Blockchain Confidential Transactions Protocol. In Proc. of the ACM Conference on Computer & Communications Security (CCS'19), ACM

封面图来自unsplash，作者XPS

往期回顾

格（Lattice）学习笔记之一：历史与基本概念格（Lattice）学习笔记之二：计算问题格（Lattice）学习笔记之三：对偶格格（Lattice）学习笔记之四：SIS与LWE 问题格（Lattice）学习笔记之五：基于SIS的OWF格（Lattice）学习笔记之六：SIS的困难度论证格（Lattice）学习笔记之七：SIS的效率与RingSIS格（Lattice）学习笔记之八：SIS OWF的应用格（Lattice）学习笔记之九：Ring-SIS与Ideal Lattice