Undeniable digital signature scheme based on quadratic field

Abstract

An efficient undeniable digital signature scheme based on a quadratic field is disclosed. Public keys (D, P, k, t) and secret keys (D1, q) are defined by generating two primes p, q (p, q>4, p=3 mod 4, √{square root over (p/3)}<q), computing D1=−p and D=D1q, obtaining a bit length k of √{square root over (|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). Then the signature verification is realized by first checking whether a norm N(S) of the signature S 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=(M/S), generating a random ideal B whose norm is smaller than k−1 bits, and computing the challenge C=BH, at a verifier side; then computing a response W by mapping the challenge C 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 then checking whether W=Bholds or not, and judging that the signature S is legal when W=Bholds or that the signature S is illegal otherwise, at the verifier side.