Private signature and proof systems

• US 5,493,614 A
• Filed: 05/03/1994
• Issued: 02/20/1996
• Est. Priority Date: 05/03/1994
• Status: Expired due to Term

• Current Assignee: Van Detsan Networks LLC (Intellectual Ventures LLC)
• Original Assignee: David Chaum
• Inventors: Chaum, David
• Primary Examiner(s): Cain, David C.
• Application Number:
  US08/237,098
• Time in Patent Office: 658 Days
• Field of Search: 380/30, 380/28, 380/23
• US Class Current: 380/30
• CPC Class Codes: H04L 9/3221 interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

Cryptographic methods and apparatus for forming (102) and verifying (103) private signatures and proofs (203,204, 207, and 209) are disclosed. Such a signature convinces the intended recipient that it is a valid undeniable or designated-confirmer signature. And such a proof convinces the intended recipient, just as any cryptographic proof. Even though the signatures and proofs are convincing to the intended recipient, they are not convincing to others who may obtain them.

Unlike previously known techniques for convincing without transferring the ability to convince others, those disclosed here do not require interaction--a signature or proof can simply be sent as a single message. Because the intended recipient can forge the signatures and proofs, they are not convincing to others; but since only the intended recipient can forge them, they are convincing to the intended recipient. Exemplary embodiments use a cryptographic challenge value that is said to pivot on a trap-door function, in that the value can be manipulated by those with the corresponding trap-door information, and is believed impractical to manipulate without it.

Claims

1. In a cryptographic proof system, in which a prover party is to convince a recipient party of an assertion, the improvement comprising the steps of:

performing at least a first cryptographic operation by said prover party in preparing a first proof of said assertion for said recipient party;

possessing, by said recipient party, of trap-door information corresponding to said first cryptographic operation; and

all such that (1) said proof is substantially convincing to said recipient party; and

(2) said trap-door information substantially allows said recipient party, having said assertion but without having received said first proof, to develop at least a substantially equivalent proof of said assertion, thereby substantially obscuring at least which of said prover and said recipient parties originated said first proof from parties other than said prover and said recipient parties.

2. In the method of claim 1, said recipient being able to develop substantially equivalent proofs of false assertions.

3. In the method of claim 1, said proof being of the validity of a signature corresponding to a public key of at least one signature party, and said proof allowing a proof by said at least one signature party of validity when said signature is valid and allowing proof of invalidity by said signature party of said signature when an alleged said signature is invalid.

4. In the method of claim 3, said signature party being said prover.

5. In the method of claim 3, said signature party being a third party.

6. In the method of claim 3, said signature party including cooperation of at least two parties other than the recipient.

7. In an undeniable signature system, the improvement comprising the step of:

completing a signature showing and a confirmation by a single message sent from the prover party to the recipient party.

8. In a designated confirmer signature system, the improvement comprising the step of:

completing a signature showing and a confirmation by a single message sent from the prover party to the recipient party.

9. In a challenge creation method, pivoting the challenge on at least one trap-door operation.

10. In a designated confirmer signature systems, hinging a signature scheme that allows existential forgery.

11. A cryptographic method between a prover party and an intended recipient party, in which said recipient party has trap-door information corresponding to a trap-door operation known to at least said prover party, including the steps of:

developing, by said prover party, of a commit value corresponding to said assertion to be proved;

developing, by said prover party, of an input and a corresponding output of said trap-door operation;

combining, by said prover party, of said input to said trap-door operation and said commit value to form a challenge value, such that substantially any challenge can substantially readily be chosen by a party having said trap-door information corresponding to said trap-door operation and that it is substantially infeasible for a party not having said trap-door information corresponding to said trap-door operation to choose substantially any challenge;

forming, by said prover party, of a response depending on said commit and said challenge, such that said challenge would be convincing to at least said recipient party provided said challenge was substantially uncontrolled by said prover party;

transmitting, by said prover party, and receipt by said recipient party, of information allowing said recipient party to substantially readily develop said commit, said challenge, and said response values;

checking, by said recipient party, that said transmitted information indicates that said challenge was substantially controlled by at least one value computed by said trap-door operation;

ensuring, by said recipient party, that said challenge could be formed as the output of said combining operation applied both to said commit and to said output of said trap-door operation;

verifying, by said recipient, that said commit, said challenge, and said response, form a consistent proof.

12. In a cryptographic proof system apparatus, in which a prover party is to convince a recipient party of an assertion, the improvement comprising:

means for performing at least a first cryptographic operation by said prover party in preparing a first proof of said assertion for said recipient party;

means for storing, by said recipient party, of trap-door information corresponding to said first cryptographic operation; and

all such that (1) said proof is substantially convincing to said recipient party; and

(2) said trap-door information substantially allows said recipient party, having said assertion but without having received said first proof, to develop at least a substantially equivalent proof of said assertion, thereby substantially obscuring at least which of said prover and said recipient parties originated said first proof from parties other than said prover and said recipient parties.

13. In the apparatus of claim 12, said recipient being able to develop substantially equivalent proofs of false assertions.

14. In the apparatus of claim 12, said proof being of the validity of a signature corresponding to a public key of at least one signature party, and said proof allowing a proof by said at least one signature party of validity when said signature is valid and allowing proof of invalidity by said signature party of said signature when an alleged said signature is invalid.

15. In the apparatus of claim 14, said signature party being said prover.

16. In the apparatus of claim 14, said signature party being a third party prover.

17. In the apparatus of claim 14, said signature party including means for cooperation of at least two parties other than the recipient.

18. In an undeniable signature system apparatus, the improvement comprising the means for:

completing a signature showing and confirmation with a single message sent from the prover party to the recipient party.

19. In a designated confirmer signature system apparatus, the improvement comprising the means for:

completing a signature showing and confirmation with a single message sent from the prover party to the recipient party.

20. In a challenge creation apparatus, pivoting the challenge on at least one trap-door operation.

21. In a designated confirmer signature system apparatus, hinging a signature scheme that allows existential forgery.

22. Cryptographic apparatus for use between a prover party and an intended recipient party, in which said recipient party has trap-door information corresponding to a trap-door operation known to at least said prover party, comprising:

means for developing, by said prover party, of a commit value corresponding

said assertion to be proved;

means for developing, by said prover party, of an input and a corresponding output of said trap-door operation;

means for combining, by said prover party, of said input to said trap-door operation and said commit value to form a challenge value, such that substantially any challenge can substantially readily be chosen by a party having said trap-door information corresponding to said trap-door operation and that it is substantially infeasible for a party not having said trap-door information corresponding to said trap-door operation to choose substantially any challenge;

means for forming, by said prover party, of a response depending on said commit and said challenge, such that said challenge would be convincing to at least said recipient party provided said challenge was substantially uncontrolled by said prover party;

means for transmitting, by said prover party, and receipt by said recipient party, of information allowing said recipient party to substantially readily develop said commit, said challenge, and said response values;

means for checking, by said recipient party, that said transmitted information indicates that said challenge was substantially controlled by at least one value computed by said trap-door operation;

means for ensuring, by said recipient party, that said challenge could be formed as the output of said combining operation applied both to said commit and to said output of said trap-door operation;

means for verifying, by said recipient, that said commit, said challenge, and said response, form a consistent proof.