Encryption of programs represented as polynomial mappings and their computations

1. A computer-implemented method of encrypting plural variables and mapping components of multivariate mappings, represented, with univariate mappings of an appropriate representation, comprising the steps of:

A. determining a representation for the encryption;

B. replacing each variable to be decrypted x i with a decrypted equivalent s e+i (x i );

C. composing the decrypted equivalents with a mapping h; and

D. composing each mapping component to be encrypted, h i , with an encryption function r i , to create r i (h i ( . . . )).

2. The method as claimed in claim 1 , wherein the multivariate mappings comprise mappings represented as one of function tables and polynomials.

3. A computer-implemented method of generating keys for multivariate encryption of multivariate mappings, comprising the steps of:

A. determining a representation for the keys including key triples;

B. defining a polynomial f to translate from base-N vectors having c i components to base- N c i , number;

C. defining, for an i th key triple, arrays R i and S i each having N c i ×(c i +1) elements;

D. permuting a ring Z N c i , and simultaneously translating a permutation and its inverse to a field Z N c i , storing ring permutations in R i and storing translated permutations and inverses in S i ;

E. repeating steps B–D for each key triple not set equal to identity; and

F. converting each array R i and S i to the determined key representation.

4. The method as claimed in claim 3 , wherein the mappings to be encrypted are expressed using polynomials, further comprising the step of computing the permutation and its inverse by interpolation, using at least a portion of R and S as interpolation data, using a i (x), once for each unique key triple that is to be generated.

5. The method as claimed in claim 3 , further comprising the step of setting all key triples that are to do neither encryption nor decryption to the identity mapping.

6. The method as claimed in claim 3 , further comprising the steps of (1) pre-computing arithmetic operations over the field Z N and (2) pre-computing coefficients of the functions a j (x), wherein the steps of permuting comprises using the pre-computed a j (x).

7. The method as claimed in claim 3 , further comprising the step of restricting a new set of key triples based on a pattern of encryption used during an encryption of the first multivariate polynomials.

8. A computer-implementation method of encrypting plural groups of variables and groups of mapping components of multivariate mappings, with other multivariate mappings, comprising the steps of:

A. determining a mapping representation for encryption;

B. replacing each group of encrypted variables {right arrow over (w)} i , with a decrypted equivalent s i+l ({right arrow over (w)} i );

C. composing each of the decrypted equivalents with a mapping h; and

D. composing each group of mapping components to be encrypted v i with r i giving r i (v i ( . . . )).