Encryption method and apparatus using composition of ciphers

• US 8,681,975 B2
• Filed: 08/31/2009
• Issued: 03/25/2014
• Est. Priority Date: 08/31/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Farrugia, Augustin J., Sullivan, Nicholas, Fasoli, Gianpaolo, Ciet, Mathieu
• Primary Examiner(s): Kim, Jung
• Assistant Examiner(s): PARSONS, THEODORE C
• Application Number:
  US12/551,360
• Publication Number:
  US 20110051931A1
• Time in Patent Office: 1,667 Days
• Field of Search: 380/255, 380/42, 280/255
• US Class Current: 380/42
• CPC Class Codes: H04L 2209/603 Digital right managament [DRM]
• CPC Class Codes: H04L 63/0464 using hop-by-hop encryption, i.e. wherein an intermediate entity decrypts the information and re-encrypts it before forwarding it
• CPC Class Codes: H04L 9/0822 using key encryption key
• CPC Class Codes: H04L 9/0827 involving distinctive intermediate devices or communication paths network architectures or network communication protocols using different networks H04L63/18
• CPC Class Codes: H04L 9/083 involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]

Abstract

A method and associated apparatus for use in a data distribution process to allow an untrusted intermediary to re-encrypt data for transmission from an originator to a message receiver without revealing the data (message) or the cipher to the intermediary. This method uses a composition of two ciphers for re-encrypting the message at the intermediary, without revealing the plain text message or either cipher to the intermediary.

Claims

1. A method of distributing a message from a message originating computing device through at least two separate intermediary computing devices to a message receiving computing device, the computing devices coupled in a sequence, the method comprising:

at each particular intermediary computing device in the sequence of computing devices;

receiving the message ciphered with a previous substitution cipher applied to the message on a previous computing device in the sequence of computing devices, the received message comprising a plurality of units, each unit including at least two bits of information;

re-ciphering the received message with a composition cipher that comprises a composition of an inverse of the previous substitution cipher and a substitution cipher, associated with the particular intermediary computing device, that replaces each of a plurality of the units of the received message with a ciphered unit according to a predetermined system that maps different possible values for message units to different cipher values for the message units, wherein the composition cipher is part of a sequence of composition ciphers that are each for use on a different intermediary computing device, and wherein the composition ciphers conceal their constituent substitution ciphers and the inverse ciphers; and

transmitting the re-ciphered message to a next computing device in the sequence of computing devices over a data connection.

2. The method of claim 1, wherein, at each particular intermediary computing device, the composition cipher is such that its application to the received message results in the message being ciphered only in the substitution cipher associated with the particular intermediary computing device.

3. The method of claim 1, wherein the message is received at an input port of each particular intermediary computing device from a previous computing device in the sequence of computing devices.

4. The method of claim 1, wherein the composition cipher is at least one of a transitive function and a homomorphic function.

5. The method of claim 1 further comprising, at each particular intermediary computing device in the sequence of computing devices:

storing the received message in a first storage; and

storing the re-ciphered message in a second storage prior to transmitting the re-ciphered message to the next computing device in the sequence of computing devices.

6. The method of claim 1 further comprising, at each particular intermediary computing device in the sequence of computing devices:

prior to receiving the ciphered message, receiving the composition cipher; and

storing the composition cipher for later use in re-ciphering the ciphered message.

7. The method of claim 1, wherein the message comprises digital rights management data.

8. The method of claim 1, wherein an inverse of a last substitution cipher in the sequence of composition ciphers is for use in deciphering the message on the message receiving computing device.

9. The method of claim 1, wherein a first intermediary computing device in the sequence of computing devices receives the message ciphered with a substitution cipher applied by the message originating computing device.

10. A system for securely transmitting a message through a sequence of computing devices, the system comprising:

a message originating computing device to (i) generate a message comprising a plurality of units, each unit including at least two bits of information, (ii) generate a sequence of substitution ciphers that each correspond to a different intermediary computing device, (iii) distribute each substitution cipher to its corresponding intermediary computing device, (iv) cipher the message with a first substitution cipher, and (v) transmit the ciphered message to a first intermediary computing device;

a plurality of intermediary computing devices coupled in a sequence, each particular intermediary computing device to (i) receive the message ciphered with a previous substitution cipher from the sequence of substitution ciphers, the previous substitution cipher applied to the message by a previous computing device in the sequence of computing devices, (ii) re-cipher the received message with a particular composition cipher that comprises an inverse of the previous substitution cipher applied to the message and a different substitution cipher that replaces each of a plurality of the units of the received message with a ciphered unit according to a predetermined system that maps different possible values for message units to different cipher values for the message units, the particular composition cipher stored on the particular intermediary computing device, and (iii) transmit the re-ciphered message to a next computing device in the sequence of computing devices; and

a message receiving computing device to (i) receive the ciphered message from a last intermediary computing device and (ii) decipher the message a final substitution cipher in the sequence of substitution ciphers.

11. The system of claim 10, wherein the message originating computing device is a central server and the message receiving computing device is a media player.

12. A non-transitory machine readable medium storing a program for distributing a message from a message originating computing device through a particular user controlled intermediary computing device to at least two separate recipient devices the program for execution by at least one processing unit on the user controlled intermediary computing device, the program comprising sets of instructions for:

receiving a message ciphered with a previous substitution cipher applied to the message by the message originating computing device, the received message comprising a plurality of units, each unit including at least two bits of information;

re-ciphering the received message with a composition cipher that comprises a composition of an inverse of the previous cipher and a substitution cipher, associated with the particular user controlled intermediary computing device, that replaces each of a plurality of the units of the received message with a ciphered unit according to a predetermined system that maps different possible values for message units to different cipher values for the message units, wherein the composition cipher is part of a sequence of composition ciphers that are each for use on the message originating computing device, the particular user controlled intermediary computing device, and the recipient devices; and

transmitting the re-ciphered message to the recipient devices, wherein the intermediary computing device and the recipient devices are part of a group of devices that the user controls.

13. The non-transitory machine readable medium of claim 12, wherein the composition cipher is such that its application to the received message at the particular user controlled intermediary device results in the message being encrypted only in the substitution cipher associated with the particular user controlled intermediary computing device.

14. The non-transitory machine readable medium of claim 12, wherein the substitution cipher associated with the particular user controlled intermediary computing device includes at least one of a transitive function and a homomorphic function.

15. The non-transitory machine readable medium of claim 12, wherein the program further comprises sets of instructions for:

storing the received message in a first storage on the particular user controlled intermediary computing device; and

storing the re-ciphered message in a second storage on the particular user controlled intermediary computing device.

16. The non-transitory machine readable medium of claim 12, wherein the program further comprises a set of instructions for storing the composition cipher in a storage on the particular user controlled intermediary computing device.

17. The non-transitory machine readable medium of claim 12, wherein the message comprises digital rights management data.