Cryptographic device and an encoding device

• US 10,567,158 B2
• Filed: 10/10/2016
• Issued: 02/18/2020
• Est. Priority Date: 10/12/2015
• Status: Active Grant

• Current Assignee: Koninklijke Philips N.V.
• Original Assignee: Koninklijke Philips N.V.
• Inventors: Rietman, Ronald, De Hoogh, Sebastiaan Jacobus Antonius, Gorissen, Paulus Mathias Hubertus Mechtildis Antonius, Mallon, Willem Charles, Tolhuizen, Ludovicus Marinus Gerardus Maria, Hollmann, Hendrik Dirk Lodewijk
• Primary Examiner(s): Pwu, Jeffrey C
• Assistant Examiner(s): Woldemariam, Nega
• Application Number:
  US15/767,210
• Publication Number:
  US 20190074959A1
• Time in Patent Office: 1,226 Days
• Field of Search: 380 28
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI
• CPC Class Codes: H04L 9/0819 Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) network architectures or network communication protocols for key distribution in a packet data network H04L63/062
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

A cryptographic device (200) is provided to compute a key dependent cryptographic function for an input message. The cryptographic device has a data store arranged to store multiple variables (w) on which the cryptographic device acts to compute the cryptographic function, a variable (w) being distributed over multiple shares (w^j) and represented in the data store as multiple encoded shares (x^j), an encoded share being an encoding (x^j=Enc_j (w^j, s^j)) of a share (w^j) together with a state (s^j), the multiple states (s^j) corresponding to the same variable (w) having a relationship with the input message (M) so that there exists an injective mapping (Σ) from the input message (M) to the multiple states (Σ(M)=(s⁰, . . . , sⁿ⁻¹)).

Claims

1. A cryptographic device arranged to compute (ƒ

_K^(M)) a key (K)-dependent cryptographic function (ƒ

) for an input message (M), the cryptographic device comprising

a data store arranged to store multiple variables (w) on which the cryptographic device acts to compute the cryptographic function, a table store storing multiple look-up tables, the multiple look-up tables together forming a table network implementing the cryptographic function, and a control unit configured to apply the cryptographic function to the input message by applying the multiple look-up tables to the variables represented in the data store, characterized in that

a variable (w) is distributed over multiple shares (w^j) and represented in the data store as multiple encoded shares (x^j), an encoded share being an encoding (x^j=Enc_j(w^j,s^j) of a share (w^j) together with a state (s^j), the multiple states (s^j) corresponding to the same variable (w) having a relationship with the input message (M) so that there exists an injective mapping (Σ

) from the input message (M) to the multiple states (Σ

(M)=s⁰, . . . , s<sup>n−

1</sup>)), and

a look-up table takes as input one or more encoded shares of one or more variables, the table network performing operations on the multiple shares (w^j) of the encoded variable (W) and simultaneously performing redundant operations on the multiple states (s^j) maintaining an injective mapping from the input message (M) to the multiple states.

2. A cryptographic device as in claim 1, wherein a total bit size of the multiple states (s^j) corresponding to the same variable (w) is at least as large as the bit size of the input message (M).

3. A cryptographic device as in claim 1, wherein the encoding is a bijection.

4. A cryptographic device as in claim 1, wherein a combining function (d(w⁰, . . . , wⁿ⁻

1)=w) maps the shares (w^j) to the variable (w), the combining function having the property that that the mapping from any single share (w^k) to the variable (w), obtained by fixing the values of the other shares (w⁰ . . . , w<sup>k−

1</sup>, w^k+1, . . . , w<sup>n−

1</sup>) is a bijection.

5. A cryptographic device as in claim 1, wherein the sum of the multiple shares (w^j) equals the corresponding variable (w=Σ

_j=0<sup>n−

1</sup>w^j).

6. A cryptographic device as in as in claim 1, wherein

the table store stores a multiplication table network for multiplying a first variable (w) distributed over a first multiple of shares (w^j) and represented in the data store as a first multiple of encoded shares (x^j) and a second variable (v) distributed over a second multiple of shares (v^j) represented in the data store as a second multiple of encoded shares (y^j), the multiplication table network acting on the first and second multiple of encoded shares (x^j,y^j) obtaining a third multiple of encoded shares (z^j) representing the product of the first and second variable,

the multiplication table network comprising one or more cross-product table sub-networks for computing the product of a first share (w¹) of the first multiple shares and a second share (v²) of the second multiple of shares, the cross-product table sub-networks computing the sum of the product of the first share and the second share from the corresponding encoded shares plus a randomization function (R_1,2) from the input message (M).

7. A cryptographic device as in claim 1, wherein

the table store stores a table network for performing an operation, taking as input a first encoded variable (w₁) and a second encoded variable (w₂) and producing as output a third encoded variable (w₃), the table network being arranged so that the multiple states encoded in the third encoded variable (x₃⁰, . . . , x₃ⁿ⁻

1) depend only on the states encoded in one of the first encoded variable (x₁⁰, . . . , x₃<sup>n−

1</sup>) and the second encoded variable (x₂⁰, . . . , x₂<sup>n−

1</sup>).

10. A cryptographic device as in claim 1, comprising the encoding device of claim 8.

12. An encoding method for encoding an input message (M) for use with a cryptographic device as in claim 1, the encoding method comprising

receiving the input message (M), the input message comprising multiple input parts (M=(m₀, m₁, . . . )),

for each part (m_i) of the input message (M)

distributing the part (m_i) of the input message (M) into multiple shares by applying multiple distribution functions (h_i^j) to the input message to obtain the multiple shares (w_i^j=h_i^j(M)), wherein a combining function applied to the distribution functions (h_i^j) equals the part (m_i) of the input message (M) (d(h_i⁰, . . . , h_iⁿ⁻

1)(M)=m_i;

Σ

_jh_i^j(M)=m_i)

applying an injective mapping (Σ

_i) from the input message (M) to obtain multiple states (s_i^j), the number of multiple shares and multiple states being the same

encoding each share of the multiple shares together with a corresponding state of the multiple states, obtaining multiple encoded shares (x_i^j) representing the part (m_i).

8. An encoding device for encoding an input message (M), the encoding device comprising

a receiving unit for receiving the input message (M), the input message comprising multiple input parts (M=(m₀, m₁, . . . )), and

an encoding unit, characterized in that the encoding unit is arranged to, for each part (m_i) of the input message (M)

distribute the part (m_i) of the input message (M) into multiple shares by applying multiple distribution functions (h_i^j) to the input message to obtain the multiple shares (w_i^j=h_i^j(M)), wherein a combining function applied to the distribution functions (h_i^j) equals the part (m_i) of the input message (M) (d(h_i⁰, . . . , h_iⁿ⁻

1)(M)=m_i;

Σ

_jh_i^j(M)=m_i)

apply an injective mapping (Σ

_i) from the input message (M) to obtain multiple states (s_i^j), the number of multiple shares and multiple states being the same

encoding each share of the multiple shares together with a corresponding state of the multiple states, obtaining multiple encoded shares (x_i^j) representing the part (m_i).

9. An encoding device as in claim 8, wherein

the injective m

apping (Σ

_i) comprises multiple state functions (g_i^j), obtaining multiple states (s_i^j) comprises applying the multiple state functions (g_i^j) to respective multiple input parts (s_i^j=g_i^j(m_j)), wherein the multiple state functions are bijective.

11. A cryptographic method arranged to compute (ƒ

_K(M)) a key (K)-dependent cryptographic function (ƒ

) for an input message (M), the cryptographic method comprising

storing multiple variables (w) on which the cryptographic device acts to compute the cryptographic function, storing multiple look-up tables, the multiple look-up tables together forming a table network implementing the cryptographic function, and applying the cryptographic function to the input message by applying the multiple look-up tables to the variables represented in the data store, characterized in that

a variable (w) being distributed over multiple shares (w^j) and represented in the data store as multiple encoded shares (x^j), an encoded share being an encoding (x^j=Enc_j(w^j,s^j) of a share (w^j) together with a state (s^j), the multiple states (s^j) corresponding to the same variable (w) having a relationship with the input message (M) so that there exists an injective mapping (Σ

) from the input message (M) to the multiple states (Σ

(M)=(s⁰, . . . , s<sup>n−

1</sup>)),

a look-up table taking as input one or more encoded shares of one or more variables, the table performing operations on the multiple shares (w^j) of the encoded variable (w) and simultaneously performing redundant operations on the multiple states (s^j) maintaining an injective mapping from the input message (M) to the multiple states.

13. A computer program comprising computer program instructions arranged to perform the method of claim 11 when the computer program is run on a computer.

14. A computer readable medium comprising the computer program in claim 13.