Ⅰ.서론

M.Yoshida 등은 유한체 IF상의 2차원 벡터 공간에서 정의되는 벡터 분해 문제(vector decomposition prob­ lem 또는 VDP)라고 불려지는 새로운 계산적으로 어려운 문제와 그 문제의 어려움에 기반한 inseparable multiplex transmission (IMT) 스킴을 제안하였다 〔1, 2〕. 그들은 IMT 스킴의 비분리성을 이용하여 암호학적 데이터(예를 들어 암호문, 서명, 암호학적 키 등) 에 워터마크를 내장시키는 응용 기법을 제공하였다. 현재까지 계산적 Diffie-Hellman 문제 (Computational Diffie- Hellman problem 또는 CDHP)는 어려운 문제로 인정되고 있는데, Yoshida는 그의 논문(⑵에서 2차원 벡터 공간상의 벡터 분해 문제가 어떤 특별한 조건하에서는 1 차원 부분 공간상의 계산적 Diffie- Hellman 문제 (Computational Diffie-Hellman problem)로 변환되는 것을 보였다.

증명 과정을 구체적으로 설명해보면, 1차원 부분 공간상에서의 CDHP는 CDHP의 instaimce로 주어진 벡터를 이용하여 두 쌍의 기저를 생성한 다음, 주어진 벡터에 대해서 생성된 한 쌍의 기저에 대한 벡터 분해를 적용한 후 얻은 결과 벡터에 다시 나머지 쌍의 기저에 대한 벡터 분해를 적용하면 해결되는 것을 증명하였는데, 이것은 2차원 벡터공간상에서의 VDP가 쉽게 해결된다면 2번의 벡터 분해를 통하여 CDHP 문제가 해결됨을 의미하므로, VDP가 최소한 그것의 1차원 벡터 공간상에서의 CDHP보다 어렵다는 것을 의미한다고 말할 수 있다. 또한 Kiyavash와 Duursma는 그들의 논문 1*)에서 VDP가 어려운 문제가 될 수 있는 특별한 조건을 만족하는 타원곡선은 supersingular 곡선만 가능하다는 것과, 또한 supersingular가 아닌 경우로써 그들이 찾아낸 genus 2인 일련의 초타원(hyperelliptic)곡선들이 VDP가 어려운 문제가 될 수 있는 특별한 조건을 만족시키는 것을 보였다. 그러나 우리는 본 논문에서 벡터분해 문제가 어렵다는 사실에 반하는 예를 보여준다. 즉 타원곡선의 어떤 2차원 부분 공간 7 와 그것의 1차원 부분 공간 丫 '이 VDP에서 요구하는 특별한 조건을 만족한다 할지라도 V 에 속하는 벡터들이 ¥ 의 어떤 특정 기저에 관해서는 다항식 시간 안에 분해 될 수 있다는 것을 보여준다. 이것은 VDP가 어떤 기저에 관한 임의의 벡터의 분해에 대해서는 어려운 문제가 될 수 없다는 것을 보여주는 실제 예가 된다. 사실 우리가 위에서 간단히 기술한, M.Yoshida 등''에 의해 VDP가 어렵다는 것을 보여주는 증명은 VDP를 어렵게 하는 in­ stance 의 존재성만을 보여주고 있다. 다시 말하면, 그들의 증명은, 암호학적인 프로토콜에 적용하기 위하여 필요한, 즉 임의로 주어진 기저에 대한 벡터 공간상의 임의의 벡터에 대한 벡터 분해 문제가 어렵게 된다는 사실을 보인 것은 아니기 때문에, 우리가 앞에서 얘기한 것과 같은 예를 찾을 수 있게 된 것이다. 그러나 Duursma와 Kiyavash는 그들의 논문⑶에서, 여기서 우리가 VDP가 어려운 문제라는 것에 대한 반례로 찾은 기저를 VDP를 어렵게 하는 기저로 이용하였다.

다음으로 우리는 주어진 기저에 관련해 임의의 벡터에 대한 VDP를 어렵게 하는 그와 같은 기저의 존재성을 찾아보고 그와 같은 구조의 기저들에 대한 임의의 벡터의 분해는 적어도 CDHP 만큼 어렵다는 것을 증명한다. 즉 벡터 분해 문제가 쉽게 해결되는 기저가 존재하는 반면에 어떤 모양의 기저에 대해서는 VDP를 적어도 CDHP 만큼 어렵게 하는 그런 기저가 존재함을 증명하였다.

이 논문은 다음과 같이 구성된다. 단원 II에서는 논문 1, 기에서 정의된 VDP와 CDHP에 관한 정의와 관련된 결과를 정리한다. 단원 III에서는 어떤 2차원 벡터공간 V 가 M.Yoshida 등이 제안한 특별한 조건을 만족한다 할지라도, 어떤 특정한 기저에 관해서는 V 에속하는 임의의 벡터에 대하여 약간의 계산을 통하여 그 기저에 관한 벡터 분해가 다항식 시간 안에 해결 될 수 있다는 것을 증명한다. 또한 단원 IV에서는 VDP를 어렵게 하는 기저를 찾아보고 그와 같은 기저에 관련한 임의의 벡터들은 모두 VDP의 strong instance가 될 수 있음을 증명한다. 마지막으로 단원 V에서는 결론을 언급한다.

Ⅱ. 벡터 분해 문제(The vector decomposition problem)

먼저 논문'⑵에서 정의된 벡터 분해문제와 CDHP의정의를 살펴 본 毛 관련된 몇 가지 성질과 논문⑵에서 보여준 증명을 살펴보기로 한다.

, 를 소수 위수 m을 갖는 유한체 IF상의 2차원 벡터공간이라고 하고, '을 卩 의 1차원 부분 공간이라고 하자. 또한 벡터。eU에대해 <。>는 {avia eF} 를 의미한다. 이 때 V상의 벡터분해문제는 다음과 같이 정의된다. :

, 卩상의 벡터분해문제 (vector decomposition prob­ lem; VDP): {今档 }가 V에 대한 F-기저이고, elre2, v e, 가 주어졌을 때, w e < >, v-u eve?>를 만족하는 벡터 e ¥ 를 찾는 문제를 V 상의 벡터분해문제(VDP)로 정의한 ・ V ' 상의 계산적 Diffie-Hellman문제 (Computatio­ nal Diffie-Hellman problem; CDHP) : a, b e F 에 대하여 e & V '/ 0 와 de, 诡 £ V e 그 가주어졌을 때 泌e G V e > 를 찾는 문제를 말한다.

Yoshida 등이 논문'에서 주장한, , 卩상의 VDP 가, 어떤 특별한 조건하에선, 적어도 1차원 부분 공간 V ' 상의 계산적 Diffie-Hellman 문제 (CDHP) 보다 어렵다” 에 관한 구체적 정리는 다음과 같다.

(정리1) 다음 세 가지 조건을 만족하는 선형 동형사상 (linear isomorphism) 饥, <j>e:V V 이 임의의 e e r '에 대해 존재하면 V 상의 VDP는 적어도 f'(u 卩)상의 CDHP보다 어렵다⑴.

(조건1) 어떤。£ 卩 에 대해 血(0), 但 (。) 는 효율적으로 정의되고 다항식 시간 내에 계산가능하다.

(조건2) {e, 仇(e)} 는 u 에 대한 F-기저이다. 0(e) =016,

(조건3) 饱(仇(e)) =c的e + a3也Je), . 사》.六 0

을 만족하는 Oi a2 «3 e 존재하고 이런 원소 為, %, 心 와 각각의 역원들은 다항식 시간 내에 계산 가능하다.

참조: 이후 우리는 위의 조건을 Yoshida 조건이라고 통칭한다.

(정리1)의 증명을 개략적으로 살펴보도록 흐卜자. 우리는 일반성의 손실이 없으면서 증명을 단순화 하기 위해 CDHP 문제의 입력값인 (e, ae, be) 에 대해 ( a3 一 色 ) a X 1인 경우로 제한하여 증명을 살펴보기로 한다. 또한 여기서 벡터 분해를 제공해 주는 함수 이름을 VDP 라고 쓰기로 하자.

즉, 4, &2, v V 에 대해 {負, e2 } 가 만약 V 에대한 F-기저이면서, u e < ej > 이고 V - u < e2 > 이라면 ED/, ((eb e2), V)= u 가 됨을 의미한다.

(정리1)의 개략적 증명⑴ : CDHP 문제의 입력값인 (e, ae, be) 에 대해 abe 는 VDP 함수를 다음처럼 두 번 적용하는 것에 의해 계산되어 질 수 있다. 먼저 다음처럼 정의된 矿의 기저 何, 62 }를 선택한다.

= ae + ipe(a21 («3 _ aQae ―皈%) = ae + 入仇(e) 로 정의하고

(여기서 入 는 入 = Qi1(013 — «i) a — 02 1 를 표시), e2 = 饥(、%、) 로 정의한다. 이 때 e2 에 대해 좀 더 계산을 해보면 다음 결과를 이끌어 낼 수 있다. 즉, &1 = c“ae + A(a2e + <鸟‘如(e)) = ( a^a + Xa2)e + 入心视(e)= (a3a-l)e + 入어戒(e) 임을 알 수 있다. 이 때 벡터 be 와 기저 (elr e2 }에 대해 다음처럼 VDP 함수를 적용하면, 0输 - 62 = 8이므로 VDP施, e2), be) = a/%가 됨을 알 수 있다. 즉 기저 {eb e2 }에 대해 벡터 be의 处에 대한 성분 a3bei 이 주어진다. 이 때 이 벡터 <玲始에 a广배의 스칼라 곱을 하게 되면 우리는 벡터 be】을 얻게 된다. 마지막으로 이 벡터 M 에 기저 {e, 血(e)}와 함께 벡터 분해함수 VDP 를 다시 적용하여 VDP{ (e, 血 (e)), be、) 를 구해보면, ej = ae + X凱(e) 이E로, 벡터 be± 의기저 e 에 대한 성분인 abe을 구할 수 있다. 口 하지만 위의 증명은, 만약 우리가 CDHP를 어려운 문제라 받아들인다면 皿R(%, eAbe) 와 VDP ((e, i/;e(e)), M) 중 적어도 한 문제는 어려운 문제임을 증명한 것 이라 할 수 있다. 이것은 VDP에 관한 정리의 증명⑴이, Yoshida 조건을 만족하는 환경에서 임의의 기저가 주어지면 그 기저에 대한 임의의 벡터를 분해하는 것이 어려운 문제라는 것을 증명하기 보다는, VDP 가 어려운 문제가 되는 instance 의 존재성만을 보인 것 이라 할 수 있다. 사실 m 절에서 우리는 Yoshida 조건을 만족하는 어떤 구체적 곡선 상에서 VDP( (e , 双 (e)), beQ 가 다항식 시간에 해결 될 수 있다는 것을 보여주므로 이 증명에서는 皿归((切, e2), be)가 VDP가 어려운 instance 라고 말할 수 있다.

M.Yoshida 등은 /와 7 의 예로, 논문〔5〕의 암호 시스템과 마찬가지 환경으로 타원곡선의 m-torsion point의 군(group)인 E\m] 와 그것의 부분군 剧%) PI E\m] 를 각각 택하였는데 여기서의 시스템 매개변수들은 다음과 같이 정의되어 있다.

p : p= 2 (mod 3) 를 만족하는 소수 哈 : 위수가 p인 유한체

E : y2 = X3 + 1, ¥„ 위에서의 타원곡선 m : 6m = p + 1 의 관계를 만족하는 소수 剧F, ) :X, y eFp 인 E 위에서의 점(X, y)의 집합 硏m〕: (P I mP = 0} u E(N》).

또한 선형 동형사상 ipe, 如 : V-^V 는 ip(x, g) = (&, y) 와 Frobenius map <f>(x, g) = (xp, 俨) 으로 선택하였다. 여기서 f e IF" 는 S + f+i = o 을 만족시키는 값이다. 이 때 임의의 P 든 卩' 에 대해 우리는 다음 관계가 만족 됨을 알 수 있다.

MP) = P , <心(P)) = _」顷. 또한 Kiyavash와 Duursma는 그들의 논문''시에서 VDP가 어려운 문제가 될 수 있는 특별한 조건을 만족하는 타원곡선은 supersingular 곡선만 가능하다는 것과, 또한 supersingular/} 아닌 경우로써 그들이 찾아낸 체 Fp (여기서 p = 2 (mod 3)) 위에 정의된 genus 2인 일련의 초타원(hyperelliptic)곡선들 ^-.y2 = x6 — ax3 + 1과 0:2/2 = 0:6 — <馈3-3가 VDP가어려운문제가 될 수 있는 Yoshida 조건을 만족시키는 것을 보였다. 즉 이 곡선들 C\, CM 상에서 동형사상 ©, 心—V 를 加、h, y) = y) 와 Frobenius map 机h, y) = (", 俨)으로 선택하면 이 곡선 상에서도 역시 认P) = P , 。(寸(尸)) = — P-ip{P) 로서 Yoshida 조건을 만족시키는 것을 보였다.

Ⅲ. 정리1의 반례

이 단원에서는 M.Yoshida 등이 앞 단원에서 제안한 VDP의 특별한 조건을 만족시키는 위의 벡터 공간들에서의 벡터들이 실제로는 어떤 기저에 관해서 약간의 계산을 통하여 분해 될 수 있다는 것을 증명하고자 한다. 먼저 우리의 증명을 도와주는 보조정리를 보여줌으로써 증명을 시작하고자 한다.

(보조정리 2) 모든 Qe E\m\ 에 대해 出(出(<2)) = - Q - W(Q).

중명) 만약 Q e E\m] 의 좌표를 Q= y) 로 표시한다면, 그때 W(Q) = (加, G)이다. 또한 Q+域Q) 의 좌표를 (矿 /) 로 표시하면,

宀(鬟土)1挪=-*挪

#

#

가 됨 을 알 수 있다. 그러므로 다음이 성립한다.

#

다음에서 체 위의 2차원 벡터공간 卩와, 의 1차원 부분 공간 广 은 각각 단원 II에서 정의된 E\m] 과 MFp) n £lm] 을 의미한다. 먼저 임의의 점 Pw r ' 를 택한다. 이 때 는 벡터공간 研끼 에는 속하지만 归(嗚) 에는 속하지 않으므로 戶와 仞、P、)는 矿에서선형독립 관계이다. 그러므로 {P, 切、P) }는 2차원 벡터공간, 에 대한 체 易皿-기저가 될 수 있음을 알 수 있고 결과적으로 임의의 벡터。e 卩 에 대해 다음 식을 만족하는 체 에 속하는 원소 a, 3가 존재함을 알 수 있다. 즉, V = aP+ bip(P') = aP+i/j(bP') = A + 4>(B). (여기서 A = aP 그리고 B=bP를 표시한다.) 그러면, X=A 또는 3에 대해 ©(X) = X이고 扒帆X)) =- X- 侦X) 이므로 우리는 다음 관계 식이 성립함을 볼 수 있다.

#(1)

또한 같은 벡터 v = A + ip (B) 에 선형사상 p를 양변에 적용한 후 식에서 나타나는 값 畋(由(3)) 대신에 보조정리 2의 결과를 이용하여 -B- 帆 B) 를 대입하면 다음 등식이 얻어진다.

#(2)

등식 (2) 좌우 변에서 등식 (1)의 좌우 변을 각각 빼게 되면 다음 관계식을 얻을 수 있다.

#(3)

다시 등식 (3)의 좌우 변에 선형 사상 ©을 적용하면 아래 등식 (4)를 얻을 수 있다.

#(4)

등식⑶과 등식(4)의 좌우 변을 각각 더한 후 얻어진 관계식의 좌우 변을 다시 3-1 배 스칼라 곱을 하게 되면, 임의로 주어진 벡터 v=A + ifi(B) 에 대해서 다음 등식 (5) 가 성립함을 알 수 있다.

#(5)

그러므로 우리는 벡터공간 ¥의 체 盔-기저 {P, 以戶)}에 대해 임의의 벡터 聞 7가 주어졌을 때 이고<^(F)> 를만족하는벡터 4를, 선형사상 饥仲 맟 타원곡선상의 한 번의 뺄셈, 한 번의 덧셈, 그리고 한 번의 스칼라 곱을 사용하여 다항식 시간 안에 분해할 수 있다는 것을 증명하였다.

Ⅳ. VDP가 어려운 문제가 될 수 있는 기저

이 단원에서는 VDP를 어렵게 하는 기저를 찾아보고 그와 같은 기저에 관련한 임의의 벡터들은 모두 VDP의 strong instance가 될 수 있음을 증명한다. 그러므로 이와 같은 기저들은 벡터 분해 문제를 기반이 되는 어려운 문제로 하는 암호학적 인 프로토콜을 수행하기에 적합한 기저가 될 수 있을 것이다.

(보조정 리 3) ae, be, ce V V =< °>인 何, ae, be. ce) 가 주어질 때, V 상에서 CDHP가 어려운 문제라면, (ac~ b(2a+ l))e를 계산하는 것은 어려운 문제이다.

중명) (e, ae, be.)가 V상에서 CDHP의 임의의 instance 라고 하자. 이때 만약 우리가 ce=be로 둔 경우에 (ac—/>(2a+l))e를 다항식 시간 안에 얻을 수 있다면 우리는

X= (ac — b(2a + 1 ))e = (ab — b(2a + 1 ))e =—abe — be

를 다항식 시간 안에 얻을 수 있고 一 X- be= abe 의 해 CDHP의 임의의 instance (e, ae, be)에 대한 abe 를 다항식 시간 안에 얻을 수 있게 된다.

다음 정리는 위의 (보조 정리 3)을 이용하여 벡터 공간 V의 임의의 벡터 v e y에 대해 VDP를 어렵게 하는 기저를 제공해 준다.

(정리 4) * ' =< e >을 일차원 부분 공간으로 갖는, 유한 체 IF위의 {e, 砂(e)} 에 의해 생성되는 2차원 벡터 공간 V에서 (정리1)의 ai = l, a2=-l, %=—1 인 경우의 Yoshida 조건을 만족하는 선형 동형사상 小 : 卩- 卩 가 있을 때, 특히 이때 仲는모든 D w V 에 대해 V)( 砂(a)) = —V — 职我) 를만족하며 1/厂' 도 다항식 시간 내에 계산 가능한 사상일 때, 2ae+e 女 0 (여기서。은 V의 zero vector 를 의미)인 임의의 벡터 ae e < e > 에 대해 아래의 두 벡터 {ei, e2} 는 V 의 기저가 되며,

#

#

이 기저에 대한 V 상의 임의의 벡터에 대한 VDP 는 적 어도 V ' 상의 CDHP 만큼 어렵다.

중명) 표현의 간편성을 위해 2a + 1 을 入로 표시하자. 이때 切 = ae + W(e) 로 표시되고 e2 = (-a-1) e-W(e) 가 되며 특히 A 0 이므로 毎, e2) 는 V의 또 다른 기저가 된다. 그러므로 V의 모든 벡터는 기저 {%, %} 의 선형 조합으로 표현될 수 있고 따라서 아래 식을 만족하는 s, t w F 가 존재한다.

#(5)

여기서 우리는 {e, W(e)} 또한 V의 기저이기 때문에

#(6)

이 되어야 함을 알 수 있고 A # 0 이므로 식 (6) 으로부터 결국 는 (;)=(=圮°)) 의 값을 갖게 됨을 알 수 있다. 이제 우리는 be, ce 가 卩 ' = < e > 에 속하는 임의의 벡터일 때, V 상의 임의의 벡터 0=况 +出(ce) 에 대해 VDP{eie2i v) > 다항식 시간 내에 풀 수 있다면 CDHP(e, ae, be) 또한 다항식 시간 내에 풀 수 있음을 보이고자 한다. - ej — e2 = e 이고 (5)에서 寸(e) = 人7(1 + q)切 + 人一七吻 로 표현되므로 우리는 기저 {幻, 吻} 에관하여 日 를 다음과 같이 쓸 수 있다.

#(7)

만약 皿尸((四成)/u) 가 다항식 시간에 해결된다면, 우리는식 (7)로부터 다항식 시간에 V— 皿尸((红吻), 日) = (一3 + 心-妇厄를 얻을 수 있다. 다시 여기서 기저 {e, ©(e)} 에 관해

#

로 표현될 수 있고 이절에서 증명한 것처럼 기저 {e, W(e)} 에 관해 VDP 는 다항식 시간에 해결 될 수 있으므로 다음 벡터를 얻을 수 있다.

#(8)

또한 동형사상 寸-' 도 다항식 시간 내에 계산 될 수있으므로 식 (8)의 결과에『를 적용하여 부호를 변화시키면 다항식 시간 안에 (ac —8入)e를 얻을 수 있다. 그런데 우리는 (보조 정리3)에서 instance (e, ae, be.ce) 에 대해 다항식 시간 안에 (ac-"tX)e 를 얻을 수 있다면 이 오라클을 이용하여 CDHP를다항식 시간 내에 구할 수 있다는 것을 보였다.

Ⅴ. 결론

본 논문에서 우리는 M.Yoshida 등이 제안한 특별한 조건", 2〕을 만족하는 벡터 공간이라 할지라도 벡터들이 어떤 특정한 종류의 기저에 관해서는 다항식 시간 안에 분해 될 수 있다는 것을 보여주었다. 또한 그와 다른 형태를 갖는 어떤 모양의 기저에 대해서는 임의의 벡터에 대해 VDP가 어려운 문제가 되는 strong instance들이 된다는 것을 증명하였다. 그러므로 VDP가 어려운 문제가 되기 위해서는 기저를 선택함에 있어 주의를 기울어야 할 것이다.