Post Quantum Signature Chains For Quantum Resistant BlockChain

Abstract

Financial institutions will be interested in securing their payment portals against potential future threats from future quantum computing capabilities. There is a need to make information systems “quantum resistant”. There is a need for blockchain based products to improve the security using post quantum cryptographic algorithms. The Quantum Resistant ledger is a cryptocurrency that strives to remain on the bleeding edge of security and functionality. “Quantum cryptography,” also called “quantum key distribution,” expands a short shared key into an effectively infinite shared stream. There is a need to improve the efficiency of post-quantum cryptography. Financial Firms need to have confidence in post-quantum cryptography. Software firms will continue to improve the usability of post-quantum cryptography. Block chain security will be at risk when quantum computers emerge. Functioning cryptographic systems such as DES, Triple DES, AES, RSA, Merkle hash-tree signatures, Merkle–Hellman knapsack encryption, Buchmann–Williams class-group encryption, ECDSA, HFEv−, etc are going to break with quantum computer. Shor’s algorithm is the quantum-computer discrete-logarithm algorithm that breaks RSA and DSA and ECDSA cryptographic systems.

Keywords: Post Quantum Cryptography, Quantum Resistant Blockchain, Cryptography, BlockChain

INTRODUCTION

Quantum algorithms beat the classical computers not only because they run on faster hardware but also the quantum mechanical mathematics requires fewer steps. Quantum computers work on principles based on the behavior of subatomic particles as described by quantum mechanics. Quantum mechanics is a subfield of physics related to the complex behavior of subatomic particles such as electrons. Electrons can exist in multiple distinct states at the same time known as superposition. Heisenberg uncertainty principle states that a quantum system has complete knowledge of both an object’s momentum and location. Any measurement of momentum will change the location because the act of observing the state changes it. Electrons can be “entangled”. A change to one influences another when they are physically distant from each other. To capture these complexities, quantum mechanics describes the state of subatomic particles probabilistically using complex numbers.

Grover demonstrated that a quantum computer could solve a phone book search problem proportional to the square root of the number of phone book entries in O(√n) time. Grover’s algorithm could find you in a phone book with 100 million names with just 10,000 operations.One area in which quantum computing is already having an impact is encryption. The most widely used techniques for encrypting and protecting transactions depend on the impossibility of quickly finding the prime factors of large numbers. A quantum computer could conceivably break this type of encryption. The algorithm reduces the security of symmetric key cryptography by a root factor. AES-256 will offer 128-bits of security. Finding a pre-image of a 256-bit hash function would only take 2128 time. We can increase the security of a hash function or AES by a factor of two is not very burdensome.

Researchers have set a new record for the quantum factorization of the largest number to date, 56,153, smashing the previous record of 143 that was set in 2012. There is a need to make information systems “quantum resistant”.The first robust encryption protocol prototype showed slow down of cracking process by 21 percent than the versions using elliptic curve cryptography. The mathematical operation of new protocol is based upon multiplying polynomials together and adding some random noise. In 1994 Peter Shor developed a quantum algorithm for integer factorization that runs in polynomial time.

There are upcoming products and solutions in the post quantum security area related to Data at rest, Data in transit, Access to data, Business Processes, Multi-party authentication and Multi-Party Authorisation. They present algorithms and techniques to tackle Man-in-middle detection, quantum security encryption,Phishing resistance, Biometric Security, Accountability and segregation of Duties. Data at rest can be breached by an insider or an external attacker. Data in transit can be intercepted and tampered by malicious insiders and external aggressors across networks. Confidential business data and personally identifiable information are scenarios related to data in transit. Mission critical data cannot be protected by using simple role based access and rigid role based controls. Data governance need to be enforce across the organization.

POST QUANTUM CRYPTOGRAPHY

Classic problem in security solutions is to encrypt, decrypt, sign and verify transactions and data. On a classical computer using < 2n operations, attacker tries to intercept and steal the secure data like credit card numbers and social security of the customers. With quantum computer, attacker has higher processing power and quantum algorithms like Shors to break the cryptographic systems. The goal of post quantum cryptographic designers is improve the efficiency and usability & build the usability of the new algorithms. Complete hybrid systems and high speed resistant algorithms are required to strengthen post quantum cryptography based security solutions. McEliece public key encryption, NTRU public key encryption and lattice based public key encryption systems are not yet broken by quantum algorithms.

The important classes of post quantum cryptographic systems are hash based, code based, lattice based, multivariate quadratic equations and secret key cryptography. These are secure against both quantum and classical computers. These systems can interoperate with different communications protocols and networks. The goal for post quantum cryptography research is to meet demands for cryptographic usability & flexibility and win the confidence from security experts.

POST QUANTUM SCHEMES

Post quantum schemes protect confidentiality and provide integrity, authenticity, and non-repudiation. The post quantum schemes related to post quantum cryptography are elliptic curves, lattices, isogenies, codes and hash functions. Lattices and codes based algorithms require slight modification of NP- hard problems. Their weakness is that keys are large matrices. Crystals constructions based cryptographic systems are Kyber and Dilithium.

Kyber is a key-encapsulation mechanism uses algebraic number theory. Key sizes are approximately 1kb for reasonable security parameters. Encryption and decryption time is on the order of .075 ms. The Kyber KEM seems promising for post-quantum key exchange.Dilithium is a digital signature scheme which achieves quite good performance. Public key sizes are around 1kb and signatures are 2kb. The average number of cycles required to compute a signature was around 2 million and verification took 390,000 cycles on average.

Isogenies are functions that transforms one elliptic curve into another. They use a Diffie-Hellman type protocol. The Supersingular Isogeny Diffie-Hellman scheme uses secret keys which are a chain of isogenies and public keys are curves. Isogenies traverse through a sequence of elliptic curves themselves. The group structure of the first curve is reflected in the second during transformation by isogneie. This is similar to a group homomorphism with some added structure dealing with the geometry of each curve. Supersingular elliptic curves are guaranteed to have a fixed number of isogenies from it to other supersingular curves. Isogeny-based cryptography has extremely small key sizes in the range of 330 bytes for public keys.

Hash based constructions techniques are related to good hash functions. Hash signatures use inputs to a hash function as secret keys and outputs as public keys. Hash-based signatures are not a post-quantum cryptography schemes because one cannot build a public key encryption scheme out of hashes. Hash signatures are not space efficient.

Lamport Diffie one time signature system signs a message generating uniform random string and computes the bits using cryptographic hash function. Chaining is the technique to sign more than one message. The signer includes in the signed message a generated public key to sign the next message. The verifier checks the signed message and new public key is used to check the signature of next messages. The signature of nth message consists all n-1 previous signed messages. Hashbased cryptography helps in securing post quantum public key signature systems. Codes which can be considered for error correction cryptographic algorithms are Goppa, alternate, GRS, Gabidulin, Reed-Muller, Algebraic, BCH and Graph based codes.

Most promising of all is Mceliece public key crypto system with Goppa codes. Mceliece is based on the difficult problem of decoding unknown error-correcting code. Goppa codes have a fast polynomial time decoding algorithm. From the family of Goppa codes, private key is chosen from a generator matrix. The generator matrix is from the key space which consists of invertible binary matrix and permutation matrix. Different families are suggested for Goppa codes such as Generalized Reed-Solomon Codes, Gabidulin Codes and Reed Muller Codes. Pierre Loidreau modified by using automorphism group of Goppa codes. He did not increase the size of the public key. As the number of Goppa Codes increases exponentially with the length of the code and generating polynomial degree, the structural attacks against the system will be tough to penetrate. The work factor for the attacks would increase exponentially.

McEliece public key cryptography system has generator matrix G with parameters n, t to generate code G over F of dimension k and minimum distance d >= 2t +1. S is a k x k random binary non singular matrix. P is a n x n random permutation matrix. SGP is computed by the matrix Gpub k x n matrix for Public key. Private key is based on S, Decoding algorithm DG and P the permutation matrix. To encrypt the message, use E(Gpub,t) function and decryption is done by using D(S,DG ,P) function.

Post Quantum Signature Chains

Naor Yung signature chains are related to signing a message which will have a hash of the public key to sign the next signature. This creates a chain of related messages. The public key of the chain’s first node is used as a long term public key to create a hash address. Verifying a long term public key is to check if it belongs to the corresponding signature chain. It is tough to change previously created signatures as chaining provide forward security to signature schemes.

The chain is forked by signing n new public key hashes instead of one. This results in a tree of signatures so that a previous fork can be used in case current chain is broken. Verification of signature happens when signed public key hashes are sent along with it. The signature of a long term address σlt as a tuple of one time signature and a number of public key hashes.

σlt = (σots,pkh0,…,pkhb−1)

The entire chain of signatures need to be stored so that every previous link in signature chain can be looked up. Many algorithms rely on signature chains which have key generation, signing and verification algorithms.

QUANTUM RESISTANT BLOCKCHAIN

A blockchain is a ledger that records information related to transactions. The transactions are continually added by a block size. At the end of a given time period, the block is encrypted using a hashing function. Public permission-less blockchain networks allow disruption of centralized player. Public blockchains ensure immutable records and security of transactions. Quantum computers can break the hash signatures using Shor’s algorithm. There is a need for a post quantum secure signature scheme for post quantum block chain security.

The Quantum Resistant ledger is a cryptocurrency that strives to remain on the bleeding edge of security and functionality. It features quantum resistant cryptographic protocols and a custom proof of stake system.The cryptocurrency ledger is resistant to both classical and quantum computing attack. It uses hash-based digital signatures which are quantum-resistant. The ledger provides an ultra secure backup store of value in the event of a sudden advance in quantum computing. The initial aim of the chain is to offer a low volume of ultra secure transactions in the first iteration with guaranteed longevity.

Quantum resistant hashtag based signature tree like Extended Merkel signature scheme and a low power proof of stake algorithm is used for quantum resistant ledgers. Extended Merkel signature uses a one time signature scheme. This scheme signs one message with one key. One Time Signature (OTS) key is used to sign two different messages so that an attacker could generate a valid signature for a third message you had never signed before. An attacker can generate a valid transaction which is never approved. One can use a different OTS key for each message.

A quantum secure signature scheme combined with a hash based signature scheme with Naor Yung chaining secures a block chain. Extended Naor Yung Signature scheme has algorithms for key generation, signing and verification of block chain transaction blocks. The entire chain is stored in the block chain and look up for finding one with root public keys is easy. Hash chains suffer from the limitation related to having a finite number of links which when exhausted requires the system to be re-initialized. Conventional Hash chain needs to be replaced by Re-initializable Hash Chain. Reinitializable hash chain has the property that if its links are exhausted. It can be securely re-initialized in a non-repudiable manner to result in another hash chain. This process can be continued indefinitely to give rise to an infinite length hash chain. Thus an infinite number of finite length hash chains tied together.

CONCLUSION

Post Quantum cryptography is catching up and four types of crypto systems elliptic curves, lattices, isogenies and hash based signatures are grabbing attention in academia and NIST. McEliece with Goppa codes is the reliable crypto system. Using a Shor’s algorithm variant, quantum computer underpins the security of blockchain. Quantum cryptographic codes can secure block chains and the transactions. Quantum key distribution with post quantum cryptography helps in securing block chain. Block chain communities are proactively looking to come up with innovative techniques to tackle quantum computing process power.

REFERENCES

NIST Post Quantum Cryptography Project
Block Chain Research Institute Quantum Proofing Block Chain
European Telecommunications Standards Institute Quantum Safe Cryptography

About the Author:

Bhagvan Kommadi is the Founder of Architect Corner & has around 18 years’ experience in the industry, ranging from large scale enterprise development to helping incubate software product start-ups. He has done Masters in Industrial Systems Engineering at Georgia Institute of Technology (1997) and Bachelors in Aerospace Engineering from Indian Institute of Technology, Madras (1993). He is member of IFX forum,Oracle JCP and participant in Java Community Process.

He founded Quantica Computacao, the first quantum computing startup in India. Bhagvan has engineered and developed simulators and tools in the area of quantum technology using IBM Q, Microsoft Q# and Google QScript. Company’s focus is on developing quantum cryptographic tools which will be able to provide quantum proof data security, which will help the banking institution to protect their transactions.

He is a hands on CTO who has been contributing to open source , blogs , latest technologies stack like go, python, Django, node.js & java, mysql, postgres, mongo and cassandra.He is an Individual member of Oracle JCP : https://jcp.org/en/participation/members/K. He is the technical reviewer for Packt publishing and reviewed — building-serverless-python-web-services- zappa : https://www.packtpub.com/application-development/building- serverless-python-web-services-zappa . He is writing for Packt Publishing — Hands-On Data Structures and Algorithms with Go. He has presented in PyCon before on topics such as Adaptive Learning etc.,