2016 암호여름학교 - Provable Security of Public-Key Cryptography

2016 암호여름학교 NIMS 
한참 재밌게 듣다가 갑자기 놓침....

Provable Security of Public-Key Cryptography

Aaram Yun, School of ECE, UNIST

Summary

• '증명가능한 안전성', 즉 provable security는 80년대 중반에 Goldwasser와 Micali가 계산복잡도 이론에 근거해서 암호화 방식의 안전성을 엄밀하게 정의하고 이를 환원 증명을 통해 증명한 이후로 암호학적 설계에서 중요한 패러다임으로 자리 잡았고, 오늘날은 사실상 공개키 암호학의 거의 전 분야에서 요구되고 있다. 본 강의에서는 구체적인 예를 통해 증명가능한 안전성에 관해 설명하고자 한다. 특히, IND-CCA 안전성을 만족하는 최초의 효율적인 암호화 방식인 Cramer-Shoup의 안전성 증명을 자세히 살펴보도록 한다.

Provable Security?

A bit of History...

• 1976 : Diffie & Hellman, "New direction in cryptography"
• 1982 : Goldwasser & Micali, "Probabilistic encryption and how to play mental poker, keeping secret all partial information", STOC 1982
  • Turing award for 2012

Provable security

Goldwasser & Micali

Why proof?

• Else, how can we be sure nobody learned anyting from what they have eavesdropped?
• or, how do you know that nothing happened?

Unconditionally?

• Bad new: currently, we don't know how to design a cryptosystem with proven security
• Because, if P=NP, then you can break

P and NP

Class P

• A problem is in class P: if it can be solved efficiently(in polynomial time)
• EX : Eulerian path problem
• "Given a graph G, is there an Eulerian path in this graph?"
• Eulerian path itself is the witness

Class NP

• A problem is in class NP : if given an answer, checking it can be done efficiently
• EX : Hamiltonian path problem
• "Given a graph G, is there a Hamiltonian path in this graph?"
• Hamiltonian path itself is the witness
• 정답을 확인하는 것은 쉽지만 정답을 찾는 건 어렵다.
• Another Example : "Given a bitstring c and a public key pk, is this c an encryption of some message with respect to the public key pk?"
• That is, do we have c = Encpk(m) for some message m?
• what can be the witness?

P vs NP Problem

• We have P =< NP. Do we have NP = P? or is there some problem in NP which is outside of P?
• Most people believe P != NP, but very hard to prove
• If NP = P, you can solve any NP problems efficiently
• You can answer questions like "Do we have c Encpk(m) for some messages m?"
• Big Deal?

Unconditional security

• So, P = NP --> such cryptosystem will not be secure
• Then, provably secure cryptosystem -> prrof of P = NP
• This is far beyond cryptography

Reduction

Use reduction between problems

• Given algorithm A for solving problem a, design algorithm B for solving b, which uses A as a subroutine
• Later, solving a -> solving b
• On the other hand, infeasible to solve b -> infeasible to solve a

Reductions everywhere

Reduction became the core methodology in complexity theory

• In a sense, bypassing P vs NP problem
• classifying between problems

Reduction and P.S.

• X : difficult mathematical problem
• E : cryptosystem
• R : polytime reduction for solving X, using an
• E can be attacked efficiently -> X can be solved efficiently
• Contrapositive : X cannot be solved efficiently -> E cannot be attacked efficienty
• The trust in the hardness of X is transferred into the trust in the security of E

More History

• Middle 80s - Early 90s : ad-hoc crypto & provable security went in parallel
• Random Oracle Model : to design practical & somewhat provable schemes
• Bellare & Rogaway : "Random Oracles are Practicals", 1993
• 2000 - : trying to do things in the Standard model

Case study : Cramer-Shoup encryption

Notion of PKE

Provable security of PKE

• 3-step recipe for provable security
• Step 1 : you need to define what you are making
  • Step 1-1 : you need to describe its syntax, or, correctness
  • Step 1-2 : you need to describe its security properties
• Step 2 : describe a concrete scheme realizing above notion
• Step 3 : give a reduction proof

Public-key encryption

Consists of 3 Polynomial algorithms( Gen, Enc, Dec)

• (pk, sk) <- Gen(1^lambda) : given security para lambda, Gen outputs public key & security key pair (pk, sk)
• c <- Encpk(m) : given a public key pk and a plaintext m, Enc outputs corresopnding ciphertext c
• Decsk(c) outputs a message, or it may fail to decrypt

Syntax of PKE

• The algorithm should satisfy the following:
• for any lambda, if key pair (pk, sk) is generated by (pk, sk) <- Gen(1^lambda), then for any plaintext

IND-CCA encryption

• Cramer-Shoup "First practical IND-CCA public key encryption scheme in the standard model"

Semantic Security

Intuitive security we want for an encryption

• "Even if you happen to know c, it won't help you at all in learning anything more about the plaintext m"
• c doesn't leak even one bit of information about m
• This is called semantic security
• Satisfying definition, but hard to use

Indistinguishability

• I'll give you a ciphertext c. This is either encryption of m0, or m1. Guess which is the case
• By default, you can win this game with probability 1/2$12$

Similar to semantic security, or, a special case of semantic security

• You already know that the plaintext is m0, or, m1

Semantic security VS IND

• Clearly, if your encryption scheme satisfies semantic security, then it also satifies IND
• Importantly, the other direction is also true
• 그래서 보편적으로 IND를 암호화 다룰 때 더 많이 씀

IND game

• A : polytime adverary
• IND GAME
• (pk, sk) <- Gen(1^lambda)
• (m0', m1', state) <- A('find', pk)
• b <- {0, 1}; c' <- Encpk(mb')
• b' <- A('guess', c', state) (not allowed to query c')
• A wins IND game if b = b'

Chosen ciphertext attack

Chosen plaintext attack

• The attacker's ability to create a ciphertext for any plaintext chosen by the attacker
• Obvious in PKE

Chosen ciphertext attack

• The attacker's ability to obtain decryption of any ciphertext chosen by the attacker
• IND-CCA : even against such powerful attacker, any ciphertext which is untouched by the attacker is still IND-secure

IND-CCA Justification?

Security assumption

Diffie-Hellman

• G : a group of prime order p
• g (- G : uniform random
• Assume discrete logarithm is hard on G : given g^a
• If you know g, g^a, and b (- Zp, then easy to compute gab=(ga)b$g^{ab}{g}^a{}^b$

Decisioin Diffie-Hellman

DDH Problem

DDH assumption : alternatively

DDH game

• b <- {0, 1}
• If b = 0, sample (g1, g2, u1, u2) <- D
• Else, sample (g1, g2, u1, u2) <- R
• b' <- A(g1, g2, u1, u2)
• b = b'

Collision-resistant hashing

• one more ingredient : hash function
• A hash function H maps elements in a large domain to a small, fixed size codomain
• Naturally, there should be lots of collisions : a pair (x, y) where H(x) = H(y) but x!=y$xy$
• H is collision-resistent, if it is computationally hard to actually find a collision
• 계산 자원에 제약이 주어지는 상황에서는 찾아내는 것이 불가능

Key generation

• Choose G with prime order p according to security parameter
• Choose g1,g2<−G$g_1{g}_{2}G$ : uniform random
• Choose x1,x2,y1,y2,z<−Zp$x1x_2{y}_1{y}_{2}z{Z}_p$: uniform random
• c=g1x1g2x2,d=g1y1g2y2,h=g1z$c{g_1}^{x_1}{g_2}^{x_2}d{g_1}^{y_1}{g_2}^{y_2}h{g_1}^z$

Encryption & Decryption

• (사정상 생략)

IND-CPA security of Cramer-Shoup

IND-CAP security

• Cramer-Shoup is IND-CPA, if DDH assumption holds

IND-CPA reduction proof

Basic idea

• B is DDH solver, so it receives a tuple t=(g1,g2,u1,u2)$t{g}_1{g}_2{u}_1{u}_2$
• B wants to find out if this tuple is a DDH tuple(from D), or a random tuple (from R)
• B simulates the IND-CPA game environment of A

How to determine t using A?

• B's simulation should at
• B will use this tuple t to create challenge ciphertext c∗$c^{}$ for A
• c∗=(u1,u2,u1zmb,u1x1+y1au2x1+y1a)where,a=H(u1,u2,u1z)$c^{}{u}_1{u}_2{u_1}^z{m}_b{u_1}^{x_1{y}_{1}a}{u_2}^{x_1{y}_{1}a}whereaH{u}_1{u}_2{u_1}^z$
• If t is from D, then c∗$c^{}$ is the same as correctly created
• On the other hand, if t is from R, then c∗$c^{}$ is a fake encryption for mb∗${m_b}^{}$
• c∗=(u1,u2,u1zmb,u1x1+y1au2x1+y1a)$c^{}{u}_1{u}_2{u_1}^z{m}_b{u_1}^{x_1{y}_{1}a}{u_2}^{x_1{y}_{1}a}$
• claim : from A' is point of view, u1z${u_1}^z$ is uniform random
• If so, u1zmb${u_1}^z{m}_b$ is also uniform random : it can be anything in G equally likely : no matter what b is
• In that case, A can win the fake IND-CPA game with prob. 1/2
• c∗=(u1=g1r,u2=g2r′,v=u1x1+y1au2x1+y1a)$c^{}{u}_1{g_1}^r{u}_2{g_2}^{r^{}}v{u_1}^{x_1{y}_{1}a}{u_2}^{x_1{y}_{1}a}$
• (이하 생략. PPT 참조 바람.)

Bypassing the problem

• B will simulate IND-CPA game, but generating a fake pk
• Choose x1,x2,y1,y2,z1,z2<−Zp$x_1{x}_2{y}_1{y}_2{z}_1{z}_2{Z}_p$ : uniform random

• compute c=g1x1g2x2,d=g1y1g2y2$c{g_1}^{x_1}{g_2}^{x_2}d{g_1}^{y_1}{g_2}^{y_2}$

• Claim : this modification is completely invisible to A

Reassessing the situation

• B will use tuple t to create challenge ciphertext c∗$c^{}$ for A
• c∗=(u1,u2,u1z1u2z2mb,u1x1+y1au2x1+y1a)where,a=H(u1,u2,u1z1u2z2)$c^{}{u}_1{u}_2{u_1}^{z_1}{u_2}^{z_2}{m}_b{u_1}^{x_1{y}_{1}a}{u_2}^{x_1{y}_{1}a}whereaH{u}_1{u}_2{u_1}^{z_1}{u_2}^{z_2}$

Uniform randomness

Going to IND-CCA