Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Decryption Failure Attacks on Post-Quantum Cryptography

Nilsson, Alexander LU orcid (2023) In Series of licentiate and doctoral theses
Abstract
This dissertation discusses mainly new cryptanalytical results related to issues of securely implementing the next generation of asymmetric cryptography, or Public-Key Cryptography (PKC).

PKC, as it has been deployed until today, depends heavily on the integer factorization and the discrete logarithm problems.
Unfortunately, it has been well-known since the mid-90s, that these mathematical problems can be solved due to Peter Shor's algorithm for quantum computers, which achieves the answers in polynomial time.
The recently accelerated pace of R&D towards quantum computers, eventually of sufficient size and power to threaten cryptography, has led the crypto research community towards a major shift of focus.

A... (More)
This dissertation discusses mainly new cryptanalytical results related to issues of securely implementing the next generation of asymmetric cryptography, or Public-Key Cryptography (PKC).

PKC, as it has been deployed until today, depends heavily on the integer factorization and the discrete logarithm problems.
Unfortunately, it has been well-known since the mid-90s, that these mathematical problems can be solved due to Peter Shor's algorithm for quantum computers, which achieves the answers in polynomial time.
The recently accelerated pace of R&D towards quantum computers, eventually of sufficient size and power to threaten cryptography, has led the crypto research community towards a major shift of focus.

A project towards standardization of Post-quantum Cryptography (PQC) was launched by the US-based standardization organization, NIST.
PQC is the name given to algorithms designed for running on classical hardware/software whilst being resistant to attacks from quantum computers.
PQC is well suited for replacing the current asymmetric schemes.
A primary motivation for the project is to guide publicly available research toward the singular goal of finding weaknesses in the proposed next generation of PKC.

For public key encryption (PKE) or digital signature (DS) schemes to be considered secure they must be shown to rely heavily on well-known mathematical problems with theoretical proofs of security under established models, such as indistinguishability under chosen ciphertext attack (IND-CCA).
Also, they must withstand serious attack attempts by well-renowned cryptographers both concerning theoretical security and the actual software/hardware instantiations.
It is well-known that security models, such as IND-CCA, are not designed to capture the intricacies of inner-state leakages.
Such leakages are named side-channels, which is currently a major topic of interest in the NIST PQC project.

This dissertation focuses on two things, in general:
1) how does the low but non-zero probability of decryption failures affect the cryptanalysis of these new PQC candidates?
And 2) how might side-channel vulnerabilities inadvertently be introduced when going from theory to the practice of software/hardware implementations?
Of main concern are PQC algorithms based on lattice theory and coding theory.

The primary contributions are the discovery of novel decryption failure side-channel attacks, improvements on existing attacks, an alternative implementation to a part of a PQC scheme, and some more theoretical cryptanalytical results. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Prof. of Practice Saarinen, Markku-Juhani, Tampere University, Finland.
organization
publishing date
type
Thesis
publication status
published
subject
keywords
Post-quantum cryptography, Code-based cryptography, Lattice-based cryptography, side-channel attack
in
Series of licentiate and doctoral theses
issue
155
pages
294 pages
publisher
Lunds Universitet/Lunds Tekniska Högskola
defense location
Lecture Hall E:A, building E, Ole Römers väg 3, Faculty of Engineering LTH, Lund University, Lund. The dissertation will be live streamed, but part of the premises is to be excluded from the live stram.
defense date
2023-05-11 09:15:00
ISSN
1654-790X
1654-790X
ISBN
978-91-8039-696-7
978-91-8039-695-0
project
Side channels on software implementations of post-quantum cryptographic algorithms
Side-channel attacks in software in autonomous systems
language
English
LU publication?
yes
id
9a16223b-09dc-4188-b384-bc25b3d83437
date added to LUP
2023-04-12 11:59:22
date last changed
2023-04-24 13:10:11
@phdthesis{9a16223b-09dc-4188-b384-bc25b3d83437,
  abstract     = {{This dissertation discusses mainly new cryptanalytical results related to issues of securely implementing the next generation of asymmetric cryptography, or Public-Key Cryptography (PKC).<br/><br/>PKC, as it has been deployed until today, depends heavily on the integer factorization and the discrete logarithm problems.<br/>Unfortunately, it has been well-known since the mid-90s, that these mathematical problems can be solved due to Peter Shor's algorithm for quantum computers, which achieves the answers in polynomial time.<br/>The recently accelerated pace of R&amp;D towards quantum computers, eventually of sufficient size and power to threaten cryptography, has led the crypto research community towards a major shift of focus.<br/><br/>A project towards standardization of Post-quantum Cryptography (PQC) was launched by the US-based standardization organization, NIST. <br/>PQC is the name given to algorithms designed for running on classical hardware/software whilst being resistant to attacks from quantum computers.<br/>PQC is well suited for replacing the current asymmetric schemes.<br/>A primary motivation for the project is to guide publicly available research toward the singular goal of finding weaknesses in the proposed next generation of PKC.<br/><br/>For public key encryption (PKE) or digital signature (DS) schemes to be considered secure they must be shown to rely heavily on well-known mathematical problems with theoretical proofs of security under established models, such as indistinguishability under chosen ciphertext attack (IND-CCA).<br/>Also, they must withstand serious attack attempts by well-renowned cryptographers both concerning theoretical security and the actual software/hardware instantiations.<br/>It is well-known that security models, such as IND-CCA, are not designed to capture the intricacies of inner-state leakages.<br/>Such leakages are named side-channels, which is currently a major topic of interest in the NIST PQC project.<br/><br/>This dissertation focuses on two things, in general:<br/>1) how does the low but non-zero probability of decryption failures affect the cryptanalysis of these new PQC candidates?<br/>And 2) how might side-channel vulnerabilities inadvertently be introduced when going from theory to the practice of software/hardware implementations?<br/>Of main concern are PQC algorithms based on lattice theory and coding theory.<br/><br/>The primary contributions are the discovery of novel decryption failure side-channel attacks, improvements on existing attacks, an alternative implementation to a part of a PQC scheme, and some more theoretical cryptanalytical results.}},
  author       = {{Nilsson, Alexander}},
  isbn         = {{978-91-8039-696-7}},
  issn         = {{1654-790X}},
  keywords     = {{Post-quantum cryptography; Code-based cryptography; Lattice-based cryptography; side-channel attack}},
  language     = {{eng}},
  month        = {{05}},
  number       = {{155}},
  publisher    = {{Lunds Universitet/Lunds Tekniska Högskola}},
  school       = {{Lund University}},
  series       = {{Series of licentiate and doctoral theses}},
  title        = {{Decryption Failure Attacks on Post-Quantum Cryptography}},
  url          = {{https://lup.lub.lu.se/search/files/143742917/thesis.pdf}},
  year         = {{2023}},
}