Three party signing protocol providing non-linkability

• US 20030190046A1
• Filed: 10/17/2002
• Published: 10/09/2003
• Est. Priority Date: 04/05/2002
• Status: Abandoned Application

• Current Assignee: PersonalPath Systems, Inc. (Abbott Laboratories)
• Original Assignee: PersonalPath Systems, Inc. (Abbott Laboratories)
• Inventors: McNab, Carol Anne, Matyas,, Stephen Michael Jr., Kamerman, Matthew Albert
• Application Number:
  US10/272,063
• Publication Number:
  US 20030190046A1
• Time in Patent Office: Days
• US Class Current: 380/286
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/006 involving public key infrastructure [PKI] trust models network architecture or network communication protocol for supporting authentication of entities using certificates in a packet data network H04L63/0823
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures
• CPC Class Codes: H04L 9/3265 using certificate chains, trees or paths; Hierarchical trust model

Abstract

A three-party signing protocol uses a Trusted Third Party (denoted T) to simulate a two-party protocol in which a sender, designated party A, anonymously signs data intended for a particular receiver, designated party B, such that B can verify the signature on the data without learning A'"'"'s true identity, and data and signatures received by different receivers cannot be cross-linked, aggregated, or associated with a single sender. In this three-party signing protocol, A has only one public/private signature key-pair. In the three-party signing protocol, T is permitted to “see” signatures generated by A, but B is not permitted to “see” signatures generated by A, unless they are randomized or encrypted, since doing so would permit A'"'"'s generated signatures and signed data to be cross-linked. Thus, in the three-party signing protocol, T is used to “vouch to B on behalf of A” that signatures generated by A are valid.

Claims

1. A three-party signing method that protects the privacy of the signer and prevents verifiers from colluding to cross-link information signed by the signer, the method comprising the steps of:

generating by a signer A a signature S1 on a representation of at least data D;

sending by A the representation of at least the data D with the signature S1 to a trusted third party T;

verifying by T the signature S1 on the representation of at least data D, and if the signature S1 on the representation of at least data D is valid, then generating by T a signature S2 on the representation of at least data D;

sending by T a representation of signature S1 together with the representation of at least data D and the signature S2 to an intended receiver B, or else sending by T a representation of signature S1 together with the representation of at least data D and the signature S2 to A, who in turn sends the representation of signature S1 totether with the representation of at least data D and the signature S2 to B, whereby the representation of signature S1 is such that it cannot be used by B to cross-link information signed by A; and

verifying by B the signature S2, and if the signature S2 on the representation of at least the data D is valid, then

escrowing by B at least a copy of the representation of at least the data D, the representation of signature S1, and the signature S2 in case a dispute arises in which B must later prove to an impartial party that A indeed signed the representation of at least the data D, whereby B is assured that A'"'"'s signature S1 generated on the representation of at least data D was also valid, in which case B can trust that A did indeed sign the representation of at least data D, even though B does not verify A'"'"'s signature S1 directly.

2. The three-party signing method of claim 1, wherein the signature S1 is selected from the group consisting of a non-randomized signature and a randomized signature.

3. The three-party signing method of claim 2, wherein the signature S1 is a non-randomized signature.

4. The three-party signing method of claim 2, wherein the signature S1 is a randomized signature.

5. The three-party signing method of claim 4, wherein said randomized signature S1 has a property of appearing to be randomly generated.

6. The three-party signing method of claim 5, wherein said randomized signature S1 is generated by a signature algorithm that automatically produces randomized signatures.

7. The three-party signing method of claim 4, wherein said randomized signature S1 has a property of appearing to be randomly generated even when a same key is used repeatedly to sign the same data.

8. The three-party signing method of claim 4, wherein said randomized signature S1 is generated by the step of padding at least the data D with a random pad value R prior to generating the signature S1 on at least the data D, further comprising the steps of:

sending by A the random pad value R along with the at least the data D (D, R) to T; and

sending by T the random pad value R along with the at least the data D (D, R) to B, or else sending by T the random pad value R along with the at least the data D (D, R) to A, who in turn sends the random pad value R along with the at least the data D (D, R) to B.

9. The three-party signing method of claim 1, wherein the representation of signature S1 is selected from the group consisting of an encryption of A'"'"'s non-randomized signature and A'"'"'s randomized signature.

10. The three-party signing method of claim 9, wherein said representation of signature S1 is an encryption of A'"'"'s non-randomized signature, further comprising the step of encrypting by T S1 under a key that will permit T to later decrypt and recover it, the encrypted signature S1 being sent to B by T together with the representation of at least the data D, or else the encrypted signature S1 being sent by A to T together with the representation of ast least the data D, and in turn the encrypted signature S1 being sent to B by A together with the representation of at least the data D.

11. The three-party signing method of claim 10, wherein the step of encrypting signature S1 is performed with a public/private key encryption method.

12. The three-party signing method of claim 1, wherein the step of generating by T a signature S2 on the representation of at least data D is performed with a public/private key signature method.

13. The three-party signing method of claim 12, wherein T uses a single public/private key pair for all different A and B pairs.

14. The three-party signing method of claim 13, wherein pseudonymous identifiers A1, A2, . . . , An are used to distinguish one A from another A and wherein the pseudonymous identifiers are different from the public key of the public/private key pair.

15. The three-party signing method of claim 1, wherein to preclude possible protocol difficulties or abuses, wherein B inadvertently or purposely loses the representation of signature S1, thereby preventing T from proving to an impartial party that A signed data in question, further comprising the step of signing by T both the representation of at least the data D and the signature S1 so that T is assured that B must make the representation of the signature S1 available to an impartial party who is asked to verify S2.

16. The three-party signing method of claim 1, wherein the representation of at least the data D is selected from the group consisting of at least the data and a hash value computed on at least the data.

17. The three-party signing method of claim 16, wherein the representation of at least the data D is at least the data.

18. The three-party signing method of claim 16, wherein the representation of at least the data D is a hash value computed on the at least the data.

19. The three-party signing method of claim 1, wherein the step of verifying by B includes the step of validating a received representation of at least data D against an available copy of the data D.

20. The three-party signing method of claim 19, wherein B generates the data D which is sent to A and use by A to generate a signature S1 on a representation of at least data D.

21. The three-party signing method of claim 19, wherein A generates the data D, used by A to generate a signature S1 on a representation of at least data D, and provides a copy of the data D to B.

22. The three-party signing method of claim 19, further comprising the steps of:

padding by A at least the data D with a random pad value R prior to generating the signature S1 on at least the data D;

computing by A a hash value H(D, R) on a concatenation of at least the data D and the random pad value R;

sending by A the computed hash value H(D, R) with the representation of the signature S1 and the random pad value R along with the representation of at least the data D to T which, if verified by T, sends the computed hash value H(D, R) to B, or T sends the compute has value H(D, R) to A who in turn sends the computed hash value H(D, R) to B;

sending by A an encrypted (D, R) to B;

decrypting by B the received encrypted (D, R);

computing by B the hash value of the decryption of the encrypted (D, R) received from A; and

comparing by B the hash value of (D, R) computed by B with the hash value received by B from T, or from A.

23. A three-party signing method that protects the privacy of the signer and prevents verifiers from colluding to cross-link information signed by the signer, the method comprising the steps of:

generating by a sender A a value M1 containing information identifying the sender A to a trusted third party T, information identifying an intended receiver B to the trusted third party T, information specifying data D, a signature S1 on at least a sub-portion of M1 containing at least the information specifying the data D;

sending by A the value M1 containing the information specifying the data D with the signature S1 to the trusted third party T;

validating by T the value M1, and if the value M1 is validated, then generating by T a psuedonymous identifier A1 for the sender A and a value M2 containing psuedonymous identifier A1 permitting A'"'"'s psuedonymous identity to be determined by the receiver B, a copy of the information specifying the data D, a copy of A'"'"'s signature S1 encrypted in a key that will allow only the trusted third party T to decrypt and recover it, a copy of T'"'"'s signature S2 on at least a sub-portion of the value M2 containing at least a copy of the information specifying the data D that sender A provided to trusted third party T in value M1;

sending by T the value M2 to the A, who in turn sends M2 to the intended receiver B, or else sending by T the value M2 directly to B; and

validating by B the value M2, and if the value M2 is valid, then B is assured that A'"'"'s signature S1 generated on data D was also valid, in which case B can trust that A did indeed sign D, even though B does not verify A'"'"'s signature directly, or even “

see”

A'"'"'s signature.

24. The three-party signing method of claim 23, wherein A'"'"'s signature S1 is encrypted using a public key cryptographic method.

25. A three-party signing method that protects the privacy of the signer and prevents verifiers from colluding to cross-link information signed by the signer, the method comprising the steps of:

creating and transmitting protocol information between a sender A, a trusted third party T and an intended receiver B, which includes generating and verifying of digital signatures S1 for the sender A and S2 for the trusted third party T in a manner that prevents the signature S1 from being cross-linked to data signed by the sender A;

escrowing the protocol information; and

resolving disputes between the sender A and the receiver B using an impartial party IP which accesses the escrowed protocol information.

26. The three party signing method of claim 25, wherein the step of resolving disputes between the sender A and the receiver B using an impartial party IP comprises the steps of:

initiating by the receiver B a resolution protocol in response to a claim by the sender A that it did not sign data D;

accessing by receiver B information corresponding to data D from its place of escrow needed in order to carry out necessary steps of the resolution protocol;

constructing by receiver B IP information for the impartial party IP from the information accessed from the place of escrow;

sending by receiver B the constructed IP information to the impartial party IP;

validating by the impartial party IP the IP information received from the receiver B;

determining if the IP information sent by B is valid and, if not, notifying the sender A and the receiver B that sender A wins the dispute and receiver B loses;

otherwise,

determining by the impartial party IP that further checking must be performed by IP in order to determine whether A'"'"'s signature is valid or not valid;

sending by the IP information to T and requesting T'"'"'s help in resolving the dispute between A and B;

accessing by trusted third party T information corresponding to data D;

constructing by the trusted third party T second IP information for the impartial party IP from the information accessed by T;

sending by trusted third party T second IP information to the impartial party IP;

validating by impartial party IP the second IP information received from trusted third party T, whereby if A'"'"'s signature is valid, then B wins, T wins, and A loses, but if A'"'"'s signature is not valid, then B wins, A wins, and T loses; and

notifying A and B of the outcome of the validating step.

27. The three-party signing method of claim 26, wherein the data D is selected from the group consisting of the data D and a value computed as a function of the data D.