Coercion resistant one-time-pad cryptosystem that facilitates transmission of messages having different levels of security

• US 6,021,203 A
• Filed: 12/11/1996
• Issued: 02/01/2000
• Est. Priority Date: 12/11/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Calligaro, Michael P., Douceur, John R., Thomlinson, Matthew W.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): CALLAHAN, PAUL E
• Application Number:
  US08/763,333
• Time in Patent Office: 1,147 Days
• Field of Search: 380/43, 380/59, 380/21, 380/28, 380/4, 380/9, 380/44, 380/49
• US Class Current: 380/252
• CPC Class Codes: H04L 9/0656 Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher

Abstract

A protocol is provided for transmitting low security messages and high security messages with one-time-pad cryptosystem. In one implementation of the present invention, low security messages are encrypted using random bit strings in accordance with a one-time-pad encryption scheme. A high security message and a decoy message are embedded within a set of encryption keys and cyphertexts that is to be transmitted from a sender to a receiver. The encryption keys are transmitted over a secure channel from the sender to the receiver, and the cyphertexts are transmitted over a publicly accessible channel from the sender to the receiver. The receiver uses the encryption keys and knowledge regarding keys for a high security message and a decoy message to decrypt the low security messages, extract the high security message and/or decoy message, and decrypt the high security message and/or decoy message. The provision of the decoy message is revealed when duress is applied to coerce the receiver into revealing the key for a supposedly high security message.

Claims

1. In a one-time pad (OTP) cryptosystem for use with a sending computer system and a receiving computing system connected via a communications link, a method comprising the steps of:

composing a high security message and a decoy message;

providing random bit strings and low security messages;

producing a set of OTP keys and cyphertexts from the high security message, the decoy message, the random bit strings and the low security messages, wherein the high security message and the decoy message are embedded in the set of OTP keys and cyphertexts, and wherein the high security message is distributed among a subset of the OTP keys and the cyphertexts; and

transmitting the OTP keys and the cyphertexts over the communications link to the receiver.

19. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 1.

2. In a one-time pad (OTP) cryptosystem for use with a sending computer system and a receiving computing system connected via a communications link, a method comprising the steps of:

composing a high security message and a decoy message;

providing random bit strings and low security messages;

producing a set of OTP keys and cyphertexts from the high security message, the decoy message, the random bit strings and the low security messages, wherein the high security message and the decoy message are embedded in the set of OTP keys and cyphertexts, and wherein the decoy message is distributed among a subset of the OTP keys and the cyphertexts; and

transmitting the OTP keys and the cyphertexts over the communications link to the receiver.

20. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 2.

3. In a computer system, a method comprising:

generating, using a plurality of keys, a plurality of cyphertexts for transmission to a receiver;

embedding a message within the plurality of keys; and

transmitting the plurality of keys to the receiver.

4. The method of claim 3 wherein the cyphertexts are generated in accordance with a one-time-pad encryption protocol.

5. The method of claim 4 wherein the cyphertexts are generated using an exclusive OR function.

6. The method of claim 3 further comprising embedding multiple secure messages within the plurality of keys.

7. The method of claim 3 wherein the message includes a decoy message and a high security message.

17. The method of claim 3, further comprising transmitting the plurality of cyphertexts to the receiver.

18. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 3.

8. In a computer system, a method comprising:

receiving a plurality of cyphertexts;

receiving a plurality of encryption keys within which is embedded at least one secure message;

decrypting, using the plurality of encryption keys, a number of the plurality of cyphertexts to yield plaintext messages; and

extracting the at least one secure message from the plurality of encryption keys.

9. The method of claim 8 wherein the plurality of cyphertexts are encrypted using a one-time pad (OTP) encryption scheme and the plurality of encryption keys comprise a plurality of OTP keys.

10. The method of claim 8 wherein the plurality of encryption keys are received separately from the plurality of cyphertexts.

11. The method of claim 8 wherein multiple secure messages are embedded in the plurality of encryption keys.

12. The method of claim 11 wherein the multiple secure messages are extracted from the plurality of encryption keys.

13. The method of claim 11 wherein at least one of the multiple secure messages is a decoy message.

14. The method of claim 8, further comprising revealing information to a third party to enable the third party to decrypt one of the at least one secure messages that is a decoy message.

21. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 8.

15. In a one-time pad (OTP) cryptosystem for use with a sending computer system and a receiving computing system connected via a communications link, a computer-readable medium holding computer-executable instructions for performing, a method comprising the steps of:

composing a high security message and a decoy message;

providing random bit strings and low security messages;

producing a set of OTP keys and cyphertexts from the high security message, the decoy message, the random bit strings and the low security messages, wherein the high security message and the decoy message are embedded in the set of OTP keys and cyphertexts, wherein the high security message is distributed among a subset of the OTP keys and the cyphertexts; and

transmitting the OTP keys and the cyphertexts over the communications link to the receiver.

22. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 15.

16. In a one-time pad (OTP) cryptosystem for use with a sending computer system and a receiving computing system connected via a communications link, a computer-readable medium holding computer-executable instructions for performing, a method comprising the steps of:

composing a high security message and a decoy message;

providing random bit strings and low security messages;

producing a set of OTP keys and cyphertexts from the high security message, the decoy message, the random bit strings and the low security messages, wherein the high security message and the decoy message are embedded in the set of OTP keys and cyphertexts, wherein the decoy message is distributed among a subset of the OTP keys and the cyphertexts; and

transmitting the OTP keys and the cyphertexts over the communications link to the receiver.

23. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 16.

24. A method comprising:

generating a plurality of keys;

generating, using the plurality of keys, a plurality of cyphertexts; and

transmitting, as a set of keys, the plurality of keys and an encrypted high security message to a receiver.

25. The method of claim 24, further comprising transmitting, as part of the set of keys, an encrypted decoy message.

26. The method of claim 24, further comprising generating the encrypted high security message by encrypting a high security message based at least in part on the plurality of keys.

27. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 24.

28. In a system having a sender and a receiver, a method comprising:

generating a first key;

generating a plurality of additional keys;

generating, based at least in part on the plurality of additional keys, a plurality of cyphertexts for transmission from the sender to the receiver;

determining, based at least in part on the first key, whether to embed a secure message within the plurality of additional keys or the plurality of cyphertexts;

embedding the secure message within either the plurality of additional keys or the plurality of cyphertexts based on the determining; and

transmitting the plurality of additional keys and the plurality of cyphertexts to the receiver.

29. The method of claim 28 wherein the transmitting comprises transmitting the plurality of additional keys over a secure channel to the receiver.

30. The method of claim 28 wherein the transmitting comprises transmitting the plurality of cyphertexts over a non-secure channel to the receiver.

31. The method of claim 28 wherein the generating the plurality of additional keys comprises assigning at least one of the plurality of additional keys a random value.

32. The method of claim 31 wherein the generating the plurality of additional keys comprises assigning each of the plurality of additional keys a different random value.

33. The method of claim 28 wherein the generating the plurality of cyphertexts comprises generating at least one of the cyphertexts by exclusive ORing one of the plurality of additional keys with a low security message.

34. The method of claim 28 wherein the generating the plurality of additional keys comprises, for a selected one of the plurality of additional keys, producing the selected one by exclusive ORing the secure message with at least one of the plurality of cyphertexts and at least one of the plurality of additional keys.

35. The method of claim 28 wherein the generating the plurality of cyphertexts comprises, for a selected one of the plurality of cyphertexts, producing the selected one by exclusive ORing the secure message with at least one of the plurality of cyphertexts and at least one of the plurality of additional keys.

36. The method of claim 28 wherein the generating the plurality of additional keys comprises, for a selected one of the plurality of additional keys, producing the selected one by exclusive ORing a decoy message with at least one of the plurality of cyphertexts and at least one of the plurality of additional keys.

37. The method of claim 28 wherein the generating the plurality of cyphertexts comprises, for a selected one of the plurality of cyphertexts, producing the selected one by exclusive ORing a decoy message with at least one of the plurality of cyphertexts and at least one of the plurality of additional keys.

38. The method of claim 28, further comprising:

determining, based at least in part on a second key, whether to embed a decoy message within the plurality of additional keys or the plurality of cyphertexts; and

embedding the decoy message within either the plurality of additional keys or the plurality of cyphertexts.

39. The method of claim 38 wherein the determining whether to embed the decoy message in the plurality of additional keys or the plurality of cyphertexts comprises:

dividing the second key into a first portion and a second portion;

comparing each bit in the first portion with a corresponding bit in the second portion;

identifying a set of bits in the first portion that differ from the corresponding bits in the second portion;

selecting one bit of the set of bits; and

if the selected one bit of the set of bits has a first value, then determining to embed the decoy message in the plurality of additional keys, otherwise determining to embed the decoy message in the plurality of cyphertexts.

40. The method of claim 28 wherein the determining whether to embed the secure message in the plurality of additional keys or the plurality of cyphertexts comprises:

dividing the first key into a first portion and a second portion;

comparing each bit in the first portion with a corresponding bit in the second portion;

identifying a set of bits in the first portion that differ from the corresponding bits in the second portion;

selecting one bit of the set of bits; and

if the selected one bit of the set of bits has a first value, then determining to embed the secure message in the plurality of additional keys, otherwise determining to embed the secure message in the plurality of cyphertexts.

41. The method of claim 40 wherein each bit in at least a subset of bits in the first portion corresponds to one of the plurality of cyphertexts and each bit in at least a subset of bits in the second portion corresponds to one of the plurality of additional keys.

42. The method of claim 40 wherein the first portion comprises a first half of the first key and the second portion comprises a second half of the first key.

43. The method of claim 40 wherein the first value comprises zero.

44. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 28.

45. A computer system comprising:

a processor;

a memory device, coupled to the processor, storing one or more programs that, when executed by the processor, cause the processor to;

generate a first key;

generate a plurality of additional keys;

generate a plurality of cyphertexts for transmission from the computer system to a receiver;

determine, based at least in part on the first key, whether to embed a high security message within the plurality of additional keys or the plurality of cyphertexts;

embed the high security message within either the plurality of additional keys or the plurality of cyphertexts based on the determining; and

transmit the plurality of additional keys and the plurality of cyphertexts to the receiver.

46. The computer system of claim 45, wherein the one or more programs, when executed by the processor, further cause the processor to:

determine, based at least in part on a second key, whether to embed a decoy message within the plurality of additional keys or the plurality of cyphertexts; and

embed the decoy message within either the plurality of additional keys or the plurality of cyphertexts.

47. In a system having a sender and a receiver, a method comprising:

receiving a first key from the sender;

receiving a plurality of additional keys from the sender;

receiving a plurality of cyphertexts from the sender;

determining, based at least in part on the first key, whether a secure message is embedded within the plurality of additional keys or the plurality of cyphertexts; and

retrieving the secure message from either the plurality of additional keys or the plurality of cyphertexts based on the determining.

48. The system of claim 47 wherein the receiving the plurality of additional keys from the sender comprises receiving the plurality of additional keys from the sender over a secure channel to the receiver.

49. The system of claim 47 wherein the receiving the plurality of cyphertexts from the sender comprises receiving the plurality of cyphertexts from the sender over a non-secure channel.

50. The system of claim 47, further comprising:

determining, based at least in part on a second key, whether a decoy message is embedded within the plurality of additional keys or the plurality of cyphertexts; and

retrieving the decoy message from either the plurality of additional keys or the plurality of cyphertexts.

51. The method of claim 50 wherein the determining whether the decoy message is embedded within the plurality of additional keys or the plurality of cyphertexts comprises:

dividing the second key into a first portion and a second portion;

comparing each bit in the first portion with a corresponding bit in the second portion;

identifying a set of bits in the first portion that differ from the corresponding bits in the second portion;

selecting one bit of the set of bits; and

if the selected one bit of the set of bits has a first value, then determining the decoy message is embedded within the plurality of additional keys, otherwise determining the decoy message is embedded within the plurality of cyphertexts.

52. The method of claim 47 wherein the determining whether the secure message is embedded within the plurality of additional keys or the plurality of cyphertexts comprises:

dividing the first key into a first portion and a second portion;

comparing each bit in the first portion with a corresponding bit in the second portion;

identifying a set of bits in the first portion that differ from the corresponding bits in the second portion;

selecting one bit of the set of bits; and

if the selected one bit of the set of bits has a first value, then determining the secure message is embedded within the plurality of additional keys, otherwise determining the secure message is embedded within the plurality of cyphertexts.

53. The method of claim 52 wherein each bit in at least a subset of bits in the first portion corresponds to one of the plurality of cyphertexts and each bit in at least a subset of bits in the second portion corresponds to one of the plurality of additional keys.

54. The method of claim 52 wherein the first portion comprises a first half of the first key and the second portion comprises a second half of the first key.

55. The method of claim 52 wherein the first value comprises zero.

56. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 53.

57. A system comprising:

a sending computer system to,

generate a plurality of keys,

generate a plurality of low security message cyphertexts based at least in part on both the plurality of keys and a plurality of low security messages,

generate a cyphertext for a high security message based at least in part on the plurality of keys and the plurality of low security message cyphertexts, and

generate a cyphertext for a decoy message based at least in part on the plurality of keys and the plurality of low security message cyphertexts; and

a receiving computer system to,

receive the plurality of keys, the plurality of low security message cyphertexts, the cyphertext for the high security message, and the cyphertext for the decoy message from the sending computer system, and

decrypt the high security message from the cyphertext for the high security message.

58. The system of claim 57 wherein the plurality of keys comprise a plurality of one-time pad (OTP) keys.

59. The system of claim 57 wherein the sending computer system is further to embed the cyphertext for the high security message in the plurality of keys.

60. The system of claim 57, wherein the sending computer system is further to embed the cyphertext for the decoy message in the plurality of keys.

61. One or more computer-readable storage media having stored thereon a computer program, the program comprising the following steps:

identifying a first key corresponding to a high security message;

identifying a second key corresponding to a decoy message;

generating a plurality of one-time pad (OTP) keys;

generating a plurality of cyphertexts based at least in part on both the plurality of OTP keys and a plurality of low security messages;

determining, using the first key, whether to embed the high security message in the plurality of OTP keys or the plurality of cyphertexts;

determining, using the second key, whether to embed the decoy message in the plurality of OTP keys or the plurality of cyphertexts;

encrypting the high security message using both the plurality of cyphertexts and the plurality of OTP keys;

embedding the high security message in either the plurality of OTP keys or the plurality of cyphertexts;

encrypting the decoy message using both the plurality of cyphertexts and the plurality of OTP keys; and

embedding the decoy message in either the plurality of OTP keys or the plurality of cyphertexts.

62. The computer-readable storage media of claim 61 wherein the determining whether to embed the high security message in the plurality of OTP keys or the plurality of cyphertexts comprises:

dividing the first key into a first half and a second half;

comparing each bit in the first half with a corresponding bit in the second half;

identifying a set of bits in the first half that differ from the corresponding bits in the second half;

selecting one bit of the set of bits; and

if the selected one bit of the set of bits has a value of zero, then determining to embed the high security message in the plurality of OTP keys, otherwise determining to embed the high security message in the plurality of cyphertexts.

63. The computer-readable storage media of claim 62 wherein each of at least a subset of bits in the first half corresponds to one of the plurality of cyphertexts and each of at least a subset of bits in the second half corresponds to one of the plurality of OTP keys.

64. The computer-readable storage media of claim 61 wherein:

the determining whether to embed the high security message in the plurality of OTP keys or the plurality of cyphertexts comprises;

dividing the first key into a first half and a second half;

comparing each bit in the first half of the first key with a corresponding bit in the second half of the first key;

identifying a first set of bits in the first half of the first key that differ from the corresponding bits in the second half of the first key;

selecting one bit of the first set of bits;

if the selected one bit of the first set of bits has a value of zero, then determining to embed the high security message in the plurality of OTP keys, otherwise determining to embed the high security message in the plurality of cyphertexts; and

the determining whether to embed the decoy message in the plurality of OTP keys or the plurality of cyphertexts comprises;

dividing the second key into a first half and a second half;

comparing each bit in the first half of the second key with a corresponding bit in the second half of the second key;

identifying a second set of bits in the first half of the second key that differ from the corresponding bits in the second half of the second key;

selecting one bit of the second set of bits; and

if the selected one bit of the second set of bits has a value of zero, then determining to embed the decoy message in the plurality of OTP keys, otherwise determining to embed the decoy message in the plurality of cyphertexts.