KEY SHARE SYSTEM, PUBLIC KEY ENCRYPTION SYSTEM, SIGNATURE SYSTEM, KEY SHARE DEVICE, ENCRYPTION DEVICE, DECODER, SIGNATURE DEVICE, AUTHENTICATION DEVICE, KEY SHARE METHOD, ENCRYPTION METHOD, DECODING METHOD, SIGNATURE METHOD, AUTHENTICATION METHOD, PROGRAM

摘要

PROBLEM TO BE SOLVED: To provide a key share system or the like suitable for a public key encryption system and a signature system. SOLUTION: In the key share system 101 for using a polynomial T(., .) defined by T(a, x)≡S(a, x) mod n on a Galois field GF(n) with respect to a Chebychev polynomial S(., .) defined by S(a, cosθ)=cos(aθ) with respect to public key X belongs to GF(n) of 2 or more and less than n belonging to the Galois field GF(n) with respect to an integer n(n>=2) and an integer a(a>=2), an integer acquisition section 103 of a key share device 102 acquires an integer p being 2 or more and less than n, a transmission key calculation section 104 calculates a transmission key Y belongs to GF(n) by Y=T(p, X) from the acquired integer p, a transmission key section 105 transmits a calculated transmission key Y to other key share device 102, a transmission key reception section 106 receives a transmission key W sent from other key share device 102 and a common key calculation section 107 calculates a share key Z belongs to GF(n) by Z=T(p, W) from the received transmission key W.