Nippon Telegraph and Telephone Corporation

Ingrid Biehl

Sachar M Paulus

Tsuyoshi Takagi

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&#x3e;4, p=3 mod 4, &#x221a;{square root over (p/3)}&#x3c;q), computing D1=&#x2212;p and D=D1q, obtaining a bit length k of &#x221a;{square root over (|D1|)}/4 and a bit length t of q&#x2212;(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&#x2212;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.

Growing community of inventors

Neunkirchen, Germany

Ingrid Biehl