Quantum computing

An adversary armed with a quantum computer has algorithms[66, 33, 34] at their disposal, which are capable of breaking our current methods of encryption. Even with the birth of post-quantum cryptography[52, 62, 61], some of best cryptanalytic algorithms are still quantum [45, 8]. This thesis contains several experiments on the efficacy of lattice reduction algorithms, BKZ and LLL. In particular, the difficulty of solving Learning With Errors is assessed by reducing the problem to an instance of the Unique Shortest Vector Problem. The results are used to predict the behavior these algorithms may have on actual cryptographic schemes with security based on hard lattice problems. Lattice reduction algorithms require several floating-point operations including multiplication. In this thesis, I consider the resource requirements of a quantum circuit designed to simulate floating-point multiplication with high precision.

Quantum cryptography offers a wonderful source for current and future research. The idea started in the early 1970s, and it continues to inspire work and development toward a popular goal, large-scale communication networks with strong security guarantees, based on quantum-mechanical properties. Quantum cryptography builds on the idea of exploiting physical properties to establish secure cryptographic operations. A particular quantum-based protocol has gathered interest in recent years for its use of mesoscopic coherent states.
The AlphaEta protocol has been designed to exploit properties of coherent states of light to transmit data securely over an optical channel. AlphaEta aims to draw security from the uncertainty of any measurement of the transmitted coherent states due to intrinsic quantum noise. We propose a framework to combine this protocol with classical preprocessing, taking into account error-correction for the optical channel and establishing a strong provable security guarantee. Integrating a state-of-the-art solution for fast authenticated encryption is straightforward, but in this case the security analysis requires heuristic reasoning.

Quantum computers are envisioned to be able to solve mathematical problems
which are currently unsolvable for conventional computers, because of their
exceptional computational power from quantum mechanics. Therefore, if quantum
computers are ever built in large scale, they will certainly be able to solve many classical
exponential complexity problems such as the hard problems which the current
public key cryptography is constructed upon. To counteract this problem, the design
of post-quantum cryptography protocols is necessary to preserve the security in the
presence of quantum adversaries. Regardless of whether we can estimate the exact
time for the advent of the quantum computing era, security protocols are required to
be resistant against potentially-malicious power of quantum computing.
In this thesis, the main focus is on the sperformance improvement of one
of the potential PQC candidates, isogeny-based cryptography. Several optimized
implementations of cryptography applications based on this primitive are presented.
From a general viewpoint, the proposed methods, implementation techniques and
libraries have a practical impact on the performance evaluation of post-quantum
cryptography schemes in a wide range of applications. In particular, the provided benchmarks and optimizations on ARM-powered processors provide a reference for
comparison and evaluation of isogeny-based cryptography with other post-quantum
candidates during the first round of NIST's PQC standardization process.

Quantum computers and quantum computing is a reality of the near feature. Companies
such as Google and IBM have already declared they have built a quantum computer
and tend to increase their size and capacity moving forward. Quantum computers have
the ability to be exponentially more powerful than classical computers today. With this
power modeling behavior of atoms or chemical reactions in unusual conditions, improving
weather forecasts and traffic conditions become possible. Also, their ability to exponentially
speed up some computations makes the security of todays data and items a major
concern and interest. In the area of cryptography, some encryption schemes (such as RSA)
are already deemed broken by the onset of quantum computing. Some encryption algorithms
have already been created to be quantum secure and still more are being created
each day. While these algorithms in use today are considered quantum-safe not much is
known of what a quantum attack would look like on these algorithms. Specifically, this
paper discusses how many quantum bits, quantum gates and even the depth of these gates
that would be needed for such an attack. The research below was completed to shed light
on these areas and offer some concrete numbers of such an attack.

We explore quantum-resistant key establishment and hybrid encryption. We
nd that while the discrete logarithm problem is e ciently solved by a quantum
computer using Shor's algorithm, some instances are insecure even using classical
computers. The discrete logarithm problem based on a symmetric group Sn is e -
ciently solved in polynomial time.
We design a PUF-based 4-round group key establishment protocol, adjusting
the model to include a physical channel capable of PUF transmission, and modify
adversarial capabilities with respect to the PUFs. The result is a novel group key establishment
protocol which avoids computational hardness assumptions and achieves
key secrecy.
We contribute a hybrid encryption scheme by combining a key encapsulation
mechanism (KEM) with a symmetric key encryption scheme by using two hash
functions. We require only one-way security in the quantum random oracle model
(QROM) of the KEM and one-time security of the symmetric encryption scheme in
the QROM. We show that this hybrid scheme is IND-CCA secure in the QROM.
We rely on a powerful theorem by Unruh that provides an upper bound on indistinguishability between the output of a random oracle and a random string, when
the oracle can be accessed in quantum superposition. Our result contributes to the
available IND-CCA secure encryption schemes in a setting where quantum computers
are under adversarial control.
Finally, we develop a framework and describe biometric visual cryptographic
schemes generically under our framework. We formalize several security notions and
de nitions including sheet indistinguishability, perfect indistinguishability, index recovery,
perfect index privacy, and perfect resistance against false authentication. We
also propose new and generic strategies for attacking e-BVC schemes such as new
distinguishing attack, new index recovery, and new authentication attack. Our quantitative
analysis veri es the practical impact of our framework and o ers concrete
upper bounds on the security of e-BVC.