Introduction to Security Reduction(4)
강의를 듣고 정리한 것이 아닌 ppt만 참고하여 내용을 정리한 것입니다.
SnP 연구실 김종호 선배님의 도움을 받아 작성되었습니다.
Lecture 4 : Entry to Security Reduction
이번 포스팅은 Security Reduction을 실제로 어떻게 할 것인지에 대한 내용이다.
outline은 아래와 같다.
1. Reduction in Computational Complexity
1장에서는 Computational Complexity에서 Reduction이 무엇인지에 대해서 이야기하려고 한다.
■ Proof by Contradiction
computational complexity에서 추가적인 가정없이 “풀고자하는 computing problem B를 푸는 것은 어렵다”라는 것을 증명하기엔 불가능하다. 그래서 우리는 어떤 computing problem이 어렵다는 추가적인 가정으로 문제 B의 hardness를 증명할 수 있다.
다시 말해서 어떤 hard problem이 어렵다는 것을 이용해서 우리가 풀고자 하는 문제도 이만큼 어렵다는 것을 말할건데, **이러한 proof process를 reduction이라고 부르며 "모순에 의한 증명"이라고 한다.**
네모 박스에 있는 것은 1,3 포스팅에서도 계속 이야기했던 Reduction에 대한 설명이다.
- Reduction이란?
scheme이 안전하다는 것을 보이기 위해 보이는 것으로, scheme을 깨는 attacker가 존재한다면 가정을 깨는 attacker가 존재하게 된다. 그런데 가정은 computationally 풀기 어렵다는 가정이 있기 때문에 모순이 되고, 결국 scheme이 안전함을 증명하게 되는 증명 기법이다.
computing problem A는 어렵다고 알려져있다. 그리고 computing problem B도 어렵다는 것을 증명하고 싶은데, 앞에서 말한 것처럼 추가적인 가정없이 direct하게 어렵다라고 증명하기엔 불가능하다. 그래서 computing problem A가 어렵다는 것을 이용해서 computing problem B도 어렵다고 말할 건데,
만약에 problem B가 쉽다면 우리는 problem A도 또한 쉽다고 증명할 수 있다. 그런데 그렇게되면 문제 A가 어렵다라고 되어있는 가정과 모순이 되기 때문에 결국 문제 B도 어렵다. 라고 설명할 수 있다.
**우리는 이것을 old problem A는 new problem으로 reducible한다.(바뀐다.)라고 말한다.**
■ Reducible
The problem A is reducible to the problem B
reducible하다라는 건 무슨 의미일까요?
ppt에 나와있는걸 보자면
- problem B를 푸는 것은 problem A를 풀 수 있다는 것을 의미한다.
- 우리는 problem instance $x_A$가 problem instance $x_B$로 변환될 수 있다.
- 우리는 problem solution $y_B$가 problem solution $y_A$로 변환될 수 있다.
일단 적혀있는 내용을 그대로 받아드리고 다음 예시를 보며 더 정확히 이해하려고 한다.
Problem A와 problem B가 있을 때, problem A는 problem B로 reducible한다.라는 것을 어떻게 prove할 것인가?
이 내용에 대한 설명은 ppt에 적힌 것으로 대신하고 넘어간다.
그래서 이런걸 problem A가 problem B로 reducible한다. 라고 말할 수 있다.
2. Security Reduction in Cryptography
2장에서는 Cryptography에서 Security Reduction이 무엇을 의미하는지 살펴본다.
앞에서는 problem 2개를 가지고 이야기를 했는데 여기서 security reduction은 어떤 problem이 어떤 scheme에 reducible한다.라고 이야기할 것이다.
■ Security Reduction(Overview)
방금 앞에서 이야기한대로 Security Reduction에서는 Problem is reducible to Scheme이다. 그 아래의 흐름은 앞에서의 흐름과 동일하다.
앞에서 problem instance $x_A$가 problme instance $x_B$를 생성하는데 사용될 수 있다는 것을 봤었다.
이제는 Security Reduction에서 이야기해보면, problem $P$가 proposed scheme으로 reducible하다는 것은 problem instance $x_P$가 scheme을 “simulate”할 때 사용될 수 있다는 것을 의미한다.
즉, simulated scheme을 깬다는 것은 문제 P에 대한 solution을 얻어낼 수 있음을 의미한다.
■ Framework
그래서 이제 전체적인 구조를 보려고 한다.
Security Reduction의 framework를 보면,
우리가 제안하는 scheme을 깰 수 있는 공격자가 있다고 가정할 것이다.
그리고 simulation, solution, analysis가 존재하는데 하나씩 보면 아래와 같다.
-
Simulation
Problem instance $x_P$를 이용한 simulated scheme을 생성하고 adversary와 interaction을 한다.
다시 말해서, 실제로 scheme을 실행하는게 아니라 뭔가 우리 scheme처럼 보이게 만들어주는 것이다. -
Solution
simulated scheme에 대해서 adversary의 공격으로 알게된 solution $y_P$를 추출한다.
-
Analysis
그러면 실제로 이런 공격자가 존재했을 때 hard problem P가 non-neg한 확률로 깨진다는 것을 분석해야 한다.
b284-d9abe87c59b5.png”>
여기서의 설명은 간단하게 말하면,
어떤 scheme을 깨는 adversary가 존재한다면~~하고서 다른 문제로 매핑하는데(다른 문제도 풀 수 있다~라는 식으로), 실제로는 그런 공격자는 존재하지 않으니까 증명해줄 순 없지만! 논리적으로는 분석해서 말해줄 수 있다는 것이다.
이 ppt에서는 크게 중요한 내용이 없어서 이정도만 이해하고 넘어간다.
Security reduction이 어떤식으로 구성되어있는지 본다.
먼저 Real Attack은 실제 scheme을 통해서 adversary가 공격하는 것을 뜻하고 Simulation은 simulated scheme을 가지고 adversary가 공격하는 것을 뜻한다.
그래서 그림을 보면, Real Attack부분에서 adversary와 Real Scheme인 challenger와 interaction을 하며 adversary가 공격을 하는 것이고 오른쪽 Simulation을 보면 real scheme이 아니라 hard problem에 대한 instance를 통해서 simulated scheme인 simulator를 생성해서 adversary와 interaction하고 adversary가 그 simulated schemed을 attack한다. ppt에 나와있는 표를 참고한다.
| Real Scheme | Simulated Scheme |
|---|---|
| Challenger | Simulator |
| Real attack | Simulation |
ppt에 나와있는 설명을 이어서 작성하면 다음과 같다.
-
Real scheme
real scheme은 proposed scheme에서 설명된 scheme algs에 따라 security parameter를 사용하여 생성된 scheme이다.
-
Simulated scheme
simulated scheme은 reduction algs에 따라 기본 hard problem의 random instance로 생성된 scheme이다.
adversary의 관점에서, real scheme과 simulated scheme에 의한 response는 동일하게 보인다, indistinguishable하다.
Indistinguishable이 무엇을 의미하는지 더 자세히 이야기하려고 한다.
Approach 1이랑 Aproach2를 보면, b만 봤을 땐 1에서 온 것인지 2에서 온 것인지 ouput의 distribution에서는 똑같기 때문에 구분할 수가 없다.
결국 정리를 하자면, algs이 Indistinguishable하다는건 output의 distribution이 같으면 된다. attacker라는게, 앞 ppt를 보면, 실제 real attack이라고 하는건 우리가 항상 논문보면 앞에 define을 한다. scheme이 어떤식으로 있을 때 이 attacker가 challenger와의 interaction을 통해 이루어지는 game이고, 이 game에서 advantage(공격자가 이길 확률)가 negligible해야 한다. 라고 왼쪽 그림으로 항상 말한다. 그리고 증명할 땐 오른쪽 그림으로 한다. 즉, 왼쪽으로 근거해서 secure하다라고 정의하고선 증명은 오른쪽으로 한다.
그럼 오른쪽 그림이 왼쪽 그림이랑 같은가?—attacker 입장에선 Indistinguishable하다는 것이다. attacker가 query보내고 response받고 하는데 알고리즘은 못보고 response만 보는데, attacker 입장에선 잘된다면 같다고 인식되는 것이다.
simulation은 내가 reduce를 하려고, 이 scheme이 어떤 문제만큼 어려운 것이다. 라는 것을 증명하려고 simulator를 만든 것이다. 이 simulation은 이 scheme, 예를 들어서 A라는 문제만큼 어렵다.라는게 가능해야하지만 그 문제를 가지고 simulation을 할 수 있는 것이다. reduce되는 문제가 안되면 simulation이 안된다.
여기서 실제 입력이 problem instance이다..얘가 reducible되는 문제이기 때문에,, 이걸 가지고서 원래 scheme과 attacker가 원하는 입력과 결과에 대해서 attacker입장에선 구분이 안되는 input과 output을 줄 수 있다는 것이다.!
이런 security reduction의 목표는 근본적인 hard problem을 풀기 위해 adversary의 attack을 reduce하는 것이다.
3. Evaluation of Security Reduction
3장에서는 Security Reduction을 실제로 할 때 time이나 advantage가 어떻게 되는지에 대해 이야기를 한다.
### ■ Cost and Loss in Reduction
어떤 adversary가 scheme을 깨는데 $(t,\epsilon)$-break하다고 할 때, 근본적인 hard problem을 깨는데 걸리는 시간이 $t’$이다.
일단 $T$는 simulation을 위한 추가 시간인데, 원래 $t$라는 시간이 adversary가 원래 scheme을 깨는데 걸리는 시간이다. 그런데 내가 reduction을 하다보니까 simulation을 하려면 어떤식으로 잘 조작해서 만들어줘야하니까 simulation을 위한 추가적인 시간이 든다. 결국 scheme에 맞춰서 해야되는 추가적인 계산량이 있는 것이다.
그리고 reduction loss에 대한 내용은, 원래 Attacker가 깰 성공할 확률이 1이었는데 reduction을 하다보면,, hard problem을 풀 확률은 마찬가지로 1은 아니고 줄어든다고 가정을 하겠다는 것이다.
일반적으로 항상 simulation을 하기 위한 추가적인 cost가 항상 있고, reduction loss가 없으면 좋은데 보통 하다보면 확률적으로 깨기 때문에 줄어드는 경우가 있다. 그래서! 추가적인 cost나 loss가 없어야 좋은 것이다.
댓글남기기