A Survey on Applications of H-Technique: Revisiting Security Analysis of PRP and PRF

(오류가 있을 가능성이 굉장히 큽니다.)  

1. Introduction 

낯선 키워드가 너무 많다.  

H-technique : $H$는 input $a_i$를 output $b_i$로 올바르게 보내는 키의 갯수를 의미한다. KPA, CPA 등등의 환경에서 $a_i$와 $b_i$가 특정 조건을 만족할 때 H의 upper/lower bound를 알아낼 수 있다. 이를 통해 cryptographic construction $A$와 ideal object $B$가 indistinguishable함을 보일 수 있다. 일단 The “Coefficients H” Technique 논문에서는 여기까지만 이해..  

1.1 
Symmetric-key의 안전성을 증명하는 테크닉  

- Game-Playing Techinique : adversary와 oracle이 일종의 game을 진행하는 방식. ind-cca 이런거랑 비슷한듯  

- Coefficients H-tequenique : 위에 써둠. 여기서는 예시로 uniform random function과 uniform random permutation을 구분해낼 때의 advantage를 예기하고 있음 

- Maurer's random system methodology, Expectation Method, CCoupling Techinuque, $\chi^2$-Method and Hellinger Distance : 패스 

1.2 
이 논문에서 몇가지 construction에 대한 H-technique based proof를 제공할 것이라고 함 

2. Preliminaries

2.1
$[m]$ : $\{1, 2, \cdots, m\}$, $x^q = (x_1, x_2, \cdots, x_q)$, $\{x^q\} = \{x_i : 1 \leq i \leq q\}$.

Binary monoton sequence : $0^i1^{q-i}$

$\mathcal{X}^{(r)} = $ set of all $r$ tuples $x^r \in \mathcal{X}^r$ s.t. $x_i$ are distinct.

$(N)_r = n$ permutation $r$

$(x^q, y^q)$ is function compatible : $x_i = x_j \Rightarrow y_i = y_j$, denote as $x^q \rightsquigarrow y^q$

$(x^q, y^q)$ is permutation compatible : $x_i = x_j \Leftrightarrow y_i = y_j$, denote as $x^q \leftrightsquigarrow y^q$

$(t^q, x^q, y^q)$ is tweakable permutation compatible if $(t_i, x_i) = (t_j, x_j) \Leftrightarrow (t_i, y_i) = (t_j, y_j)$

2.2
유한 집합에 대한 두 확률 함수의 statistical distance는 각 원소에서의 차이의 합 / 2. Corollary 1은 패스

3. Models for Interactive Algorithms

3.1
Input space $\mathcal{X}$, output space $\mathcal{Y}$, $\mathcal{X}\xrightarrow{\text{*}}\mathcal{Y}$은 random coin space $\mathcal{R}$이 있어 $\mathcal{R} \times \mathcal{X}\xrightarrow{}\mathcal{Y}$인 상황을 의미

Random coin space가 singleton이라면(뜻이 잘 이해가 안감..) probabilistic function이 function으로 reduce됨. 뭔가 좀 제대로 이해 못함

key를 random coin처럼 생각하면 input->output 매칭을 probabilistic function으로 생각할 수 있다?

3.2
Joint Response Function : $\mathcal{X}^q \rightarrow \mathcal{Y}^q$ s.t. all random coin $r$, $x^q \rightarrow F(r,x^q)_i$가 $x_{i+1}, \cdots, x_q$에 independent. 즉 k번째의 response $y$는 그 이전의 query에만 영향을 받는다. 즉 공격 대상 알고리즘

Joint Query Function : $\mathcal{Y}^q \rightarrow \mathcal{X}^q$ s.t. all random coin $r$, $y^q \rightarrow A(r,y^q)_i$가 $y_i, \cdots, x_q$에 independent. 즉 k번째의 query $x$는 그 이전의 response에만 영향을 받는다. 즉 공격자

nonadaptive : response에 따라 query가 바뀌지 않음

deterministic : 말 그대로 deterministic

transcript random variable $\tau = (x^q, y^q)$ 정도로만 생각.

Joint Response Function $\mathcal{F}$와 Joint Query Function $\mathcal{A}$에 대해 transcript random variable $\tau(\mathcal{A}^\mathcal{F}) = (X^q, Y^q)$로 정의됨. $\mathcal{A}, \mathcal{F}$에서 random coin이 fix되면 $(x^q, y^q)$ 쌍은 unique함

MBO extension에서 support S는 q번의 쿼리에서 문제가 있는 쿼리는 1, 없는 쿼리는 0임. 한번 문제가 생기면 쭉 문제가 있기에 S는 $0^i1^{q-i}$꼴이고 S가 $0^q$일 때만 good. 이 때 B = 0, 그렇지 않으면 B = 1.

3.3
위쪽 def는 생략, 3.3.1부터

random function이라 함은 확률이 균등하게 꽂히는거, random permutation도 마찬가지로 균등한 확률

식 (4)와 (5)는 tweakable permutation compatible이기 때문에 나오는 식

4 H-Technique Tools

4.1
b는 $\mathcal{F}, \mathcal{G}$ 구분. $\mathcal{F}$에 대해 1을 반환할 확률과 $\mathcal{G}$에 대해 1을 반환할 확률의 차이가 식 (6)에 정의된 delta.

4.2  
sprp와 prp에서 왜 식의 차이가 생기는가 -> sprp의 자체가 adversary가 inverse query 또한 쓸 수 있는 상황임. sprp의 정확한 정의는 나중에 찾아봐야 할듯

4.3
Lemma 4.1에서 내가 참고하지 않을 결과를 전부 $\Omega_{bad}$에 몰아둔 후에 주어진 식처럼 확률을 계산했을 때 그 값이 $1-\epsilon$이라면 advantage의 상한이 $\Omega_{bad}$에 나올 확률 + $\epsilon$이라는 의미. 

4.4
일단 넘어가자

5. Hash-based Constructions

$\mathbb{H} : \mathcal{M} \xrightarrow{\text{*}} \mathcal{X}$은 $m \neq m' \in \mathcal{M}$에 대해 $H(m) = H(m')$일 확률이 $\epsilon$ 이하이면 $\epsilon -universal$이라고 부름

 

5.1

Hash-then-PRF : 말그대로 hash를 거친 후에 random function에 넣음.

 

Hash 함수가 $\epsilon -universal$일 때 q개의 쿼리로 얻을 수 있는 어드벤티지가 $\binom{q}{2} \epsilon$ 이하이다. 대충 보니 collision이 발생하면 구분이 가능할테니 대충 식이 왜 이런지 느낌으로는 알겠는데 우리는 증명을 이해해야 함