2016 암호여름학교 - Post-Quantum Public-key Cryptography (미완)

""솔직히 너무 어려워서 잘 이해를 못하고 받아 적기만...."" 

Post-Quantum Public-key Cryptography

IT requires Public-key Cryptography

• 전자상거래의 증가

Factorization Progress

Inter Factorization Problem (IFP)

• Given a composite n = pq, find p and q
• 소인수 분해의 이산대수 문제
• 분석 기술이 나날이 발전중

DLP Progress in F_p^n

Discrete Logarithm Problem

• Given g^x in

ECDLP Progress

Elliptic Curve DLP

• Given xP in E(F_q), compute x.

The quantum computer threat

Shor Algorithm 1997

• Polynomial-Time algorithm for Prime Factorization and Descrete Logarithm on quantum computer
• RSA and ElGamal insecure

Quantum computer realistic?

• NSA seeks to build quantum computer that could crack most types of encryption
• Researchers use silicon to push quantum computing toward reality

만약 양자컴퓨터를 만들어도 발표하지 않고 사용할 가능성이 높기 때문에 위험

Target Environment

Post-quantum cryptography for small devices

• identity and adapt the most suitable PQ candidates to the requirements of constrained devices and to produce efficient and physically secure implementations *

PQ-Crypto for internet

• internet severs are subject to tremendous performance pressures
• goal is to intergrate high-security PQ-crypto into internet

PQ-Crypto for Cloud

NSA Suite B Cryptography

NSA announced that it is moving towards quantum-resistant algorithm

• Suite B is a family of cryptography......

Public key Cryptography

Quantum Cryptography

• Quantum key distribution(QKD)
• QKD is still vulnerable to a man-in-the-middle attack
• so far lacks the functionality of digital signatures
• 모든 키분배는 중간자 공격에 안전하지 않다.
• 양자 암호로는 인증까지는 할 수 없다. 그래서 공개키 암호와 함께 사용

Post-Quantum Problems

• Solving non-linear equation systems over finite fields
• Bounded distance decoding over finite fields
• Short and close lattice vectors
• Breaking cryptography hash functions
• Quantum key exchange
• 찝찝한 부분은 양자 컴퓨터에 안전하다고 증명되어 있지는 않다.
• 다만, 알려져있는 양자 알고리즘에 적용할 수 없는 알고리즘을 사용한 암호

Quantum Algorithms

Grover algorithm brings faster simultaneous search in data

• some security loss in symmetric crypto
• some security loss in hash functions

Polynomial-time quantum algorithm for

• factoring .....
• 생략

Quantum algorithms for Lattice-based crypto

SOLILOQUY, a lattice-based primitive designed at CESG in2016

• the security of SOLILOQUY is based on two well known hard problems
• closed vector problem
• principal ideal problem

Multivariate Quadratic-based PQ-Crypto

Retrospective of MQ-PKC

• Claude E. Shannon

• Breaking a good cipher should requires as much work as solving a system of simultaneous equation in a large number of unknowns of a complex type

• After the NESSIE consortium proposed SFLASH to be standardized. -> 2010 년도에 깨짐

MQ-Encryption

Multivariate public key cryptosystems

• Cryptosystems, whose public keys are a set of multivariate

• the public key is given as :

  • G(X1, ... , Xn) = (G1(X1, ... , Xn), ... , Gm(X1, ... , Xn))

• We use the finite field k = GF[2]/(x^2 + x+ 1) with 2^2 elements

• (more)

Soving Polynomial System (SPS) Problem

• given a system P = P1, ... , Pm of m nonlinear polynomial equations
• ....

Destructive Aspect of MQ-Problem

• 안좋은 면 : MQ를 이용해서 암호화 알고리즘을 설계하는 데 다른 암호 알고리즘을 깰 수도 있다.
• AES 같은 걸 깰 수 있음
• 관계식에서 아는 것과 모르는 것을 구분해 낼 수 있으면 그게 다변수 방적식

Attacks on AES

• 2^8에서 시도를 하면 3986개의 변수를 갖는 시스템을 풀면 AES 깰 수 있다.
• 카탄과 같은 경량 암호들도 다변수 시스템으로 나타낼 수 있기 때문에 공격 가능

Constructive Aspect of SPSP

ASA(Affine-Substitution-Affine) Structure

• trapdoor S have been hidden in secret affine layer
• AES-128 10 rounds with 19 layers

SASAS Structure

ASASA Structure

• truly random polynomial
• large public key size => 연산이 계속 늘어나면 degree가 점점 늘어남

MQ-PKCs

MQ-PKCs can be divided into the following two types

• MI-Scheme