Secret-key-controlled reversible circuit and corresponding method of data processing

• US 7,913,083 B2
• Filed: 09/05/2003
• Issued: 03/22/2011
• Est. Priority Date: 09/05/2003
• Status: Active Grant

• Current Assignee: Telecom Italia S.p.A.
• Original Assignee: Telecom Italia S.p.A.
• Inventors: Golic, Jovan
• Primary Examiner(s): Smithers; Matthew B
• Assistant Examiner(s): SHOLEMAN, ABU S
• Application Number:
  US10/568,618
• Publication Number:
  US 20060236102A1
• Time in Patent Office: 2,755 Days
• Field of Search: 713/168, 713/161, 380/29, 380/36, 380/37, 380/42, 380/200, 380/210, 380/277
• US Class Current: 713/168
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation

Abstract

A combinatorial key-dependent network suitable for the encryption/decryption of data on buses and in memories of data-processing devices, has a number of layers, where each layer has a number of elementary building blocks operating on very small block sizes. A generic building block acts on a small number of input data bits, which are divided into two groups of m and n bits, respectively. The m input bits, which are passed to the output intact, are used to select k out of 2^mk key bits by a multiplexer circuit; the k bits are then used to select an (n×n)-bit reversible transformation acting on the remaining n input bits to produce the corresponding n output bits. The total number of the key bits in the building block is thus 2^mk, which can easily he made larger that m+n. An inverse building block is the same except that the reversible transformations are replaced by their inverses.

Claims

1. A combinatorial key-dependent network for encryption/decryption of input digital data having a first word size into output digital data of the same word size, comprising at least two layers, each layer comprising at least an elementary building block, each building block operating on an input block of bits having a second word size smaller than or equal to said first word size, for generating an output block of bits, said building block comprising:

a multiplexer circuit that receives a first portion of said input block of bits and a first set of key bits as inputs, the first portion of said input block of bits operable to select a second set of key bits out of the first set of key bits, wherein the selected second set of key bits are output by said multiplexer circuit, said first portion of bits are transferred intact without modification by an encryption operation to an output of said building block, and the number of bits in the second set of key bits is less than the number of bits in the first set of key bits; and

a transformation circuit, for transforming a second portion of said input block of bits into transformed bits according to a reversible transformation chosen, by means of said selected second set of key bits, among a plurality of reversible transformations implemented in said transformation circuit, wherein said transformation circuit transforms said second portion of said input block of bits without receiving said first portion of said input block of bits as an input and said output block of bits comprises the transformed bits followed by said first portion of said input block of bits.

2. The network according to claim 1, wherein adjacent layers are connected by means of a fixed bit permutation block.

3. The network according to claim 2, comprising a plurality of fixed bit permutation blocks of the same type.

4. The network according to claim 2, comprising at least two different types of fixed bit permutation blocks.

5. The network according to claim 2, wherein bits in said first portion of said input block of bits are used, in a next layer, as bits to be transformed.

6. The network according to claim 2, wherein, for each building block, said first portion of said input block of bits are extracted from at least two building blocks in a preceding layer, provided that said first portion of said block of bits comprise at least two bits.

7. The network according to claim 2, wherein, for each building block, said second portion of said input block of bits are extracted from at least two building blocks in a preceding layer, provided that said second portion of said block of bits comprises at least two bits.

8. The network according to claim 1, wherein each layer comprises at least two building blocks.

9. The network according to claim 8, wherein said reversible transformations are such that each output bit of said transformed bits is a non-linear function of said first portion of said input block of bits and of said second set of key bits, with the algebraic normal form containing at least one binary product involving both said second portion of said input block of bits and said second set of key bits.

10. The network according to claim 9, wherein said reversible transformations satisfy a criterion that the uncertainty of the second portion of said input block of bits provided by uniformly random second set of key bits when the transformed bits are known is equal to a bit size of the transformed bits.

11. The network according to claim 1, wherein said multiplexer circuit comprises a lookup table whose content is defined by the first set of key bits.

12. The network according to claim 1, wherein said transformation circuit comprises XOR gates and controlled switches.

13. The network according to claim 12, wherein each XOR gate has two input bits and one output bit, one of the two input bits being a key bit, and each controlled switch has two input bits, two output bits and one control bit that determines if the input bits are swapped or not, said control bit being a key bit.

14. The network according to claim 13, wherein said multiplexer circuit has two control bits, four 3-bit inputs and one 3-bit output, and said transformation circuit comprises two XOR gates and one controlled switch.

15. The network according to claim 14, wherein the three bits of said 3-bit output are connected respectively to a first input bit of each XOR gate and to the control bit of said controlled switch.

16. The network according to claim 15, wherein a second input bit of each XOR gate is connected to a bit of said second portion of said input block of bits.

17. The network according to claim 16, wherein the output bits of said XOR gates are connected to the two input bits of said controlled switch.

18. The network according to claim 17, wherein the two output bits of said controlled switch generate the transformed bits of said transformation circuit.

19. The network according to claim 12, comprising a plurality of building blocks of the same type.

20. The network according to claim 1, comprising at least two different types of building blocks.

21. The network according to claim 1, wherein adjacent layers are connected by means of a block implementing a reversible linear function.

22. The network according to claim 1, wherein two additional input and output keys having a word size equal to the first word size are bitwise XORed respectively with said input digital data and with said output digital data.

23. The network according to claim 1, wherein said first set of key bits in each layer, having a first bit size, are generated from a smaller number of secret key bits, having second bit size, by means of a key expansion algorithm.

24. The network according to claim 23, wherein said secret key bits are first expanded by means of linear transformations into said first set of key bits, using a linear code so that any subset of expanded key bits having a third bit size, are linearly independent, where the third bit size is less than or equal to the second bit size.

25. The network according to claim 24, wherein said expanded key having first bit size is used as an input to a further combinatorial key-dependent network having a of block size equal to the first bit size which is parameterised by a fixed randomly generated key satisfying the condition that every multiplexer implements balanced binary lookup tables.

26. The network according to claim 25, wherein the expanded key having the first bit size produced after every two layers of said further combinatorial key-dependent network are used as said first set of key bits from the multiplexer circuits within the layers of the combinatorial network.

27. The network according to claim 25, wherein said further combinatorial key-dependent network comprises a plurality of layers, each layer comprising a plurality of simplified building blocks, each building block comprising:

a multiplexer having one input receiving one control bit which is passed to the output intact, for selecting one out of two key bits on a one bit output; and

a controlled switch having two input bits, two output bits and one control bit connected to the output of said multiplexer, said control bit determining if said two input bits are swapped or not.

40. A data processing device comprising a central processing unit, volatile or non-volatile memory, and at least a data, instruction or address bus, comprising at least a combinatorial key-dependent network according to any one of claims 1 to 27, for encryption/decryption of digital data on said data, instruction, or address bus and/or into said memories.

41. A multimedia device for storing and playing copyright digital data comprising at least a combinatorial key-dependent network according to any one of claims 1 to 27, for encryption/decryption of said copyright digital data.

28. A block for secret-key-controlled cryptographic functions, operating on an input block of bits for generating an output block of bits comprising:

a multiplexer circuit that receives a first portion of bits of said input block of bits and a first set of key bits as inputs, the first portion of said input block of bits operable to select a second set of key bits out of the first set of key bits, wherein the selected second set of key bits are output by said multiplexer circuit, said first portion of bits are transferred intact without modification by an encryption operation to an output of said building block, and the number of bits in the second set of key bits is less than the number of bits in the first set of key bits; and

a transformation circuit for transforming a second portion of said input block of bits into transformed bits, according to a reversible transformation chosen, by means of said selected second set of key bits, among a plurality of reversible transformations implemented in said transformation circuit, wherein said transformation circuit transforms said second portion of said input block of bits without receiving said first portion of said input block of bits as an input and said output block of bits comprises the transformed bits followed by said first portion of said input block of bits.

29. The block according to claim 28, wherein said transformation circuit comprises XOR gates and controlled switches.

30. The block according to claim 29, wherein each XOR gate has two input bits and one output bit, one of the two input bits being a key bit, and each controlled switch has two input bits, two output bits and one control bit that determines if the input bits are swapped or not, said control bit being a key bit.

31. The block according to claim 30, wherein said multiplexer circuit has two control bits, four 3-bit inputs and one 3-bit output, and said transformation circuit comprises two XOR gates and one controlled switch.

32. The block according to claim 31, wherein the three bits of said 3-bit output are connected respectively to a first input bit of each XOR gate and to the control bit of said controlled switch.

33. The block according to claim 32, wherein a second input bit of each XOR gate is connected to a bit of said second portion of said block of bits.

34. The block according to claim 33, wherein the output bits of said XOR gates are connected to the two input bits of said controlled switch.

35. The block according to claim 34, wherein the two output bits of said controlled switch generate the transformed bits of said transformation circuit.

36. A method for encryption/decryption of input digital data having a first word size into an output digital data of the same word size, comprising;

a) dividing said input digital data into blocks of bits, each having a second word size smaller than said first word size, each block of bits being divided into a first portion and a second portion;

b) for each block of bits;

b1) receiving, at a multiplexer circuit, a first portion of said input block of bits and a first set of key bits as inputs, the first portion of said input block of bits operating to select a second set of key bits out of the first set of key bits, wherein the selected second set of key bits are output by the multiplexer circuit, said first portion of bits are transformed intact without modification by an encryption operation to a first portion of transformed bits, and the number of bits in the second set of key bits is less than the number of bits in the first set of key bits;

b2) selecting, by means of said selected second set of key bits, a reversible transformation among a plurality of reversible transformations, by inputting said selected second set of key bits into a transformation circuit without also inputting said first portion of bits into said transformation circuit;

b3) applying said reversible transformation to said second portion of bits, thus generating a second portion of transformed bits;

c) collecting the transformed bits from each block into said output digital data, wherein the transformed bits from each block comprise the second portion of transformed bits followed by the first portion of transformed bits.

37. The method according to claim 36, wherein said step b) is reiterated on a block of bits comprising said first and second portions of previously transformed bits.

38. The method according to claim 37, wherein, before each reiteration of step b), a fixed bit permutation is applied to said previously transformed bits.

39. The method according to claim 37, wherein, before each reiteration of step b), a reversible linear function is applied to said previously transformed bits.