페어링 암호 연산을 위한 세제곱근 연산 방법
Method of computing cube roots for pairing computations
특허 요약
본 발명은 에서의 세제곱근 연산방법에 관한 것으로서, C∈ 에 대하여, SPB를 기저로 한 C 1 /3 의 x 1/3 과 x 2/3 를 계산하는 단계; 및 계산된 x 1/3 과 x 2/3 를 이용하여 C 1 /3 를 계산하는 경우, 모듈로 감산 연산이 필요없도록 SPB를 사용할 때 C에 곱해지는 x -r 의 r값을 결정하여, C의 세제곱근을 연산하는 단계를 포함하는 것을 특징으로 하며, 세제곱근 연산의 효율성을 결정하는 x 1/3 의 헤밍웨이트가 기존의 결과에 비해 거의 모든 경우에 대하여 감소하여 세제곱근 연산을 효율적으로 수행할 수 있고, SPB를 이용함으로써, 에서의 세제곱근 연산 시 다항식 곱셈 횟수가 현저하게 줄어들었으며, 특정 SPB를 선정하여 모듈러 감산 연산을 제거하여 세제곱근 연산량이 더욱 줄어들도록 할 수 있다.
청구항
번호청구항
1

f(x)=xm+axk+b(a,b∈F3)가 F3[x]의 삼항 기약다항식이고, =F3[x]/(f(x))이라 할 때, C∈에 대하여, SPB(Shifted Polynomial Basis)를 기저로 한 에 속하는 다항식 C를 생성하는 SPB 기저 생성부; 상기 생성한 다항식 C에 대하여 세제곱근 식을 생성하는 세제곱근 생성부; 상기 세제곱근 식에 대하여 모듈로 감산 연산이 필요하지 않도록 하는 상기 SPB의 x-r을 결정하는 시프트 베이스 결정부; 및 상기 결정된 x-r을 이용하여 상기 C의 세제곱근을 연산하는 세제곱근 연산부를 포함하는 에서의 세제곱근 연산장치를 이용하여 상기 에서의 세제곱근 연산방법에 있어서,상기 세제곱근 생성부가 상기 C∈에 대하여, 상기 SPB를 기저로 한 C1/3의 x1/3과 x2/3를 상기 m과 k에 따라 계산하는 단계;상기 시프트 베이스 결정부가 상기 계산된 x1/3과 x2/3를 이용하여 상기 C1/3를 계산하는 경우, 상기 모듈로 감산 연산이 필요없도록 상기 SPB를 사용할 때 상기 C에 곱해지는 x-r의 r값을 결정하는 단계; 및상기 세제곱근 연산부가 상기 C의 세제곱근을 연산하는 단계를 포함하고,상기 시프트 베이스 결정부는 상기 C1/3의 최소 디그리(degree)와 최대 디그리를 이용하여 상기 r값을 결정하는 것을 특징으로 하는 에서의 세제곱근 연산방법.

2

제 1 항에 있어서,상기 m≡0(mod 3), 상기 k≡1(mod 3)이고, 임의의 양수 u와 v에 대하여(u003e#v) m=3u이고, k=3v+1이라 하면, 상기 r값은 3v 또는 3v+1인 것을 특징으로 하는 에서의 세제곱근 연산방법.

3

제 1 항에 있어서,상기 m≡0(mod 3), 상기 k≡-1(mod 3)이고, 임의의 양수 u와 v에 대하여(u≥v) m=3u이고, k=3v-1이라 하면, 상기 r값은 3v-2 또는 3v-1인 것을 특징으로 하는 에서의 세제곱근 연산방법.

4

제 1 항에 있어서,상기 m≡1(mod 3), 상기 k≡0(mod 3)이고, 임의의 양수 u와 v에 대하여(u≥v) m=3u+1이고, k=3v이라 하면, 상기 r값은 3u 또는 3u+1인 것을 특징으로 하는 에서의 세제곱근 연산방법.

5

제 1 항에 있어서,상기 m≡-1(mod 3), 상기 k≡0(mod 3)이고, 임의의 양수 u와 v에 대하여(u003e#v) m=3u-1이고, k=3v이라 하면, 상기 r값은 3u-2 또는 3u-1인 것을 특징으로 하는 에서의 세제곱근 연산방법.

6

C∈에 대하여, SPB(Shifted Polynomial Basis)를 기저로 한 에 속하는 다항식 C를 생성하는 SPB 기저 생성부; 상기 생성한 다항식 C에 대하여 세제곱근 식을 생성하는 세제곱근 생성부; 상기 세제곱근 식에 대하여 모듈로 감산 연산이 필요하지 않도록 하는 상기 SPB의 x-r을 결정하는 시프트 베이스 결정부; 및 상기 결정 된 x-r을 이용하여 상기 C의 세제곱근을 연산하는 세제곱근 연산부를 포함하는 에서의 세제곱근 연산장치를 이용하여 상기 에서의 세제곱근 연산방법에 있어서,상기 세제곱근 생성부가 상기 C∈에 대하여, 상기 SPB를 기저로 한 C1/3의 x1/3과 x2/3를 계산하는 단계;상기 시프트 베이스 결정부가 상기 계산된 x1/3과 x2/3를 이용하여 상기 C1/3를 계산하는 경우, 모듈로 감산 연산이 필요없도록 상기 SPB를 사용할 때 상기 C에 곱해지는 x-r의 r값을 결정하는 단계; 및상기 세제곱근 연산부가 상기 C의 세제곱근을 연산하는 단계를 포함하는 것을 특징으로 하는 에서의 세제곱근 연산방법.

7

제 6 항에 있어서,상기 x1/3과 상기 x2/3의 계수들의 개수를 각각의 해밍 웨이트라고 할 때, 상기 SPB를 기저로 하는 경우 상기 해밍 웨이트가 최소가 되는 것을 특징으로 하는 에서의 세제곱근 연산방법.

8

삭제

9

제 1 항 내지 제 7 항 중에 어느 한 항의 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.

10

f(x)=xm+axk+b(a,b∈F3)가 F3[x]의 삼항 기약다항식이고, =F3[x]/(f(x))이라 할 때, 에서의 세제곱근 연산장치에 있어서,C∈에 대하여, SPB(Shifted Polynomial Basis)를 기저로 한 에 속하는 다항식 C를 생성하는 SPB 기저 생성부;상기 생성한 다항식 C에 대하여 세제곱근 식을 생성하는 세제곱근 생성부;상기 세제곱근 식에 대하여 모듈로 감산 연산이 필요하지 않도록 하는 상기 SPB의 x-r을 결정하는 시프트 베이스 결정부; 및상기 결정된 x-r을 이용하여 상기 C의 세제곱근을 연산하는 세제곱근 연산부를 포함하고,상기 세제곱근 식의 최소 디그리(degree)와 최대 디그리를 이용하여 상기 x-r을 결정하는 것을 특징으로 하는 에서의 세제곱근 연산장치.

도면대표도면