Private signature and proof systems

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.

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.

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.