Post-Quantum Cryptography: Why? What is it? / La crittografia post-quantistica: perché? Che cos'è?

Post-Quantum Cryptography: Why? What is it? / La crittografia post-quantistica: perché? Che cos'è?

Segnalato dal Dott. Giuseppe Cotellessa / Reported by Dr. Giuseppe Cotellessa

      Overview

Due to their computing power, quantum computers have the disruptive potential to break various currently used encryption algorithms. Quantum computer attacks on today's cryptography are expected to become reality within the next 15 to 20 years. Once available, quantum computers could solve certain calculations much faster than today's computers, threatening even best currently known security algorithms such as RSA and ECC. Various internet standards like transport layer security (TLS), S/MIME or PGP/GPG use cryptography based on RSA or ECC to protect data communication with smart cards, computers, and servers or embedded IoT systems. Online banking on "https" sites or "instant messaging" encryption on mobile phones are well-known applications using these standards.
The solution is post-quantum cryptography (PQC) for security technologies. In a world of quantum computers, PQC should provide a level of security that is comparable with what RSA and ECC provide today in the classical computing world. However, to withstand quantum calculation power, key lengths need to be longer than the usual 2048 bits of RSA or the 256 bits of ECC. Nevertheless, it is imperative that commercially available security chips with PQC come without requiring additional memory space and hence a larger chip size. Starting now, we need to prepare for ensuring that the security technology is available and commercially feasible by the time quantum computers arrive.

When I wrote my first blog entry here ("Ola from Gustavo"), I gave a short description of what will happen when someone presents the first quantum computer, i.e., most of the actual cryptography (ECC, RSA) will be dead. One statement about quantum computers and cryptography is:
"Well, we don't have a quantum computer now and the expectation for one is around 15 years, why I should be worried now?"
I will give one good reason, imagine that you use some encryption (RSA, ECC or whatever) in your messages and someone starts storing these messages. Now, this agency/person/computer is not able to read your messages. However, in 15 years (around this) when a real quantum computer appears then, it will be possible to break the encryption and read everything about your past. For this reason, we need to be prepared against this threat now and we don't need to wait for the quantum computer to start to protect ourselves. For this protection, we have good guardians of the privacy that with the union of their powers started the research in Post-Quantum cryptography (PQC).

PQC divides into four big areas, i.e., Hash-based, Code-based, Multivariate-quadratic-equations-based and Lattice-based. There are other areas but these four became more important in the last 10 years. In the following, I will give a very brief explanation and examples of schemes of each area in PQC. There is a website about PQCrypto with initial recommendations and a list of publications in the area to access click here.

HASH-BASED Cryptography

In hash-based, we can see important signature schemes such as Lamport-Diffie OTS, Merkle's hash-tree, XMSS, SPHINCS and a lot of relevant work. I decided to talk about one of the newest works in the area, i.e., SPHINCS.
SPHINCS was presented in 2015 at EUROCRYPT under the title of "SPHINCS: practical stateless hash-based signatures". In order to understand better the idea behind this work, it is necessary to have a previous knowledge about hash signatures because they present two new ideas: replacement of the leaf OTS (One-time Signature) with a hash-based FTS (Few-time Signature) and Goldreich’s construction as a hyper-tree construction with h layers of trees of height 1. For more details about the implementation and construction of SPHINCS, it is possible to access here.
Also, if you have more interest in Hash-Based cryptography can be checked via pqcrypto hash-based and at this webpage of Andreas Hülsing.

CODE-BASED Cryptography

The classic name that appears in Code-based is McEliece’s hidden-Goppa-code public-key encryption system from 1978. However, there is new work in the area such as the work from Misoczki, Tillich, Sendrier, and Barreto using quasi-cyclic moderate-density-parity-check (QC-MDPC) codes for the McEliece encryption system. The principal contribution of this work for the area is the use of small key sizes.
Other relevant work, this time in the fast implementation area, came from Bernstein, Chou, and Schwabe under the name of "McBits: Fast constant-time code-based cryptography". The main contribution of this work is a constant-time in the implementation of code-based cryptography and they avoid time attacks.
The literature for code-based is very big and can be checked in this link.

MQ-BASED Cryptography

The Multivariate Cryptography schemes are based on the difficult to solve non-linear systems of equations over
finite fields. Finding a solution for these systems, in general, is considered a NP-complete/-hard problem. One of many
interesting examples is Patarin’s Hidden Fields , generalizing a proposal by Matsumoto and Imai (1988).
The original work from Paratin can be found at: Hidden Field Equations (HFE) andIsomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms.

If we want to see what happened recently in the MQ area, there is slides from the PQCrypto winter school are available online atPQCrypto . The slides from Jintai Ding gave a very nice overview of the state-of-art in the Multivariate
Public Key Cryptography (MPKC). In the slides, he gave an introduction MQ with a small example to understand
how MQ works. After that, the author gives the principal cryptosystems in MPKC.
The slides are available at this link and more material about MQ-based cryptography can be checked at PQCrypto project.

LATTICE-BASED Cryptography

The lattice area received a lot of attention in the past years, new cryptosystems, new attacks, and implementations. Everything is based on hard problems in lattices such as shortest-vector problem (SVP), Ideal Lattice, Closest-vector Problem (CVP) and others. There is a lattice challenge to show the shortest vector in a Lattice and the ideal Lattice given the dimension of it, more details about it can be checked at Lattice Challenge.

In the area of public-key cryptography, there are several schemes and mostly is based on SVP and Ideal lattices. That is the case for  the scheme described by Peikert and Stehlé et al.

ITALIANO

Panoramica

A causa della loro potenza di calcolo, i computer quantistici hanno il potenziale perturbativo di rompere vari algoritmi di crittografia attualmente utilizzati. Gli attacchi di computer quantistici alla crittografia odierna dovrebbero diventare realtà entro i prossimi 15-20 anni. Una volta disponibile, i computer quantistici potrebbero risolvere determinati calcoli molto più velocemente rispetto ai computer di oggi, mettendo a rischio anche i migliori algoritmi di sicurezza attualmente conosciuti come RSA e ECC. Diversi standard internet come la sicurezza TLS, S / MIME o PGP / GPG utilizzano la crittografia basata su RSA o ECC per proteggere la comunicazione dati con smart card, computer e server o sistemi embedded IoT. La banca in linea sui siti "https" o la crittografia "messaggistica istantanea" sui telefoni cellulari sono applicazioni note con queste norme.

La soluzione è la crittografia post-quantistica (PQC) per le tecnologie di sicurezza. In un mondo di computer quantistici, PQC dovrebbe offrire un livello di sicurezza comparabile a quello che oggi RSA e ECC forniscono nel mondo dell'informatica classica. Tuttavia, per sopportare il potere di calcolo quantico, le lunghezze delle chiavi devono essere più lunghe rispetto ai 2048 bit tradizionali di RSA o 256 bit di ECC. Tuttavia, è indispensabile che i chip di sicurezza disponibili in commercio con PQC vengano forniti senza richiedere spazio di memoria aggiuntivo e quindi un formato di chip più grande. A partire da ora, dobbiamo prepararci per assicurare che la tecnologia di sicurezza sia disponibile e commercialmente fattibile per quando i computer quantistici arriveranno.

Quando ho scritto qui il mio primo blog ("Ola da Gustavo"), ho descritto brevemente ciò che accadrà quando qualcuno presenta il primo computer quantistico, cioè la maggior parte della crittografia effettiva (ECC, RSA) sarà morta. Una dichiarazione sui computer quantistici e sulla crittografia è:

"Beh, adesso non abbiamo un computer quantistico e l'aspettativa per uno è di circa 15 anni, perché dovrei essere preoccupata adesso?"

Ti darò una buona ragione, immagino di usare qualche crittografia (RSA, ECC o altro) nei tuoi messaggi e qualcuno inizia a memorizzare questi messaggi. Ora, questa agenzia / persona / computer non è in grado di leggere i tuoi messaggi. Tuttavia, in 15 anni (intorno a questo periodo) quando compare un vero computer quantistico, sarà possibile rompere la crittografia e leggere tutto sul tuo passato. Per questo motivo dobbiamo essere preparati contro questa minaccia ora e non abbiamo bisogno di aspettare che il computer quantistico cominci a proteggere noi stessi. Per questa protezione, abbiamo buoni tutori della privacy che con l'unione dei loro poteri hanno avviato la ricerca nella crittografia Post-Quantum (PQC).

PQC si divide in quattro grandi aree, cioè basate su Hash (Tagliare a pezzetti) , basate su codice, basate su equazioni multivariato-quadratiche e basate su Lattice (Reticolo). Ci sono altre aree, ma questi ultimi sono diventati più importanti negli ultimi 10 anni. In seguito, darò una breve spiegazione e esempi di schemi di ciascuna area in PQC. 

Crittografia HASH-BASED

In base a hash, possiamo vedere schemi di firma importanti come Lamport-Diffie OTS, hash-tree di Merkle, XMSS, SPHINCS e un sacco di lavori rilevanti. 

SPHINCS è stato presentato nel 2015 a EUROCRYPT sotto il titolo di "SPHINCS: firme a base di hash senza precedenti". Per comprendere meglio l'idea dietro questo lavoro, è necessario avere una conoscenza precedente sulle firme di hash perché presentano due nuove idee: la sostituzione del foglio OTS (One-Time Signature) con un FTS a base di hash (Poche ore Signature) e la costruzione di Goldreich come costruzione iper-albero con h livelli di alberi di altezza 1. 

Criptazione basata su codici

Il nome classico che appare in codice è il sistema di crittografia pubblica di codice McEliece nascosto-codice Goppa a partire dal 1978. Tuttavia, c'è un nuovo lavoro nell'area come il lavoro di Misoczki, Tillich, Sendrier e Barreto usando quasi-ciclici codici di controllo a parità di densità (QC-MDPC) per il sistema di crittografia McEliece. Il principale contributo di questo lavoro per l'area è l'utilizzo di piccole dimensioni chiave.

Altri lavori rilevanti, questa volta nell'area di implementazione veloce, sono venuti da Bernstein, Chou e Schwabe sotto il nome di "McBits: Fast-cryptography basata su codice a tempo costante". Il contributo principale di questo lavoro è un tempo costante nell'attuazione della crittografia a codice e evita tempi di attacco.

Crittografia MQ-BASED

I sistemi di crittografia multivariata si basano sui difficili sistemi non lineari da risolvere di equazioni sopra

campi finiti. Trovare una soluzione per questi sistemi, in generale, è considerato un problema NP-complete / -hard. Uno dei tanti interessanti esempi sono i campi nascosti di Patarin, generalizzando una proposta di Matsumoto e Imai (1988).

Il lavoro originale di Paratin può essere trovato in: Equazioni di Hidden Field (HFE) eIsomorfismi dei Polinomi (IP): due nuove Famiglie di Algoritmi Asimmetrici.

Se vogliamo vedere ciò che è successo recentemente nell'area MQ, ci sono diapositive dalla scuola invernale PQCrypto disponibili online pressoPQCrypto. Le diapositive di Jintai Ding hanno dato una panoramica molto bella dello stato dell'arte nel Multivariato

Crittografia a chiave pubblica (MPKC). Nelle diapositive, ha dato un introduzione MQ con un piccolo esempio per capire come funziona MQ. Dopo di che, l'autore dà i principali cryptosystems in MPKC.

Le diapositive sono disponibili a questo collegamento e più materiale sulla crittografia a base di MQ può essere controllato al progetto PQCrypto.

Crittografia a base di reticolo.

L'area reticolo ha ricevuto molta attenzione negli ultimi anni, nuovi cryptosystems, nuovi attacchi e implementazioni. Tutto è basato su problemi duri nei reticoli quali il problema più breve vettoriale (SVP), la griglia ideale, il problema più vicino vettoriale (CVP) e altri. C'è una sfida a reticolo per mostrare il vettore più corto in un Reticolo e il Reticolo ideale è dato dalla dimensione di esso, maggiori dettagli su di esso possono essere controllati a Lattice Challenge.

Nell'ambito della crittografia a chiave pubblica, esistono diversi schemi e per lo più si basano su SVP e lattice Ideal. Questo è il caso dello schema descritto da Peikert e Stehlé et al.

Da:

http://www.globalspec.com/events/eventdetails?eventid=1556&evtsrc=InfineonTechnologies%5F170921%5FInv1&et_rid=1808109563&et_mid=83531336&cid=webinar

http://ecrypt-eu.blogspot.it/2016/04/post-quantum-cryptography-why-what-is-it.html