COMPUTING DEVICE COMPRISING A TABLE NETWORK

Abstract

A computing device is provided configured to compute a data function on a function-input value comprising an electronic storage storing a table network configured for the data function and an electronic processor coupled to the storage and configured to compute the data function by applying the table network, wherein the device is configured to obtain the function-input value as an encoded input value, the encoded input value combines the function-input value together with a state-input value encrypted together into a single value, the table network is configured to take as input the encoded input value and produce as output an encoded output value, the encoded output value combines a function-output value together with a state-output value encrypted data function together into a single value, wherein the function-output value equals the result of applying the data function to the function-input value, and the state-output value equals the result of applying a state function to the state-input value.

Claims

1. A compiler configured for compiling a computer program, the compiler being configured for parsing the computer program to identify multiple operators, including a data function (f) and a state function (g), and for producing a table network configured for the data function and the state function, wherein the table network is configured to take as input an encoded input value and produce as output an encoded output value, the encoded output value combines a function-output value together with a state-output value encrypted together into a single value, wherein the function-output value equals the result of applying the data function to the function-input value, and the state-output value equals the result of applying the state function to the state-input value, wherein the encoded input value combines the function-input value together with a state-input value encrypted together into a single value.

2. A computing device configured to run a computer program compiled by a compiler as in claim 1, the device comprising an electronic storage storing the table network produced by the compiler, configured for a data function (f) and a state function (g), and an electronic processor coupled to the storage and configured to compute the data function and the state function by applying the table network, wherein the device is configured to obtain the function-input value as an encoded input value, the encoded input value combines the function-input value together with a state-input value encrypted together into a single value, the table network is configured to take as input the encoded input value and produce as output an encoded output value, the encoded output value combines a function-output value together with a state-output value encrypted together into a single value, wherein the function-output value equals the result of applying the data function (f) to the function-input value and the state-output value equals the result of applying a state function (g) to the state-input value.

3. A computing device as in claim 2 configured to use the state or data function of the table network depending on a current encoding of the table network inputs.

4. A computing device as in claim 3, wherein the encoded input value combines the function-input value and the state-input value encrypted together into a single value according to a first encoding (E), the table network is configured to obtain a function-input value and a state-input value as a further encoded input value, the further encoded input value combines the function-input value together with the state-input value encrypted together into a single value according to a second encoding ({tilde over (E)}) the table network is configured to take as input the further encoded input value and produce as output a further encoded output value, the further encoded output value combines a function-output value together with a state-output value encrypted together into a single value, wherein the function-output value equals the result of applying the state function (g) to the function-input value and the state-output value equals the result of applying the data function (f) to the state-input value.

5. A computing device as in claim 4, wherein the first encoding is defined by a first encoding function E(x,y), wherein x denotes a function-input and y a state-input, and the second encoding is defined by a second encoding function defined by {tilde over (E)}(x,y)=E(y,x).

6. A computing device as in claim 4 configured to pre- and post processes inputs and output of the table network (F) with the function composition ({tilde over (E)}E.sup.−1) of the second encoding ({tilde over (E)}) and the inverse of the first encoding (E).

7. A computing device as in claim 2, wherein the table network comprises a single table taking as input the encoded input value and producing as output the encoded output value.

8. A computing device as in claim 2, wherein the table network comprises a state extractor table configured such that state extractor table applied to the encoded input value produces the state-input value, a state function table configured such that the state function table applied to the state-input value produces the state-output value.

9. A computing device as in claim 8, wherein the table network comprises a re-encoding table configured for receiving as input the encoded input value and the state-output value and producing as output a recoded input value, the recoded input value combines the function-input value together with the state-output value encrypted together into a single value.

10. A computing device as in claim 9, wherein the table network comprises a data function table configured for receiving as input the recoded input value and as output the encoded output value.

11. A computing device as in claim 8, wherein the table network comprises a reduced state function table configured for receiving the state-input value and produce as output an intermediate state value equal to the result of a reduced state function applied to state-input value, the range of the reduced state function being larger than a single value and smaller than the range of the state function, the encoded input value being recoded in dependence upon the intermediate state value.

12. A computing device as in claim 11, wherein the table network comprises a first re-encoding table configured for receiving as input the encoded input value and the intermediate state value and producing as output a recoded input value, the recoded input value combines the function-input value together with the intermediate state value encrypted together into a single value, a data function table configured for receiving as input the recoded input value, and as output an recoded output value, the recoded output value combines the function-output value together with the intermediate state value encrypted together into a single value a second re-encoding table configured for receiving as input the recoded output value and the state-output value and producing as output the encoded output value.

13. A computing device as in claim 11, wherein the table network comprises a first re-encoding table configured for receiving as input the encoded input value and the intermediate state value and producing as output a recoded input value, the recoded input value being the function-input re-encoded, the re-encoding being selected in dependence upon the intermediate state value, a data function table configured for receiving as input the recoded input value and reduced state value, and as output the function-output value in an encoded form, a second re-encoding table configured for receiving as input the function-output value in an encoded form and the state-output value and producing as output the encoded output value.

14. A computing device as in claim 1, wherein the table network comprises a first re-encoding table configured for receiving as input the encoded input value and the state-output value and producing as output a recoded input value, the recoded input value being the function-input re-encoded, the re-encoding being selected in dependence upon the state-output value.

15. A computing device as in claim 1 wherein the table network is configured for function-input values having at least 4, preferably at least 8 bits.

16. A computing device as in claim 1 wherein the table network is configured for state-input value values having at least 4, preferably at least 8 bits.

17. A computing device as in claim 1 wherein function-input value and state-input value have the same bit size.

18. A method for running a computer program compiled by a compiler as in claim 1, the method comprising computing a data function and a state function by applying a table network produced by the compiler to an encoded input value and producing as output an encoded output value, the encoded input value combines the function-input value together with a state-input value encrypted together into a single value, the encoded output value combines a function-output value together with a state-output value encrypted together into a single value, wherein the function-output value equals the result of applying the data function to the function-input value, and the state-output value equals the result of applying a state function to the state-input value.

19. A computer program comprising computer program code means adapted to perform all the steps of claim 1 when the computer program is run on a computer.

20. A computer program as claimed in claim 19 embodied on a computer readable medium.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0043] These and other aspects of the invention are apparent from and will be elucidated with reference to the embodiments described hereinafter. In the drawings,

[0044] FIG. 1 is schematic chart illustrating a table network implementing a data function and a state function,

[0045] FIG. 2 is schematic chart illustrating a table network implementing a data function and a state function,

[0046] FIG. 3a is schematic chart illustrating a table network implementing a data function and a state function,

[0047] FIG. 3b is schematic chart illustrating a table network implementing a data function and a state function,

[0048] FIG. 3c is schematic chart illustrating a table network implementing a data function and a state function,

[0049] FIG. 4 is a block diagram illustrating table networks in general,

[0050] FIG. 5 is a block diagram illustrating a computing device,

[0051] FIG. 6 is a flowchart illustrating a compiler,

[0052] FIG. 7 is a flowchart illustrating a method for computing a data function.

[0053] It should be noted that items which have the same reference numbers in different Figures, have the same structural features and the same functions, or are the same signals. Where the function and/or structure of such an item has been explained, there is no necessity for repeated explanation thereof in the detailed description.

DETAILED EMBODIMENTS

[0054] While this invention is susceptible of embodiment in many different forms, there is shown in the drawings and will herein be described in detail one or more specific embodiments, with the understanding that the present disclosure is to be considered as exemplary of the principles of the invention and not intended to limit the invention to the specific embodiments shown and described.

[0055] In the figures, tables are illustrated with rectangles, and values are illustrated with a rectangle with the upper right corner cut-off.

[0056] FIG. 4 illustrates the general concept of table network, shown is table network 400. Most functions may be expressed as a network of tables. In particular any composition of arithmetic and logic operations may be so expressed. For example, the network of tables, may be an implementation, e.g. of a cipher. Shown are 8 tables of multiple tables. A table transforms an input value to an output value by table-lookup of the input value. Shown are three of the input tables 410, for receiving input from outside the function implementation. Shown is one of the output tables 430. The output tables 430 together form the output of the function implementation, e.g. by concatenation. Shown are four tables of the intermediate tables 420, 422, 424, 426, who receive at least one input from another one of the tables, and who produce an output for use as an input for at least one other table. The tables together form a network. The cipher may be a block cipher; the block cipher may be configured for encryption or for decryption. The block cipher encrypts a block cipher, say AES. The implementation may be for a particular key, in which case the tables may depend on the particular key.

[0057] Look-up table 426 represents an operator having two inputs and one output. The construction of look-up tables for monadic operators may be extended to dyadic operators. For example, the second input may be ‘curried out’; referring to the function transformation technique, currying is the technique of transforming a function that takes n multiple arguments (or an n-tuple of arguments) in such a way that it can be called as a chain of functions, each with a single argument. When this approach is used the look-up table 426 is implemented as multiple monadic look-up tables. On the other hand one may also generate bit strings for each input and concatenate the results. In this way the look-up table is generated directly, and one single but larger look-up table is obtained. Although, the layout of the look-up tables may differ based on the construction, they have equal size and the same properties. Note that it is not necessary that the multiple input values are encoded according to the same encoding.

[0058] The table network may use multiple tables encoding two functions or have as sub network table networks that encode for two functions. The system may be configured to use that state or data function of a network table depending on the current encoding. Table network obfuscation techniques may be applied, also in table networks as described herein.

[0059] For example, suppose a second table receives as input the output of a first table, then the output of a first table may be encoded with a secret, e.g. randomly chosen, encoding, and the input of a second table may be encoded with the inverse encoding.

[0060] FIG. 1 shows a table network 180 embedded in a larger table network 100. Table network 180 contains only a single table 130.

[0061] Table network 180 is configured to take multiple encoded input values as input, shown are encoded input values 122 and 124. Table network 180 is configured to produce as output an encoded output value 160. In the description below we will assume data functions and state functions having two input values and a single output value. However, the embodiments may be extended to any number of input values and/or output values. In particular data/state functions with one input and one output are possible and data/state functions with two inputs and one output are possible.

[0062] Table network 180 is configured for the data function and is stored in an electronic storage, coupled to an electronic processor configured to compute the data function by applying the table network.

[0063] The encoded value 122 is obtained from a function input value 102 and a state input value 112. For example, this may be done by an encoder 110. Encoder 110 may be included in the same device which stores table network 180, but this is not needed. Input values may be received already in encoded form and/or be transmitted in encoded form. Or they may be received/transmitted in un-encoded form. In the latter case they may be encoded and used internally in encoded form. There may also be a re-encoding, e.g., if outside of the device a different encoding is used. For example, function output value 162 and state output value 164 may be obtained from a decoder 170.

[0064] Encoded input of the data function may be the output of another table or table network. The latter may or may not be a table network configured for two functions. By combining table networks configured for different data functions, entire programs may be built up.

[0065] Encoder/decoder 110 and 170 may be obtained as each other's inverse. Encoder 110 may be obtained as follows. Each possible combination of function input value and state input value is listed. For example, if both are 4 bit wide, than there are 16*16=256 possible combinations. The 256 combinations may be mapped to itself in a random bijective order. The same applies to other sizes. Also an encryption function may be used, e.g., an 8 bit block cipher may be applied, using some secret encoding key.

[0066] The encoded input value contains the function input value 102 and state input value 112 in an interdependent way, e.g., the function input depends on all bits of the encoded input. Thus, knowing only part of encoded input value 122 will generally not allow one to find either function input value 102 or state input value 112.

[0067] Below we will give a number of embodiments using mathematical language. One advantage of combining function inputs values with state values is that the function inputs have multiple representations. Function f refers to the data function and g to the state function. The function f is encoded into F such that a value in the domain of F has multiple representatives. In order to hide which function f is being encoded, input(s) and output(s) of f have multiple representations in the domain and range of the encoded version F of f. The function F is designed such that whenever X is a representative of x, then F(X) is a representative of f(x). In the sequel we sometimes speak about “long” variables (input/output of F) and “short” variables (input/output of f) to emphasize that each input/output of f corresponds to multiple input/output of F, so that we need in general more bits to represent inputs/outputs from F than to represent inputs/outputs from f. One way, to obtain multiple representations for operands is described below. Again note that for simplicity, we consider functions with equal input and output symbols; this may be generalized.

[0068] Let W denote the set of operands we wish to encode. We introduce a finite set Σ of “states” and a finite set V with cardinality equal to the product of the cardinalities of W and Σ. The elements of W×Σ are mapped in a one-to-one manner to V by a secret encoding function E. The representatives of the element w in W are the members of the set Ω(w)={E(w,σ)|σεΣ}.

[0069] The number of representatives of each element in W thus equals the cardinality of Σ. As a result, data paths carrying symbols from V are wider than data paths for carrying symbols from W. For example, if W is the set of 16-bits integers and the state space E has 16=2.sup.4 elements, data paths for V use 16+4=20 bits, while data paths for W use 16 bits.

[0070] The embodiment below encodes a function of two variables. Consider a function f: W×W.fwdarw.W that we wish to encode. We construct a function F: V×V.fwdarw.V such that for all w.sub.1, w.sub.2 ≡W and σ.sub.1, σ.sub.2εΣ we have that

F(E(w.sub.1,σ.sub.1),E(w.sub.2,σ.sub.2))εΩ(f(w.sub.1,w.sub.2)).

[0071] Or, stated in words: F maps any pair of representatives of w.sub.1 and w.sub.2 to a representative of f(w.sub.1, w.sub.2).

[0072] The state of the representative of f(w.sub.1, w.sub.2) can depend on both operands w.sub.1 and w.sub.2 and could even depend on both states σ.sub.1 and σ.sub.2, in either a deterministic or in a randomized manner. More specifically, the state can depend only on the states σ.sub.1 and σ.sub.2, which can be implemented by taking a function g: Σ×Σ.fwdarw.Σ and by defining

F(E(w.sub.2,σ.sub.1),E(w.sub.2,σ.sub.2))=E(f(w.sub.1,w.sub.2),g(σ.sub.1,σ.sub.2)).

[0073] An interesting special case of the embodiment above arises if we take Σ=W. Then the function F that encodes f using the function E also encodes the function g, albeit with a different encoding function {tilde over (E)}. That is, it cannot be deduced which of the two functions, for g, is being implemented by F. We define {tilde over (E)}(x,y)=E(y,x). By computation we find that

[00001]$F\left(\tilde{E}\left({\sigma }_1,w_1\right),\tilde{E}\left({\sigma }_2,w_2\right)\right)=F\left(E\left(w_1,{\sigma }_1\right),E\left(w_2,{\sigma }_2\right)\right)=E\left(f\left(w_1,w_2\right),g\left({\sigma }_1,{\sigma }_2\right)\right)=\tilde{E}\left(g\left({\sigma }_1,{\sigma }_2\right),f\left(w_1,w_2\right)\right).$

[0074] A table for F thus implements the function f if the encoding E is being used, and the function g if {tilde over (E)} is being used as encoding function. In this way, it is proven that from table 130 alone one cannot tell which function is being used, since it could encode for at least two functions.

[0075] The table for F can serve to compute both f and g. Indeed, if E is used, then, as said before, the table for F implements f. The same table can also be used for implementing g by pre- and post processing inputs and output with the function {tilde over (E)}E.sup.−1. To be precise, let w.sub.1,w.sub.2εW, σ.sub.1, σ.sub.2εΣ, and write v.sub.i=E(w.sub.i,σ.sub.i), i=1, 2. Then we have that

[00002]$F(\left(\tilde{E}.Math.E^{-1}\left(v_1\right),\tilde{E}.Math.E^{-1}\left(v_2\right)=F\left(\tilde{E}\left(w_1,{\sigma }_1\right),\tilde{E}\left(w_2,{\sigma }_2\right)\right)=F\left(E\left({\sigma }_1,w_1\right),E\left({\sigma }_2,w_2\right)\right)=E\left(f\left({\sigma }_1,{\sigma }_2\right),g\left(w_1,w_2\right)\right)\right).$

[0076] Consequently, we have that

{tilde over (E)}E.sup.−1[F(({tilde over (E)}E.sup.−1(v.sub.1),{tilde over (E)}E.sup.−1(v.sub.2))]=(g(w.sub.1,w.sub.2),f(σ.sub.1,σ.sub.2)).

[0077] The encoded input values may be input values to a computer program, possibly containing or represented by the data function. The computer program may be running on a computer. The instructions of the computer program may be represented by the data function. The encodings and decodings may be under control of a secret key. The encoding and decoding table themselves may be regarded as such a key. If an instruction f operating on data encoded with encoding E.sub.k is applied, then it first decodes the data, then f is applied on the decoded data, and subsequently the result is encoded again. That is, the data x results in the output F(x)=E.sub.k(f(D.sub.k(x)). By direct storage of the function F, for example as a lookup table, the function f and its semantics are hidden. In a specific embodiment, the decoding is the left inverse of encoding, that is, D.sub.k(E.sub.k(x))=x for all x. This has the advantage if two functions f and g are encoded and decoded with the same functions E.sub.k and D.sub.k, then encoded version of the function f(g(x)) can be done by using successively using the tables for G(x)=E.sub.k(g(D.sub.k(x)) and F(x)=E.sub.k(f(D.sub.k(x)). Indeed, it can be seen that for each x we have that E.sub.k(f(g(D.sub.k(x))=F(G(x)), so that the encoded version for f(g(x)) can be obtained from subsequent accesses of tables for G and for F. In this way, sequences of operations can be applied without encoding and decoding between successive operations, thus greatly enhancing the security. In an embodiment of, encoding and decoding only take place at the secure side, while all encoded operations take place at an open, insecure side. The output(s) of one or more encoded functions may serve as input(s) to another encoded function. As we have seen this can be conveniently arranged if the encodings and decodings are each other's inverses. A preferred embodiment for executing a sequence of operations with our inventions is the following. First, in the secure domain, “short” variables are transformed to “long” variables. Randomisation is involved to make sure that the “long” variables occur approximately equally often. This can for example be achieved by having a device that generates a random state oσεΣ, and mapping the variable x on E.sub.k(x,σ) where E.sub.k is an encoding of the “long” variables. After all computations at the open side, all operating using “long” variables, the decoding D.sub.k is applied at the secure side, and next, the “short” variable corresponding to the decoded long variable is determined. Alternatively, the decoding and determination of the short variable is done in one combined step. The letter k denotes a secret, e.g. a secret key.

[0078] Having multiple representatives for variables implies that data-paths become longer. Also, it implies that the table for implementing the encoded version F of f becomes larger. For example, consider a function f(x,y) which has as input two 16-bits variables x and y and as output a 16-bits variable. A table for implementing an encoded version of f, without having multiple representatives, uses a table with 2.sup.162.sup.16 entries, each table entry being 16 bits wide, which amounts to a table size of 2.sup.36 bits. Now assume that each 16-bits variable has 16 representatives; the set of representatives thus can be represented with 20 bits. We now use a table with 2.sup.20×2.sup.20 entries, each table entry being 20 bits wide, which amounts to a table of size 5×2.sup.42 bits. That is, the table is 5×2.sup.6=320 times as large as without having multiple representatives.

[0079] FIG. 2 shows a way to reduce the impact of combining data and state representation on the table size. Table network 200 computes the same data function and the same state function as in FIG. 1.

[0080] Table network 200 is configured for the data function and is stored in an electronic storage, coupled to an electronic processor configured to compute the data function by applying the table network.

[0081] Table network 200 comprises state extractor tables 212 and 214 configured to extract from encoded input values 122 and 124 the corresponding state values 112 and 114. Note that this does not imply that the input values are obtained in plain form at any moment. The state values are used as inputs to a state function table 230. State function table 230 represents the state function. Note that state extractor table 212, state extractor table 214 and state function table 230 could use an encoding for the state values, possibly even a different encoding for values 112 and 114; however this encoding only depends on the state value and not on the input value; the encoding may be secret, e.g., private to the particular implementation. From state function table 230 the state output value 232 is now known.

[0082] Table network 200 further comprises re-encoding tables 242, 244. These tables accept the encoded input values 122 and 124 but re-encode them to have a common state value in this particular embodiment state output 232. This means that data function table 260 may be significantly simplified since it no longer needs to be configured for the possibility that it receives two different state values. Note that the same encoded output value 160 is obtained as in FIG. 1.

[0083] Below we will give a number of embodiments using mathematical language. We consider a function f of m operands. As a first step, we may determine representations of the operands of f such that at least two operands have the same state. To show the advantages, we consider the case that the operands can attain w values and each value of the operand has s representations. The approach of FIG. 1 results in a table with (sw).sup.m entries. If all operands of f are forced to the same state, we may use a table with only sw.sup.m entries. In an embodiment of FIG. 2 at least two operands of f's multiple operands are forced to a common state in a state space.

[0084] One way to obtain multiple representations for operands is the following. Let W denote the set of operands we wish to encode. We introduce a finite set Σ of “states” and a finite set V with cardinality equal to the product of the cardinalities of W and Σ. The elements of W×Σ are mapped in a one-to-one manner to V by a secret encoding function E. The representatives of the element w in W are the members of the set Ω(w)={E(w,σ)|σεΣ}.

[0085] The number of representatives of each element in W thus equals the cardinality of Σ. As a result, data paths carrying symbols from V are wider than data paths for carrying symbols from W. For example, if W is the set of 16-bits integers and the state space E has 16=2.sup.4 elements, data paths for V use 16+4=20 bits, while data paths for W use 16 bits.

[0086] Now we consider a function f: W×W.fwdarw.W that we wish to encode. We construct a function F: V×V.fwdarw.V such that for all w.sub.1, w.sub.2εW and σ.sub.1, σ.sub.2εΣ we have that

F(E(w.sub.1,σ.sub.1),E(w.sub.2,σ.sub.2))εΩ(f(w.sub.1,w.sub.2)).

[0087] Or, stated in words: F maps any pair of representatives of w.sub.1 and w.sub.2 to a representative of f(w.sub.1, w.sub.2). We now consider the situation that the state of a representative only depends on the states σ.sub.1 and σ.sub.2, which can be implemented by taking a function g: Σ×Σ.fwdarw.Σ and by defining

F(E(w.sub.1,σ.sub.1),E(w.sub.2,σ.sub.2))=E(f(w.sub.1,w.sub.2),g(σ.sub.1,σ.sub.2)).

[0088] We note that this function F has two input variables from V. A table for F thus has |V|.sup.2 entries, and that each entry in an element from V. Below we show how to reduce the table size significantly. We use a table for the state-extractor S.sub.e: V.fwdarw.Σ defined as

S.sub.e(E(w,σ))=σ

In FIG. 2, state extractor tables 212 and 214 represent these state-extractor functions S.sub.e. Note that it is possible that a different state encoding was used in encoded input value 122 than in encoded input value 124.

[0089] We also use a table for computing the function g implemented in 230 in FIG. 2. Also, we use (secret) encodings {tilde over (E)}.sub.1: W×Σ.fwdarw.W and {tilde over (E)}.sub.2: W×Σ.fwdarw.W, and tables (corresponding to tables 242 and 244 in FIG. 2) for implementing the functions ε.sub.1: V×Σ.fwdarw.W and ε.sub.2: V×Σ.fwdarw.W, which are such that for i=1, 2 and all wεW, σ, τεΣ, we have ε.sub.i(E(w,σ),τ)={tilde over (E)}.sub.i(w,τ).

[0090] And finally, we use a table for implementing the function φ: W×W×T.fwdarw.V such that for all w.sub.1εW, w.sub.2εW and τεΣ, we have that

φ({tilde over (E)}.sub.1(w.sub.1,τ),{tilde over (E)}.sub.2(w.sub.2,τ),τ)=E(f(w.sub.1,w.sub.2),τ).

[0091] Now consider inputs v.sub.1=E(w.sub.1,σ.sub.1) and v.sub.2=E(w.sub.2,σ.sub.2). Note that an attacker can observe v.sub.1 and v.sub.2, but cannot observe w.sub.1 and w.sub.2.

We run the following program.
s.sub.1:=S.sub.e[v.sub.1]; s.sub.2:=S.sub.e[v.sub.2]; τ:=g[s.sub.1,s.sub.2]; (** so s.sub.1=σ.sub.1,s.sub.2=σ.sub.2**)
y.sub.1:=ε.sub.1[v.sub.1,τ]; y.sub.2:=ε.sub.2[v.sub.2,τ]; (** so y.sub.i={tilde over (E)}.sub.i(w.sub.i,τ)**)
z:=φ[y.sub.1,y.sub.2,τ]. (** so z=E(f(w.sub.1, w.sub.2), g(σ.sub.1, σ.sub.2))**)

[0092] The penultimate line above corresponds to tables 242,244, 252 and 254 of FIG. 2. The last line above corresponds to table 260 of FIG. 2.

[0093] We now determine the total size of the required tables. The table for S.sub.e has |V| entries, each of which is an element of Σ: |V|log.sub.2|Σ| bits. The table for g has |Σ|.sup.2 entries, each of which is an element of Σ: |Σ|.sup.2 log.sub.2|Σ| bits. The tables for ε.sub.1 and ε.sub.2 both have |V∥Σ| entries, each of which is an element of W: |V∥Σ| log.sub.2|W| bits per table. The table for φ has |W|.sup.2|Σ| entries, each of which is an element of V: |W|.sup.2|Σ| |V| bits. The total number of required bits thus equals (|V|+|Σ|.sup.2) log.sub.2|Σ|+2|V∥Σ|log.sub.2|W|+|W|.sup.2|Σ|log.sub.2|V|.

[0094] So, if |W|=|Σ|, then we find, using that |V|=|W∥Σ|, that the number of required bits equals (4|W|.sup.3+2|W|.sup.2) log.sub.2|W|. FIG. 1 uses |V|.sup.2 log.sub.2|V|=2|W|.sup.4 log.sub.2|W| bits. So in this example, the table size is reduced with nearly a factor of |W|/2.

[0095] FIG. 3a shows how table size and security may be exchanged in a trade off. In addition to the state function table 230 as in FIG. 2, table network 300 comprises a reduced state function table 310. Reduced state function table 310 computes a different function on state input values 112 and 114 than state function table 230. In fact reduced state function table 310 could compute any function on the 112 and 114, e.g. a random function, except that reduced state function table 310 has a smaller range than state function table 230. That is, the number of possible output values of reduced state function table 310 is smaller than the number of possible output values of state function table 230. Reduced state function table 310 produces a reduced state value 320. For example, state output value 232 may be 4 bits and reduced state output value may be 2 bits. To simplify one may select the bits of value 320 from the bits of state output value 232; however preferably, tables 310 and 230 are distinct and not correlated, especially not in this linear fashion.

[0096] Instead of re-encoding the input values to the state output value, table network 300 re-encodes to the reduced state value 320. Table network 300 comprises re-encoding tables 332 and 334 configured to accept as input the encoded input values 122 and 124 respectively and produce new encoded values encoded for reduced state value 320 instead of state output value 164. The results are recoded input value 342, 344 respectively. So recoded input values 342 combines their function-input value in encoded input 122 with the reduced state value 320 (instead of state input value 112) encrypted together into a single value; the same holds for recoded input value 344.

[0097] Finally, data function table 350 is like data function table 260 except that it accepts a reduced range of state values. The function computed on the input value corresponds to the data function; the function on the state function could be anything, say random, or the identity. Finally, the result is re-encoded with re-encoding table 360, so that the encoded output value corresponds to state output value 164 as well as function output value 162. Re-encoding table 332 and re-encoding table 334 are also referred to as first re-encoding tables. Re-encoding table 360 is also referred to as second re-encoding table 360. Note that the recoded input 342 and recoded input 344 both contain the reduced state, this means that part of the of input of table 350 is duplicated, as a result the table may be sparse, and thus, say, compresses well if data compression is applied to it.

[0098] For example if function values and state values are each 4 bit wide and reduced state values are 2 bits wide than: re-encoding table 332/334 has 4+4+2=10 bits as input and 6 bits as output; data function table 350 has 6+6=12 bits as input. If Table 350 produces output values of the same size as the encoded input/output values, it has 4+4=8 bit outputs; if the state values are reduced, it has 6 bits outputs; if the output only has function output values (possibly encoded) it has 4 bit outputs. The exemplifying values, such as bits width 4 and 2, may be varied.

[0099] Table network 300 is configured for the data function and is stored in an electronic storage, coupled to an electronic processor configured to compute the data function by applying the table network.

[0100] FIG. 3b shows how a different way in which table size and security may be exchanged in a trade off. Like FIG. 3a, table network 300 comprises a reduced state function table 310. However FIG. 3b does not include re-encoding tables 332 and 334. Instead, state dependent re-encoding tables 372 and 374 are used.

[0101] State dependent re-encoding tables 372 takes as input encoded input value 122, which combines a function input value and state input value but in encoded (encrypted) form. The State dependent re-encoding tables 372 extracts the function input and encodes it in a different manner, the re-encoding being dependent upon reduced state value 320. A different way to say this is, that the function input in encoded input value 122 is encrypted with the reduced state value 320 as key. State dependent re-encoding table 374 does the same thing but for encoded input value 124. The results of tables 372 and 374 are recoded input values 382 and 384.

[0102] For example if function values and state values are each 4 bit wide and reduced state values are 2 bits wide than: re-encoding table 372/374 has 4+4+2=10 bits as input and 4 bits as output; data function table 385 has 4+4+2=10 bits as input. If Table 385 produces output values of the same size as the encoded input/output values, it has 4+4=8 bit outputs; if the state values are reduced, it has 6 bits outputs; if the output only has function output values (possibly encoded) it has 4 bit outputs. The exemplifying values, such as bits width 4 and 2, may be varied.

[0103] Below we will give a number of embodiments using mathematical language. The embodiments, allows a further reduction of the size of the required tables at the potential expense of hiding the function f less well.

[0104] We use a table for state-extractor function S.sub.e: V.fwdarw.Σ defined as S.sub.e(E(w,σ))=σ; the table has |V| entries, each of which is an element of Σ, hence it uses |V|log.sub.2|Σ| bits. This is table 212 and 214 in FIG. 3. Similarly, the table for implementing g has |Σ|.sup.2 log.sub.2|Σ| bits; This is table 230 in FIG. 3. Next, we use an “internal state space” T and a table for a mapping t: Σ×Σ.fwdarw.T. The table for t uses |Σ|.sup.2 log.sub.2|T| bits; This is Table 310 in FIG. 3.

[0105] Also, we use (secret) encodings {tilde over (E)}.sub.1: W×T.fwdarw.W and {tilde over (E)}.sub.2: W×T.fwdarw.W. Moreover, we use tables for implementing the functions ε.sub.1: V×T.fwdarw.W and ε.sub.2:V×T.fwdarw.W, which are such that for i=1, 2 and all wεW, σεΣ and τεT, we have ε.sub.i(E(w,σ),τ)={tilde over (E)}.sub.i(w,τ). The table for each ε.sub.i has |V∥T| entries, each of which is an element from W, and so it uses |V∥T|log.sub.2|W| bits. These are tables 372 and 374 in FIG. 3. We use a function φ: W×W×T.fwdarw.V such that for all w.sub.1εW, w.sub.2εW and τεT, we have φ({tilde over (E)}.sub.1(w.sub.1, τ), {tilde over (E)}.sub.2 (w.sub.2, τ),τ)={tilde over (E)}(f(w.sub.1, w.sub.2),τ), where {tilde over (E)} is a secret permutation of W×T. The table for φ has |W|.sup.2|T| entries, each of which is an element of V, and so the number of required bits equals |W|.sup.2|T|log.sub.2|V|. This is Table 385 in FIG. 3. Finally, we use a table for implementing a function Ψ: W×T×Σ:.fwdarw.V such that for all wεW, τεT, σεΣ, we have Ψ({tilde over (E)}(w,τ), σ)=E (w, σ). This is Table 360 in FIG. 3. The number of bits for this table equals |W∥T∥Σ| log.sub.2|V|.

[0106] The total number of required bits thus equals (|V|+|Σ|.sup.2) log.sub.2|Σ|+|Σ|.sup.2 log.sub.2|T|+2|V∥T| log.sub.2|W|+|W∥T|(|W|+|Σ|) log.sub.2|V|. In the special case |W|=|Σ|, this reduces to |W|.sup.2 log.sub.2|T|+2|W|.sup.2(3|T|+1) log.sub.2|W|.

[0107] From the above, it appears that a smaller internal state space T may reduce the required table size. Next, we explicitly show how to use the tables mentioned above. We consider inputs v.sub.1=E(w.sub.1, σ.sub.1) and v.sub.2=E(w.sub.2, σ.sub.2). Note that an attacker can observe v.sub.1 and v.sub.2, but cannot observe w.sub.1 and w.sub.2. We run the following program.

s.sub.1:=S.sub.e[v.sub.1]; s.sub.2:=S.sub.e[v.sub.2]; τ=t[S.sub.1, S.sub.2]; (** so s.sub.1=σ.sub.1, s.sub.2=σ.sub.2**)
y.sub.1=ε.sub.1[v.sub.1,τ]; y.sub.2=ε.sub.2[v.sub.2,τ]; (** so y.sub.i={tilde over (E)}.sub.i(w.sub.i,τ) **)
z:=φ[y.sub.1,y.sub.2,τ]; (** so z={tilde over (E)}(f(w.sub.1,w.sub.2),τ) **)
σ:=g[s.sub.1,s.sub.2]; (** so σ=g(σ.sub.1,σ.sub.2) **)

[0108] u:=Ψ[z, σ] (** so u=E((f(w.sub.1,w.sub.2),g(σ.sub.1,σ.sub.2)).**)

[0109] A disadvantage of a small state space is the following. In the above program, one computes y.sub.1, y.sub.2 which are such that y.sub.i={tilde over (E)}.sub.i(w.sub.i, τ). So if an attacker observes that for two different values v.sub.1 and v.sub.1′ the corresponding values y.sub.1 and y.sub.1′ are actually equal, then he knows that v.sub.1 and v.sub.1′ respresent the same value of w. If T is small, then it is quite likely that different representatives for w.sub.1 yield the same value for y.sub.1. As an extreme case: if T has just one element, different representatives of an element in W always give the same value of y.sub.1. It is thus advantageous that T is not chosen too small. For example, T may have 4 elements or 8 or 16.

[0110] Below an example is given of a construction of an encoder 110, decoder 170 and state extractor tables 212 and 214. We will assume a single function input and a single state input (there may be more of either), of each 4 bits.

TABLE-US-00001 Function input State input Encoding 0000 0000 0100 0110 0000 0001 0101 1000 . . . . . . . . . 0000 1111 1100 1100 0001 0000 1001 0111 0001 0001 0111 1010 . . . . . . . . . 1111 1111 0011 1001

[0111] The first two columns lists all possible combinations of function input values and state input values. The last column lists a random permutation of the number 0 to 255 in binary. Note that the encryption is perfect, in the sense that even with perfect knowledge of 256−2=254 input-output pairs, the remaining two pairs still have one bit of uncertainty in them. A less perfect but still very usable encoding could be obtained, by using an 8 bit wide block cipher.

[0112] An encoding table is obtained by sorting on the first two columns, the resulting table shows how to obtain the last column (encoding) from the first two. By sorting on the last column, a table is obtained that decodes instead of encodes. By removing the first column and sorting on the last column a state extractor function is obtained. Note that generally, it is not needed to store both the input and output column. For example, if the input column is sorted and contains all possible combinations, it may be omitted.

[0113] FIG. 3c shows state dependent re-encoding without using a reduced state function. The state dependent re-encoding tables 372 and 374 of FIG. 3c are the same as those of FIG. 3b except that they have as input the state output value 232 instead of the reduced state value. This means that the re-encoding which takes places is more secure. On the other hand the tables in 372, 374 and 385 have a wide input. Interestingly, although data function table 385 of FIG. 3c has a larger input, than that of FIG. 3b, no re-encoding table 360 is needed since table 385 now has the correct state output value to incorporate in the output (although this is possible, which would reduce table size).

[0114] Taking again 4 bits for function and state values as an example, the table 372 of FIG. 3c has 4+4+4=12 bits as input and 4 bits as output. Table 385 of FIG. 3c has 4+4+4=12 bits as input and 4+4=8 bits as output.

[0115] FIG. 5 shows a computing device 500, having a storage device 510. Storage device 510 is typically one or more non-volatile memories, but may also be a hard disc, optical disc, etc. Storage device 510 may also be a volatile memory comprising downloaded or otherwise received data. Computing device 500 comprises a processor 550. The processor typically executes code 555 stored in a memory. For convenience the code may be stored in storage device y 510. The code causes the processor to execute a computation. Device 500 may comprise an optional I/O device 560 to receive input values and/or transmit results. I/O device 560 may be a network connection, removable storage device, etc.

[0116] Storage device 510 contains one or more table networks according to one of the FIGS. 1 to 3.

[0117] In an embodiment, the computing device may work as follows during operation: computing device 500 receives input values. The input values are encoded, e.g. by using the encoding table 541, e.g. table 110. Thus the input values are obtained as encoded input values. Note that the input values could be obtained as encoded input values directly, e.g. through device 560. Encoding an input value to an encoded input value implies that a state input has to be chosen. There are several ways to do so, for example the state input may be chosen randomly, e.g., by a random number generator. The state input may be chosen according to an algorithm; the algorithm may be complicated and add to the obfuscation. The state input value may also be constant, or taken sequentially from a sequence of numbers, say the sequence of integers having a constant increment, say of 1, and starting at some starting point; the starting point may be zero, a random number, etc. Choosing the state inputs as a random number and increasing with 1 for each next state input choice is a particular advantageous choice. If the state inputs are chosen off-device the attacker has no way to track where state input values are chosen and what they are.

[0118] Processor 550 executes a program 555 in memory 510. The program causes the processor to apply look-up tables to the encoded input values, or to resulting output values. Look-up tables may be created for any logic or arithmetic function thus any computation may be performed by using a sequence of look-up tables. This helps to obfuscate the program. In this case the look-up tables are encoded for obfuscation and so are the intermediate values. In this case the obfuscation is particularly advantageous because a single function input value may be represented by multiple encoded input values. Furthermore, some or all table and/or table networks have the multiple function property.

[0119] At some point a result value is found. If needed the result may be decoded, e.g. using the decoding table 542, e.g. table 170. But the result may also be exported in encoded form. Input values may also be obtained from input devices, and output values may be used to show on a screen.

[0120] The computation is performed on encoded data words. The computation is done by applying a sequence of table look-up accesses. The input values used may be input values received from outside the computing device, but may also be obtained by previous look-up table access. In this way intermediate results are obtained which may then be used for new look-up table accesses. At some point one of the intermediate results is the encoded result of the function.

[0121] Computing device 500 may comprise a random number generator for assigning state input values to data function inputs.

[0122] FIG. 6 illustrates as flow chart a compiling method 600. In step 610 a first computer program is received by a receiver. In step 620 a lexical analysis is performed, e.g., to identify tokens, by a lexical analyzer. Possibly processing such as macro expansion is also done. In step 630 the program is parsed by a parser. For example, the parser generates a parsing tree according to a formal grammar of the programming language of the first program. The parser identifies the different language constructs in the program and calls appropriate code generation routines. In particular, an operator or multiple operators are identified. In that case, in step 640 code generation is done by a code generator. During code generation some code is generated and if needed accompanying tables. The accompanying tables include tables that are configured for two functions: one for the needed operator and a state function. The generated code does not need, and generally will not, contain the operator as it is replaced by one or more look-up tables. The state function may be chosen at random. The state function may also be chosen as a result of the program, for example, the state function may be another needed operator, which will allow the table to be re-used. For example, the parser will identify and add operation and translate this into a look-up table for the add instruction and in generated code for applying the look-up table to the correct values. As the state function the compiler may select a random function. The compiler may also select at random a function from a set of functions, say addition, subtraction, multiplication and the like.

[0123] In step 655 the generated tables are merged to a table base, since it may well happen that some tables are generated multiple times, in that case it is not needed to store them multiple times. E.g. an add-table may be needed and generated only once. When all code is merged and all tables are merged the compilation is finished. Optionally, there may be an optimization step.

[0124] Typically, the compiler uses encoded domains, i.e., sections of the program in which all value, or at least all values corresponding to some criteria, are encoded, i.e., have code word bit size (n). In the encoded domain, operations may be executed by look-up table execution. When the encoded domain is entered all values are encoded, when the encoded domain is left, the values are decoded. A criterion may be that the value is correlated, or depends on, security sensitive information, e.g., a cryptographic key.

[0125] An interesting way to create the compiler is the following. In step 630 an intermediate compilation is done. This may be to an intermediate language, e.g. register transfer language or the like, but may also be a machine language code compilation. This means that for steps 610-630 of FIG. 6 a conventional compiler may be used, which is does not produce table networks. However in step 640 code generation is done based on the intermediate compilation. For example, if machine language code was used, each instruction is replaced by a corresponding operator free implementation of that instruction, i.e., a table-based implementation of that instruction. This represents a particular straightforward way to create the compiler. FIG. 6 may also be used to generate a compiler that produces not machine language but a second programming language.

[0126] In an embodiment, the compiler is a compiler for compiling a first computer program written in a first computer programming language into a second computer program, the compiler comprises a code generator to generate the second computer program by generating tables and machine language code, the generated tables and the generated machine language code together forming the second computer program, the generated machine language code referencing the tables, wherein the compiler is configured to identify an arithmetic or logical expression in the first computer program, the expression depending on at least one variable, and the code generator is configured to generate one or more tables representing pre-computed results of the identified expression for multiple values of the variable and representing at least one other expression, and to generate machine language code to implement the identified expression in the second computer program by accessing the generated one or more tables representing pre-computed results. Ideally, the machine language code generated to implement the identified expression does not contain arithmetic or logic machine instructions itself, at least no arithmetic or logic machine instructions related to sensitive information. An attacker who reverse engineered the tables may find that it may represent the identified expression, but that it may also represent the other expression.

[0127] This increases resistance against reverse engineering and lowers, side-channel leakage of the second computer program because it contains fewer arithmetic or logic operations. Ideally all arithmetic and logical expressions and sub-expressions in are replaced by table accesses. Since those instructions which constitute the arithmetic or logical expression or sub expressions are absent they cannot leak any information. The table is pre-computed; the power consumed to perform the arithmetic or logical behavior enclosed in the table is not visible during execution of the program.

[0128] FIG. 7 illustrates in a flowchart a method 700 for computing a data function on a function-input value. In step 710 a function-input value is combined together with a state-input value in an encoded input value. This combination is done in an encrypting manner. Note that the encoding of input values may be done at a different location and/or by a different party. In step 720 a table network is applied to the encoded input value to produce as output an encoded output value. In step 730, the function-output value is obtained from the encoded output value. Note that the state-output value could also be obtained from the encoded output value but this may not be needed. The function-output value equals the result of applying the data function to the function-input value, and the state-output value equals the result of applying a state function to the state-input value. Step 730 may be done at a different location and/or by a different party.

[0129] Many different ways of executing the methods disclosed herein are possible, as will be apparent to a person skilled in the art. For example, the order of the steps can be varied or some steps may be executed in parallel. Moreover, in between steps other method steps may be inserted. The inserted steps may represent refinements of the method such as described herein, or may be unrelated to the method.

[0130] A method according to the invention may be executed using software, which comprises instructions for causing a processor system to perform method 700. Software may only include those steps taken by a particular sub-entity of the system. The software may be stored in a suitable storage medium, such as a hard disk, a floppy, a memory etc. The software may be sent as a signal along a wire, or wireless, or using a data network, e.g., the Internet. The software may be made available for download and/or for remote usage on a server.

[0131] It will be appreciated that the invention also extends to computer programs, particularly computer programs on or in a carrier, adapted for putting the invention into practice. The program may be in the form of source code, object code, a code intermediate source and object code such as partially compiled form, or in any other form suitable for use in the implementation of the method according to the invention. An embodiment relating to a computer program product comprises computer executable instructions corresponding to each of the processing steps of at least one of the methods set forth. These instructions may be subdivided into subroutines and/or be stored in one or more files that may be linked statically or dynamically. Another embodiment relating to a computer program product comprises computer executable instructions corresponding to each of the means of at least one of the systems and/or products set forth.

[0132] It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design many alternative embodiments. In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. Use of the verb “comprise” and its conjugations does not exclude the presence of elements or steps other than those stated in a claim. The article “a” or “an” preceding an element does not exclude the presence of a plurality of such elements. The invention may be implemented by means of hardware comprising several distinct elements, and by means of a suitably programmed computer. In the device claim enumerating several means, several of these means may be embodied by one and the same item of hardware. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.

LIST OF REFERENCE NUMERALS IN FIGS. 1-5

[0133] 100 a table network [0134] 102, 104 a function input value [0135] 110 an encoder [0136] 112, 114 a state input value [0137] 122, 124 an encoded input value [0138] 130 a data function [0139] 160 an encoded output value [0140] 162 a function output value [0141] 164 a state output value [0142] 170 a decoder [0143] 180 a table network [0144] 200 a table network [0145] 212,214 a state extractor table [0146] 230 a state function table [0147] 242, 244 a re-encoding table [0148] 252, 254 recoded input value [0149] 260 a data function table [0150] 310 a reduced state function table [0151] 320 a reduced state value [0152] 332, 334 a re-encoding table [0153] 342, 344 recoded input value [0154] 350 data function table [0155] 360 re-encoding table [0156] 372, 374 state dependent re-encoding table [0157] 382, 384 recoded input value [0158] 410 an input table [0159] 420 an intermediate table [0160] 430 an output table [0161] 500 a computing device [0162] 510 a storage device [0163] 521, 522 single input look-up tables [0164] 531, 532 multiple input look-up tables [0165] 5311-5323 single input look-up tables [0166] 541 encoding look-up table [0167] 542 decoding look-up table [0168] 555 machine language code [0169] 550 a computer processor [0170] 560 I/O device