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, q4, 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)^r, 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=B² holds or not, and judging that the signature S is legal when W=B² holds or that the signature S is illegal otherwise, at the verifier side.