# Post-Quantum Cryptography

Learn about the number of classes of algorithms that are believed to be resistant to attacks from both classical and quantum computers in this lesson.

## Overview

The major public-key cryptography schemes, such as RSA, DSA, and ECDSA, which are used today on the Internet and in blockchain applications, are based on algorithms that are vulnerable to quantum attacks and can easily be broken by Shor’s algorithm if an adversary is in possession of a large-scale quantum computer.

Thus, it’s a crucial task to identify quantum-safe cryptographic primitives that might serve as the basis for post-quantum algorithms for digital signing in future public-key infrastructures. There are numerous references, reports, and recommendations to post-quantum cryptography from various standard institutions, such as

## Code-based cryptography

The major example of code-based cryptography is

## Lattice-based cryptography

Lattice-based cryptography has received a lot of attention for postquantum approaches as they offer efficient implementations and as they have very strong security proofs. A lattice $\mathcal{L}$ of $\mathcal{R}^{n}$ is a discrete subgroup of $\mathcal{R}^{n}$, or more formally (

### Lattice

A **lattice** $\mathcal{L}$ is a set that can be expressed by the sum of integer multiples of vectors, i.e.,

$\mathcal{L}\left(b_{1}, \ldots, b_{n}\right)=\left\{\sum_{i=1}^{n} x_{i} b_{i}: x_{i} \in \mathbb{Z} \text { for } 1 \leq i \leq n\right\}$

of $n$ linearly independent vectors $b_{1}, \ldots, b_{n} \in \mathbb{R}^{n}$, which form the basis of the lattice.

Lattice-based systems rely on lattice problems, which are known to be NP-hard, such as the Shortest Vector Problem (SVP), where the problem is to find the shortest nonzero vector in the lattice. This problem is considered to be hard in both classical and quantum computation models.

## Hash-based cryptography

Hash-based signature schemes offer many advantages since their security only relies on the one-wayness of hash functions $H$, whose security is very well understood. Furthermore, it’s well-known that cryptographic hash functions are hard to invert, also for quantum computers, since Grover’s algorithm only yields a quadratic speed-up. For example,

## Multivariate polynomial cryptography

The security of multivariate public-key cryptosystems (MPKC) is based on the assumption of the hardness of solving systems of multivariate nonlinear equations, usually polynomials, over a finite field. The signature scheme SFLASH, which is based on the Matsumoto-Imai scheme, was accepted as a security standard by the New European Schemes for Signature, Integrity, and Encryption (NESSIE) in 2003, but was subsequently completely broken by

Get hands-on with 1200+ tech skills courses.