Selected-exponent signature systems

• US 4,996,711 A
• Filed: 06/21/1989
• Issued: 02/26/1991
• Est. Priority Date: 06/21/1989
• Status: Expired due to Term

• Current Assignee: Van Detsan Networks LLC (Intellectual Ventures LLC)
• Original Assignee: David L. Chaum
• Inventors: Chaum, David L.
• Primary Examiner(s): Buczinski, Stephen C.
• Assistant Examiner(s): Gregory, Bernarr Earl
• Application Number:
  US07/368,677
• Time in Patent Office: 615 Days
• Field of Search: 380/6, 380/9, 380/24, 380/28, 380/30, 380/44, 380/23, 380/25, 380/49, 380/50
• US Class Current: 380/30
• CPC Class Codes: G06Q 20/3678 e-cash details, e.g. blinded, divisible or detecting double spending
• CPC Class Codes: G06Q 20/3825 Use of electronic signatures
• CPC Class Codes: G07F 7/1016 Devices or methods for securing the PIN and other transaction-data, e.g. by encryption arrangements for secret communication, see H04L9/00
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3257 using blind signatures
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

Digital signature techniques are disclosed in which exponents may be selected by the message to be signed itself, by the signing party, by the party providing the message to the signing party for signature, and/or by a party to whom the signature is shown. When a message selects the exponent(s), the need for "hash functions" in known signature schemes is overcome. When the exponent is chosen by the party receiving the signature, to take another example, computation, storage and bandwidth requirements of known one-show blind signature systems may be improved. Also, the bank cannot falsely incriminate a payer for showing a signature more than once, even if the bank has unlimited computing resources.

Claims

1. A method for verifying public-key digital signatures, the method comprising the steps of:

determining an exponent from a first message by a first party using a procedure known to the first party and a second party, the exponent containing at least one prime factor uniquely determined by said message;

forming by said first party of a root based on a constant known to said first party and said second party, said root forming a part of said exponent;

communicating said root to said second party by said first party; and

checking the validity of said root by said second party computing said exponent, raising said root to said exponent to provide a result, and verifying that the result is said constant.

2. A method for verifying public-key digital signatures, the method comprising the steps of:

determining, from a first message and a state variable, a set of exponents by a first party using a procedure known to the first party and a second party, the set of exponents being distinct from every subset of a set corresponding to different message;

forming by said first party of roots on at least one constant, the constant known to said first party and said second party, and the roots corresponding to at least the members of said set of exponents;

communicating said roots and said state variable to said second party by said first party; and

checking the validity of said roots by said second party computing said set of exponents, raising said roots to the powers that are members of said set of exponents to produce a result, and verifying that the result is said constant.

3. A method of verifying public-key digital blind signatures, the method comprising the steps of:

forming a plurality of candidates by a first party, each such candidate formed as at least one base value raised to a proper subset of powers chosen from a set of different powers;

forming by a second party, on a at least one subset of said candidates received from said first party, roots including, on at least one candidate, at least one inverse of one of said set of distinct powers;

unblinding said roots received by said first party cancelling a subset of said at least one base values from said subset of said candidates, those base values cancelled being those that received only roots cancelling said powers that were included in the step of forming by a second party.

4. A method for transactions between a first and a second party, where the first party should be able to provide information on all transactions and such information and its completeness is protected from being convincingly disputed by the second party, the method comprising the steps of:

initially establishing by said second party of a public key;

initially establishing by said first party of a first transformed message under an agreed one-way function, where the corresponding message prior to transformation is known to said first party;

transacting a k'"'"'th transaction between said first and said second party, including

(a) said first party issuing to said second party a k+1'"'"'th transformed message under said established one-way function of a k+1'"'"'th message not known to said second party;

(b) said second party issuing to said first party a digital signature including as message content at least said at least k+1'"'"'th transformed message;

(c) said first party receiving from said second party a digital signature on said k+1'"'"'th transformed message;

(d) said first party checking the validity of said signature using said initially established public key; and

(e) said first party issuing said k'"'"'th message to said second party, only if said check is successful.

5. The method of claim 4, wherein the one-way function includes plural messages for substantially every transformed message.

6. The method of claim 4, wherein other transaction details are included in and checked for in said digital signature.

7. A method for showing and verifying public-key blind signatures by a first party to a second party, the method comprising:

issuing a challenge by said second party to said first party that is unpredictable to said first party;

forming by said first party a response to said challenge that includes only those roots and corresponding bases whose public exponents are indicated by said challenge and excludes those roots and corresponding bases whose public exponents are not indicated by said challenge; and

said second party checking said response by raising said response to said public exponents indicated by said challenge to produce a result and verifying the result.

8. The method of claim 7, further comprising including in said challenge an amount part that is mutually agreed between said first and second parties and which causes particular values to be revealed by the first party to the second party;

and said values corresponding, as determined by the corresponding roots, to certain amounts of value in a value transfer system.

9. A method for showing and verifying public-key blind signatures by a first party to a second party, the method comprising:

issuing a challenge by said second party to said first party that is unpredictable to said first party;

forming by said first party a response to said challenge that includes only those roots whose public exponents are indicated by said challenge and excludes those roots whose public exponents are not indicated by said challenge; and

said second party checking said response by raising said response to said public exponents indicated by said challenge to produce a result and verifying the result.

10. A method for conducting a cut-and choose protocol using public-key blinded signatures, the method comprising the steps of:

forming, by a first party, plural collections of blinded candidate values;

choosing by a second party, for each signature to be issued by the second party, one of said candidate values from each of said collections received from said first party; and

returning a digital signature on the product of each chosen candidate value by said second party to said first party; and

checking said signature by said first party responsive to said candidate value chosen by said second party.

11. The method of claim 10, wherein the root under which each of said candidates appears corresponding with a public exponent associated with each of said collections from which a candidate is chosen.

12. The method of claim 10, further comprising the steps of forming by said second party of plural signatures of different selections from said collections of candidates received.

13. Apparatus for effecting public-key digital signatures, the apparatus comprising:

means for determining an exponent from a first message by a first party using a procedure known to the first party and to a second party, the exponent containing at least one prime factor uniquely determined by said message;

means for forming by said first party a root on a constant known to said first and second party, said root corresponding to said exponent;

means for communicating said root to said second party by said first party; and

means for checking said root by said second party, including means for computing said exponent, for raising said root to said exponent to produce a result, and for verifying that the result is said constant.

14. Apparatus for effecting public-key digital signatures, the apparatus comprising:

means for determining, from a first message and a state variable, a set of exponents by a first party using a procedure known to the first party and a second party, the set of exponents containing at least one prime factor uniquely determined by said state variable and the set of exponents being different from every subset of a set corresponding to a different message;

means for forming by said first party of roots on a constant, the constant known to said first and second party, and the roots corresponding to at least the members of said set of exponents;

means for communicating said roots and said state variable to said second party by said first party; and

means for checking said roots by said second party computing said set of exponents, raising said roots to the powers that are members of said set of exponents to produce a result, and verifying that the result is said constant.

15. Apparatus for showing and verifying public-key blind signatures by a first party to a second party, the apparatus comprising:

means for issuing a challenge by said second party to said first party that is unpredictable to said first party;

means for forming by said first party a response to said challenge that includes only roots and corresponding bases whose public exponents are indicated by said challenge and excludes roots and corresponding bases whose public exponents are not indicated by said challenge; and

means for checking said response by said second party raising said response to said indicted powers to produce a result and verifying the result.