Post-Quantum Cryptography - Daniel J. Bernstein, Tanja Lange

# Post-Quantum Cryptography - Daniel J. Bernstein, Tanja Lange {%hackmd @HITCON/r1z4zylVv %} > 從這開始 motivation one communication channels are syping on out data motivation two communication channels are modifying our data literal meaning of crytography secret writing achieves various security goals by ... cryptography with symmetric keys ... cyrptography with public keys ... alogorithms for quantum computation discrete logarithms and factoring google says it is a powerful quantum computer ... quantum computinig could end encryption within five years says google boss chinese researchers expect quantum leap in comuting challenging google's supremacy https://www.globaltimes.cn/content/1198916.shtml Algorithms for quantum computation: discrete logarithms and factoring https://ieeexplore.ieee.org/document/365700/authors#authors what are they doing secretly? who knows ... public keys turned threaded if alice and bob alreardy share long secret key k one time pad for confidentiality wegman carter mac for integrity and authenticity aes 256 standardized method to expand short secret key 256-bit k into string indistinguishable from long secret key aes introduced in 1998 by daemen and rijmen security analyzed in papers by dozens of crytanalysts no credible threat from quantum algorithms grover costs //(2^{128}//) some results assume attacker has quantum access to computation then some systems are weaker but i dont know if my laptop had turned into a quantum computer crytography under the assumption that the attacker has a quantum computer 1994 : shors quantum alorithm 1996 : grovers quantum algorithm many subsequent papers on quantum algorithms see quantumalgorithmzoo.org 2003 : daniel j bernstein introduces term post quantum crytography 2006 : first international workshop on post quantum cryptography pqcrypto 2006, 2008, 2010, 2013, 2014, 2016, 2017, 2018, 2019, (soon) 2020 2015 : nist hosts its first workshop on post quantum cryptography 2016 : nist announces a standardization project for post quantum systems 2017 : deadline for submissions to the nist competietion 2019 : second round of nist competition begins 2020 : Third round of NIST competition begins. 21 december 2017 : mist posts 69 submissions from 260 people big quake bike ... by end of 2017 : 8 out of 69 submission attacked ... guess again hk17 racoss rvb dont use them above ... by end of 2018 : 22 out of 69 submissions attacked Some less seurity than claimed;some really broken ; some attack scripts. 30 january 2019 : 26 candidates retained for second round merges for second round : hila5 ... merges for third round : classic mceliece and nts-kem national academy of sciences (us) 4 december 2018 : report on quantum computing Don't panic. "Key Finding 1 : given the current state of quantum computing and recent rates of progress itis highly unexpected that a quantum computer that can compromise rsa 2048 or comparable discrete logarithm based public key cryptosystems will be built within the next decade panic key finding 10 : even if a quantum computer that can decrypt current cryptographic ciphers is more than a decade off the hazard of such a machine is high enough and the time frame for transitioning to a new security protocol is sufficiently long and uncertain that prioritization of the development standardization and deployment of post quantum cryptography is critical for minimizing the chance of a potential security and privacy disaster in particular all encrypted data that is recorded today and stored for future use will be cracked once a large scale quantum computer is developed many stages of research from design to deployment define the goals explore space of cryptosystems study algorithms for the attackers focus on secure cryptosystems study algorithms for the users study implementations on real hardware study side channel attacks fault attacks atc focus on secure reliable implementations focus on implementations meeting performance requirements integrate securely into real world applications warning : waterfall data flow undesirable major categories of public key post quantum systems code based encryption : mceliece cryptosystem has survived since 1878 short ciphertexts and large public keys security relies on hardness of decoding error correcting codes Hash-based signatures: - very solid security - small public keys - Require only a secure hash function (hard to find second preimages) Isogeny-based encryption: new kid on the block, promising shrt keys and ciphertexts and non-interactive key exchange. Security relies on hardness of finding isogenies between elliptic cureves over finite fields. Lattice-based encryption and signhatures : possiability for balanced sizes. Security relies on hardness of finding short vectors in some (typically special ) lattice. Multivariate-quadratic signatures : short signatures and large public keys.Security relies on hardness of solving systems of multivariate equations over finite fields.  post quantum public key signatures Alice = = = = > 量子電腦(Eve) = = = = => Bob 明文=> Secret Key & Public Key => 加密 => 解密 Alice Public Key => 明文 only one prerequisite a good hash function sha3-512 ... hash functions map long strings to fixed length strings $H:\{0, 1\}^* \to \{0, 1\}^n$ Quantum computers affect the hardness only marginally(Grover, not Shor.) Old ides: 1979 Lamprot one-time signatures; 1979 Merkle extends to more signtures. on the fast track stateful hash based signatures cfrg has published 2 rfcs : rfc 8391 and rfc 8554 Using smart card & chip to encode. (?) on the fast track stateful hash bassed signatures cfrg has published 2 rfxs : ... NIST has gone through tw... Stateful Hash-Based Signatures. a signature scheme for empty messages : key generation "empty message" >> useful ? first part of signempty.py ```python= import os import hashlib def keypair(): secret = sha3_256(os.urandom(32)) public = sha3_256(secret) return public, secret ``` rest of signempty.py ```python= def sign(message, secret): if message != '':raise Exception('nonempty message') signedmessage = secret return signedmessage def open(signedmessage, public): if sha3_256(signedmessage) != public: raise Exeption('Bad signature') message = '' return message ``` the best post quantum systems in round 3 of the nist competition systems from us and from our colleagues at academia sinica 這四種演算法就是目前還比較好的解決方案： McEliece - classic.mceliece.org Rainbow - Multivariate-based signatures - https://www.pqcrainbow.org NTRU Prime. - Lattice-based encryption SPHINCS+. - Hash-based signatures. - https://sphincs.org further information pqcrypto.org 主要是破質數分解影響公開金鑰加密系統，提出多種解法，但也很多種解法被破解了… 後續主要解釋其中一種 stateful hash-based signature. ###### tags: `HITCON2020`,`HITCON`

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.