Progress on Hcash's Post-Quantum R&D [Part 1]

[hcash]

I.Research and Design of Post-Quantum Technology Solution
1.Technology choice and solution design of Post-Quantum Signature:
•Security and Performance Analysis and Assessment of existing post-quantum signature solution We have carried out deep security and performance analysis and assessment of the following post-quantum signature solution such as Hash-based signature schemes: MSS (Merkle Signature Scheme), XMSS (eXended Merkle Signature Scheme), LMS, SPHINCS, NSW; Lattice-based signature schemes: GVP, LYU, GLP, BLISS, DILITHIUM, NTRU; Code-based signature schemes: CFS, QUARTZ; Multivariate-polynomial-based signature schemes: RAINBOW, etc. Compared to traditional signature solution (such as ECDSA algorithm commonly used in cryptocurrency system), post-quantum signature solution’s public key and signature are much longer. If we simply introduce post-quantum signature into existing cryptocurrency or Blockchain system, TPS will be reduced significantly. Take bitcoin for example, current TPS is 7 transactions per second. If we introduce post-quantum signature DILITHIUM, its TPS will be reduced to 0.389 transaction/second.
•In the design of Hcash post-quantum solution, we wish to achieve the following 4 features:
1) Compatibility: Compatible with existing ECDSA (Elliptic Curve Digital Signature Algorithm) signature solution;
2) Flexibility: Support multiple post-quantum signature solutions that are thoroughly analysed, assessed and proved by international cryptography research institutions, meanwhile their security and performance must be outstanding.
3) Security: the post-quantum solution must be proved secure in theory, and side-channel attack proof in practice;
4) high performance: Signing and signature verification must be fast. Most importantly, the public key and signature must be short.

•Based upon the principles described above, we have made our technology choice. On one hand, from security point of view, we have chosen Hash function based post-quantum signature solution (MSS or LMS), these solutions have weak security hypothesis and their security rely on Hash function. In another word, if the Hash function is secure, then the solution is secure. In our solution, we choose SHA-3 (that is Keccak. Keccak is chosen by NIST as international standard Hash function in October 2012). According to thorough analysis and assessment on Keccak done by international cryptography search institutions, we expect Keccak is very secure for a very long period in future. Compared to traditional computers, quantum computers do not have much advantage on attacking (collision attack, pre-image attack, secondary pre-image attack) Hash functions, which means Keccak function based MSS or LMS will have very strong security for a very long period in future. Besides, Keccak function based MSS or LMS solution is side-channel attack proof. On the other hand, from performance point of view (including signing / signature verification performance, public key / signature length), public key and signature length can significantly affect cryptocurrency or blockchain system’s TPS, therefore we have chosen Bliss whose overall performance is the best. This solution’s security is built on top of difficult mathematics problem based on LWE. Currently quantum computer does not have effective algorithm to solve the difficult math problem based on LWE. Because Bliss algorithm’s signing and signature verification performance is good, and its public key and signature length is shortest among the existing post-quantum signature algorithms, Hcash’s TPS will benefit from Bliss. To be clear, MSS, LMS and Bliss algorithms are all analysed, assessed and proved by international cryptography research institutions and their security and performance are all outstanding. (Although MSS/LMS has different security hypothesis from Bliss, their security can all be proved in theory)
•Based on the technology choice, we will adopt Keccak function based MSS or LMS (strong theoretical security and side-channel attack proof), and LWE based Bliss algorithm (theoretical security depends on LWE’s difficult math problem and its performance is the best among the existing post-quantum signature solutions). However, we still need to solve the following two critical problems:
1) public key and signature are much longer than traditional digital signature ECDSA’s public key and signature. If we implement these signature algorithms in cryptocurrency or blockchain, transaction size will increase a lot and TPS will be reduced significantly.
2) Discrete Gauss Sampling (DGS) module in Bliss algorithm has side-channel attack risk in practice. For problem 1, we propose a new SegWit (Segregated Witness) solution which solve the problem quite well.
For problem 2, there are some existing side-channel attack to Bliss algorithm. We have to point out that these attacks are difficult to implement. In the attack to multiplication calculation, the author himself points out that the attack which utilises Markov model cannot succeed if the Hamming weight acquired has relatively high level noise. In practise, Hamming weight always has some noise. When attacking sampling function with power consumption and electromagnetic information, firstly data quality will affect branch clause analysis, secondly even if data quality is high, it is difficult engineering job to accurately locate the divulge point on the curve. For the same reason, when analysing applications on the system using branch trace, although every branch clause can be recorded accurately (without noise), it is difficult to locate the attacking point among large amount of branch records. Regarding Cache attack, how to keep flush and reload happen alternatively in time series is a tough problem. It’s hard to implement without changing the source code. Although it’s very difficult to implement these side-channel attacks, we should pay enough attention to potential side-channel leaking problem in Bliss algorithm. Hence we propose effective protection solution after deeply analysing possible side-channel information leaking points in Bliss algorithm. This solution does not harm Bliss algorithm’s performance (Most importantly, the solution doesn’t change public key and signature length at all). The research outcome mentioned above will guarantee we implement highly secure and performant post-quantum feature in Hcash.

•The advantages of our solutions are:
1.Compatibility: before quantum computers come into use, cryptocurrency and blockchain systems can still use ECDSA signature solution. Our solution is compatible with existing ECDSA signature solution, hence it can not only connect with current mainstream cryptocurrency exchange platforms, but also build a foundation to support cross chain interaction in future.
2.Flexibility: our solution supports two post-quantum signature solutions that are thoroughly analysed, assessed and proved by international cryptography research institutions. Their security and performance are both outstanding. It will provide great flexibility and sound security for Hcash
3.Security: Our solution supports two post-quantum signature algorithms: MSS/LMS and Bliss. For MSS/LMS, its security hypothesis is weak (that is, its security only relies on the security of SHA-3 function). If SHA-3 function is secure, then the solution is secure. According to thorough analysis and assessment on Keccak done by international cryptography search institutions, we expect Keccak is very secure for a very long period in future. Compared to traditional computers, quantum computers do not have much advantage on attacking (collision attack, pre-image attack, secondary pre-image attack) Hash functions, which means Hash adopting Keccak based MSS/LMS will have very strong security for a very long period in future. Further more, Keccak based MSS/LMS solution is side-channel attack proof. For Bliss algorithm, its security is based on LWE’s difficult math problem (under this hypothesis it can be proved secure). So far quantum computers have no effective algorithms to solve LWE’s difficult math problem that Bliss algorithm relies on. Besides, we thoroughly analysed possible side-channel information leaks in Bliss algorithm and propose an innovative and effective protection solution, so that Bliss algorithm can effective prevent side-channel attack without compromising performance.
4.High performance: our solution supports 2 post-quantum algorithms whose signing/signature verification and public key/signature length are both outstanding among existing algorithms. Because post-quantum signature solution’s public key and signature length are much longer than traditional ECDSA’s, it will increase transaction size a lot and reduce the number of transaction in each block, and reduce TPS in the end. To solve this problem, we propose an innovative SegWit scheme which can solve this problem quite well. It’s deserved to be mentioned that, our post-quantum solution integrated with our new combined consensus scheme (which is already implemented in Hcash) will materialise our absolute superiority in TPS. e.g., if we implement DILITHIUM signature in Bitcoin, its TPS is maximum 0.389 transactions / second, while if we implement our post-quantum solution, its TPS is about 150 transactions / second.
5.Usability: our post-quantum signature solution can be used widely in existing cryptocurrency and blockchain systems.