在匿名加密货币中，在保障隐私的同时，如何高效地验证交易的合法性一直是比较热门的话题。而格密码具有的抵抗量子攻击的特性，也一直被认为是下一代密码学的研究热点。这两个热点问题结合，就碰撞出了19年CCS的MatRiCT——抗量子攻击的匿名保密交易协议。之前啃这篇文章的时候，对格密码不是很了解。在看完东泽大神的格密码科普系列后，再读这篇文章，很多问题感觉豁然开朗！这里我就尽量避免格密码里的复杂公式，跟大家来一起学习MatRiCT吧~
保密交易的验证
一个RingCT协议大致提供了以下两点安全，每种均采用一个零知识证明完成：
· 交易金额保密：通过区间证明（range proof）实现；
· 用户身份保密：通过环签名（linkable ring signature）实现。
格密码效率
虽然在格密码中，也已经有对于以上的区间证明和环签名的解决方案[CRYPTO’19]，但是相比离散对数假设下的方案，其效率是极低的。比如对于一个区间证明，Bulletproof仅需不到1KB的空间，而[CRYPTO’19]需要花费约100KB。
在格密码下低效的主要原因之一是承诺的大小远超其他元素的大小。这个问题是因为要保证格密码中的问题依然困难（M-SIS和M-LWE）被迫选择较大的安全参数造成的。此外在区间证明中，因为需要隐藏的交易金额并不一定是short的，所以没办法采用Hashed-Message Commitment（HMC）的承诺方法，而只能采用Unbounded-Message Commitment（UMC）。这里我们不去管HMC和UMC是如何实现的，简单对比下他们的优缺点：
MatRiCT概述
MatRiCT就是匿名货币的基于格密码的高效RingCT协议[CCS’19]（这里容我插一句，其实效率相比传统方案并不高，只是提高了[CRYPTO’19]的性能）。其主要包括两个部分：
Balance Proof：替换传统区间证明并达到同样效果；
高效环签名：提高了传统环签名的拒绝采样的效率。
此外，MatRiCT针对匿名货币的场景还有通过其他小技术进行优化和扩展性能。这些小技术比较简单直接，所以这里就不具体介绍了。具体包括：
· 承诺组合：组合多个线性关系的承诺为一个承诺；
· 两组参数：对于二进制证明和其他部分采用两组参数，优化证明空间；
· 可验证承诺：基于HMC设计的有“迷你陷门”的承诺方式，审计员可以通过其私钥和陷门来逆向承诺，获得消息明文（这个需要根据应用场景选择是否采用）；
· RingCT协议新模型：通过加入区块链状态等其他信息，扩展RingCT模型，并使之支持stealth addresses技术。
MatRiCT中Balance Proof
我们之前说过对于一个交易，首先保证以下两个要求：
1. 输入、输出金额非负；
2. 输入之和等于输出之和。
MatRiCT中环签名
MatRiCT发现delta有一个特点：仅有一个元素是1，其余均为0。根据这个特点，可以设计一种高效的拒绝采样（rejection sampling）方式。下面先插播一段格密码中拒绝采样的原理，对于这个内容清楚的小伙伴们可以直接跳过~
MatRingCT
总结
最后做个总结，针对目前格密码中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