Cryptography

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.

Elliptic curves have played a large role in modern cryptography. Most notably,
the Elliptic Curve Digital Signature Algorithm (ECDSA) and the Elliptic Curve
Di e-Hellman (ECDH) key exchange algorithm are widely used in practice today for
their e ciency and small key sizes. More recently, the Supersingular Isogeny-based
Di e-Hellman (SIDH) algorithm provides a method of exchanging keys which is conjectured
to be secure in the post-quantum setting. For ECDSA and ECDH, e cient
and secure algorithms for scalar multiplication of points are necessary for modern use
of these protocols. Likewise, in SIDH it is necessary to be able to compute an isogeny
from a given nite subgroup of an elliptic curve in a fast and secure fashion.
We therefore nd strong motivation to study and improve the algorithms used
in elliptic curve cryptography, and to develop new algorithms to be deployed within
these protocols. In this thesis we design and develop d-MUL, a multidimensional
scalar multiplication algorithm which is uniform in its operations and generalizes the
well known 1-dimensional Montgomery ladder addition chain and the 2-dimensional
addition chain due to Dan J. Bernstein. We analyze the construction and derive many
optimizations, implement the algorithm in software, and prove many theoretical and practical results. In the nal chapter of the thesis we analyze the operations carried
out in the construction of an isogeny from a given subgroup, as performed in SIDH.
We detail how to e ciently make use of parallel processing when constructing this
isogeny.

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.

With the publication of Shor's quantum algorithm for solving discrete logarithms in
finite cyclic groups, a need for new cryptographic primitives arose; namely, for more secure
primitives that would prevail in the post-quantum era.
The aim of this dissertation is to exploit some hard problems arising from group theory
for use in cryptography. Over the years, there have been many such proposals. We first look
at two recently proposed schemes based on some form of a generalization of the discrete
logari thm problem (DLP), identify their weaknesses, and cryptanalyze them.
By applying the exper tise gained from the above cryptanalyses, we define our own
generalization of the DLP to arbitrary finite groups. We show that such a definition leads
to the design of signature schemes and pseudo-random number generators with provable
security under a security assumption based on a group theoretic problem. In particular,
our security assumption is based on the hardness of factorizing elements of the projective
special linear group over a finite field in some representations. We construct a one-way
function based on this group theoretic assumption and provide a security proof.

Finite elds of the form F2m play an important role in coding theory and
cryptography. We show that the choice of how to represent the elements of these elds
can have a signi cant impact on the resource requirements for quantum arithmetic.
In particular, we show how the Gaussian normal basis representations and \ghost-bit
basis" representations can be used to implement inverters with a quantum circuit
of depth O(mlog(m)). To the best of our knowledge, this is the rst construction
with subquadratic depth reported in the literature. Our quantum circuit for the
computation of multiplicative inverses is based on the Itoh-Tsujii algorithm which
exploits the property that, in a normal basis representation, squaring corresponds
to a permutation of the coe cients. We give resource estimates for the resulting
quantum circuit for inversion over binary elds F2m based on an elementary gate set
that is useful for fault-tolerant implementation.
Elliptic curves over nite elds F2m play a prominent role in modern cryptography.
Published quantum algorithms dealing with such curves build on a short
Weierstrass form in combination with a ne or projective coordinates. In this thesis
we show that changing the curve representation allows a substantial reduction in the number of T-gates needed to implement the curve arithmetic. As a tool, we present
a quantum circuit for computing multiplicative inverses in F2m in depth O(mlogm)
using a polynomial basis representation, which may be of independent interest.
Finally, we change our focus from the design of circuits which aim at attacking
computational assumptions on asymmetric cryptographic algorithms to the design of
a circuit attacking a symmetric cryptographic algorithm. We consider a block cipher,
SERPENT, and our design of a quantum circuit implementing this cipher to be used
for a key attack using Grover's algorithm as in [18]. This quantum circuit is essential
for understanding the complexity of Grover's algorithm.

Every transitive permutation representation of a finite group is the representation of the group in its action on the cosets of a particular subgroup of the group. The group has a certain rank for each of these representations. We first find almost all rank-3 and rank-4 transitive representations of the projective special linear group P SL(2, q) where q = pm and p is an odd prime. We also determine the rank of P SL (2, p) in terms of p on the cosets of particular given subgroups. We then investigate the construction of rank-3 transitive and primitive extensions of a simple group, such that the extension group formed is also simple. In the latter context we present a new, group theoretic construction of the famous Hoffman-Singleton graph as a rank-3 graph.

This research addresses the need for increased interoperability between the varied access control systems in use today, and for a secure means of providing access to remote physical devices over untrusted networks. The Universal Physical Access Control System (UPACS) is an encryption-enabled security protocol that provides a standard customizable device control mechanism that can be used to control the behavior of a wide variety of physical devices, and provide users the ability to securely access those physical devices over untrusted networks.

RSA cryptosystems with decryption exponent d less than N 0.292, for a given RSA modulus N, show themselves to be vulnerable to an attack which utilizes modular polynomials and the LLL Basis Reduction Algorithm. This result, presented by Dan Boneh and Glenn Durfee in 1999, is an improvement on the bound of N0.25 established by Wiener in 1990. This thesis examines in detail the LLL Basis Reduction Algorithm and the attack on RSA as presented by Boneh and Durfee.