Landmark Computer Science Proof Cascades Through Physics and Math
Computer scientists established a new boundary on computationally verifiable knowledge. In doing so, they solved major open problems in quantum mechanics and pure mathematics.
Real-world measurements of structured-lattices and supersingular isogenies in TLS
This is the third in a series of posts about running experiments on post-quantum confidentiality in TLS. The first detailed experiments that measured the estimated network overhead of three families of post-quantum key exchanges. The second detailed the choices behind a specific structured-lattice scheme. This one gives details of a full, end-to-end measurement of that scheme and a supersingular isogeny scheme, SIKE/p434. This was done in collaboration with Cloudflare, who integrated Microsoft’s SIKE code into BoringSSL for the tests, and ran the server-side of the experiment.
Because optimised assembly implementations are labour-intensive to write, they were only available/written for AArch64 and x86-64. Because SIKE is computationally expensive, it wasn’t feasible to enable it without an assembly implementation, thus only AArch64 and x86-64 clients were included in the experiment and ARMv7 and x86 clients did not contribute to the results even if they were assigned to one of the experiment groups.
CECPQ1 was the experiment in post-quantum confidentiality that my colleague, Matt Braithwaite, and I ran in 2016. It’s about time for CECPQ2.
CECPQ2 will be moving slowly: It depends on TLS 1.3 and, as mentioned, 1.3 is taking a while. The larger messages may take some time to deploy if we hit middlebox- or server-compatibility issues. Also the messages are currently too large to include in QUIC. But working though these problems now is a lot of the reason for doing CECPQ2—to ensure that post-quantum TLS remains feasible.
A Guide to Post-Quantum Cryptography
A taxonomy of candidates.
Post-quantum cryptography is the study of cryptosystems which can be run on a classical computer, but are secure even if an adversary possesses a quantum computer. Recently, NIST initiated a process for standardizing post-quantum cryptography and is currently reviewing first-round submissions. The most promising of these submissions included cryptosystems based on lattices, isogenies, hash functions, and codes.
Quantum computing in the NISQ era and beyond
“Intermediate scale” refers to computers with between 50 and a few hundred qubits. The 50 qubit milestone is significant because that takes us beyond what we can simulate by brute force using the most powerful existing supercomputers. “Noisy” emphasises that we’ll have imperfect control over those qubits. Because of the noise, we expect a limit of about 1000 gates in a circuit – i.e., 1000 fundamental two-qubit operations. Executing a single gate is about 1000 times slower on an ion trap quantum processor than on a superconducting circuit.
Regarding the near future potential of quantum computers.
For a look at the past, Shor’s Algorithm: https://blog.acolyer.org/2018/02/02/polynomial-time-algorithms-for-prime-factorization-and-discrete-logarithms-on-a-quantum-computer/
Math and Computation
This book is devoted to computational complexity theory, and its many connections and interactions with mathematics. This mathematical discipline arose from the quest to understand eﬃcient computation. In its half-century of existence it has developed into a rich, deep and broad theory with remarkable achievements and formidable challenges. It had important practical impact on computer science and industry, and has forged strong connections with a diverse set of mathematical ﬁelds.
Quantum algorithms to find collisions
The reality, however, is that the CNS algorithm is not an efficient way to find collisions. In fact, it’s so inefficient that it’s beaten by the standard non-quantum method of finding collisions, namely “parallel rho” collision search from 1997 van Oorschot–Wiener. Let’s take an in-depth look at what’s going on here.
Besides the beatdown, some good notes on finding collisions and performance assessment. Not always as simple as big O.
Improving the SPHINCS post-quantum signature scheme
Side-Channel Attacks on BLISS Lattice-Based Signatures
In this paper, we investigate the security of the BLISS lattice-based signature scheme, one of the most promising candidates for post-quantum-secure signatures, against side-channel attacks.
We also show that other parts of the BLISS signing algorithm can leak secrets not just for a subset of secret keys, but for 100% of them. The BLISS Gaussian sampling algorithm in strongSwan is intrinsically variable time. This would be hard to exploit using a noisy source of leakage like EMA, but branch tracing allows to recover the entire randomness and hence the key: we show that a single execution of the strongSwan signature algorithm is actually sufficient for full key recovery.
RWC 2017 - Post-quantum cryptography in the real-world
This year, for the first time in RWC, post-quantum cryptography (PQC) was given an entire session, clear sign that time is changing and the moment has come to bring the discussion to the real world. The message is clear: even if quantum computers are not popping up in tomorrow’s newspapers, we can’t postpone any longer.
NewHope without reconciliation
The price for that simplicity is small: one of the exchanged messages increases in size by 6.25% from 2048 bytes to 2176 bytes. The security of NewHope-Simple is the same as the security of NewHope; the performance is very similar.
Keywords. Post-quantum key exchange, NewHope, code simplicity.
The quantum computing talk
If you don’t talk to your kids about quantum computing, Scott Aaronson will. This is really good.
Our second goal was to measure the feasibility of deploying post-quantum key-agreement in TLS by combining NewHope with an existing key-agreement (X25519). We called the combination CECPQ1.
It’s feasible, but not necessary today. Experiment concluded.
Post quantum crypto miniworkshop slides and videos
In the future, math will be weird, not hard.