Introduction to Security Reduction(3)
강의를 듣고 정리한 것이 아닌 ppt만 참고하여 내용을 정리한 것입니다.
SnP 연구실 오동환 선배님의 도움을 받아 작성되었습니다.
Lecture 3 : Preliminaries
이번 포스팅은 3장에 대해서 설명하려고 한다.
Outline은 아래와 같다.
1. Preliminaries
■ Computational and Decisional
우리는 컴퓨터로 많은 문제를 해결합니다. 예를 들어서 프로그래머스에서도 문제를 풀 때 컴퓨터로 문제를 푸는데요. 그러면 컴퓨터로 푸는 ‘문제’ 라는건 무엇일까요?
A computing problem defined over a methematical primitive is a mathematical object representing certain questions and answers.
위에 나와있는 내용을 제가 이해한 걸로는 “어떠한 computing problem을 푼다고 하면 거기에 맞는 question(input)과, 그에 맞는 answer(output)으로 나타낸다.” 입니다.
이러한 computing problem은 question을 instance라고 하고 answer를 solution이라고 했을 때, instance와 solution의 쌍 (x, y)를 무한개, 그리고 cryptography에서는 같은 길이인 x에 대한 쌍들만 고려한다고 합니다.
이렇게 computing problem를 풀기위해서 알고리즘(algorithm)을 제안하는데요. 알고리즘이란 무엇일까요?
어떤 문제를 해결하는 방법을 컴퓨터가 이해할 수 있는 단계로 풀어서 기술한 것
컴퓨터가 이해할 수 있는 단계는 CPU의 명령어 정도로, 어떤 문제를 풀기 위해서는 알고리즘 여러 단계를 거쳐야할 수 있습니다. 이때 어떤 입력에 대해서 알고리즘이 거친 단계의 수가 알고리즘의 수행 시간과 대응하다고 할 수 있습니다. 왜냐하면 입력의 크기가 커지면 그만큼 알고리즘이 거치는 단계의 수가 많아지니까 수행하는 시간도 당연히 늘어나게 됩니다.
PPT에 적혀있는 마지막 글을 보면 computing problems은 computational problems + decisional problems라고 되어있습니다.
computational problem은 problem instance, 문제 x에 대한 solution y가 large space에서 나타냅니다. 예를 들어서 최대 space size는 $2^3$ 입니다. 예를 들어서 x문제에 대한 답이 011이면(컴퓨터는 0,1로만 표현하므로) 최대 $2^3$ 임을 확인할 수 있습니다.
CDH(Computational Diffie-Hellman) problem은 instsance(문제) $x = ( g, g^a, g^b) ∈ \mathbb{G}$ 가 주어졌을 때, 이 3개만 보고 $g^{ab}$ 가 되는 $y$를 계산해서 구하는 것입니다. $y$를 계산해서 구하는 것이기 때문에 computational이라고 말하며, computational problem은 computational complexity에서 serach problem이라고도 불린다고 합니다.
Decisional Problem은 problem instance x에 대한 solution y가 2개의 답변만 있는 집합 {0,1}으로 나타냅니다. 문제(입력)가 True인지 False인지만 따지는 것으로, True이면 $y=1$ 이고 False이면 $y=0$ 이 됩니다.
DDH(Decisional Diffie-Hellman) problem은 instsance(문제) $x = ( g, g^a, g^b, z) ∈ \mathbb{G}$ 가 주어졌을 때, 이 4개만 보고 $g^{ab}$ 가 되는 $y$를 계산해서 $z = y$ 이면 1을 return하고 $z\neq y$ 이면 0을 return합니다.
모든 true instance들을 포함하는 set을 formal language L이라고 하고 Decisional problem은 x가 L에 속한 것인지 속하지 않은 것인지 결정하는 것이라고 합니다.
■ Deterministic and Probabilistic
이제 Deterministic과 Probabilistic에 대해서 살펴보는데, 모든 알고리즘은 이 두가지로 분류할 수 있습니다.
Deterministic algorithm은 동일한 input에 항상 같은 output이 나오게 하는 알고리즘이고
Probabilistic algorithm은 동일한 input에 항상 다른 output이 나오게 하는 알고리즙입니다.
Probabilistic algorithm이 문제를 푸는데 Deterministic algorithm보다 더 효율적이라고 합니다. 그리고 denote by $(t, \epsilon)$ 은 success probability $\epsilon$ 으로 time $t$ 안에 correct result를 return하는 알고리즘입니다.
cryptography에서는 알고리즘을 위에 ppt와 같이 분류된다고 합니다. 이 부분은 security reduction을 이해하기 위한 dummy concept이므로 가볍게 넘어가겠습니다.
■ Polynomial and Exponential
이 부분에서는 PPT8를 보기 전에 PPT9페이지를 먼저 보겠습니다.
앞에서 이야기한 것 중에 아래와 같은 말이 있었습니다.
문제의 크기가 커지면 그만큼 수행 시간이 늘어난다.
Cryptogrpahy에서 우리는 time cost 즉, 문제를 푸는데 걸리는 시간을 고려해서 polynomial time과 exponential time도 고려합니다.
여기서 저는 모든 사람들은 문제를 빨리 풀고 싶어하잖아요. 효율적인걸 굉장히 따지는데,, 그렇게 때문에 time cost를 고려한다라고 이해했습니다.
이어서 보면 polynomial time은 polynomial speed로 정확히 이해해야 한다고 되어있습니다.
Polynomial time should be exactly understood as “polynomial speed”.
그러니까 $\lambda$ (람다)가 커지는 속도에 따라 푸는데 걸리는 시간이 어느정도의 속도로 늘어나는지에 대한 것으로 ppt8로 돌아가면,,
Polynomial쪽에 나와있는 수식을 보면, $c·\lambda^k$ 이러한 형태로 커지는 function이면 polynomial function이라고 하겠다. 의 의미입니다. $c·\lambda^k$ 이 형태가 polynomial이니까 $\lambda$가 polynomial하게 커지겠죠? 그래서 Polynomial이고,
Exponential쪽은 $2^{c·\lambda}$ 이러한 형태로, $\lambda$가 지수에 있기 때문에 $\lambda$가 커지면 지수함수로 엄청 빠르게 커지겠죠? 그래서 exponential이라고 합니다.
정리해보면 $\lambda$에 대해서 문제를 푸는데 걸리는 시간이라고 했으니까 Polynomial speed는 아래와 같은 문제를 푸는 시간이 polynomial하게 늘어나는 것이고
\[f(\lambda) \le c·\lambda^k\]Exponential speed는 아래와 같은 문제를 푸는 시간이 polynomial하게 늘어나지 않는다, exponential하게 늘어난다. 라고 합니다.
\[2^{c·\lambda} \le f(\lambda)\]이런 computational complexity는 different definition을 가지는데 암호학에서는 이렇게 정의한다고 합니다. 그럼 이제 다음으로 넘어가볼까요.
■ Negl. and Non-Negl.
이번에는 negligible과 non-nengligible인데요. negligible의 뜻이 ‘무시해도 될 정도의’ 입니다.
그래서 본문으로 들어가면 첫 번째 내용이 security parameter인 $\lambda$가 neg하려면, 일단 $f(\lambda)$가 exponential하게 늘어난다고 해보면 $\lambda$가 커질수록 $f(\lambda)$가 빠르게 커진다는 사실을 앞부분에서 확인했습니다. 그렇다면 $f(\lambda)$는 어떠한 polynomial로도, 어떤 super-polynomial을 가져와도, 이 $f(\lambda)$ 는 polynomial로 bound할 수 없습니다.
그런데 수식을 보면
\[negl(\lambda) = \frac{1}{f(\lambda)}\]$f(\lambda)$ 가 분모에 있으니까 $\lambda$가 커지면 커질수록 neg function은 더 작아지겠죠? 그래서 엄청작아지면 negligible하다~라고 할 수 있습니다.
그런데 $non-neg(\lambda)$에 있는 $f(\lambda)$가 polynomial이면 생각보다 작아지지 않는 것입니다. 우리의 adversary는 보통 polynomial time의 adversary이기 때문에 adversary가 어떤식으로 잘,,무슨 방법을 써서 맞출 수 있는 확률이 있을 수 있으니까 무시하기엔 좀 큰 확률이다~ 라고 할 수 있습니다.
그래서 이 2개의 컨셉은 value에 대한 것이 아니라 speed에 대한 것임을 알 수 있습니다 .
■ Probability and Advantage
Probability는 사건이 발생할 가능성을 측정하는 것이고 Event는 computing problem에서는 주어진 문제에 대한 답을 return, breaking a scheme은 successful attack을 return하는 것입니다.
Probabiliy는 다양한 범위를 가지고 있는데요, hard problem을 푸는 것에 대한 예시로 Digital Signature를 먼저 보겠습니다.
$Pr[Win_{sig}]$는 adversary가 valid signature를 successfully forge할 확률입니다. 그래서 아래와 같은 범위로 확인할 수 있습니다.
\[0 \le Pr[Win_{sig}] \le 1\]이번에는 secure scheme을 깨는 것에 대한 예시로 Encryption을 보는데요. $Pr[Win_{Enc}]$는 encryption 모델에서 indistinguishability security model에서 message를 correctly guess할 확률입니다. indistinguishability security model이라는 것은 ppt 왼쪽 아래에서 보면, challenger랑 adversary가 있을 때 adversary가 $m_0, m_1$를 가지고 있고 2개를 다 challenger한테 보냅니다. $m_0, m_1$을 받은 challenger는 2개 중 한 개를 랜덤하게 뽑아서 encryption을 합니다. adversary가 encryption한 것을 보냈을 때 adversary가 $m_0$를 encryption한 것인지 $m_1$을 encryption한 것인지를 구분할 수 있냐 없냐, 그런데 adversary는 구분할 수 있는 확률이 neg하니까 secure하다~ 이런 흐름입니다. 그래서 0 또는 1이니까 어떻게 찍어도 $\frac{1}{2}$의 확률이잖아요. 그래서 여기서는 아래와 같은 범위로 확인할 수 있습니다.
\[\frac{1}{2} \le Pr[Win_{Enc}] \le 1.\]
$Pr[Win_{D}]$는 앞에서 봤던 DDH 문제에서 target Z를 correctly guess할 확률입니다. 그래서 이 ppt에 대한 내용은 위에서 설명한 내용과 비슷하므로 생략하도록 하겠습니다.
이번에는 Advantage에 대한 내용입니다. 제가 아는 Advantage라는건 “Adversary가 맞출 확률”입니다. 더 정확히 이야기하면, 맞출 확률에서 잘못 맞출 확률을 뺀 값이 advantage입니다.
Advantage = 맞출 확률 - 잘못 맞출 확률을 뺀 값
동전으로 예를 들면, Adversary가 동전을 던졌을 때 앞면이 나오면 1이라고 하고 뒷면이 나오면 0이라고 하겠습니다. 그러면 adversary가 동전이 앞면이 나왔을 때 1이라고 할 확률(맞출 확률)과 동전이 뒷면이 나왔을때 1이라고 할 확률(잘못 맞출 확률)이 둘 다 $\frac{1}{2}$이라서 이때의 adversary의 advantage는 0이 됩니다. 그러면 이 advantage는 0이니까 의미가 없겠죠? 그런데 만약에 adversary가 어떤 좋은(?) 능력이 있어서 앞면과 뒷면을 구분할 수 있다면, 이번에는 앞면이 나왔을 때 1이라고 할 확률은 1이고 뒷면이 나왔을 때 1이라고 할 확률은 0이 되니까 advantage는 1이 됩니다.
그래서 advantage는 0과 1사이의 값을 가지고 크면 클수록 맞출 확률이 높은 것입니다.
이 페이지에서는 위에 나와있는 글을 보기 전에 아래 부분을 먼저 보겠습니다.
만약에 $P_{ideal}$이 non-negligible이면 우리는 advantage를 아래와 같이 정의한다고 합니다.
\[Advantage = Probability of Successful Attack - P_{ideal}\]그리고 이번에는 만약에 $P_{ideal}$이 negligible하다면 우리는 advantage를 아래와 같이 정의한다고 합니다.
\[Advantage = Probability of Successful Attack\]여기서 $P_{ideal}$이 neg하니까 뒤에 붙어있어도 의미가 없잖아요? 그래서 위와 같은 형태구나~라고 생각하고 위에 글을 보겠습니다.
$P_{ideal}$이 무엇인지 보면 베이스로 쓰이는 secure하다라고 증명되어있는 scheme을 깰 최대 확률 또는 어려운 문제를 풀 최대 확률을 $P_{ideal}$이라고 합니다. 그러면 예를 들어서 내 스킴이 있고 그 아래에 베이스로 쓴 secure하다고 증명된 secure scheme이 있을 때, ($P_{ideal}$이 secure scheme을 깰 확률인데) $P_{ideal}$이 non-neg하다면 이 $P_{ideal}$이 깨져서 내 스킴이 깨질 확률이 있을 수 있습니다. 그러면 이건 내 스킴의 잘못이 아니니까 $P_{ideal}$만큼은 빼겠다.라는 것입니다. 그래서 아래와 같이 Advantage에 $- p_{ideal}$이 있는 것입니다.
그런데 $P_{ideal}$이 neg하다면(그만큼 안전하다면), 내 scheme이 깨질 확률은 이 자체라는 것입니다. 그래서 아래와 같이 Advantage를 나타내고 있습니다.
\[Advantage = Probability of Successful Attack\]
maximal advantage는 다를 수 있고 definition과 관련이 있습니다. 예를 들어서 ppt와 같이 2가지로 define을 할 수 있습니다. 하지만 우리는 이런 maximal advantage를 신경쓰는 것이 아니라 오로지 그냥 advantage가 neg인지 non-neg인지를 신경쓴다고 합니다. 그리고 maximum이 1인 advantage definition(1번째 수식)을 권장한다고 합니다.
그리고 Advantage는 아래의 condition이 hold일때 잘 define됐다고 하는데요.
t polynomial time안에 모든 adversary가 스킴을 깨거나 문제를 푸는 것에 대해서 neg adv $\epsilon$를 가진다면 스킴은 secure하고 문제는 hard하다 라고 합니다.
2. Hard Problem
■ Hardness Definition
이제 2단원의 첫 번째 Hardness Definition에서 Computational Hardness를 먼저 보겠습니다.
$x$를 computational problem 중 random instance라고 했을 때, Adversary가 probabilistic algorithm을 polynomial time안에 풀 확률이 neg하다면 우리는 이 computational problem을 hard하다 라고 말합니다.
Decisional Hardness는 위와 비슷한 내용으로 생략하도록 하겠습니다.
hard problem과 hardness assumption의 concept은 equivalent하지만 slightly different하다고 합니다. ppt 아래에 제가 작성한 부분을 먼저 보겠습니다.
DL과 같은 hard problem을 가져다가 암호 scheme을 만듭니다(예. Schnorr). 이렇게 하는 이유가 hard problem은 구하기 어려운 문제니까 이 어려운 문제를 가져와서 우리의 scheme을 만들게 되면 우리의 scheme도 어려우니까 못 풀 것이다! 안전하다! 라는 것을 보여주는 것입니다. 그래서 hard problem을 못 구한다는 가정으로 우리의 scheme이 안전하다라는 것을 증명할 때, 만약 우리의 scheme이 secure하지 않다면 DL도 secure하지 않다. 그런데 DL은 안전하다니까 결국 우리의 scheme도 안전하다. 라는 reduction 방식으로 증명을 합니다.
그래서 이제 위에 글을 보면 “proposed scheme을 깨는 것이 근본적인 hard problem을 푸는 것을 의미한다.” -> 앞에서 우리의 scheme이 secure하지 않다면 DL도 secure하지 않다 라는 의미는 결국 우리의 스킴을 깨는 것이 근본적인 hard problem(DL)을 푸는거겠죠?
그러므로 “스킴은 hardness assumption 아래에 secure하다.” -> hardness assumption이 ‘hard problem을 구하기 어렵다는 가정’의 의미인데요. 가정에서 hard problem이 안전하니 결국 우리의 scheme도 안전하다고 위에서 말했으니 이 부분도 이해가 될 것입니다.
Harness assumption은 weak assumption과 strong assumption이 있는데 Weak와 Strong은 problem과 관련있는 것이 아니라 strength of the hardness와 관련이 있습니다.
Weak assumption은 몇 가지의 condition이 hold일때 computing problem이 hard이고 Strong assumption은 많은 condition이 hold일때 computing problem이 hard하다고 합니다.
앞에서 CDH와 DDH 문제가 있었는데요. 둘 중에 어떤 문제가 더 어렵나요? 당연히 CDH 문제가 더 어렵고 DDH 문제가 더 쉽습니다. 그러면 이 DDH scheme을 만들려면 강하게 믿어야지만 안전한 것이잖아요. 그래서 더 strong assumption이 필요한 것으로 CDH는 strong assumption에 해당합니다. 다시 말해서 DDH가 더 쉬운 문제이므로 더 쉽게 깨지니까 더 안깨질 것이라는 더 많은 strong한 가정이 필요한 것입니다.
CDH같은 경우는 문제가 더 어렵기 때문에 weak assumption으로도 가능한 것입니다. 이것이 더 strong security를 보장하겠죠?
사실..저는..아직도..헷갈립니다..이것이 맞는지요…흑극극
그래서 우리한테 좋은 것은 Strong model에 weak assumption이다~~~라는 것입니다.
■ Examples
예시들이 ppt에 더 많이 나와있는데 생략하겠습니다.
■ Hardness Analysis
이 부분은 가볍게 읽고 넘어가시면 될 것 같습니다.
이 페이지에서는 우리는 computing problem A의 hardness를 증명할 것이라고 가정했을 때 2가지의 일반적인 방법이 있다고 합니다.
첫 번째가 Reduction이고 두 번째가 Weak Computational Model인데요.
(1)Reduction
- Reduction
Scheme이 안전하다는 것을 보이기 위해 보이는 것으로, Scheme을 깨는 attacker가 존재한다면 가정을 깨는 attacker가 존재하게 된다.
그런데 가정은 computationally 풀기 어렵다는 가정이 있기 때문에 모순이 되고, 결국 scheme이 안전함을 증명하게 되는 증명 기법입니다.
(2)Weak Computational Model
- Weak Computational Model
이 방법은 직접적으로 계산을 할 수 없다는 것을 증명하는 방법으로, generic group model에서 어렵다는 것을 증명합니다. Standard computational model은 turing machine인데 여기서 증명이 안되니까 weak로 내려와서 증명하는 것입니다.
여기서 generic group model이라는 것은 나중에 포스팅할 예정이지만 간단하게 먼저 이야기하자면, attacker가 직접 연산을 할 수 없습니다. 다시 말해서, 직접 연산할 수 없는 제한된 능력을 가진 attacker이기 때문에 oracle에 query를 보내야만 info를 얻을 수 있습니다.
그리고 또 다른 special한 방법으로 membership proof가 있는데 이 부분은 별로 중요하지 않아서 넘어가도록 하겠습니다.
3. Secure Scheme
■ Security Parameter
Lecture3에서의 마지막 3단원을 보겠습니다. 먼저 Security Parameter는 또 다시 이야기가 나오는데요.
문제의 크기가 커지면 그만큼 수행 시간이 늘어난다.
그래서 문제, security parameter $\lambda$를 길게 할수록 어렵고 시간이 늘어나니까, 문제를 얼마나 어렵게 할지 이 $\lambda$로 결정을 합니다.
■ Security Level
Security level은 스킴을 깨거나 문제를 푸는데 strength of an adversary임을 의미한다고 합니다. 그러면서 스킴을 깨거나 문제를 푸는데 time cost로도 볼 수 있다고 하는데, strength of an adversary라는게 “문제를 푸는데 드는 수고(문제를 깨기 위해 필요한 공격량)”이라고 이해하면 쉬울 것 같습니다. 즉 security level은 문제를 푸는데 걸리는 양으로 적어도 ~~이만큼 일해야 하니까 걸리는 시간, time cost라고 볼 수 있는 것입니다.
그래서 아래를 보면 2/3 성공 확률로 스킴을 깨거나 문제를 풀기 위해서 adversary가 $2^k$만큼 step/operation을 한다면 스킴과 문제는 k-bit의 security를 가진다고 말합니다.
그래서 이 부분은 앞에 내용을 수식으로 표현한 것입니다.
이제 여기서 Upper bound와 Lower bound가 나오는데, 저는 여기서 base로 쓰이는 hard problem이나 secure scheme을 기준으로 잡고 이해했습니다.
그래서 이 PPT에서의 Upper bound를 보면,
hard problem인 DL 문제를 푸는 것이 확실히 scheme을 깰 수 있다. 라는건 다시 말해서 DL을 풀면 내 스킴도 깨진다? 그럼 DL이 더 어렵다는 의미잖아요. 그러면 당연히 security level은 hard problem인 DL이 더 높겠죠?
그래서 아래와 같이 말할 수 있습니다.
The discrete log hardness is the upper bound security level.
그런데 이번에 Lower Bound를 보면,
스킴을 깨는 것이 hard problem A를 깨는 것을 의미한다고 가정한다고 되어있습니다. 그럼 여기서는 스킴이 더 어렵다는 의미잖아요.
그러면 아까 제가 말한대로 hard problem을 기준으로 봤을 때, 이번에는 security level이 더 높은 쪽은 hard problem쪽이 아니라 scheme이 됩니다.
그래서 아래와 같이 말할 수 있습니다.
The hardness of problem A is the lower bound security of scheme.
이 부분은 정리한 것으로 넘어가도록 하겠습니다.
■ Definition of Security
마지막으로 Definition of Security를 보겠습니다.
security model은 adversary가 무엇을 아는지 defin하는 것입니다.
attacker가 있다고 했을 때, 그 attacker가 어느정도까지 능력을 가진 attacker인지 정의를 합니다.(attacker도 다 능력이 다르기 때문에)
그래서 4가지로 볼 수 있는데요.
- Ciphertext-only attack
- attacker가 CT에 대한 정보만 얻을 수 있다.
- Known-plaintext attack
- 주어진 PT에 대한 CT를 알고 있다.
- Chosen-plaintext attack
- attacker가 원하는 PT에 대해서 CT를 얻을 수 있다. 즉, encryption oracle을 가진 attacker를 가정한다.
- Chosen-ciphertext attack
- 원하는 PT에 대해서 CT를 얻고, 원하는 CT에 대해서 PT를 얻을 수 있다. 즉, encryption oracle과 decryption oracle을 모두 가진다.
이렇게 attacker의 능력이 다 다르기 때문에 어떤 security model인지에 따라서 스킴을 깨는 hardness도 다릅니다. 그래서 scheme의 security level은 security model과 연관되어있다고 말할 수 있고, Security definition은 security model을 분명하게 define해야 합니다.
이 2페이지는 읽어보면 될 것 같습니다.
이렇게 Lecture3가 끝이 났습니다. 끝~!~!~!
댓글남기기