Establishment of a trusted relationship between unknown communication parties

• US 8,132,005 B2
• Filed: 09/29/2005
• Issued: 03/06/2012
• Est. Priority Date: 07/07/2005
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Nokia Corporation
• Inventors: Asokan, Nadarajah, Tarkkala, Lauri
• Primary Examiner(s): Arani, Taghi
• Assistant Examiner(s): CHANG, KENNETH W
• Application Number:
  US11/237,881
• Publication Number:
  US 20070011453A1
• Time in Patent Office: 2,350 Days
• Field of Search: 380/30, 380/44, 380/37, 380/282, 380/283, 380/284, 380/285, 713/161, 713/162, 713/169, 713/170, 713/171, 713/176, 713/168, 726/3, 726/4, 726/5, 726/8, 726/14, 726/17, 726/18, 726/21, 705/64, 705/65, 705/66, 705/67, 705/71, 705/74
• US Class Current: 713/168
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3297 involving time stamps, e.g. generation of time stamps

Abstract

The present invention provides an establishment of a trusted relationship between two mutually unknown communication parties in a communication system without the use of a trusted third party. The invention is based on non-interactive proofs-of-work being purpose-bound for establishing the trusted relationship and cryptographically signing information to be transferred between the communication parties using such proofs-of-work for the solving of a problem instance along with verifying the proofs-of-work and generating a session object for a trusted relationship, when the verifying yields an affirmative result.

Claims

1. A method comprising:

(i) performing the following at a first communication party of two communication parties between which a trusted relationship is to be established,

creating a set of data comprising at least identities of the two communication parties and identifying a session between the two communicating parties;

performing a first set of cryptographic computations based on the created set of data relating to an identity of the first communication party to derive a first problem instance;

solving the first problem instance, where solving the first problem instance requires at least superpolynomial effort;

generating a proof-of-work for the solving of the first problem instance, wherein the proof-of-work is purpose-bound for establishing the trusted relationship; and

transmitting the set of data and the proof-of-work to the second communication party, and thereupon

(ii) performing the following at the second communication party,

receiving the set of data and the proof-of-work from the first communication party;

performing a second set of cryptographic computations based on the received set of data to derive a second problem instance,

where the first problem instance is identical to the second problem instance;

verifying the proof-of-work for the solving of the second problem instance; and

generating and transmitting to the first communication party a session object for the trusted relationship based on the session identified in the set of data, when the verifying yields an affirmative result,

where the session object comprises information for communicating between the two communication parties without an introduction protocol.

3. The method according to claim 1, wherein the proof-of-work is a solution to the first problem instance and the set of data contains a public key of the first communication party.

4. The method according to claim 1, wherein the proof-of-work is a digital signature based on a proof-of-knowledge of a solution to the first problem instance, wherein the proof-of-work does not reveal the solution to the first problem instance and wherein the digital signature is computed over all or part of the set of data.

6. The method according to claim 1, further comprising:

modifying at least a part of the set of data created and performing the set of cryptographic computations based on the modified set of data, when the solving fails.

7. The method according to claim 1, wherein the creating the set of data further comprises creating a timestamp in the set of data.

8. The method according to claim 1, wherein the verifying the proof-of-work comprises checking a timestamp to be valid.

9. The method according to claim 1, wherein the session object contains a cryptographic key.

10. The method according to claim 1, further comprising encrypting the session object prior to being transmitted.

11. The method according to claim 10, wherein the encrypting the session object is conducted on a basis of a public key of the first communication party which is contained in the set of data created.

21. The method according to claim 1, where the pseudo-random function is a hash function.

22. The method according to claim 1, where the first set of cryptographic computation are identical to the second set of cryptographic computation.

2. A method comprising:

receiving a set of data and a proof-of-work from a first communication party, where the set of data comprises at least identities of two communication parties between which a trusted relationship is to be established and identifying a session between the two communicating parties;

performing a set of cryptographic computations based on the received set of data to derive a problem instance,

where the problem instance is identical to another problem instance used by the first communication party to generate the proof-of-work and where solving the problem instance requires at least superpolynomial effort;

verifying the proof-of-work for solving the problem instance, wherein the proof-of-work is purpose-bound for establishing the trusted relationship; and

generating and transmitting to the first communication party a session object for the trusted relationship based on the session identified in the set of data, when the verifying yields an affirmative result,

where the session object comprises information for communicating between the two communication parties without an introduction protocol,

wherein the performing of the set of cryptographic computations comprises performing a pseudo-random function on at least a part of the received set of data, and

wherein the verifying the proof-of-work comprises;

performing the set of cryptographic computations based on the set of data on which the set of cryptographic computations at the first communication party are based; and

validating that the proof-of-work received corresponds to the performing of the set of cryptographic computations.

5. The method according to claim 2, wherein the performing of the set of cryptographic computations further comprises:

performing a mapping function for mapping a result of the pseudo-random function to a problem instance.

19. The method according to claim 2, wherein the proof-of-work is a solution to the problem instance and the set of data contains a public key of the first communication party.

20. The method according to claim 2, wherein the proof-of-work is a digital signature based on a proof-of-knowledge of a solution to the problem instance, wherein the proof-of-work does not reveal the solution to the problem instance and wherein the digital signature is computed over all or part of the set of data.

12. An apparatus comprising at least one processor;

and at least one memory including computer program code, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following;

to receive, from a first communication party, a proof-of-work for a solution to a problem instance together with a set of data comprising at least identities of two communication parties between which a trusted relationship is to be established and identifying a session between the two communicating parties, wherein the proof-of-work is purpose-bound to establish the trusted relationship;

to perform a set of cryptographic computations based on the received set of data to derive a problem instance,

where the problem instance is identical to another problem instance used by the first communication party to generate the proof-of-work and where solving the problem instance requires at least superpolynomial effort;

to verify the proof-of-work received for solving the problem instance;

to generate a session object for the trusted relationship based on the session identified in the set of data, when the verifier yields an affirmative result; and

to transmit the session object generated to the first communication party,

where the session object comprises information for communicating between the two communication parties without an introduction protocol,

wherein the performing of the set of cryptographic computations comprises performing a pseudo-random function on at least a part of the received set of data, and

wherein the at least one memory and the computer program code are further configured to cause the apparatus;

to perform the set of cryptographic computations based on the set of data on which the set of cryptographic computations at the first communication party are based; and

to validate that the proof-of-work received corresponds to the performance of the set of cryptographic computations.

14. The apparatus according to claim 12, wherein the at least one memory and the computer program code are further configured to cause the apparatus to check a timestamp to be valid.

15. The apparatus according to claim 12, wherein the at least one memory and the computer program code are further configured to cause the apparatus to generate a session object containing a cryptographic key.

16. The apparatus according to claim 12, wherein the at least one memory and the computer program code are further configured to cause the apparatus to encrypt the session object prior to the transmission of the session object.

17. The apparatus according to claim 16, wherein the at least one memory and the computer program code are further configured to cause the apparatus to encrypt the session object on a basis of a public key of the first communication party.

13. An apparatus comprising:

means for receiving, from a first communication party, a proof-of-work for a solution to a problem instance together with a set of data comprising at least identities of two communication parties between which a trusted relationship is to be established and identifying a session between the two communicating parties, wherein the proof-of-work is purpose-bound for establishing the trusted relationship,

means for performing a set of cryptographic computations based on the received set of data to derive a problem instance,

where the problem instance is identical to another problem instance used by the first communication party to generate the proof-of-work and where solving the problem instance requires at least superpolynomial effort;

means for verifying the proof-of-work received for solving the problem instance;

means for generating a session object for the trusted relationship based on the session identified in the set of data, when the verifier yields an affirmative result; and

means for transmitting the session object generated by the generator to the first communication party,

where the session object comprises information for communicating between the two communication parties without an introduction protocol,

wherein the performing means comprises means for performing a pseudo-random function on at least a part of the received set of data, and

wherein the verifying means comprises;

means for performing the set of cryptographic computations based on the set of data on which the set of cryptographic computations at the first communication party are based; and

means for validating that the proof-of-work received corresponds to the performing of the set of cryptographic computations.

18. A non-transitory computer readable medium tangibly encoded with a computer program executable by a processor to perform the actions comprising:

receiving a set of data and a proof-of-work from a first communication party, where the set of data comprises at least identities of two communication parties between which a trusted relationship is to be established and identifying a session between the two communicating parties;

performing a set of cryptographic computations based on the received set of data to derive a problem instance,

where the problem instance is identical to another problem instance used by the first communication party to generate the proof-of-work and where solving the problem instance requires at least superpolynomial effort;

verifying the proof-of-work for a solution to the problem instance, wherein the proof-of-work is purpose-bound for establishing a trusted relationship; and

generating and transmitting to the first communication party a session object for the trusted relationship based on the session identified in the set of data, when the verifying yields an affirmative result,

where the session object comprises information for communicating between the two communication parties without an introduction protocol,

wherein the performing of the set of cryptographic computations comprises performing a pseudo-random function on at least a part of the received set of data, and

wherein the verifying the proof-of-work comprises;

performing the set of cryptographic computations based on the set of data on which the set of cryptographic computations at the first communication party are based; and

validating that the proof-of-work received corresponds to the performing of the set of cryptographic computations.