One-time programs

• US 8,762,736 B1
• Filed: 04/02/2009
• Issued: 06/24/2014
• Est. Priority Date: 04/04/2008
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Goldwasser, Shafi, Kalai, Yael Tauman, Rothblum, Guy Nathanel
• Primary Examiner(s): KIM, TAE K
• Application Number:
  US12/417,152
• Time in Patent Office: 1,909 Days
• Field of Search: 726/2, 726/3, 726/4, 726/5, 726/9, 726/16, 726/17, 726/20, 726/27, 726/29, 726/30, 726/31, 713/182, 713/184, 713/185, 713/189, 713/190, 235/375, 235/380, 235/382, 235/382.5
• US Class Current: 713/189
• CPC Class Codes: G06F 21/14 against software analysis or reverse engineering, e.g. by obfuscation
• CPC Class Codes: G06F 21/556 involving covert channels, i.e. data leakage between processes inhibiting the analysis of circuitry or operation with measures against power attack G06F21/755
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box
• CPC Class Codes: H04L 9/003 for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

Abstract

A method, apparatus and computer program product for providing one-time programs is presented. A program to be converted to a new program having a predetermined lifetime is identified. The program is compiled to produce the new program having a predetermined lifetime and wherein the new program having a predetermined lifetime is guaranteed to only have the predetermined lifetime.

Claims

1. A computer-implemented method in which a computer system performs operations comprising:

identifying a program to be converted to a new program having a predetermined lifetime; and

compiling, by said computer system in communication with a secure hardware device wherein said secure hardware device comprises a One-Time Memory (OTM), said OTM initialized with two keys k₀ and k₁ and a tamper proof bit set to a value of zero, wherein said OTM receives an input bit b, verifies said tamper proof bit is zero, sets said tamper proof bit to a 1, and outputs a key k_b based on said two keys and said input bit, said program to produce said new program having a predetermined lifetime and wherein said new program having a predetermined lifetime is guaranteed to only have the predetermined lifetime and wherein said predetermined lifetime comprises a predetermined number of uses and wherein said program is executed at most k times, wherein k is equal to or greater than one,

wherein said secure hardware device stores security data and wherein execution of said program having a predetermined lifetime requires use of at least a portion of said security data.

2. The method of claim 1 wherein said secure hardware device prevents arbitrary access to said security data.

3. The method of claim 1 further comprising utilizing said new program having a predetermined lifetime to perform a one-time proof (OTP), wherein said OTP comprises a system with a predetermined lifetime that allows proving a validity of a statement.

4. The method of claim 3 wherein said OTP is selected from the group consisting of proving an identity, providing credentials, knowing a secret, and having authority to access a resource.

5. The method of claim 3 wherein said OTP is used to provide at least one electronic token.

6. The method of claim 5, wherein said electronic token is useful for providing at least one of the group consisting of a limited number of purchases, a limited number of entrance passes, a limited number of accesses to information and a limited number of abilities to compute.

7. The method of claim 1 wherein said new program having a predetermined lifetime is selected from the group consisting of a program allowing someone to run only a limited number of computations, a program allowing someone to run a program that uses a secret key in a controlled manner, and a program delegating the ability produce digital signatures in a controlled manner.

8. The method of claim 1 wherein said new program having a predetermined lifetime is used as an electronic blank check that are issued and later used to sign a document.

9. The method of claim 3 wherein said OTP is used to prove a statement related to a secret key.

10. The method of claim 2 wherein said secure hardware device utilizes tamper proof bits to prevent access to other keys.

11. The method of claim 10 wherein said secure hardware device prevents side channel attacks.

12. The method of claim 1 wherein side channel security is achieved by using data a limited number of times.

13. The method of claim 1 wherein adversaries are restricted to side channel attacks and can only make observations on events that are influenced by data the device computed on.

14. The method of claim 1 wherein said security data on said hardware device is encrypted.

15. The method of claim 14 wherein another device is used to decrypt said security data.

16. The method of claim 1 wherein said secure hardware device is accessed over a network.

17. The method of claim 1 wherein after said device outputs the key k_b said device self-destructs.

18. A non-transitory computer readable storage medium having computer readable code thereon for providing a program having a predetermined lifetime, the medium including instructions in which a computer system performs operations comprising-implemented method in which a computer system performs operations comprising:

identifying a program to be converted to a new program having a predetermined lifetime; and

compiling said program by said computer system in communication with a secure hardware device wherein said secure hardware device comprises a One-Time Memory (OTM), said OTM initialized with two keys k₀ and k₁ and a tamper proof bit set to a value of zero, wherein said OTM receives an input bit b, verifies said tamper proof bit is zero, sets said tamper proof bit to a 1, and outputs a key k_b based on said two keys and said input bit, to produce said new program having a predetermined lifetime and wherein said new program having a predetermined lifetime is guaranteed to only have the predetermined lifetime and wherein said predetermined lifetime comprises a predetermined number of uses and wherein said program is executed at most k times, wherein k is equal to or greater than one,

wherein said secure hardware device stores security data and wherein execution of said program having a predetermined lifetime requires use of at least a portion of said security data.

19. The computer readable storage medium of claim 18 wherein said secure hardware device prevents arbitrary access to said security data.

20. The computer readable storage medium of claim 18 further comprising utilizing said new program having a predetermined lifetime to perform a one-time proof (OTP), wherein said OTP comprises a system with a predetermined lifetime that allows proving a validity of a statement.

21. The computer readable storage medium of claim 20 wherein said OTP is selected from the group consisting of proving an identity, providing credentials, knowing a secret, and having authority to access a resource.

22. The computer readable storage medium of claim 20 wherein said OTP is used to provide at least one electronic token.

23. The computer readable storage medium of claim 22, wherein said electronic token is useful for providing at least one of the group consisting of a limited number of purchases, a limited number of entrance passes, a limited number of accesses to information and a limited number of abilities to compute.

24. The computer readable storage medium of claim 18 wherein said new program having a predetermined lifetime is selected from the group consisting of a program allowing someone to run only a limited number of computations, a program allowing someone to run a program that uses a secret key in a controlled manner, and a program delegating the ability produce digital signatures in a controlled manner.

25. The computer readable storage medium of claim 18 wherein said new program having a predetermined lifetime is used as an electronic blank check that are issued and later used to sign a document.

26. The computer readable storage medium of claim 20 wherein said OTP is used to prove a statement related to a secret key.

27. The computer readable storage medium of claim 19 wherein said secure hardware device utilizes tamper proof bits to prevent access to other keys.

28. The computer readable storage medium of claim 27 wherein said secure hardware device prevents side channel attacks.

29. The computer readable storage medium of claim 18 wherein side channel security is achieved by using data a limited number of times.

30. The computer readable storage medium of claim 18 wherein adversaries are restricted to side channel attacks and can only make observations on events that are influenced by data the device computed on.

31. The computer readable storage medium of claim 18 wherein said security data on said hardware device is encrypted.

32. The computer readable storage medium of claim 31 wherein another device is used to decrypt said security data.

33. The computer readable storage medium of claim 18 wherein said secure hardware device is accessed over a network.

34. The computer readable medium of claim 18 further comprising instructions wherein after said device outputs the key k_b said device self-destructs.

35. A computer system comprising:

a memory;

a processor;

a communications interface;

an interconnection mechanism coupling the memory, the processor and the communications interface; and

wherein the memory is encoded with an application providing a program having a predetermined lifetime, that when performed on the processor, provides a process for processing information, the process causing the computer system to perform the operations of;

identifying a program to be converted to a new program having a predetermined lifetime; and

compiling said program by said computer system in communication with a secure hardware device wherein said secure hardware device comprises a One-Time Memory (OTM), said OTM initialized with two keys k₀ and k₁ and a tamper proof bit set to a value of zero, wherein said OTM receives an input bit b, verifies said tamper proof bit is zero, sets said tamper proof bit to a 1, and outputs a key k_b based on said two keys and said input bit, to produce said new program having a predetermined lifetime and wherein said new program having a predetermined lifetime is guaranteed to only have the predetermined lifetime and wherein said predetermined lifetime comprises a predetermined number of uses and wherein said program is executed at most k times, wherein k is equal to or greater than one,

wherein said secure hardware device stores security data and wherein execution of said program having a predetermined lifetime requires use of at least a portion of said security data.

36. The computer system of claim 35 wherein said secure hardware device prevents arbitrary access to said security data.

37. The computer system of claim 35 further comprising utilizing said new program having a predetermined lifetime to perform a one-time proof (OTP), wherein said OTP comprises a system with a predetermined lifetime that allows proving a validity of a statement.

38. The computer system of claim 37 wherein said OTP is selected from the group consisting of proving an identity, providing credentials, knowing a secret, and having authority to access a resource.

39. The computer system of claim 37 wherein said OTP is used to provide at least one electronic token.

40. The computer system of claim 39, wherein said electronic token is useful for providing at least one of the group consisting of a limited number of purchases, a limited number of entrance passes, a limited number of accesses to information and a limited number of abilities to compute.

41. The computer system of claim 35 wherein said new program having a predetermined lifetime is selected from the group consisting of a program allowing someone to run only a limited number of computations, a program allowing someone to run a program that uses a secret key in a controlled manner, and a program delegating the ability produce digital signatures in a controlled manner.

42. The computer system of claim 35 wherein said new program having a predetermined lifetime is used as an electronic blank check that are issued and later used to sign a document.

43. The computer system of claim 37 wherein said OTP is used to prove a statement related to a secret key.

44. The computer system of claim 36 wherein said secure hardware device utilizes tamper proof bits to prevent access to other keys.

45. The computer system of claim 44 wherein said secure hardware device prevents side channel attacks.

46. The computer system of claim 35 wherein side channel security is achieved by using data a limited number of times.

47. The computer system of claim 35 wherein adversaries are restricted to side channel attacks and can only make observations on events that are influenced by data the device computed on.

48. The computer system of claim 35 wherein said security data on said hardware device is encrypted.

49. The computer system of claim 48 wherein another device is used to decrypt said security data.

50. The computer system of claim 35 wherein said secure hardware device is accessed over a network.

51. The computer system of claim 35 wherein after said device outputs the key k_b said device self-destructs.