Paper 2020/1362

Lattice-Based Proof-of-Work for Post-Quantum Blockchains

Rouzbeh Behnia, Eamonn W. Postlethwaite, Muslum Ozgur Ozmen, and Attila Altay Yavuz


Proof of Work (PoW) protocols, originally proposed to circumvent DoS and email spam attacks, are now at the heart of the majority of recent cryptocurrencies. Current popular PoW protocols are based on hash puzzles. These puzzles are solved via a brute force search for a hash output with particular properties, such as a certain number of leading zeros. By considering the hash as a random function, and fixing a priori a sufficiently large search space, Grover's search algorithm gives an asymptotic quadratic advantage to quantum machines over classical machines. In this paper, as a step towards a fuller understanding of post quantum blockchains, we propose a PoW protocol for which quantum machines have a smaller asymptotic advantage. Specifically, for a lattice of rank \(n\) sampled from a particular class, our protocol provides as the PoW an instance of the Hermite Shortest Vector Problem (Hermite-SVP) in the Euclidean norm, to a small approximation factor. Asymptotically, the best known classical and quantum algorithms that directly solve SVP type problems are heuristic lattice sieves, which run in time \(2^{0.292n + o(n)}\) and \(2^{0.265n + o(n)}\) respectively. We discuss recent advances in SVP type problem solvers and give examples of where the impetus provided by a lattice based PoW would help explore often complex optimization spaces.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
BlockchainsProof-of-workPost-quantum cryptographyConsensus protocolsLattice-based cryptographyShortest vector problem
Contact author(s)
rouzbeh behnia @ gmail com
2020-10-29: revised
2020-10-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rouzbeh Behnia and Eamonn W.  Postlethwaite and Muslum Ozgur Ozmen and Attila Altay Yavuz},
      title = {Lattice-Based Proof-of-Work for Post-Quantum Blockchains},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1362},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.