Impact of Quantum Computing on IoT Security
Aref MEDDEB
NOCCS Lab
National Engineering School of Sousse
University of Sousse
Faculty of Informatics, Brno
Masaryk University
March 16th, 2023
Outline
What is Quantum Computing ?
Quantum Computing and
Cybersecurity
Quantum Algorithms
Impact of Quantum Computing
on IoT Security
What is Quantum
Computing ?
Quantum Mechanics In a
nutshell
Quantum bit
Quantum Computer
Examples
3
Quantum Mechanics in a nutshell
Quantum mechanics is a fundamental theory in physics
that provides a description of the physical properties of
nature at the scale of atoms and subatomic particles.
It provides a mathematical description of how
elementary particles move and interact.
It is based on the wave–particle dual description
formulated by Bohr, Einstein, Heisenberg, Schrödinger,
and others.
The basic units of nature are particles, but the
description of their motion involves wave mechanics.
Textbook: Mahan, Gerald D. “Introduction.” Quantum Mechanics
in a Nutshell, Princeton University Press, 2009, pp. 1–13. JSTOR,
https://doi.org/10.2307/j.ctt7s8nw.4. Accessed 15 Feb. 2023.
4
Quantum Particles
5
Quantum
information
science
Quantum Mechanics lay the foundation of
all quantum physics including quantum
chemistry, quantum field theory, quantum
technology, and quantum information
science.
Quantum information science is a field
that combines the principles of quantum
mechanics with information science to
study the processing, analysis, and
transmission of information.
6
Three fundamental principles
Quantization: Energy, momentum, angular
momentum, and other quantities of a bound
system are restricted to discrete values. First
discovered by Max Plank in 1920.
Wave–particle duality: Objects have characteristics
of both particles and waves. Discovered by Louis de
Broglie in 1924 and further developed by others.
Uncertainty : There are limits to how accurately the
value of a physical quantity can be predicted prior
to its measurement given a complete set of initial
conditions. Discovered by Werner Heisenberg in
1927.
In 1913, Niels Bohr proposed that the
electrons in an atom were restricted to
certain energy levels or orbits, and that
when electrons absorbed or emitted energy,
they did so in discrete packets or quanta.
7
ΔE = h f
Planck’s constant
The important parameter in quantum mechanics
is Planck’s constant ℎ=6.626 10−34 Js or Joule/Hz.
It relates the energy of a photon to its frequency.
It is common to divide it by 2𝜋 and to put a
slash through the symbol: ℏ=1.054 10−34 Js.
8
Uncertainty principle
An electron can be described by a wave function, which
associates to each point in space a probability
amplitude.
The Born rule assigns to these amplitudes a probability
density function for the position that the electron
would be in when an experiment is performed to
measure it.
.
9
Superposition principle
The idea of superposition was first proposed by
Erwin Schrödinger in 1926.
A particle can exist in multiple states or
locations at the same time until it is observed
or measured.
The Schrödinger equation relates the probability
amplitudes associated to one moment of time
to a collection of probability amplitudes
associated to another moment in time.
This is the best theory so far!
10
The Entanglement Phenomenon
The concept of entanglement was first
introduced in a 1935 paper by Albert
Einstein, Boris Podolsky, and Nathan Rosen,
which became known as the EPR paradox.
Consider a pair of particles created at the
same time and place with opposite properties,
such as spin.
The property of one particle is undefined until
it is measured, at which point the property of
the other particle would become defined
instantaneously, even if the particles were
separated by a large distance.
11
Entanglement is real,
not “spooky”
Einstein, Podolsky, and Rosen believed that this
idea violated the principles of locality and
causality, which suggest that the behavior of
particles can only be influenced by their
immediate surroundings and that nothing can
travel faster than light.
Experiments and developments have shown that
entanglement is a real phenomenon
It is not inconsistent with the principles of
locality and causality, but instead represents a
fundamental feature of the quantum world.
12
The spin of an electron
The concept of electron spin was first proposed by George
Uhlenbeck and Samuel Goudsmit in 1925 to explain certain
features of the atomic spectra.
The spin of an electron is an intrinsic property of the electron
itself that describes its angular momentum.
It is not related to the electron's orbital motion around the
nucleus.
13
The spin of an electron
The spin of an electron is typically represented by
the symbol "s" and has a value of 1/2 in units of
the reduced Planck constant ħ.
The electron can have two possible spin states,
which are usually denoted as “spin-up” and “spin-
down”.
The spin of an electron has several important
applications in physics, including the behavior of
atoms and the properties of materials.
14
+1/2 -1/2
Photon polarization
The polarization of a photon is a property that describes the
orientation of the electric field oscillation of the photon.
The polarization of a photon can be linear or circular.
In the case of linear polarization, the electric field oscillates
along a straight line, while in circular polarization, the electric
field rotates around the direction of the photon's motion.
Circular polarization can be further classified as left-handed
or right-handed, depending on the direction of rotation.
15
Photon polarization applications
The polarization of a photon has important applications in
optical communication and quantum information.
In optical communication, information can be encoded in the
polarization of photons, and in quantum information, qubits can
be implemented using the polarization states of photons.
The polarization of a photon can be manipulated using various
techniques, such as polarization filters or wave plates, which
are optical components that modify the polarization of light.
16
The no-cloning theorem
A fundamental principle formulated by Wootters and Zurek in 1982,
it is impossible to create an exact copy of an unknown quantum state without
changing its properties.
The theorem has important implications for quantum information processing,
cryptography, and communication
It means that information encoded in a quantum state cannot be intercepted or
copied without being detected.
This makes it impossible to create a perfect quantum teleportation system, where
quantum states can be transmitted over long distances without being physically
transported.
It is still possible to create approximate copies of quantum states using estimation.
17
Quantum bit
A quantum bit, or qubit, is the basic unit of quantum
information.
In classical computing, the basic unit of information is the
classical bit, which can take on one of two values: 0 or 1.
A qubit can exist in a superposition of two states, which
means it can represent a 0 and a 1 at the same time.
This property of superposition allows quantum computers
to perform certain types of calculations much faster than
classical computers.
18
How to make a
Qubit ?
A qubit can be implemented using a variety
of physical systems, such as the spin of an
electron, the polarization of a photon, or
the vibration of an atom.
The state of a qubit can be manipulated
using quantum gates, which are analogous
to classical logic gates, but operate on
quantum states.
Measuring a qubit collapses its
superposition into one of the two possible
classical states, either 0 or 1.
19
Maintaining the
coherence of the
qubits
One of the challenges in building a
practical quantum computer is to
maintain the coherence of the qubits.
Qubits are highly sensitive to their
environment and can easily lose their
quantum properties through interactions
with other particles.
The development of techniques to
control and protect qubits is a major
area of research in quantum computing.
20
Qubit Dirac notation
Qubits are typically represented using a notation called the
Dirac notation or bra-ket notation, which was developed by
Paul Dirac.
A qubit is represented as a vector in a two-dimensional
complex Hilbert space, which is also known as the state
space.
The Dirac notation uses two symbols: the bra vector ⟨ | and
the ket vector | ⟩.
The bra vector represents the complex conjugate of a ket
vector, and the ket vector represents a quantum state.
The bra vector and ket vector are combined to form a
complex inner product, which gives the probability amplitude
for a quantum measurement.
21
The quantum state
The quantum state |Ψ> (Psi) is the linear combination of |0>
and |1> with the probability of being in state |0> is |α|², and the
probability of being in state|1> is |β|².
α, β ∈ ℂ² are the probability amplitudes while α* and β* are the
complex conjugates of α and β, respectively.
Normalization constraint: |α|²+|β|²=1.
22
Bloch sphere
23
Geometrical representation of the possible states of a qubit
Qubit operations
Qubit operations are the basic operations that can be performed on qubits
to manipulate their quantum states.
These operations can be combined to implement more complex quantum
algorithms and circuits.
Implementing quantum gates is challenging due to the inherent noise and
decoherence in real-world quantum systems, which can lead to errors in
the computation.
Developing error-correction codes and techniques to suppress noise and
decoherence is an active area of research in quantum computing.
24
Common Gates
1.Pauli-X, Pauli-Y, and Pauli-Z gates: Single-qubit operations that correspond to flips around the x,
y, and z axes of the Bloch sphere, respectively..
2.Hadamard gate: Single-qubit gate that puts a qubit into an equal superposition of the 0 and 1
states.
3.Controlled NOT (CNOT) gate: Two-qubit gate that performs a conditional operation on the second
qubit, based on the state of the first qubit. It flips the second qubit if the first is in the state |1>.
4.SWAP gate: Two-qubit gate that exchanges the states of two qubits.
5.Controlled-phase gate: Two-qubit gate that adds a phase to the second qubit's state, based on
the state of the first qubit.
25
Pauli-X, Pauli-Y & Pauli-Z Gates
Single qubit gates:
26
Hadamard gate
Single-qubit gate
Puts a qubit into an equal superposition of the 0 and 1 states
Represented by the matrix:
27
Quantum register with n bits
States of a quantum register with n bits are vectors in a 2n dimensional complex vector space
Example for 2 bit:
28
The SWAP gate
Also known as the exchange gate
Two-qubit gate that exchanges the state of two qubits.
A non-trivial gate because it cannot be decomposed into a sequence of one-qubit gates.
Represented by the following matrix:
Fundamental gate often used in quantum algorithms and protocols, such as quantum teleportation and quantum error
correction.
Exchanges the quantum states of two qubits, which can be represented as:
SWAP |a⟩|b⟩ = |b⟩|a⟩
If the first qubit is in state |a⟩ and the second qubit is in state |b⟩, applying the SWAP gate will result in the first qubit
being in state |b⟩ and the second qubit being in state |a⟩.
29
CNOT Gate
Conditional gate
Performs a conditional operation on the second qubit, based on the state of the first qubit.
Flips the second qubit if the first qubit is in the state |1>.
Allows the implementation of if-else type of construction:
30
Controlled phase gate
The controlled phase gate, also known as the CPHASE gate or the controlled
Z gate, is a two-qubit quantum gate that applies a phase shift to the second
qubit if and only if the first qubit is in the state |1⟩.
If the first qubit is in the state |0⟩, the CPHASE gate has no effect on the
second qubit.
If the first qubit is in the state |1⟩, the CPHASE gate applies a phase shift of
-1 to the second qubit, which corresponds to a rotation around the Z-axis of
the Bloch sphere by an angle of π.
Often used in quantum algorithms to create and manipulate superpositions
of quantum states
Performs quantum entanglement and quantum teleportation.
31
CPHASE Gate matrix
Quantum Circuit
A quantum circuit is a mathematical model that represents the
behavior of a quantum computer.
A quantum circuit consists of a series of quantum gates,
which are mathematical operations that can be applied to
qubits.
Qubits are represented as lines, and the gates are represented
as boxes that operate on the qubits.
Each gate represents a specific operation that can be
performed on one or more qubits, such as flipping the state of
a qubit, entangling two or more qubits, or performing a
measurement.
Quantum circuits are used to design and implement quantum
algorithms.
32
QuantumComputers
33
Quantum Computers
Quantum computers are typically made by assembling a set of physical components
that can control and manipulate quantum states, which are the fundamental building
blocks of quantum computing. These include:
1.Qubits: The basic unit of quantum information. Typically implemented using ions,
superconducting circuits, or quantum dots.
2.Quantum Gates: basic Operations that can be performed on qubits to manipulate
quantum states.
3.Control and Readout Electronics: Control the flow of information between the
qubits and the outside world and allow for the measurement of quantum states.
4.Cryogenic Cooling System: Quantum systems are typically very sensitive to noise
and decoherence: they need to be operated at very low temperatures, typically in
the millikelvin range.
34
Implementation of a
quantum computer
The actual implementation of a quantum
computer vary depending on the specific physical
system used to realize the qubits.
Superconducting qubits are typically fabricated
on a chip using thin-film deposition and
lithography techniques
Ion trap qubits are implemented in vacuum
chambers using lasers and other optical
components.
Once the basic components are assembled, a
quantum computer can be programmed using
quantum algorithms, which take advantage of the
unique properties of quantum systems, such as
superposition, entanglement, and interference, to
perform tasks that are difficult or impossible for
classical computers.
35
Companies working on quantum computers
Several companies have built quantum computers, each with their own approach to constructing and
programming these complex machines.
IBM was one of the first companies to build a quantum computer and is a leader in the field. IBM developed
a series of quantum computers, including the IBM Q System One, which is one of the most advanced ones
for public use.
Google has developed a quantum computer called Sycamore, which is designed to solve specific problems.
They have also developed a cloud-based platform called Cirq that allows developers to build and run
quantum algorithms.
Microsoft has developed a quantum computer called Azure Quantum (not to confuse with the Canadian
Company Azur Quantum), which is part of their Azure cloud computing platform. Microsoft has also
developed a programming language called Q# that allows developers to write quantum algorithms.
36
Companies working on quantum computers
Honeywell has developed a quantum computer called the System Model H1, which is designed to be one of the most
powerful quantum computers in the world. They are also developing a cloud-based platform called Honeywell Forge that
allows users to access their quantum computer remotely.
Rigetti Computing has developed a quantum computer called the Aspen-8, which is designed to be one of the most
powerful quantum computers for public use. They have also developed a cloud-based platform called Forest that allows
developers to build and run quantum algorithms.
IonQ has developed a quantum computer based on trapped ions, which is designed to be one of the most stable and
reliable quantum computers. They have also developed a cloud-based platform called IonQ Cloud that allows users to
access their quantum computer remotely.
D-Wave Systems is a Canadian company based in British Columbia. It is one of the first companies to sell computers that exploit
quantum effects using quantum annealing, designed to solve optimization problems.
Intel is leveraging its expertise in high-volume transistor manufacturing to develop ‘hot’ silicon spin-qubits, much smaller
computing devices that operate at higher temperatures.
37
The IBM Q quantum computer
IBM has been a major player in the field of quantum
computing and has developed several generations of
quantum computers over the years.
IBM's current quantum computing platform is called
IBM Quantum, which is a cloud-based platform that
provides access to quantum computers over the
internet.
38
IBM Quantum
IBM Quantum is based on superconducting qubits, which are
implemented using superconducting circuits that are cooled to extremely
low temperatures.
The current generation of IBM Quantum devices support up to 65 qubits
and are designed to be scalable, with the goal of eventually building a
quantum computer with hundreds or even thousands of qubits.
IBM Quantum provides users with access to a variety of software tools,
including a web-based interface called the IBM Quantum Composer,
which allows users to design and run quantum circuits using a drag-anddrop
interface.
IBM Quantum also provides users with a software development kit (SDK)
called Qiskit, which is a collection of open-source software tools for
programming and simulating quantum circuits.
39
IBM Q Composer
40
IBM Quantum is
cloud-based
IBM Quantum is cloud-based, which allows users to access
their quantum computers from anywhere in the world using
a standard web browser.
IBM provides a range of resources and tutorials to help
users get started with quantum computing, including access
to a community of researchers and developers who are
working on cutting-edge quantum algorithms and
applications.
IBM Quantum is involved in several collaborations and
partnerships with academic institutions and industry
partners to advance the field of quantum computing and
develop practical applications of this emerging technology.
41
The Google Quantum
Computer
Google's quantum computer is
called Sycamore
Has a 54-qubit quantum processor
designed to perform quantum
computations faster than classical
computers for specific problems.
The processor consists of a chip
containing superconducting qubits
that are kept at ultra-low
temperatures to maintain their
quantum states.
42
The random sampling problem
In October 2019, a team of researchers at Google
announced that they had achieved “quantum supremacy”
with Sycamore: the quantum computer could solve a
specific problem faster than the world's most powerful
classical supercomputers.
Sycamore could perform a specific quantum calculation in
200 seconds, whereas the same calculation would take the
world's most powerful supercomputer, Summit, over
10,000 years to solve.
The specific problem solved by Sycamore is random
sampling where the goal is to generate a set of random
numbers with a specific probability distribution.
This type of problem is relevant in cryptography, finance,
and materials science.
43
Sundar Pichai and Daniel Sank with a Google quantum computer
The quantum
supremacy
Google's achievement of quantum supremacy is a significant milestone in the development of
quantum computing.
It demonstrates that quantum computers can perform computations that are infeasible with
classical computers.
The calculation that Sycamore performed was highly specific.
Google announced plans to develop a 1,000-qubit quantum computer, which would be a
significant advance in the field of quantum computing.
44
45
Sycamore is available for use through
the cloud-based platform:Cirq.
Cirq is a Python library for
writing, manipulating, and
optimizing quantum circuits and
running them against quantum
computers and simulators.
https://github.com/quantumlib/Cirq
Microsoft Azure Quantum
Microsoft Azure Quantum is a cloud-based platform that allows customers to access a variety of
quantum computing technologies from Microsoft and its partners.
The platform is intended to provide customers with a way to experiment with and develop quantum
applications, without having to invest in expensive quantum hardware themselves.
Azure Quantum is designed to be an open platform that supports a variety of quantum programming
languages and development tools, including Q#, Python, and Microsoft's Quantum Development Kit.
Customers can use Azure Quantum to access gate-based quantum computers, quantum annealers,
and quantum-inspired classical computing.
Microsoft Azure Quantum aims to democratize access to quantum computing technology and
accelerate the development of practical quantum applications.
46
Unique features of Azure Quantum
One of the unique features of Azure Quantum is the ability to
seamlessly integrate quantum computing with classical
computing.
Customers can use Azure Quantum to run hybrid quantumclassical
algorithms, where part of the algorithm is executed on
a quantum computer, and the remainder is executed on a
classical computer.
Azure Quantum also offers a variety of tools and services to
help customers develop and optimize quantum applications,
including a quantum simulator for testing and debugging, and
access to Microsoft's Quantum-inspired optimization service for
solving optimization problems.
47
Cryo-CMOS Technology. Image on left courtesy of The University of Sydney, Louise M. Cooper.
Noisy Intermediate-Scale Quantum
Noisy Intermediate-Scale Quantum (NISQ) designates quantum
computing devices that are currently available and can be used for
practical applications.
These devices are called “noisy” because they have a relatively high error
rate compared to ideal quantum computers, and “intermediate-scale”
because they have a limited number of qubits, typically ranging from a
few dozen to a few hundred.
NISQ devices are not yet powerful enough to solve some of the most
complex problems that quantum computers are theorized to be able to
solve, but they are still useful for a variety of applications, including
cryptography, optimization, and machine learning.
48
NISQ devices
NISQ devices are being developed and improved
by companies such as IBM, Google, and Microsoft,
as well as startups such as Rigetti Computing and
IonQ.
These companies are working to improve the
performance and reliability of NISQ devices, as
well as developing software tools and applications
that can run on these machines.
NISQ represents an exciting area of research and
development in quantum computing, with the
potential to have a significant impact on a wide
range of industries and fields.
49
(https://qiskit.org/)
Qiskit is an open-source SDK developed by IBM for working with quantum computers.
Provides tools for developing and running quantum computing experiments, including simulators and access to
real quantum devices through IBM's cloud service.
Qiskit provides a Python-based interface for programming quantum circuits, which are the basic building blocks
for quantum algorithms.
The SDK includes a variety of tools and libraries for quantum circuit design, simulation, and optimization, as well
as for accessing and controlling real quantum devices.
Qiskit is widely used by researchers and developers in the quantum computing community, and it has become
one of the most popular quantum SDK.
It is designed to be accessible to both experienced researchers and those new to quantum computing, with
extensive documentation, tutorials, and community support available.
50
51
A foundation layer for
composing quantum
programs at the circuit level
A high-performance simulator
for simulating quantum
circuits on classical computers
A library of algorithms for
solving problems in chemistry,
optimization, and other fields
A library of tools for
characterizing and mitigating
errors in quantum systems
Key components of Qiskit
Quantum
Computing and
Cybersecurity
52
Quantum
computing impact
on cybersecurity
Quantum computing has the potential to significantly impact cybersecurity, both in terms of
the vulnerabilities it may expose and the new security mechanisms it may enable.
Quantum computing poses a threat to traditional cryptographic systems.
Many modern cryptographic protocols rely on the difficulty of certain mathematical problems,
such as factoring large numbers, for their security.
Quantum computers have the potential to solve these problems much faster than classical
computers, rendering many existing cryptographic systems vulnerable to attacks.
53
To address the threats, researchers are exploring the development of “Post-Quantum Cryptography”
(PQC) that is resistant to attacks by quantum computers.
PQC algorithms rely on different mathematical problems that are believed to be hard for both
classical and quantum computers, making them potentially more secure in the era of quantum
computing.
54
Approaches to PQC
Lattice-based cryptography: use mathematical lattices to perform
encryption and decryption. Resistant to attacks by quantum
computers because the algorithms that quantum computers can
use to solve lattice problems do not provide a significant speedup
over classical algorithms.
Code-based cryptography: use error-correcting codes to perform
encryption and decryption. Resistant to attacks by quantum
computers because the algorithms that quantum computers can
use to break these codes require large amounts of memory, which
is a resource difficult to efficiently utilize by quantum computers.
Other approaches to PQC include hash-based cryptography,
isogeny-based cryptography, and multivariate cryptography, among
others.
These approaches are still being actively researched and developed,
and it is not yet clear which ones will ultimately prove to be the
most effective for PQC.
55
Quantum Key Distribution
Quantum Key Distribution (QKD) allows two parties to securely establish a shared secret key
using the principles of quantum mechanics.
QKD provides a level of security that is impossible to achieve with classical cryptographic
protocols.
Quantum computing can leverage quantum entanglement to securely transmit keys.
56
Basic idea behind QKD
Use the properties of quantum states to enable two parties to establish a shared secret key without the risk
of eavesdropping.
The two parties, often referred to as Alice and Bob, exchange quantum states over a quantum
communication channel.
The properties of these quantum states, such as their polarization or phase, are used to encode the key.
Any attempt by an eavesdropper, often called Eve, to intercept or measure the quantum states would result
in a disturbance that can be detected by Alice and Bob, thereby alerting them to the presence of an
eavesdropper and allowing them to discard the affected key.
57
QKD protocols
There are a variety of QKD protocols, but they generally involve using quantum states to
encode information that is used to establish a shared secret key between Alice and Bob.
Once the key is established, it can be used to encrypt and decrypt messages using
traditional cryptographic protocols.
58
BB84 protocol (Bennett and Brassard, 1984): One of the earliest and widely used. Involves the transmission of
single photons over a quantum channel, with the polarization of the photon representing the bit value. Uses a
randomized basis to encode the key. Transmission errors are detected using the same basis.
E91 protocol, also known as the entanglement-based protocol (Ekert, 1991): Involves the creation and
distribution of entangled photon pairs over a quantum channel. The polarization of one photon in each pair is
then used to encode the key. Used to detect eavesdropping.
SARG04 protocol (Pirandola, Mancini, Lloyd, and Braunstein, 2004): Uses coherent states of light to transmit
the key over a quantum channel. The key is encoded in the phase of the coherent states. Transmission errors
are detected using homodyne detection.
B92 protocol proposed (Bennett, 1992): Uses two non-orthogonal states to transmit the key over a quantum
channel. The key is encoded in the state of the photon. Transmission errors are detected by comparing the
expected value of the states with the actual measured value.
59
Popular
QKD
protocols
BB84 protocol
60
E91 protocol
61
N. Alshaer, A. Moawad and T. Ismail, "Reliability and Security Analysis of an Entanglement-Based QKD Protocol in a Dynamic Ground-to-UAV FSO
Communications System," in IEEE Access, vol. 9, pp. 168052-168067, 2021, doi: 10.1109/ACCESS.2021.3137357.
QKD level of security
QKD has the potential to provide a level of security that is impossible to
achieve with classical cryptographic protocols.
This is because any attempt to intercept or measure the quantum states
would result in a disturbance that can be detected by Alice and Bob, thereby
alerting them to the presence of an eavesdropper.
As a result, QKD can provide a level of security that is independent of the
computational power of an adversary, making it a promising technology for
secure communication in the era of quantum computing. 62
Challenges associated
with QKD
Practical implementation: QKD requires specialized
hardware that can be expensive and difficult to operate.
Quality of the quantum communication: Typically limited
to relatively short distances : It is difficult to maintain the
quality of the quantum communication channel over long
distances: Noise and loss, can affect the performance.
Typically limited to line-of-sight transmission. Sensitive to
environmental factors, such as temperature and vibration.
May not be suitable for fiber optics cables.
Key Rate: The rate at which secure keys can be
generated and renewed. QKD systems typically generate
keys at a much lower rate than classical methods..
63
More challenges
associated with QKD
Quantum algorithms
Quantum algorithms take advantage of the unique properties of quantum
mechanics to solve computational problems more efficiently than classical
algorithms. Some examples of well-known quantum algorithms include:
Grover's Algorithm for searching an unsorted database. It provides a quadratic
speedup over the best classical algorithm, allowing the search to be performed in
O(√N) time instead of O(N) time.
Shor's Algorithm for integer factorization. It can factor an N-digit integer in
O((log N)3) time, whereas the best-known classical algorithm takes exponential
time in the number of digits N.
65
Other Quantum
Algorithms
Quantum Walk: quantum analogs of classical random walks. They can be used for
a variety of tasks, including searching, element distinctness, and graph problems.
Quantum Phase Estimation for estimating the phase of an eigenvector of a
unitary operator. It is an important subroutine in several quantum algorithms,
including Shor's algorithm and for solving linear systems of equations.
HHL Algorithm (Harrow-Hassidim-Lloyd) for solving linear systems of equations.
It provides an exponential speedup over the best-known classical algorithm for
certain types of matrices.
66
Grover’s Algorithm
Invented by Lov Grover in 1996 and is one of the most well-known quantum
algorithms.
Grover's algorithm can be used to search an unsorted database of N=2n items in
O(√N) time, which is quadratically faster than the best known classical algorithm's
O(N) time complexity.
The algorithm works by creating a superposition of all possible states and applying
a unitary operator that reflects the amplitude of the state about the mean value.
This operator increases the probability of measuring the desired state and
decreases the probabilities of measuring the other states.
By repeating this process multiple times, the probability of measuring the desired
state increases and the probability of measuring the other states decreases.
Eventually, the desired state can be found with high probability.67
The task The task that Grover’s algorithm aims to
solve can be expressed as follows: given a
classical function f(x):{0,1}ⁿ →{0,1}, where
n is the bit-size of the search space, find an
input x0 such that f(x0)=1.
The idea is to use an oracle (black box)
which can recognize the solution to the
search problem and this recognition is
signaled by making use of an oracle qubit.
In the worst-case scenario, we must
evaluate f(x) a total of N−1 times trying out
all the possibilities. After N−1 elements, we
know it must be the remaining element.
68
High-level description of Grover's algorithm
1.Prepare a quantum state |s⟩ = (1/√N) Σ|x⟩, where x ranges over
all possible states in the database.
2.Apply the Grover iteration operator G = D.W.D-1, where D is the
diffusion operator and W is the oracle operator.
3.Repeat step 2 √N times, where √N is the square root of the
number of items in the database.
4.Measure the quantum state, which will correspond the desired
state with high probability.
69
The oracle operator
The oracle operator is a unitary operator that marks the desired state in the superposition by flipping
the sign of the amplitude of that state.
The oracle operator is typically implemented using a black-box function that evaluates to 1 for the
desired state and 0 for all other states. The oracle operator W can be expressed as:
W = I - 2|w⟩⟨w|
where |w⟩ represents the desired state, and I is the identity matrix.
The oracle operator flips the sign of the amplitude of the desired state, while leaving the amplitudes
of the other states unchanged.
This effectively “marks” the desired state in the superposition and allows the algorithm to amplify its
amplitude.
70
The Grover diffusion operator
The diffusion operator is a unitary operator that is applied to the superposition state |s⟩ after
the oracle operator is applied.
The diffusion operator reflects the amplitude of the state about the mean value of the
amplitudes, which amplifies the amplitudes of the states that are close to the mean value and
decreases the amplitudes of the states that are far from the mean value. The diffusion operator
can be expressed as:
D = 2|s⟩⟨s|-I,
where I is the identity matrix and |s⟩ = (1/√N)Σ|x⟩ is the equal superposition state.
The diffusion operator can be thought of as rotating the state vector towards the desired state.
74
The number of iterations
By applying the oracle and diffusion operators alternately, Grover's
algorithm iteratively amplifies the amplitude of the desired state in the
superposition until it can be measured with high probability.
The number of iterations required is approximately O 𝑁, where N is
the size of the search space, which is significantly faster than classical
algorithms that require O(N) time.
In an unstructured search algorithm, to find the marked item using
classical computation, one would have to check on average N/2 of the
items, and in the worst case, all of them.
Grover's algorithm can serve as a general subroutine to obtain
quadratic run time improvements for a variety of other algorithms.
75
Quantum Circuit for Grover’s Algorithm
76
Grover's algorithm
vs cryptographic
systems
The current state of quantum computing is
not yet advanced enough to break real-world
cryptographic systems using Grover's
algorithm.
This could change in the future as quantum
computers become more powerful and
scalable.
Grover's algorithm can be used to attack
cryptographic systems that rely on the
difficulty of the classical brute-force search,
such as symmetric key encryption and
hashing.
77
Grover's algorithm vs symmetric encryption
Suppose that we have a symmetric encryption key of
n bits.
In classical computing, the only way to find the key is
to try all possible 2n keys until the correct one is
found. This is a very time-consuming process, as it
takes O(2n) time.
However, Grover's algorithm can search the n-bit key
space in O(√2n) or O(2n/2) time, which is much faster
than the classical algorithm.
This roughly means than the encryption key size is
equivalent to n/2 bits.
78
Grover's algorithm vs hash functions
Grover's algorithm can be used to attack cryptographic hash
functions.
A hash function is a one-way function that maps input data to
a fixed-size output.
In classical computing, the only way to find a message that
hashes to a specific value is to try all possible messages until
the correct one is found.
Grover's algorithm can search the hash output space in O(2n/2)
time, which could potentially allow an attacker to find a
message that hashes to a specific value faster than classical
methods.
79
How to attack hash functions ?
Grover's algorithm can be used to attack cryptographic hash functions by
searching for collisions, which are pairs of messages that produce the same hash
value.
Collisions are a security weakness of hash functions because they allow an
attacker to create two different messages that have the same hash value, which
can be used for various types of attacks.
To perform a Grover's algorithm attack on a hash function, the attacker first
needs to determine the number of bits n in the hash output.
Then, they can use Grover's algorithm to search for two messages that have the
same hash value by creating a quantum circuit that generates a superposition of
all possible messages, and then apply the hash function to each message.
80
Consequence of
the attack on hash
functions
Once the attacker finds a collision,
he/she can use it to mount various
types of attacks, depending on the
context of the hash function.
For example, in a digital signature
scheme, an attacker could use a
collision to forge a signature for a
message that was not signed by the
legitimate signer.
81
Shor's algorithm
Introduced by Peter Shor in 1994.
Shor's algorithm has the potential to factor large integers much more
efficiently than classical algorithms.
Shor's algorithm can factor an N-bit integer in O(N3) time complexity,
which is much faster than any known classical algorithm.
This is because quantum algorithms can exploit the quantum
parallelism and interference to speed up computations.
The potential of quantum algorithms to efficiently factor large integers
has significant implications for cryptography, as many widely used
public key cryptography algorithms are based on the difficulty of
factoring large integers.
82
Integer factorization
Integer factorization is the process of finding the prime factors
of a composite integer, which is an integer greater than one
that is not itself a prime number.
For example, 126 can be factored into the product of its prime
factors 2, 3 and 7: 126 = 2 x 3 x 3 x 7.
Integer factorization is a fundamental problem in number
theory and has important applications in cryptography, including
in the security of widely used public key cryptography
algorithms such as RSA.
83
Classical factorization algorithms
The most widely used classical algorithms
for factorization include the Trial Division
Algorithm, the Pollard-Rho algorithm, and
the General Number Field Sieve (GNFS)
algorithm.
These algorithms have varying levels of
efficiency and are able to factor different
sizes of integers, but all of them have high
time complexity and become increasingly
slow for larger integers.
86
Shor’s period-finding
subroutine
Shor’s algorithm uses the properties of quantum computers to
efficiently find the period of a particular function.
The period-finding subroutine is the key step in Shor's algorithm,
and it is used to find the factors of an integer by finding the period
of a modular exponentiation function.
The modular exponentiation function takes three integers as input:
a base number, an exponent, and a modulus. It calculates the result
of raising the base to the exponent and then taking the result
modulo the modulus.
The function in question is related to the integer to be factored and
the factors of the integer can be obtained by using the period of
this function.
88
The modular exponentiation function
The modular exponentiation function can be
expressed as:
f(x) = ax mod N
where a is the base, x is the exponent, and N is
the modulus.
To perform modular exponentiation efficiently,
Shor's algorithm uses Quantum Fourier
Transform (QFT) and modular arithmetic.
The QFT is used to efficiently calculate ax mod N
for a range of values of x.
89
Shor's algorithm
1. N is a composite integer to be factored.
2.Choose a random integer a < N.
3.Use the period-finding subroutine to find the period r of the modular exponentiation function
f(x) = ax mod N. (The period r is the smallest positive integer such that ar mod N = 1)
4.If r is odd or ar/2 ≡ -1 mod N, then go back to step 2 and choose a different random integer a.
5.If r is even and ar/2 ≢ -1 mod N, then the factors of N can be found using the greatest
common divisor of (ar/2 + 1) mod N and (ar/2 - 1) mod N.
90
Example for N=21
91
The period r is 6, which is even.
Let a=11
Following the steps of Shor’s algorithm.
r/2 = 3, 11³(mod 21) = 8.
The prime factors of 21 are:
gcd(8+1, 21)=3
gcd(8–1, 21)=7
11x(mod21)
Time complexity of Shor's
algorithm
The time complexity of Shor's algorithm arises from the two main
steps involved in the algorithm:
1.The first step involves using a quantum Fourier transform to find
the period of the function in question. This step takes O(N2) time
complexity on a quantum computer.
2.The second step involves classical post-processing to obtain the
factors from the period found in the first step. This step takes
O(N3) time complexity on a classical computer.
Therefore, the overall time complexity of Shor's algorithm is
dominated by the classical post-processing step, leading to a total
time complexity of O(N3).
92
Quantum Circuit for Shor’s Algorithm
93
The Ua gates perform modular exponentiation on a quantum register of 2n qubits
The H gates are used to create superposition states
that enable quantum parallelism and evaluate the
modular exponentiation function for many different
input values simultaneously
The inverse QFT is needed to extract the period
information encoded in the amplitudes of the
input register after the QFT has been applied to
the output register.
The |0> state is used as the input to the
H gate to create a uniform superposition
of all possible input values, while the
|1> state is used as the input to the Ua
gate to ensure that the initial state of
the output register is a valid state for
the modular exponentiation function.
Impact of Shor's algorithm
Shor's algorithm has the potential to break
the widely-used public-key cryptography
systems such as RSA and Elliptic Curve
Cryptography (ECC).
It would allow an attacker with a large
enough quantum computer to decrypt
messages that were previously considered
secure.
This would compromise the confidentiality
and integrity of sensitive information
94
Impact of Quantum Computing on IoT Security
95
Quantum computing has the potential
to greatly impact IoT security in both
positive and negative ways.
96
Positive Impact
97
On the positive side, quantum computing
could enable new cryptographic methods that
are more secure than current classical
methods.
Quantum key distribution (QKD) can provide
secure communication channels that are
guaranteed to be free of eavesdropping, and
quantum-resistant encryption algorithms can
make it more difficult for attackers to
compromise IoT devices.
Quantum computing can be used to
accelerate the discovery of vulnerabilities and
weaknesses in IoT devices, which can be used
to enhance their security.
Quantum computing can be used to perform
more efficient security testing and analysis,
which can help identify and fix security flaws
before they are exploited by attackers.
Negative Impact
On the negative side, quantum computing
could break some of the current
cryptographic methods that are used to
secure IoT devices.
Shor's algorithm, which runs efficiently on
quantum computers, can be used to factor
large integers, breaking RSA and other
public-key cryptographic algorithms.
IoT security must evolve to include quantumresistant
cryptographic is particularly
important for systems that have long
lifetimes, such as embedded devices in
critical infrastructure and industrial control
systems.
98
Quantum-resistant cryptographic
methods are becoming increasingly
important for securing IoT systems
against quantum computing
attacks.
Let us discover some examples
of quantum-resistant
cryptographic methods that
are being developed
specifically for IoT systems.
99
Lattice-based
cryptography
100
Lattice-based cryptography is a promising quantum-resistant cryptographic methods.
It is well-suited for IoT systems because it requires less processing power and memory.
It is a public-key cryptography based on mathematical properties of lattices in high-dimensional spaces.
It can be used for secure communication and authentication in IoT systems.
It can be used for key exchange, digital signatures, and encryption.
The security of the system is based on the hardness of the Shortest Vector Problem (SVP) or the Closest
Vector Problem (CVP) in high-dimensional lattices.
These problems are considered computationally intractable for classical and quantum computers (NP-Hard).
Learning with
Errors (LWE)
One popular lattice-based
cryptographic algorithm is the
Learning with Errors (LWE)
problem.
A secret key is used to generate a
set of public keys that are noisy
versions of the secret key.
The security of the system is based
on the difficulty of distinguishing
the noisy public keys from random
noise.
101
Lattice-based
cryptography
Pros & Cons
102
Pros: Low computational and memory
requirements, which makes it well-suited for
resource-constrained devices such as IoT
devices. It also provides strong security
guarantees against both classical and quantum
attacks.
Cons: The size of the keys required for latticebased
cryptography is relatively large compared
to other cryptographic methods, which can be a
challenge for resource-constrained devices.
Additionally, the speed of lattice-based
cryptographic operations can be slower than
other cryptographic methods, which can impact
the performance of systems that use latticebased
cryptography.
Code-based cryptography
Code-based cryptography is another promising quantum-resistant
cryptographic method for IoT systems.
It is based on the theory of error-correcting codes, and it can be used for
digital signatures, key exchange, and encryption.
In code-based cryptography, the security of the system is based on the
hardness of decoding random linear error-correcting codes.
The private key in a code-based cryptographic system is a generator
matrix for the code, while the public key is a matrix that is derived from
the private key using a random permutation.
The security of the system is based on the difficulty of finding the private
key from the public key.
103
McEliece
cryptosystem
One popular code-based cryptographic algorithm is the McEliece
cryptosystem.
It was first proposed by Robert McEliece in 1978 and considered as one of
the most promising candidates for post-quantum cryptography.
A random binary Goppa code is used to generate the private key, while the
public key is derived from the private key using a random permutation.
The security of the McEliece cryptosystem is based on the hardness of
decoding random linear error-correcting codes.
104
Code-based
cryptography
Pros & Cons
106
Pros: Relatively low computational and memory
requirements, which makes it well-suited for
resource-constrained devices such as IoT
devices. Code-based cryptography has been
extensively studied and has a well-established
theoretical foundation.
Cons: The size of the keys required for codebased
cryptography can be relatively large
compared to other cryptographic methods,
which can be a challenge for resourceconstrained
devices. The speed of code-based
cryptographic operations can be slower than
other cryptographic methods, which can impact
the performance of systems that use codebased
cryptography.
Hash-based cryptography
Hash-based cryptography is a simple and efficient quantum-resistant method that can be used for IoT
systems.
It is also known as one-time signature (OTS) or Merkle signature.
A hash function is used to create a one-way function that maps a message of arbitrary length to a
fixed-length output. This output is then used as the digital signature of the message.
To verify the signature, the receiver computes the hash of the original message and compares it with
the digital signature received. If the two match, the signature is considered valid.
The security of hash-based cryptography is based on the collision resistance of the underlying hash
function.
107
Hash-based
cryptography
Pros & Cons
Pros: Relatively low computational and memory
requirements, which makes it well-suited for
resource-constrained devices such as IoT devices.
The size of the keys used in hash-based
cryptography is relatively small compared to other
cryptographic methods.
Cons: Limited number of signatures that can be
created using a given key pair. This means that the
private key must be frequently changed to avoid
exhausting the number of available signatures. Hashbased
cryptography is vulnerable to preimage
attacks, where an attacker can find an input that
hashes to a given output.
108
Quantum Key
Distribution for IoT
QKD can be used to generate
and distribute secure
cryptographic keys in IoT
systems.
In IoT systems, QKD can be
used to securely exchange keys
between devices and gateways,
which can then be used to
encrypt and decrypt data
transmitted between them.
109
QKD Pros & Cons
Pros: It provides a high degree of privacy, since
any attempt to eavesdrop on the quantum
communication channel will be detected by the
two parties.
Cons: The quantum communication channel must
be carefully engineered to ensure that the
photons can be transmitted without being
disturbed by environmental factors such as
temperature fluctuations or vibrations. QKD can
be relatively slow compared to other
cryptographic methods, which can impact the
performance of IoT systems.
110
Isogeny-based
cryptography
Isogeny-based cryptography is a promising quantum-resistant
cryptographic method that is based on the mathematical
properties of elliptic curves.
It can be used for key exchange and digital signatures in IoT
systems.
Isogenies are mathematical functions that map one elliptic
curve to another, while preserving certain algebraic
properties.
The private key consists of a secret isogeny that is used to
derive a public key, which can then be used to encrypt
messages or authenticate digital signatures.
The security of the system is based on the difficulty of
computing the secret isogenies between two elliptic curves
from the public key.
111
Isogeny-based
cryptography
Pros & Cons
112
Pros: Relatively small key sizes compared to
other post-quantum cryptographic
methods. This makes it well-suited for
resource-constrained devices such as IoT
devices.
Cons: computational complexity of the
isogenies between elliptic curves. This can
make the system relatively slow compared
to other cryptographic methods. The
security of isogeny-based cryptography is
still an active area of research, and there
may be unknown attacks that could be
used to break the system.
Conclusion
Quantum computing could be used to strengthen the security of IoT
systems, while on the other hand, it could pose new security risks to
IoT systems.
Quantum computing could be used to develop new cryptographic
systems that are resistant to quantum attacks.
Quantum computing could be used to develop new algorithms for
analyzing data collected from IoT devices.
Quantum computers can be used to crack the symmetric-key
cryptography used to secure the communication between IoT devices
and the cloud.
Quantum computers can be used to tamper with the data collected
from IoT devices.
Quantum resistance is a very hot research topic.
113
Děkuji
114