Patent ID: 6976169

Claim:
A method of processing an undeniable digital signature, comprising the steps of: (a) generating public keys (D, P, k, t) and secret keys (D1, q) at a signer side, by generating two primes p , q ⁡ ( p , q > 4 , p = 3 ⁢ ⁢ mod ⁢ ⁢ 4 , P 3 < q ) , computing D1=−p and D=D1q 2 , obtaining a bit length k of  D1  4 and a bit length t of q−(D1/q) where (D1/q) denotes Kronecker symbol, and generating a kernel element P of a map from a class group Cl(D) to a class group Cl(D1); (b) generating a signature S for a message m at the signer side, by embedding the message m into a message ideal M in the class group Cl(D) where a norm of the message ideal M is larger than k+1 bits, and mapping the message ideal M to the class group Cl(D1) and pulling the mapped message ideal M back to the class group Cl(D); and (c) verifying the signature S by: (c1) checking whether a norm N(S) of the signature S received from the signer side is smaller than k bits or not, and judging that the signature S is illegal when the norm N(S) is larger than k bits, or generating a challenge C when the norm N(S) is not larger than k bits, by computing the message ideal M of the message m, generating a random integer r smaller than t bits, computing H=(MS) r , generating a random ideal B whose norm is smaller than k−1 bits, and computing the challenge C=BH, at a verifier side; (c2) computing a response W by mapping the challenge C received from the verifier side to the class group Cl(D1) and pulling the mapped challenge C back to the class group Cl(D) and squaring a result of mapping and pulling back, using the secret keys (D1, q), at the signer side; and (c3) checking whether W=B 2 holds or not by using the response W received from the signer side, and judging that the signature S is legal when W=B 2 holds or that the signature S is illegal otherwise, at the verifier side.