Open Access

ARTICLE

Post-Quantum Blockchain over Lattice

Xiao Zhang^{1, 2, 3}, Faguo Wu^{1, 2, 3}, Wang Yao^{1, 2, 3, *}, Wenhua Wang⁴, Zhiming Zheng^{1, 2, 3}

1 School of Mathematics and Systems Science, Beihang University, and Key Laboratory of Mathematics, Informatics and Behavioral Semantics, Ministry of Education, Beijing, 100191, China.
2 Peng Cheng Laboratory, Shenzhen, 518055, China.
3 Beijing Advanced Innovation Center for Big Data and Brain Computing, Beihang University, Beijing, 100191, China.
4 Aviation Industry Development Research Center of China, Beijing, China.

* Corresponding Author: Wang Yao. Email: .

Computers, Materials & Continua 2020, 63(2), 845-859. https://doi.org/10.32604/cmc.2020.08008

Received 20 July 2019; Accepted 20 August 2019; Issue published 01 May 2020

Abstract

Blockchain is an emerging decentralized architecture and distributed computing paradigm underlying Bitcoin and other cryptocurrencies, and has recently attracted intensive attention from governments, financial institutions, high-tech enterprises, and the capital markets. Its cryptographic security relies on asymmetric cryptography, such as ECC, RSA. However, with the surprising development of quantum technology, asymmetric cryptography schemes mentioned above would become vulnerable. Recently, lattice-based cryptography scheme was proposed to be secure against attacks in the quantum era. In 2018, with the aid of Bonsai Trees technology, Yin et al. [Yin, Wen, Li et al. (2018)] proposed a lattice-based authentication method which can extend a lattice space to multiple lattice spaces accompanied by the corresponding key. Although their scheme has theoretical significance, it is unpractical in actual situation due to extremely large key size and signature size. In this paper, aiming at tackling the critical issue of transaction size, we propose a post quantum blockchain over lattice. By using SampleMat and signature without trapdoor, we can reduce the key size and signature size of our transaction authentication approach by a significant amount. Instead of using a whole set of vectors as a basis, we can use only one vector and rotate it enough times to form a basis. Based on the hardness assumption of Short Integer Solution (SIS), we demonstrate that the proposed anti-quantum transaction authentication scheme over lattice provides existential unforgeability against adaptive chosen-message attacks in the random oracle. As compared to the Yin et al. [Yin, Wen, Li et al. (2018)] scheme, our scheme has better performance in terms of energy consumption, signature size and signing key size. As the underlying lattice problem is intractable even for quantum computers, our scheme would work well in the quantum age.

---

Keywords

---