[microsoft][education] Analysis of Post Quantum Cryptography / Lee Dale / systemweakness / medium

Tue Jul 11 13:58:25 PDT 2023

[link to summary excised because it uses cross-host redirect tricks to
retain tracking ids]
[some commentary lost during system misbehavior]

The following is taken from a paper I submitted for the MSc Applied
Cryptography module
[https://www.napier.ac.uk/courses/msc-advanced-security-and-digital-forensics-postgraduate-fulltime]

The full code listing and PDF can be found on GitHub at
https://github.com/leedale1981/msc-applied-crypto-coursework

# Introduction

Currently the world of cryptography is solely based on what classical
computers can achieve with well know Turing machine based algorithms.
Quantum computers don’t come into the picture when it comes to general
use encryption. This is set to change as quantum computers start to
gain enough Qubits to successfully implement general use quantum
algorithms that can break the encryption of our current state of the
art public key exchange mechanisms [Bel+21]. Once this happens there
will be a need for robust quantum key exchange methods that allow
privacy of message exchange to be maintained, even when subjected to a
quantum computing algorithms. Quantum computers with new quantum based
algorithms will also make it possible to brute force current
encryption keys in polynomial time. This puts any data that is
currently encrypted with todays state of the art encryption algorithms
in jeopardy of being cracked and made available for anyone with a
quantum computer to view. Once a quantum computer with enough Qubits
becomes available for general use it will mean they can also be used
to keep communications between two parties secret.

This paper outlines the current weaknesses in todays cryptography
schemes including public key exchange methods that rely on the a
mathematically hard to compute private key, and why these will be
vulnerable to quantum computers in the future. It will then outline
some key solutions to this problem that will be robust in a post
quantum world.

...[the internals of the paper review classical and quantum
cryptography and go through example quantum code. a good cypherpunk
would include them so people would learn all these things. i'm not
including them for personal reasons, to pressure myself to read such
things a little rather than just copypaste.]

## Results

When Eve interfered with the Qubits the result of the difference
measurement was 65%. When no eavesdropping occurred the differences
percentage dropped to only 25%. This shows that the amount of
difference in bases comparisons increases when there is an
eavesdropper interfering with the qubits. A percentage threshold can
be set to determine when Alice and Bob should retry their
communication based on a set percentage of difference of measurements.

# Conclusions

I have outlined the problems with cryptography that relies on hard to
compute mathematical properties and the issues this creates for
current asymmetric public key exchange 11 mechanisms such as RSA and
elliptic curves. The current state of post quantum cryptography
includes new methods of encryption such as lattice based cryptography
and new public key exchange methods such as quantum key distribution.
I showed that a protocol called BB84 can be used to share bits that
can be later used to encrypt messages and which crucially doesn’t rely
on a key that is hard to crack computationally. BB84 relies on the
properties of quantum mechanics that allow two actors to know if their
communication channel has been compromised. I showed an example of the
BB84 protocol using a 6 bit key, due to the nature of the protocol
this means that we would need a quantum computer that can support 24
qubits. Scaling this up to larger keys would means a larger amount of
qubits. A 128 bit key for example would need 512 qubits and as of
November 2022 the largest quantum computer produced by IBM has 433
qubits [22], falling short of the required amount for even a 128 bit
key. For generating encryption keys it seems that lattice based
cryptography methods are showing the most promise as protection
against the computation power of quantum computers and this is most
likely the area where the most benefits will be shown in the early
stages of a post quantum world. In terms of communications channels
then QKD methods will likely be adopted with more advanced methods
like using Muons or other sources of quantum randomness to generate
secret keys being used when methods become more refined and hardware
is able to support the methods.

# References

[Deu85] D Deutsch. “Quantum theory, the Church–Turing principle and
the universal quantum computer”. In: Proceedings of the Royal Society
of London. A. Mathematical and Physical Sciences 400.1818 (Apr. 1985),
pp. 97–117. issn: 00804630. doi: 10.1098/RSPA.1985.0070. url:
https://royalsocietypublishing. org/doi/10.1098/rspa.1985.0070.

[Mon94] Peter L Montgomery. “A Survey of Modern Integer Factorization
Algorithms”. In: 7.4 (1994), pp. 337–365.

[Sho94] Peter W. Shor. “Algorithms for quantum computation: Discrete
logarithms and factoring”. In: Proceedings — Annual IEEE Symposium on
Foundations of Computer Science, FOCS (1994), pp. 124–134. issn:
02725428. doi: 10. 1109/SFCS.1994.365700.

[MR08] Daniele Micciancio and Oded Regev. “Lattice-based Cryptography
*”. In: (2008).

[Gus+09] Julia Guskind et al. “Controlling passively quenched single
photon detectors by bright light Circular Semi-Quantum Secret Sharing
Using Single Particles This content was downloaded from IP address New
Journal of Physics Controlling passively quenched single photon
detectors by bright light”. In: New Journal of Physics 11.18pp (2009),
p. 65003. doi: 10.1088/1367–2630/11/ 6/065003. url:
http://www.idquantique.com/;.

[And20] Ross Anderson. “Security engineering: a guide to building
dependable distributed systems”. In: 2020, pp. 170–170.

[BB20] Charles H. Bennett and Gilles Brassard. “Quantum cryptography:
Public key distribution and coin tossing”. In: Theoretical Computer
Science 560.P1 (Mar. 2020), pp. 7–11. doi: 10.1016/j.tcs.2014.05.025.
url: http://arxiv.
org/abs/2003.06557%20http://dx.doi.org/10.1016/j.tcs.2014.05. 025. 12

[Bel+21] Davide Bellizia et al. “Post-Quantum Cryptography: Challenges
and Opportunities for Robust and Secure HW Design”. In: Proceedings —
IEEE International Symposium on Defect and Fault Tolerance in VLSI and
Nanotechnology Systems, DFT 2021-October (2021). issn: 2765933X. doi:
10.1109/ DFT52944.2021.9568301.

[KG21] Ajay Kumar and Sunita Garhwal. “State-of-the-Art Survey of
Quantum Cryptography”. In: Archives of Computational Methods in
Engineering 2021 28:5 28.5 (Apr. 2021), pp. 3831–3868. issn:
1886–1784. doi: 10.1007/S11831–021- 09561–2. url:
https://link.springer.com/article/10.1007/s11831- 021–09561–2.

[22] IBM unveils world’s largest quantum computer at 433 qubits — New
Scientist. 2022. url: https : / / www . newscientist . com / article /
2346074 — ibm —
unveils-worlds-largest-quantum-computer-at-433-qubits/.

[CCE23] Edwin Cartlidge, Cartlidge, and Edwin. “Muons used for
cryptography system”. In: PhyW 36.3 (Mar. 2023), pp. 5–5. issn:
0953–8585. doi: 10.1088/ 2058–7058 / 36 / 03 / 05. url: https : / / ui
. adsabs . harvard . edu / abs / 2023PhyW…36….5C/abstract.

[Dal23] Lee Dale. leedale1981/msc-applied-crypto-coursework:
Coursework repository for MSc Applied Cryptography document and code.
2023. url: https : / /
github.com/leedale1981/msc-applied-crypto-coursework.