Continuous space-bounded non-malleable codes from stronger proofs-of-space

1. A method for decoding a secret, the method comprising performing on a decoding computer:

storing a codeword C comprising a proof value π and a secret S in a persistent memory of the decoding computer, the persistent memory comprising P bytes of memory, wherein the codeword C uses c bytes, wherein the proof value π is determined using the secret S and a result Y, the result Y obtained by applying a memory-hard function MHF to the secret S or to a function of the secret S, wherein the proof value π is proof-extractable, wherein the applying the memory-hard function MHF to the secret S requires at least N bytes of memory, and wherein more than one proof value is combinable with the secret S to provide a valid codeword;

receiving input data;

retrieving the codeword C from the persistent memory;

parsing the codeword C to identify the proof value π and the secret S;

performing, using a transient memory of the decoding computer, a decoding of the codeword C by:

using the proof value π to verify a correctness of the result Y as being obtained from the memory-hard function MHF using the secret S, wherein a decoding function is operable to use K bytes of memory, K being less than N;

when the correctness is true, applying a cryptographic function to the input data using the secret S to obtain output data; and

when the correctness is false, providing an error message; and

refreshing the transient memory of the decoding computer.

2. The method of claim 1 , further comprising performing on an encoding computer:

applying the memory-hard function MHF to the secret S or to a function of the secret S to obtain the result Y, wherein the applying of the memory-hard function MHF to the secret S requires the at least N bytes of memory on the encoding computer;

determining, using a proof function, a proof value π using the secret S and the result Y;

assembling the codeword C from the proof value π and the secret S; and

sending the codeword C to a device that is configured to store the codeword C in the persistent memory of the device and later decode the codeword C, wherein the proof value π is configured to be used by the decoding function of the device to verify the correctness of the result Y as being obtained from the memory-hard function MHF using the secret S.

3. The method of claim 1 , wherein E is 100 times smaller than the proof value π.

4. The method of claim 1 , wherein a size of the proof value π is smaller than P.

5. The method of claim 1 , wherein the memory-hard function MHF is a graph labeling function applied to a graph comprising a plurality of nodes, the result Y is a hash of a graph labeling, and the proof value π comprises a subset of the graph labeling.

6. The method of claim 5 , wherein verifying the correctness of the result Y further comprises:

randomly selecting nodes from the graph;

computing a partial labeling of the graph using the selected nodes; and

comparing the partial labeling of the graph to the proof value π.

7. The method of claim 5 , wherein the graph is a challenge-hard graph comprising a plurality of challenge nodes, wherein determining a graph labeling for the plurality of challenge nodes requires at least N bytes of memory and wherein determining a graph labeling for the plurality of challenge nodes occurs with exponential time.

8. The method of claim 7 , wherein the proof value π is determined with the entire result Y.

9. The method of claim 1 , wherein the proof value π is at least 100 MB.

10. The method of claim 1 , wherein the codeword C is stored in secure memory, and wherein a secure element performs the decoding of the codeword C and the applying of the cryptographic function.

11. A computer product comprising a non-transitory computer-readable medium storing a plurality of instructions for controlling a decoder computer to perform a method comprising:

storing a codeword C comprising a proof value π and a secret S in a persistent memory of the decoding computer, the persistent memory comprising P bytes of memory, wherein the codeword C uses c bytes, wherein the proof value π is determined using the secret S and a result Y, the result Y obtained by applying a memory-hard function MHF to the secret S or to a function of the secret S, wherein the proof value π is proof-extractable, wherein the applying the memory-hard function MHF to the secret S requires at least N bytes of memory, and wherein more than one proof value is combinable with the secret S to provide a valid codeword;

receiving input data;

retrieving the codeword C from the persistent memory;

parsing the codeword C to identify the proof value π and the secret S;

performing, using a transient memory of the decoding computer, a decoding of the codeword C by:

using the proof value π to verify a correctness of the result Y as being obtained from memory-hard function MHF using the secret S, wherein a decoding function is operable to use K bytes of memory, K being less than N;

when the correctness is true, applying a cryptographic function to the input data using the secret S to obtain output data; and

when the correctness is false, providing an error message; and

refreshing the transient memory of the decoding computer.

12. A device comprising:

a secure memory storing a codeword C comprising a proof value π and a secret S in a persistent memory, the persistent memory comprising P bytes of memory, wherein the codeword C uses c bytes, wherein the proof value π is determined using the secret S and a result Y, the result Y obtained by applying a memory-hard function MHF to the secret S or to a function of the secret S, wherein the proof value π is proof-extractable, wherein the applying the memory-hard function MHF to the secret S requires at least N bytes of memory, and wherein more than one proof value is combinable with the secret S to provide a valid codeword; and

a secure element configured to:

receive input data;

retrieve the codeword C from the persistent memory;

parse the codeword C to identify the proof value π and the secret S;

perform, using a transient memory of the device, a decoding of the codeword C by:

using the proof value π to verify a correctness of the result Y as being obtained from the memory-hard function MHF using the secret S, wherein a decoding function is operable to use K bytes of memory, K being less than N;

when the correctness is true, applying a cryptographic function to the input data using the secret S to obtain output data; and

when the correctness is false, providing an error message; and

refresh the transient memory of the device.

13. The device of claim 12 , wherein the codeword C is assembled by an encoding computer by a method that comprises:

applying the memory-hard function MHF to the secret S or to a function of the secret S to obtain the result Y, wherein the applying of the memory-hard function MHF to the secret S requires at least N bytes of memory on the encoding computer;

determining, using a proof function, a proof value π using the secret S and the result Y;

assembling the codeword C from the proof value π and the secret S; and

sending the codeword C to a device that is configured to store the codeword C in the persistent memory of the device and later decode the codeword C, wherein the proof value π is configured to be used by the decoding function of the device to verify the correctness of the result Y as being obtained from the memory-hard function MHF using the secret S.

14. The device of claim 12 , wherein E is 100 times smaller than the proof value π.

15. The device of claim 12 , wherein a size of the proof value π is smaller than P.

16. The device of claim 12 , wherein the memory-hard function MHF is a graph labeling function applied to a graph comprising a plurality of nodes, the result Y is a hash of a graph labeling, and the proof value π comprises a subset of the graph labeling.

17. The device of claim 16 , wherein verifying the correctness of the result Y further comprises:

randomly selecting nodes from the graph;

computing a partial labeling of the graph using the selected nodes; and

comparing the partial labeling of the graph to the proof value π.

18. The device of claim 16 wherein the graph is a challenge-hard graph comprising a plurality of challenge nodes, wherein determining a graph labeling for the plurality of challenge nodes requires at least N bytes of memory and wherein determining a graph labeling for the plurality of challenge nodes occurs with exponential time.

19. The device of claim 12 , wherein the proof value π is at least 100 MB.

20. The device of claim 12 , wherein the codeword C is stored in secure memory, and wherein the secure element performs the decoding of the codeword C and the applying of the cryptographic function.