PQC Flashcards
1
Q
Advantages QC
A
- Optimization of logistics
- Simulation of molecules
- Search in unsorted lists
- Factorization, and discrete logarithm
2
Q
Quantum algorithms: Grover’s Algorithms
A
- Grover’s algorithm weakens security of all symmetric encryption schemes (AES, SHA-256, …)
-> Search in unsorted list
-> Square root speedup for brute-force attacks
-> Easy solution: Double the key size or use larger hashes
3
Q
PQC families
A
- Code-based
- Lattice-based
- Hash-based
- Multivariate
- Isogeny-based
4
Q
Code-based Cryptography
A
- Large public keys, small ciphertexts, good performance
- Prone to decoding errors
- based on hardness of decoding a linear code
-> linear code is an error-correcting code for which any linear combination of codewords is also a codeword
5
Q
Lattice-based Cryptography
A
- Well studied problem
- Hard instances of lattice problems
- Can be further adapted
6
Q
Multivariate Cryptography
A
- Very small signature sizes, large private keys
- In contrast to “easy” linear equations, multivariate equations are known to be NP-complete
7
Q
Hash-based Cryptography
A
- Only works for signature schemes
- provably secure (given secure hash functions)
- One-way functions are a necessary assumption for cryptography
- State management can be an issue
- Stateless schemes have large signatures
- Computing pre-images of a cryptographic hash function remains hard also for quantum computers (use pre-image as private key, hash-value as public key)
8
Q
Isogeny-based Cryptography (Dis-)advantages
A
- fairly new
- computational effort
- recent breaks
-+ complicated math
+ very short keys
+ DH-like schemes
+ Development like ECC?
9
Q
Quantum algorithms: Shor’s Algorithm
A
- Breaks all asymmetric encryption and digital signatures like RSA, (EC)DH, (EC)DSA, …
-> Solves integer factorization and discrete logarithm problem
-> Speedup to polynomial time on quantum computers
-> There are no easy solutions, we need QC-resistant cryptographic schemes
10
Q
Comparison: Encryption: Keys
A
- Classic: ++
- Code: –
- Lattice: +
- Isogeny: ++
11
Q
Comparison: Encryption: Ciphertexts
A
- Classic: ++
- Code: +
- Lattice: -
- Isogeny: ++
12
Q
Comparison: Encryption: Performance
A
- Classic: o
- Code: +
- Lattice: ++
- Isogeny: –
13
Q
Comparison: Encryption: Candidates
A
- Classic: ECDH, RSA
- Code: Classic McEliece, HQC, BIKE
- Lattice: Kyber, FrodoKEM
- Isogeny: SIKE (broken)
14
Q
Comparison: Signature: Key
A
- Classic: ++
- Lattice: +
- Hash: ++
- Multivariate: –
15
Q
Comparison: Signature: Signature
A
- Classic: ++
- Lattice: +
- Hash: –
- Multivariate: ++
