Computing solutions to a problem involving inversion of a one-way function

• US 9,495,668 B1
• Filed: 09/27/2013
• Issued: 11/15/2016
• Est. Priority Date: 05/10/2013
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Juels, Ari
• Primary Examiner(s): Pearson, David
• Assistant Examiner(s): Plecha, Thaddeus
• Application Number:
  US14/039,215
• Time in Patent Office: 1,145 Days
• US Class Current: 1/1
• CPC Class Codes: G06Q 20/06 Private payment circuits, e.g. involving electronic currency used among participants of a common payment scheme
• CPC Class Codes: G06Q 20/065 using e-cash
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 63/10 for controlling access to devices or network resources
• CPC Class Codes: H04L 63/1458 Denial of Service
• CPC Class Codes: H04L 63/166 at the transport layer
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

A method comprises sending a set of values from a first party to a second party, the set of values being usable to compute a solution to a first problem involving inversion of a first one-way function. The method further comprises receiving a given value from the second party and utilizing the given value as an input for computing a solution to a second problem involving inversion of a second one-way function, wherein a valid solution to the second problem uses as input a valid solution to the first problem.

Claims

1. A method comprising:

receiving, at a first processing device from a second processing device, a request for access to a given resource controlled by the first processing device;

sending, from the first processing device to the second processing device, a set of values responsive to receiving the request for access to the given resource, the set of values being usable to compute a solution to a first problem involving inversion of a first one-way function;

receiving, at the first processing device from the second processing device, a given value representing a potential solution to the first problem;

providing, at the first processing device, access to the given resource by the second processing device responsive to verifying the given value as a valid solution to the first problem; and

utilizing, at the first processing device, the given value as an input for computing a solution to a second problem involving inversion of a second one-way function;

wherein a valid solution to the second problem uses as input the valid solution to the first problem; and

wherein the set of values comprises a supplementary value specific to a particular instance of the first one-way problem and the second processing device, the supplementary value being used as an input to the first one-way function by the second processing device.

2. The method of claim 1, wherein the first problem has k_in-bit hardness and the second problem has k_out-bit hardness such that k=k_in+k_out, where k_in≦

k/2.

3. The method of claim 1, wherein the given resource comprises one of a transmission control protocol connection to a server and a transport layer security connection to the server.

4. The method of claim 1, wherein the given resource comprises accepting an e-mail sent to the first processing device from the second processing device.

5. The method of claim 1, wherein the given resource comprises a website of the first processing device.

6. The method of claim 1, wherein the valid solution to the second problem is usable in a system for mining digital currency involving finding a solution to a third problem involving inversion of a third one-way function.

7. The method of claim 6, wherein the third problem comprises finding a value n such that:

H(X,n;

s)≦

Z

where H is the third one-way function, X comprises a set of known information, s is the supplementary value, and Z is a target value representing a difficulty of mining the digital currency.

8. The method of claim 7, further comprising providing a payment to the second processing device based at least in part on a comparison of a value of a solution to H divided by Z.

9. The method of claim 7, wherein the first one-way function, the second one-way function and the third one-way function are related such that:

H(X,n;

s)=H_out(X,H_in(X,n;

s))

where H_in is the first one-way function and H_out is the second one-way function.

10. The method of claim 9, wherein the supplementary value s is chosen by the first processing device based at least in part on the request for access to the given resource.

11. The method of claim 10, wherein:

the request for access to the given resource comprises sending an e-mail message to the first processing device; and

s is a hash of at least one of a preamble of the e-mail message and a body of the e-mail message.

12. The method of claim 9, wherein the set of values sent to the second processing device comprises X, Z_in and s and a valid solution I to the first problem is given by:

I=H_in(X,n;

s)≦

Z_in where Z_in is a target value representing a difficulty of solving the first problem.

13. The method of claim 7, wherein the first one-way function, the second one-way function and the third one-way function are related such that:

H(X,n;

s)=H_out(X,H_in(X,n;

s,r_in),r_out)

where H_in is the first one-way function, H_out is the second one-way function, r_in=H₀(r), r_out=H₁(r), H₀ and H₁ are distinct hash functions, and r is a secret value.

14. The method of claim 13, wherein the set of values sent to the second processing device comprises X, Z_in, s and r_in and a valid solution I to the first problem is given by:

I=H_in(X,n;

s,r_in)≦

Z_in

where Z_in is a target value representing the difficulty of solving the first problem.

15. An article of manufacture comprising a processor-readable storage medium having processor-readable program code embodied therein, which, when executed by a processor of a first processing device, causes the processor:

to receive, from a second processing device, a request for access to a given resource controlled by the first processing device;

to send, to the second processing device, a set of values responsive to receiving the request for access to the given resource, the set of values being usable to compute a solution to a first problem involving inversion of a first one-way function;

to receive, from the second processing device, a given value representing a potential solution to the first problem;

to provide access to the given resource by the second processing device responsive to verifying the given value as a valid solution to the first problem; and

to utilize the given value as an input for computing a solution to a second problem involving inversion of a second one-way function;

wherein a valid solution to the second problem uses as input the valid solution to the first problem; and

wherein the set of values comprises a supplementary value specific to a particular instance of the first one-way problem and the second processing device, the supplementary value being used as an input to the first one-way function by the second processing device.

16. The article of manufacture of claim 15, wherein the valid solution to the second problem is usable in a system for mining digital currency involving finding a solution to a third problem involving inversion of a third one-way function.

17. The article of manufacture of claim 15, wherein the given resource comprises accepting an e-mail sent to the first processing device from the second processing device.

18. An apparatus comprising:

a first processing device comprising;

a memory; and

a processor coupled to the memory;

the first processing device being configured to implement a puzzlet generation module configured;

to receive, from a second processing device, a request for access to a given resource controlled by the first processing device; and

to send a set of values to the second processing device responsive to receiving the request for access to the given resource, the set of values being usable to compute a solution to a first problem involving inversion of a first one-way function;

the first processing device being further configured to implement a puzzlet verification module configured;

to receive a given value from the second processing device representing a potential solution to the first problem;

to provide access to the given resource by the second processing device responsive to verifying the given value as a valid solution to the first problem; and

to utilize the given value as an input for computing a solution to a second problem involving inversion of a second one-way function;

wherein a valid solution to the second problem uses as input a valid solution to the first problem; and

wherein the set of values comprises a supplementary value specific to a particular instance of the first one-way problem and the second processing device, the supplementary value being used as an input to the first one-way function by the second processing device.

19. The apparatus of claim 18, wherein the valid solution to the second problem is usable in a system for mining digital currency involving finding a solution to a third problem involving inversion of a third one-way function.

20. The apparatus of claim 19, wherein the first processing device is part of a pool of processing devices used by a first party for mining the digital currency.