[암호학] Approximate Common Divisor Problem

한국인이면 제발 덴버 응원합시다

들어가보자

드림핵의 AbCD 문제를 풀고 풀이를 남겼을 때, 도대체 제목이 무슨뜻인지 모르겠다고 했었다.

그 게시물의 댓글로 해당문제가 ACD 문제(Approximate Common Divisor)에 대한 것임을 알 수 있었다.

그리고 이러한 문제에 대한 알고리즘을 소개하는 논문까지 알려주셨는데, 일단은 ACD가 무엇인지 알아보자.

참고로 안내 받은 논문은 오클랜드 대학에서 낸 'Algorithms for the Approximate Common Divisor Problem' 논문이다.

(아 나도 논문 내고 싶다)

일단은 이 논문을 차근차근 읽어보면서 공부를 해보겠다.라고 시작하고 작업을 시작했으나.. 논문 내용이 조금 많아서 이렇게 번역을 하면서 읽는 것이 상당히 시간이 많이 걸렸다.

그래서 ACD에 대한 설명을 보던 중간부터는 각자 공부해보기로하자 ^^

Abstract

많은 동형 암호 스킴의 안전성은 ACD 문제의 난이도에 의해 결정된다.
이 논문에서 우리는 lattice(격자, 래티스)를 이용한 ACD 문제 알고리즘을 리뷰하고 비교한다.
특히 우리는 Cohn과 Heninger에 의해 연구된 simultaneous Diophantine approximation method, orthogonal lattice method, method based on multicariate polynomials, Coppersmith's algorithm에 집중한다.
우리의 주 목적은 multivariate polynomial에 의한 접근을 다른 방식들과 비교하는 것이다.
그 결과로 multivariate polynomial 방법이 orthogonal lattice algorithm에 비해 실용적인 암호 분석에 있어서 우세하지 않음을 확인할 수 있었다.

또다른 기여는 ACD 샘플에 대한 샘플 확대 아이디어를 고안한 것과 LPN(Learning Parity with Noise)를 위한 BKW(Blum-Kalai-Wasserman) 알고리즘과 비슷한 전저리 알고리즘을 제안한 것이다.
다른 알고리즘과 달린 BKW 알고리즘에 대해서는 래티스 알고리즘에서 개선이 되지 않은 이유를 설명한다.

1. Introduciton

ACD 문제는 Howgrave-Graham에 의해서 처음 연구[HG01]되었다.
ACD에 대한 관심은 van Dijk(반다이크..?), Gentry, Halevi, Vaikuntanathan의 동형암호 스킴[DGHV10]과 그 파생[CMNT11, CNT12, CS15]에 의해서 증가했다.
이 계산 문제는 에러 값으로 상대적으로 작은 $r_i$를 설정하여 $x_i = pq_i + r_i$ 형태의 많은 샘플을 주었을 때, 비밀 값인 정수 $p$를 구하는 것이다.
좀 더 정확하게, $p$는 $\eta$ 비트의 홀수의 소수이며, $x_i$는 $\gamma$ 비트이고, $r_i$는 $\rho$ 비트이다.
이때 $\rho$는 $\eta$보다 훨씬 작은 값이다.

[HG01], [DGHV10]에서는 orthogonal lattices 방법이나 Coppersmith's method를 이용한 많은 가능한 레티스 공격을 모사한다.
더 나아간 암호분석 작업은 [CN12, CH13, CNT12, DT14]에서 진행되었다.
이 논문은 알려진 ACD 문제에 대한 레티스 알고리즘들을 조사하고 비교했다.
최근에 제안된 ACD 문제의 변종들인 [CCK+13, Lep14, CS15]들을 연구했으며, 이것들은 기존의 ACD보다 좋은 보안을 제공할 수 있다는 것을 확인했다.
우리의 주 발견은 실용적 암호 분석에서 orthogonal lattice approach가 multivariate polynomial approach보다 우수하다는 것이다.

우리는 LPN를 위한 Blum-Kalai-Wasserman 알고리즘으로부터 전처리 아이디어를 제안하게 되었으며, LPN과 LWE(Learning with Errors) 작업으로부터 샘플 확대 아이디어를 제안하게 되었다.

이 논문에서 우리는 Chen과 Nguyen, Coron, Naccache와 Tibouchi, Lee와 Seo에 의해 제안된 $r_i$에 대한 전수조사[CN12, CNT12, LS14]를 고려하지 않는다.
그런 알고리즘은 기존의 ACD 문제에서 중요했으나 Cheon-Stehle에 의한 파생에서는 중요성이 감소했기 때문이다.

나는 AbCD 문제를 전수조사로 풀었다... 

2. Background and Notation

이 논문에서는 standard notation(표준 표기)를 사용한다.
$\ll, \gg$ 기호는 단지 아주 작음이나 아주 큼을 나타낸다.

2.1 Statement of the approximate common divisor problems

ACD 문제에는 최소 4개의 버전이 존재한다.
이 것에 대해서 정확하게 정의한다.

$\gamma, \eta, \rho \in \N$이다. $p$를 $\eta$ 비트의 홀수 소수라고 하자. 이때 $p$는 아래의 대소관계를 만족한다.
$2^{\eta-1} < p < 2^{\eta}$

사실 $p$가 꼭 소수여야 하는 것은 아니다. [DGHV10]과 같은 파생에서는 확실히 소수가 아니다. $D_{\gamma, \rho}(p)$를 아래와 같이 정의한다.

$D_{\gamma, \rho}(p) = {pq + r | q \leftarrow \Z \cap [0,2^{\gamma}/p), r \leftarrow \Z \cap (-2^{\rho}, 2^{\rho})}$

실제로 $\rho$는 $\eta$보다 훨씬 작고 모든 샘플 $D_{\gamma, \rho}(p)$는 $x_i < 2^{\gamma}$를 만족시킬 가능성이 아주 크다.
그리고 $t$개의 충분한 샘플 사이즈를 만들었을 때, $2^{/gamma-1}<x_i<2^{\gamma}$를 만족하는 $i$가 적어도 하나 존재한다.

정의 1 위와 같이 표기할 때, ACD 문제는 : $D_{\gamma, \rho}(p)$에 의한 $x_i$ 샘플이 다항적으로 많을 때, $p$를 계산하는 것이다.
Partial approximate common divisor 문제는 : $D_{\gamma, \rho}(p)$에 의한 $x_i$ 샘플이 다항적으로 많고, $q_0$가 여느 $q$와 동일한 범위에서 선택되어서 $x_0 = pq_0$ 계산으로 $x_0$를 만들 때, $p$를 계산하는 것이다.

PACD 문제가 정확하게 AbCD에 대한 문제이다. 

앞에서 예고한 대로... 이제 성장해서 만나자!