Computing solutions to a problem involving inversion of a one-way function
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.
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 0 (r), r out =H 1 (r), H 0 and H 1 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.