One of the big investment/government-funding hypes of quantum computing is the threat it poses to encryption systems. But it is hype because it assumes that the mathematics and engineering communities can’t invent new encryption techniques that are invulnerable (enough) to number-factoring attacks based on Shor’s algorithm and the equivalents. One of the few things interesting about quantum computing is which will occur first: the engineering of a quantum computing with a large enough number of qubits to make Shor’s algorithm a threat, OR, the engineering of encryption algorithms resistant to attack by a large number of qubits running Shor’s algorithm. Most likely the latter, not that it matters, as engineering new algorithms resistant to quantum attack will definitely succeed enough to make investments in quantum computing for their potential use as security attack weapons as a waste of money.
One estimate pushes quantum factoring as a threat out to 2039:
“... we estimate that the proof-of-concept fault-tolerant computation based on superconducting technology is unlikely (<5% confidence) to be exhibited before 2026, and that quantum devices capable of factoring RSA-2048 are unlikely (<5% confidence) to exist before 2030.”If so, by 2039, it will be too late for any economic use, because by then the post-quantum systems will be in the marketplace. This prediction in a paper by Jaime Sevilla and C. Jess Riesdel, “Forecasting timelines of quantum computing”, available at: http://arxiv.org/pdf/2009.05045.pdf
Despite decades of research, there’s no viable roadmap for how to scale quantum cryptography to secure real-world data and communications for the masses. ... From a practical standpoint, then, it doesn’t appear that quantum cryptography will be anything more than a physically elaborate and costly -- and, for many applications, largely ignorable -- method of securely delivering cryptographic keys anytime soon. ... “To me [quantum cryptography] seems like a solution to a problem that we don’t really have.” ... “Quantum cryptography is not going to replace classical cryptography anytime soon.”And this skepticism is much true for the rise-and-fall of quantum radar, for which one of its founders, Jeffrey Shapiro, raises doubts that could equally apply to quantum decryption threats: “There is just a lot of problems that make it hard for me to believe that this [quantum radar] is going to be of any use.” ( www.sciencemag.org/news/2020/09/short-weird-life-and-potential-afterlife-quantum-radar)
“CIA has moved too slowly to put in place the safeguards that we knew were necessary given successive breaches to other US Government agencies.”, the report said, finding that “most of our sensitive cyber weapons were not compartmented, users shared systems administrator-level passwords, there were no effective removable media [thumb-drive] controls, and historical data was available to users
What follows are mentions of recent developments for engineering new encryption algorithms resistant to quantum attack. A nice, brief, introduction to the five main post-quantum cryptography techniques (elliptic curves, lattices, isogenies, codes and hash functions) is at: blog.trailofbits.com/2018/10/22/a-guide-to-post-quantum-cryptography/
All your need is DAG
Idit Keidar et alia, Technion and Novi Research, 16 February 2021
ABstract: We present DAG-Rider, the first asynchronous Byzantine Atomic Broadcast protocol that achieves optimal resilience, optimal amortized communication complexity, and optimal time complexity [for geo-replicated fault-tolerant reliability systems]. DAG-Rider is post-quantum safe and ensures that all messages proposed by correct processes eventually get decided. We construct DAG-Rider in two layers: In the first layer, processes reliably broadcast theirproposals and build a structured Directed Acyclic Graph (DAG) of the communication among them. In the second layer, processes locally observe their DAGs and totally order all proposals with no extra communication.
Physical security in the post-quantum era: a survey on side-channel analysis, random number generations, and physically unclonable functions
Sreeja Chowdhury et alia, Univ. of Florida – Gainesville, 8 February 2021
A nice paper that emphasizes an important point about post-quantum cryptography. That is beyond having a powerful algorithm, you need to understand and manage the physical security aspects of implementing your algorithm in the real world. One solution is to make use of non-computing quantum devices, especially when it comes to key generation.
Terra Quantum (Switzerland) announces how to make post-quantum encryption systems resistant to quantum attacks on the hash function
Bloomberg Quint, 08 February 2021
Article reports that Terra Quantum has found a way to invert the ‘hash functions’ used in encryption protocols, pre- and post-quantum, using quantum computers that “could be available in the next few years”. Even if a threat, Terra is offering a new post-quantum encryption protocol that is resistant to such attacks.
An open-source library of large integer polynomial multipliers [for post-quantum hardware cryptocores]
Malik Imran et alia, Tallinn Univ. of Tech., 27 January 2021
Polynomial multiplication is a bottleneck in most public-key cryptography protocols, including elliptic-curve cryptography and several of the post-quantum cryptography algorithms being studied. In this paper, we present a library of various large integer polynomial multipliers to be used in hardware cryptocores. Our library contains both digitized and non-digitized multiplier flavours for circuit designers to choose from. The library is supported by a C++ generator that automatically produces the multipliers’ logic in Verilog HDL that is amenable for FPGA and ASIC designs. Moreover, for ASICs, it also generates configurable and parameterizable synthesis scripts.
Post-quantum security of the bitcoin backbone and quantum multi-solution Bernoulli search
Alexandru Cojocaru et alias, Univ. Edinburgh, 30 December 2020
“We show that the security of the bitcoin holds as long as the quantum computational hashing power of the adversary in the Quantum Random Oracle model is appropriately bounded. ... Perhaps surprisingly, the wait time for safe settlement in the case of quantum adversaries matches (up to a constant) the safe settlement time in the setting of classical adversaries and thus does not result in any further overhead.”
Verifiable post-quantum secure electronic voting systems
Chinese Patent CN108494738B
IPSEC cipher machine with quantum computation resistance function
Chinese Patent CN212115338U
PQ-Fabric: a permissioned blockchain secure from both classical and quantum attack
Bhargav Das et alia, Univ. Waterloo, 23 December 2020
Abstract: In this paper, we propose a redesign of the credential-management procedures and related specifications in order to incorporate hybrid digital signatures (i.e., protection against both classical and quantum attacks using two signature schemes) that include the quantum-safe signatures from the upcoming NIST standards. We also validate our proposal by providing an implementation of Fabric along with the Open Quantum Safe library.
Google adopts the Signal Encryption Protocol (SEP)
in “Hacker Lexicon: what is the Signal Encryption Protocol?”, Wired, Nov. 2020
www.wired.com/story/signal-encryption-protocol-hacker-lexicon/ SEP is an end-to-end encryption protocol long-used by the popular messaging app WhatsApp, and now adopted by Google for its Android messaging app. SEP’s strength is that it implements “perfect forward secrecy”, which newly generates one of the encryption/decryption keys in the protocol after a message is sent. This makes using quantum computing for decrypting such messages practically useless. Any given the huge popularity of these messaging apps, is yet another reason quantum computing poses no threat to classical cryptographic systems.
Indistinguishability obfuscation from well-founded assumptions
Aayush Jain et alia, UCLA/UW, 18 August 2020
The authors show how to build indistinguishability obfuscation algorithms using only four “standard” security assumptions. These algorithms could be used as a basis for, and to strengthen, all other cryptographic protocols – “one cryptographic primitive to rule them all”. One of the assumptions might be susceptible to quantum attack, but work is being done to prevent this. Combining this technique with post-quantum encryption systems pretty much renders quantum computing useless as a security threat. Nice Quanta article at: www.quantamagazine.org/computer-scientists-achieve-crown-jewel-of-cryptography-20201110/
Visa and JPMorgan are already preparing for potential quantum cyberattacks
Sara Castellanos, Wall Street Journal, 09 October 2020
An article on how the financial industry is preparing now to defeat possible future quantum computing attacks on encryption systems, for example, using any one of the multiple post-quantum cryptographic systems under development.
Forecasting timelines of quantum computing
Jaime Sevilla and C. Jess Riedel, Aberdeen Univ. / NTT Research, 10 September 2020
Abstract: ... that quantum devices capable of factoring RSA-2048 are unlikely (< 5%) to exist before 2039.
Network coding-based post-quantum cryptography
Alejandro Cohen et al., MIT-RLE, 03 September 2020
Abstract: We propose a novel hybrid universal network-coding cryptosystem to obtain secure post-quantum cryptography at high communication rates. ... We construct a coding scheme in which an arbitrary secure cryptosystem is utilized on a subset of links, while a pre-processing similar to the one in individual security is utilized. ... A perhaps surprising consequence of our scheme is that, to guarantee a computational security level, it is sufficient to encrypt a single link using a computational post-quantum scheme.
MAKE: a matrix action key exchange
Nael Rahman and Vladimir Shpilrain, City College NY, 01 September 2020
Abstract: We offer a public key exchange protocol based on a semidirect product of two cyclic (semi)groups of matrices over Zp. One of the (semi)groups is additive, the other one multiplicative. This allows us to take advantage of both operations on matrices to diffuse information. We note that in our protocol, no power of any matrix or of any element of Zp is ever exposed, so all standard attacks on Diffie-Hellman-like protocols (including Shor’s quantum algorithm attack) are not applicable.
Experimental demonstrations of unconditional security in a purely classical regime
Byoung Ham, Gwangju Institute of Science and Technology, 14 August 2020
So far, unconditional security in key distribution processes has been confined to quantum key distribution (QKD) protocols based on the no-cloning theorem of nonorthogonal bases. Recently, a completely different approach, the unconditionally secured classical key distribution (USCKD), has been proposed for unconditional security in the purely classical regime. Unlike QKD, both classical channels and orthogonal bases are key ingredients in USCKD, where unconditional security is provided by deterministic randomness via path superposition-based reversible unitary transformations in a coupled Mach-Zehnder interferometer. Here, the first experimental demonstration of the USCKD protocol is presented.
The quest for quantum-proof encryption just made a great leap forward
MIT Technology Review, 03 August 2020
There are 15 contenders in NIST’s competition for quantum-proof encryption, most are lattice-based cryptography. Even with one or more winners, if the quantum computing world, much like category theory, doesn’t find something economically useful to do with quantum computing, quantum decryption will be even less of a threat.
State-of-the-art cryptography goes post-quantum: the TinySSH server aims to eliminate post-quantum cryptography weaknesses
opensource.com/article/20/7/tinyssh, July 2020
TinySSH, a minimal SSH server with an embedded focus, has implemented a hybrid key exchange involvingNTRU Prime (a round 2 finalist in the NIST competition) combined with conventional ed25519 elliptic curve keys. The approach allows ed25519 keys to generally stay in use, but transparently adds the appearance of "quantum-forward secrecy".
SPHINCS+ post-quantum digital signature scheme with Streebog hash function
E.O. Kiktenko et al., Russian Quantum Center, June 2020
Abstract: ... One of the most promising candidates for a post-quantum signature scheme is SPHINCS+, which is based on cryptographic hash functions. In this contribution, we analyze the use of the new Russian standardized hash function, known as Streebog [comparable in speed to SHA2], for the implementation of the SPHINCS+ signature scheme [which is provably secure].
A fast finite field multiple for SIKE
Yeonsoo Jeon and Dongsuk Jeon, Seoul National University, June 2020
Abstract: Various post-quantum cryptography algorithms have been recently proposed. Supersingluar isogeny Diffie-Hellman key exchange (SIKE) is one of the most promising candidates due to its small key size. However, the SIKE scheme requires numerous finite field multiplications for its isogeny computation, and hence suffers from slow encryption and decryption process. In this paper, we propose a fast finite field multiplier design that performs multiplications in GF(p) with high throughput and low latency.
IBM releases toolkit for fully homomorphic encryption
ZDNet, 05 June 2020
For over a decade, IBM has been working on fully homomorphic encryption – which allows for data calculation and transformation while the data remains encrypted. A difficult technology to implement, IBM is releasing a toolkit to allow programmers to start developing practical security systems using homomorphic encryption. And as it is based on lattice cryptography, it is mostly quantum computing resistant.
An economic model for quantum key-recovery attacks against ideal ciphers
Benjamin Harsha and Jeremiah Blochi, Purdue University, May 2020
This paper studies the practical aspects of using quantum computing to crack passwords, focusing on real world economics (mostly absent from quantum computing papers): “We argue that, even with optimistic predictions for advances in quantum computing, 128 bit keys (as used in common cipher implementations like AES-128) provide adequate security against quantum attacks in almost all use cases”. The economics is that in most cases, the cost to use quantum computing to crack a key being used is more than the economic value of the information obtained.
Physical security in the post-quantum era
Sreeja Chowdhury et alia, Univ. of Florida, May 2020
This paper emphasizes the importance of the physical and human element in security systems, for which the latest pretty/fancy technology (such as quantum cryptography) offers little. “While considerable effort has been devoted to the design of quantum-resistant and quantum-enhanced schemes, little effort has been made to understanding their physical security. Physical security deals with the design and implementation of security measures fulfilling the practical requirements of cryptographic primitives, which are equally essential for classic and quantum ones.” That is, it doesn’t matter how powerful your quantum cryptography system is, if you use “PASSWORD” as the password.
Make quantum indistinguishability great again
Tommaso Gagliardoni et alia, Unversität Darmstadt, March 2020
Abstract: ... Nevertheless, we identify a class of encryption schemes, which we call recoverable, that allow to avoid decryption failures given knowledge of the original encryption randomness, and we show that many real-world quantum-resistant schemes, including many NIST candidates, are of this type. Then we show how to define and construct type-2 encryption operators for schemes that are fully correct or recoverable. Moreover, we show that for recoverable schemes, the type-2 operator can be efficiently implemented even without knowledge of the secret key. This means that, for the public key case, type-2 operators are actually very natural, and already included in the traditional “post-quantum” definition of security.
Physical Layer Security: authentication, integrity and confidentiality
Mahdi Shakiba-Herfeh et alia, Université Cergy-Pontoise, January 2020
Abstract: The goal of physical layer security (PLS) is to use the properties of the physical layer – including the wireless communication medium and/or the transceiver hardware -- to enable critical aspects of secure communications. In particular, PLS can be employed to provide i) node authentication, ii) message authentication, and, iii) message confidentiality. Unlike the corresponding classical cryptographic approaches which are all based on computational security, PLS's added strength is that it is based on information theoretic security, in which no limitation with respect to the opponent’s computational power is assumed and is therefore inherently quantum resistant. ...
QSOR: quantum-safe Onion routing [for the Tor network]
Zsolt Tujner et alia, THO, The Hague, January 2020
Abstract: In this work, we propose a study on the use of post-quantum cryptographic primitives for the Tor network in order to make it safe in a quantum world. With this aim, the underlying keying material has first been analysed. We observe that breaking the security of the algorithms/protocols that use long- and medium-term keys (usually RSA keys) have the highest impact in security. Therefore, we investigate the cost of quantum-safe variants. These include key generation, key encapsulation and decapsulation. Six different post-quantum cryptographic algorithms that ensure level 1 NIST security are evaluated. We further target the Tor circuit creation operation and evaluate the overhead of the post-quantum variant. This comparative study is performed through a reference implementation based on SweetOnions that simulates Tor with slight simplifications. We show that a quantum-safe Tor circuit creation is possible and suggest two versions - one that can be used in a purely quantum-safe setting, and one that can be used in a hybrid setting.
Mobile energy requirements of upcoming NIST Post-Quantum Cryptography standards
Markku-Juhani Saarinen, PQShield, Oxford, UK, January 2020
Abstract ... We propose [energy, bandwidth, latency] metrics and guidelines for PQC algorithm usage in IoT and mobile systems based on our findings. Our evidence supports the view that fast-structured-lattice PQC schemes are the preferred choice for [network]-connected mobile devices in most use cases, even when per-bit data transmission energy cost is relatively high.
Performance analysis of Transport Layer Security (TLS) for quantum robust cryptography on a constrained (low-power) device
Jon Barton et alia, Edinburgh Napier University, September 2019
Conclusion: “The leading question has been answered in this paper by providing benchmarks on a constrained device for the front-running algorithms in the NIST standardisation exercise which is currently in progress. ... SABER is the clear winner for the key exchange mechanism (KEM) with operations under a millisecond and TLS handshake in under 90 ms. ... For a signature scheme, MQDSS gives a good balance of theoretical basis and reasonable run time. The issue of which ciphersuite to trust is epistemological rather than purely mathematical. Lattice-based systems are the fastest of many contenders that have been shown practicable on constrained devices.” Paper has an extensive bibliography.
Pre- and post-quantum Diffie-Hellman from groups, actions, and isogenies
Benjamin Smith, Université Paris-Saclay, December 2019
Abstract: Diffie–Hellman key exchange is at the foundations of public-key cryptography, but conventional group-based Diffie–Hellman is vulnerable to Shor’s quantum algorithm. A range of “post-quantum Diffie–Hellman” protocols have been proposed to mitigate this threat, including the Couveignes, Rostovtsev–Stolbunov, SIDH, and CSIDH schemes, all based on the combinatorial and number-theoretic structures formed by isogenies of elliptic curves. Pre- and post-quantum Diffie–Hellman schemes resemble each other at the highest level, but the further down we dive, the more differences emerge -- differences that are critical when we use Diffie–Hellman as a basic component in more complicated constructions. In this survey we compare and contrast pre- and post-quantum Diffie–Hellman algorithms, highlighting some important subtleties.
RAMESSES: a rank metric encryption scheme with short keys
Julien Lavauzelle et alia, Univ. Rennes, November 2019
“We present a rank metric code-based encryption scheme with key and ciphertext sizes comparable to that of isogeny-based cryptography for an equivalent security level. The system also benefits from efficient encryption and decryption algorithms, which rely on linear algebra operations over finite fields of moderate sizes. The security only relies on rank metric decoding problems, and does not require to hide the structure of a code. Based on the current knowledge, those problems cannot be efficiently solved by a quantum computer. ...”
The Niederreiter cryptosystem and quasi-cyclic codes that resist quantum Fourier sampling
Upendra Kapshikar and Ayan Mahalanobis, November 2019
"... We prove, if these quasi-cyclic codes satisfy certain conditions, the corresponding Niederreiter cryptosystem is resistant to the hidden subgroup problem using quantum Fourier sampling [as an attack]." They have a follow-up paper: A quantum-secure Niederreiter cryptosystem using quasi-cyclic codes, Upendra Kapshikar and Ayan Mahalanobis, May 2020 - arxiv.org/pdf/1803.07827.pdf - "In this paper, we describe a new variant of Niederreiter cryptosystem over quasi-cyclic codes of ratem (m-1)/m. We show that the proposed cryptosystem is quantum secure, in particular, it resists quantum Fourier sampling and has better transmission rate with smaller keys compared to the one using binary Goppa codes.”
The [minimal] impact of quantum computing on real-world security: a 5G case study
Chris Mitchell, Univ. London, November 2019
"This leads naturally to the specification of a series of simple, phased, recommended changes intended to ensure that the security of 5G (as well as 3G and 4G) is not badly damaged if and when large scale quantum computing becomes a practical reality. By exploiting backwards-compatibility features of the 5G security system design, we are able to describe a multi-phase approach to upgrading security that allows for a simple and smooth migration to a post-quantum-secure system."
Sapphire: a configurable crypto-processor for post-quantum lattice-based protocols
Ustav Banerjee et al., MIT Dept. of EECS, October 2019
“Cryptographers are working on quantum-resistant algorithms, and lattice-based cryptography has emerged as a prime candidate. However, high computational complexity of these algorithms makes it challenging to implement lattice-based protocols on low-power embedded devices. To address this challenge, we present Sapphire – a lattice cryptography processor with configurable parameters. Efficient sampling, with a SHA-3-based PRNG, provides two orders of magnitude energy savings; a single-port RAM-based number theoretic transform memory architecture is proposed, which provides 124k-gate area savings; while a low-power modular arithmetic unit accelerates polynomial computations.”
PQC: triple decomposition problem applied to GL(d,Fp) – a secure framework for canonical non-commutative cryptography
Pedro Hecht, October 2018
“We give support to the fact that this framework is cryptographically secure against classical attacks like linear algebra attacks, length-based attacks, side-channel attacks against square (or duplicate) and multiply (or sum) algorithm, high sensitivity to pseudo random deterministic generators, etc. At same time it is immune against quantum attacks (using Grover and Shor), if the size parameters are carefully selected."
Why quantum computing will not destabilize international security: the political logic of cryptology
Jon Lindsay, Univ. Toronto School of Global Affairs, 29 June 2018
Abstract: ... In practice, strategic interaction between intelligence competitors using real quantum systems implemented in fallible human organizations will mitigate the impact of quantum computing. The upshot is that the revolutionary scientific innovation of quantum computing will probably have only marginal political impact, in part because the fields of cryptology and computing have already undergone important transformations in recent decades.
A fast quantum-safe asymmetric cryptosystem using extra superincreasing sequences
Shenghui Su et al., Nanjing University, October 2017
"The analysis shows that the new cryptosystem has the potential to be resistant to quantum computing attack, and is especially suitable to the secret communication between two mobile terminals in maneuvering field operations under any weather."
Round5 [protocol based on non-ring and ring lattice techniques]
Round5 is a "leading candidate" for NIST Post-Quantum Cryptography key encapsulation and public-key encryption, a merger of Round2 and HILA5. They have a web site with papers, presentations and source code.
Quantum resistant public key cryptography: a survey
Ray Perlner and David Cooper, NIST Gaithersburg, ACM IDtrust 2009
Quantum-proofing the blockchain
Vlad Gheorghiu et alia, Univ. of Waterloo, November 2017
Note: one of many papers, including the “Quantum Resistant Ledger”, working to make blockchain resistant to quantum attacks.
Not surprisingly, there is a rush to patent post-quantum cryptographic systems to nullify quantum computing’s possible/future threat to cybersecurity. The following Google Patents query will return hundreds of such patent applications (most have just been filed and published, and not yet issued):
https://patents.google.com/?q=post-quantum&q=encryption. Here are titles to a random sampling:
Quantum-resistant double signature systemSemiconductor powerhouse Intel is seeking patents on a broad range for post-quantum encryption protocols based in silicon. Here’s a bet. Who will prevail – the processor circuit designers of Intel with decades of successes, or the quantum computing hackers hoping to factor 2048? A list of some of the Intel post-quantum patent applications (a patent takes many years to issue, and many of these were filed in the past year or so):
U.S. Patent 10,742,420 (Wells Fargo)
Quantum-resistant blockchain with multi-dimensional quantum key distribution
U.S. Patent 10,708,046 (NxGen Partners)
Sender optimal, breach-resilient, and post-quantum secure cryptographic methods
U.S. Patent 10,630,478 (Univ. of South Florida)
Post-quantum cryptographic communication protocol
U.S. Patent 10,581,604 (COMSATS Institue of Information Technology)
Advanced bitflip: threat-adjusted, quantum-ready, battery-friendly, cipher
U.S. Patent 10,541,808 (Gideon Samid)
Public key validation in supersingular isogeny-based cryptographic protocols
U.S. Patent 10,313,124 (Isara Corp.)
Hypersphere-based multivariable public key encryption/decryption system
U.S. Patent 10,142,105 (South Univ. of Technology)
Generating shared secrets for lattice-based cryptographic protocols
U.S. Patent 10,103,886 (Isara Corp.)
Post-quantum secure private stream aggregation
U.S. Patent Application 2018/337899. (Robert Bosch Gmbh)
Cryptographic system using pairing with errors [that is quantum-resistant]
U.S. Patent 9,246,675 (Jintai Ding)
System for synchronizing a cryptographic key state through blockchain
U.S. Patent Application US20200351074A1
Post quantum public key signature operation for reconfigurable circuit devices [such as FPGAs]
U.S. Patent Application US20190325166A
Digital [elliptic curve] signal verification for reconfigurable circuit devices
U.S. Patent Application US20190319805A1
Unified accelerator for classical and post-quantum digital signature schemes in computing environments
U.S. Patent Application US20190319804A1
Odd index precomputation for authentication path computation [for post-quantum cryptography secure hash-based signature algorithms]
U.S. Patent Application US20190319803A1
Efficient post-quantum anonymous attestation with signature-based join protocol and unlimited signatures
U.S. Patent Application US20190319801A1
Fast XMSS signature verification and nonce sampling process without signature expansion
U.S. Patent Application US20190319800A1
Message index aware multi-hash accelerator for post quantum cryptography secure hash-based signing and verification
U.S. Patent Application US20190319799A1
Accelerators for post-quantum cryptography secure hash-based signing and verification
U.S. Patent Application US20190319797A1
Low-latency post-quantum signature verification for fast secure-boot
U.S. Patent Application US20190319796A1
Hardware acceleration of BIKE for post-quantum public key cryptography
U.S. Patent Application US20190319787A1
Combined SHA2 and SHA3 based XMSS hardware accelerator
U.S. Patent Application US20190319782A1
Countermeasures against hardware side-channel attacks on [post-quantum] cryptographic operations
U.S. Patent Application US20190318130A1