摘要 |
PROBLEM TO BE SOLVED: To efficiently perform decryption processing by reducing the load of factorization processing and factor extracting processing in a public key encryption system using an algebraic curved surface. SOLUTION: A decryption device 200 includes: a section substitution part 205 substituting a section D for a plurality of cipher texts F<SB>i</SB>(x, y, t)(i=1, ..., k); a one-variable polynomial operation part 206 subtracting L sets of substituted polynomials h<SB>e</SB>(t), h<SB>w</SB>(t) from each other; and a greatest common divisor operation part 207 obtaining the greatest common divisor ϕ(t) of L pieces of polynomials of subtraction result g<SB>j</SB>(t)(=h<SB>e</SB>(t)-h<SB>w</SB>(t))(j=1, ..., L). Then, unlike the conventional cases where factors are extracted by factorizing a polynomial äh<SB>1</SB>(t)-h<SB>2</SB>(t)} of high degree, factors are extracted by obtaining the greatest common divisor ϕ(t) of low degree from a polynomial g<SB>j</SB>(t) of high degree and factorizing the greatest common divisor ϕ(t) of low degree. COPYRIGHT: (C)2010,JPO&INPIT
|