Encryption of programs represented as polynomial mappings and their computations

Abstract

Three variations of a method of representing (abstract) state machines as polynomial mappings, and three variations of a corresponding encryption program stored on a computer readable medium. The encryption program is based directly on symbolic functional composition of polynomial mappings with permutations expressed as polynomial mappings.

1 . A method creating an augmented Mealy machine from a Mealy machine having an input space Σ, a state space Q and an output space Δ, the method comprising the steps of: 
 A. selecting as a state q a  one of (A1) a dedicated output stopping state from the state space θ that is not reachable from any other state in Q such that Q′=Q and (A2) an additional stopping state not in θ if no dedicated output stopping state exists in Q such that Q′=Q∪{q a };    B. setting Δ′=Δ and adding a dedicated blank symbol B to Δ′ only if Δ does not already contain a dedicated blank symbol B;    C. modifying the state-transition mapping δ to δ such that the augmented Mealy machine always remains in q a  once q a  is entered;    D. modifying the output mapping λ to λ′ such that the augmented Mealy machine always outputs B once q a  is entered; and    E. modifying a domain D of the state-transition mapping.    
   
   
       2 . The method as claimed in  claim 1 , further comprising the steps of: 
 F. selecting an integer N′ based on the size of the state, input, and an output spaces;    G. selecting a number N, no less than N′; and    H. determining a vectorization of input, state, and output spaces resulting in vectors over Z N , wherein N is prime if the Mealy machine is represented using polynomials.    
   
   
       3 . The method as claimed in  claim 2 , further comprising the steps of: 
 F. adding dummy states until Q′ contains a number of states determined by a vectorization of the state space using N;    G. adding dummy input symbols until Σ contains a number of symbols determined by the vectorization of the input space using N;    H. adding dummy output symbols until Δ′ contains a number of symbols determined by the vectorization of the output space using N;    I. for each pair (q, σ)∉D′, setting δ′(q, σ)=q a  and λ′(q, σ)=B.    
   
   
       4 . The method as claimed in  claim 2 , further comprising the steps of: 
 F. adding states until Q′ contains a number of states determined by the vectorization of the state space using N according to the sub-steps of: 
 i. selecting a random q∈Q (alternatively in the current Q′−{q a }),  
   ii. adding a state q′ to Q′,    iii. for every σ∈Σ setting δ′(q′, σ)=δ′(q, σ) and λ′(q′, σ)=λ′(q, σ),    iv. optionally also for every pair (q, σ)∈Q′×Σ, such that δ′(q, σ)=q, randomly setting δ′(q, σ) to be one of q and q′ and randomly setting δ′(q′, σ) to be one of q and q′;    G. modifying D to D′ to reflect the addition of the new definitions;    H. adding dummy input symbols to Σ′ until it contains a number of symbols determined by the vectorization of the input space using N;    I. adding dummy output symbols to Δ′ until it contains a number of symbols determined by the vectorization of the output space using N;    J. for each pair (q, σ)∉D′, setting δ′(q, σ) to a random q′∈Q′ and setting λ′(q,σ) to a random symbol from Δ′.    
   
   
       5 . The method as claimed in  claim 2 , further comprising the steps of: 
 F. adding dummy states until Q′ contains a number of states determined by the vectorization of the state space using N;    G. adding dummy input symbols until Σ′ contains a number of symbols determined by the vectorization of the input space using N;    H. adding dummy output symbols until Δ′ contains a number of symbols determined by the vectorization of the output space using N;    I. for each pair (q,σ)∈D′, setting δ′(q, σ) to a random q′∈Q′, setting λ′(q,σ) to a random output symbol in Δ′.    
   
   
       6 . The method as claimed in  claim 1 , further comprising the step of: 
 F. interchanging states at random, and adjusting δ′ and λ′ accordingly;    G. interchanging symbols in the extended input alphabet Σ′, and adjusting δ′ and λ′ accordingly; and    H. interchanging symbols in the extended output alphabet Δ′, and adjusting δ′ and λ′ accordingly.    
   
   
       7 . A method of transforming state-transition and output mappings of an augmented Mealy machine to polynomial mappings, the method comprising the steps of: 
 computing interpolations of δ′ and λ′ from the state-transition and output mappings; and    performing polynomial interpolation of the original state-transition and output mappings.    
   
   
       8 . The method as claimed in  claim 7 , further comprising the step of pre-computing coefficients of a i (x) functions, wherein the step of performing polynomial interpolation of the original mappings uses the pre-computed coefficients of the a i (x) functions.  
   
   
       9 . A method of converting a Blum-Shub-Smale machine to a BSS′ machine, comprising: 
 A. selecting an integer N such that: (1) N is at least as large as the number of nodes, (2) N is greater than user-specified constants used in defining the Blum-Shub-Smale machine, (3) N is a prime number;    B. restricting a ring R to only integer fields of a form Z N ;    C. restricting computation mappings to only polynomial mappings;    D. providing a new node-numbering convention;    E. changing comparisons in branch nodes to set membership relations of the form ∈K, where k ⊂ (Z N −{0});    F. revising a definition of a full state space to include a current node number, an internal state space, and output and input spaces to produce a revised full state space;    G. restricting computation mappings, g n , to an identity mapping for input components of a revised full state vector;    H. restricting all computation mappings, g n , such that no output components in the full state vector may be used in further computation;    I. requiring that at least one computation mapping uses at least one input vector component;    J. requiring that all halting nodes generate output; and    K. restricting node to (1) computation nodes, which may contain at least one of computations and branches, and (2) halting nodes.    
   
   
       10 . A method of specifying a BSS′ machine, comprising the steps of: 
 A. specifying a set of nodes;    B. specifying computation mappings for each node;    C. specifying a next-node function β, along with set membership relations;    D. selecting an integer N such that: (1) N is at least as great as a number of nodes, (2) N is greater than user-specified constants used in defining a corresponding Blum-Shub-Smale machine, and (3) N is a prime number; and    E. specifying a vectorization of the state, input, and output spaces.    
   
   
       11 . The method as claimed in  claim 9 , further comprising at least one of the steps of: 
 listing explicitly the halting nodes of the BSS′ machine; and    explicitly specifying an output symbol B as a halting signal.    
   
   
       12 . The method as claimed in  claim 10 , further comprising at least one of the steps of: 
 listing explicitly the halting nodes of the BSS′ machine; and    explicitly specifying an output symbol B as a halting signal.    
   
   
       13 . A method of transforming a BSS′ machine to a multivariate polynomial mapping, comprising the steps of: 
 A. acquiring a specification of a BSS′ machine;    B. expressing a set membership relation ∈K, K ⊂ (Z N −{0}), as a polynomial;    C. expressing a next-node function β as a polynomial; and    D. expressing a complete computing endomorphism H as a multivariate polynomial mapping.    
   
   
       14 . A method of transforming a BSS′ machine to a mapping represented as a function table, comprising the steps of: 
 A. selecting a specification of a BSS′ machine if no single multivariate polynomial computing endomorphism H is given;    B. selecting a multivariate polynomial mapping H for the BSS′ machine;    C. converting state and input vectors, both with base-N components, to a base N 1+S+I  number X, where 1+S+I is a total number of components in the state and input vectors, wherein the state vector includes a node number;    D. converting the output of the computing endomorphism H with base-N components, to a base N 1+S+O  number F, where 1+S+O is the total number of components in the output of H;    E. inserting F into the X th  entry in the function table; and    F. repeating steps (C)-(E) for all possible state vector/input vector combinations.    
   
   
       15 . A method of computing with a BSS′ machine transformed to a multivariate mapping comprising the steps of: 
 A. initializing the BSS′ machine;    B. applying the multivariate mapping to the full state space vector;    C. checking if the machine has halted, and ending computation if the machine has halted; and    D. repeating steps (B) and (C) if the machine has not halted.    
   
   
       16 . The method as claimed in  claim 15 , wherein the step of applying further comprises at least one of (1) reading the output vector produced by the machine and (2) changing the input vector of the machine.  
   
   
       17 . The method as claimed in  claim 15 , wherein the step of initializing comprises the sub-steps of (1) specifying a node number; (2) specifying a remaining initial state vector; and (3) specifying an initial input vector.  
   
   
       18 . A method of specifying a pattern of encryption of multivariate mappings with univariate mappings comprising the steps of: 
 A. specifying a number d of variables of the multivariate mapping;    B. specifying a number e of mapping components of the multivariate mapping;    C. selecting variables to be used in encrypted form;    D. selecting mapping components to be encrypted; and    E. selecting equality restrictions to be placed on components in the key pairs.    
   
   
       19 . A method of generating keys for univariate encryption of multivariate mappings, comprising the steps of: 
 A. determining a key representation;    B. acquiring a specified pattern of encryption;    C. determining a number of key pairs to be generated from an acquired pattern of encryption; and    D. permuting elements of field Z N  while simultaneously recording data for the permutation and its inverse in two arrays R and S once for each unique key pair generated.    
   
   
       20 . The method as claimed in  claim 19 , wherein the multivariate mappings to be encrypted are expressed using polynomials, further comprising the step of computing the permutation and its inverse by interpolation, using a i (x); once for each unique key pair that is to be generated.  
   
   
       21 . The method as claimed in  claim 19 , wherein the multivariate mappings to be encrypted are expressed using polynomials, further comprising the steps of: 
 precomputing arithmetic operations over the field Z N ; and    precomputing coefficients of functions a i (x), wherein the step of computing the permutation and its inverse by interpolation uses the precomputed coefficients of functions a i (x) and the precomputed arithmetic operations.    
   
   
       22 . The method as claimed in  claim 19 , wherein the steps of determining a number of key pairs further comprises the step of restricting possible keys according to a user input.  
   
   
       23 . The method as claimed in  claim 19 , further comprising the step of setting keys in the key pairs, that are neither to encrypt nor decrypt, to the identity mapping.  
   
   
       24 - 25 . (canceled)  
   
   
       26 . A method of generating re-encryption keys for re-encryption of plural variables and mapping components of multivariate mappings, already partially encrypted with first univariate functions, with second univariate functions, comprising the steps of: 
 A. determining a representation for the re-encryption;    B. acquiring key pairs corresponding to the first univariate functions;    C. generating a new set of key pairs (r 1 ′,s 1 ′), . . . , (r n+m ′,s n+m ′);    D. symbolically composing r i ′, with s i  for 1≦i≦n; and    E. symbolically composing r i  with s i ′ for n<i≦n+m.    
   
   
       27 . The method as claimed in  claim 26 , further comprising the step of acquiring a pattern of encryption used for the first univariate functions, wherein the step of generating comprises generating the new set of key pairs based on the acquired pattern.  
   
   
       28 . A method of re-encryption of plural variables and mapping components of multivariate mappings already partially encrypted with first univariate functions with second univariate functions, comprising the steps of: 
 A. determine a representation for re-encryption;    B. symbolically substituting the i th  variable x i−n  with r i (s i ′(x i−n )) for all n<i≦n+m; and    C. symbolically composing r i ′(s i (x)) with the i th  function component f i  for all 1≦i≦n.    
   
   
       29 . The method as claimed in  claim 28 , further comprising the step of acquiring a corresponding set of pairs of re-encryption keys, wherein the step symbolically composing comprises composing using the acquired keys.  
   
   
       30 . A method of converting a mapping t:Z N   m →Z N   n , given as a function table, into a function t′:Z N     m   →Z N     n   , also given as a function table, comprising the steps of: 
 A. computing X=N m−1 x m + . . . +N 1 x 2 +x 1  for a vector (x 1 , . . . , x m )∈Z N   m ;    B. computing F=N n−1 f n + . . . +N 1 f 2 +f 1  for an entry (f 1 , . . . f n ) corresponding to (x 1 , . . . ,x m );    C. setting t′(X)=F; and    D. repeating for all (x 1 , . . . , x m )∈Z N   m .    
   
   
       31 . A method of converting a function t: Z N     m   →Z N     n   , given as a function table, into a function t′: Z N   m →Z N   n , also given as a function table, comprising the steps of: 
 A. computing X=N m−1 x m + . . . +N 1 x 2 +x 1      B. reducing t(X) to a base-N representation, such that t(X) is represented by a tuple (f 1 , . . . , f n );    C. setting the tuple in t′, indexed by (x 1 , . . . , x m ) to (f 1 , . . . , f n ); and    D. repeating for all (x 1 , . . . , x m )∈Z N   m .    
   
   
       32 . A method of symbolically composing mappings f:Z N   m →Z N   n  and g:Z N   n →Z N   o  represented as function tables to produce the function table for g(f(x)), comprising the steps of: 
 A. generating a new function t f :Z N     m   →Z N     n    represented by a function table, where every mapping value (f 1 , . . . ,f n ) corresponding to a (x 1 , . . . , x m ) is placed in entry number X=N m−1 x m + . . . +N 1 x 2 +x 1  as the number F=N n−1 f n + . . . +N 1 f 2 +f 1 ;    B. generating a new function t g :Z N     m   →Z N     n    represented by a function table, where every mapping value (f 1 , . . . , f n ) corresponding to a (x 1 , . . . , x m ) is placed in entry number X=N m−1 x m + . . . +N 1 x 2 +x 1  as the number F=N n−1 f n + . . . +N 1 f 2 +f 1 ; and    C. for each X from 0 to N m −1 setting t gf (X)=t g (t f (X)), where t gf  is a function table for a function t gf :Z N     m   →Z N     n   .    
   
   
       33 . A method of specifying a pattern of encryption of multivariate mappings with other multivariate mappings comprising the steps of: 
 A. selecting a number of mapping components c i  to be grouped together, c i ≧1 for in all l successive groups of components, covering all components in a mapping only once;    B. selecting a number of variables c i  to be grouped together, c i ≧1, for in all k−l successive groups of variables, covering all variables in a mapping only once;    C. selecting groups of components to be encrypted;    D. selecting groups of variables to be used in encrypted form; and    E. selecting equality restrictions to be placed on components in the key triples.    
   
   
       34 - 39 . (canceled)  
   
   
       40 . A method of generating re-encryption keys for re-encryption of plural variables and mapping components of multivariate mappings already partially encrypted with first multivariate mappings with second multivariate mappings comprising the steps of: 
 A. determining a representation for keys;    B. acquiring key triples used with the first multivariate mappings;    C. generating a new set of key triples (c 1 ′,r 1 ′,s 1 ′), . . . , (c k ′,r k ′,s k ′);    D. symbolically composing r i ′ with s i  for 1≦i≦l; and    E. symbolically composing r i  with s i ′ for l<i≦k.    
   
   
       41 . The method as claimed in  claim 40 , wherein the multivariate mappings comprise one of polynomials and function tables.  
   
   
       42 . A method of re-encrypting plural variables and mapping components of multivariate mappings already partially encrypted with first multivariate mappings with second multivariate mappings, the method comprising the steps of: 
 A. determining a representation for the re-encryption;    B. acquiring key triples used for the encryption using the first multivariate mappings;    C. symbolically substituting an i−l th  variable block {right arrow over (w)} i−l  with r i (s i ′({right arrow over (w)} i−l )), for all l<i≦k; and    D. symbolically composing r i ′(s i ({right arrow over (w)})) with an i th  function component block {right arrow over (v)} i  for all 1≦i≦l.    
   
   
       43 . A method of symbolically composing mappings f:Z N   m →Z N   n  and h 1 , . . . , h k :Z N   c     i   →Z N   c     i   , represented as function tables, to produce the function table for f(h 1 (x 1 , . . . , x c     i   ), h 2 (x c     i     +1 , . . . ,x c     i     +c     2   ), . . . ,h k (x m−c     k     +1 , . . . ,x m )), comprising the steps of: 
 A. acquiring a specification for the c i  such that                  ∑     i   =   1     k     ⁢     c   i       =   m     ;           B. generating a new function t f :Z N     m   →Z N     n    represented by a function table, where every mapping value (f 1 , . . . , f n ) corresponding to a (x 1 , . . . , x m ) is placed in entry number X=N m−1 x m + . . . +N 1 x 2 +x 1  as the number F=N n−1 f n + . . . +N 1 f 2 +f 1 ;    C. for each i generating a new function t h,i :Z N     c     i →Z N     c     i  represented by a function table where every mapping value (h i,1 , . . . , h i,c     i   ) corresponding to a (x a+1 , . . . , x a+c     i   ), where            a   =       ∑     j   =   1       i   -   1       ⁢     c   i               is placed in entry number X=N c   −1 x a+c     i   + . . . +N 1 x a+2 +x a+1  as the number H=N c     i     −1 h i,c     i   + . . . +N 1 h i,2 +h i,1 .    D. initializing a new function table for a function t fh :Z N     m   →Z N     m   ;    E. for every i from 1 to k setting y i =N c     i   ;    F. for every i from 0 to N m −1: 
 i. setting u=0;  
 ii. for every j from k to 1 setting u=y j u+t fh (b j );  
 iii. setting t fh (i)=t f (u); and  
 iv. incrementing the vectorized index (b 1 , . . . , b k ), taking into account that b 1  is in base y 1 , b 2  is in base y 2 , . . . ,b k  is in base y k .  
   
   
   
       44 . A method of symbolically composing mappings f:Z N   m →Z N   n  and h 1 , . . . , h k :Z N   c     i   →Z N   c     i    represented as function tables to produce the function table for (h 1 (f 1 (x 1 , . . . ,x m ), . . . ,f c     1   (x 1 , . . . ,x m )), . . . ,h k (f n−c     k     +1 (x 1 , . . . ,x m ), . . . ,f n (x 1 , . . . , x m ))), comprising the steps of: 
 A. acquiring a specification for the c i  such that                  ∑     i   =   1     k     ⁢     c   i       =   n     ;           B. generating a new function t f :Z N     m   →Z N     n    represented by a function table, where every mapping value (f 1 , . . . ,f n ) corresponding to a (x 1 , . . . , x m ) is placed in entry number X=N m−1 x m + . . . +N 1 x 2 +x 1  as the number F=N n−1 f n + . . . +N 1 f 2 +f 1 ;    C. for each i generating a new function t h,i :Z N     c     i →Z N     c     i  represented by a function table where every mapping value (h i,1 , . . . ,h i,c     i   ) corresponding to a (f a+1 , . . . ,f a+c     i   ), where              a   =       ∑     j   =   1       i   -   1       ⁢     c   i         ,           is placed in entry number X=N c     i     −1 f a+c     i   + . . . +N 1 f a+2 +f a+1  as the number H=N c     −1   h i,c     i   + . . . +N 1 h i,2 +h i,1 ;    D. initializing a new function table for a function t hf :Z N     m   →Z N     m   ;    E. setting y 0 =1, y 1 =1;    F. for every i from 2 to k setting y i =y i−1 N c     i     −1 ;    G. initializing a vector (b 1 , . . . ,b k ) to (0, . . . ,0);    H. for every i from 0 to N n −1: 
 i. setting u=t f (i);  
 ii. setting q=0;  
 iii. for every j from k to 1: 
 a. setting p to the integer result of u/y j ;  
 b. setting u=u−py j  to get the remainder;  
 c. setting p to the integer result of u/y j−1 ;  
 d. setting b j =t h,j (p);  
 e. adding y j b j  to q; and  
 
 iv. setting t hf (i)=q.  
   
   
   
       45 . A Turing platform, supporting unencrypted and partially encrypted polynomial computation for some machine M, on a host O, comprising: 
 A. a Turing machine;    B. a register writeable by a finite control of the Turing machine and readable by M;    C. a register readable by the finite control of the Turing machine and writeable by M;    D. a register writeable by the host O; and    E. a register readable by the host O.    
   
   
       46 . A method of computing with host O running a Turing platform T supporting at least one of a Mealy or BSS′ machine M, comprising: 
 A. initializing the machine;    B. initialize the Turing platform;    C. reading, by T, a storage cell at which its finite control is located;    D. writing, by T, a contents of the storage cell to a register readable by M;    E. writing, by O, to a remaining input of M;    F. executing, by O, one computation step for M;    G. writing, by O, some output of M to part of the register readable by T;    H. writing, by O, M′s computed direction of movement for the finite control of T to a remainder of register readable by T;    I. writing, by O, a rest of the output of M to the host O.    J. reading, by T, from the readable register of T;    K. writing, by T, a new cell value to storage;    L. moving the finite control of T one of left, right, and not at all;    M. checking by O to see if a halting condition has occurred; and    N. repeating steps (C)-(M).    
   
   
       47 . The apparatus of a register machine, comprising: 
 A. a set P={{right arrow over (P)} (i     1   , . . . ,i d )} of vectors of integers in Z N   d  indexed by vectors also in Z N   d ;    B. either a vector S indicating the end of the program in P, or a constant T, which functions as an instruction indicating that the computation is finished;    C. a vector {right arrow over (C)}∈Z N   d  functioning as instruction pointer;    D. a set S={{right arrow over (S)} i     1     , . . . ,i     d     ) } of vectors of integers in Z N   d  indexed by vectors also in Z N   d ;    E. a vector {right arrow over (D)}∈Z N   d  functioning as storage pointer;    F. at least one register ({right arrow over (R)} 1 , . . . ,{right arrow over (R)} m ) of vectors of integers in Z N   d  for 0<m≦N;    G. a next instruction pointer mapping f({right arrow over (R)} 1 , . . . ,{right arrow over (R)} m ,{right arrow over (P)} {right arrow over (C)} ,{right arrow over (S)} {right arrow over (D)} ,{right arrow over (C)},{right arrow over (D)}):Z N   d(m+4) →Z N   d ;    H. a next storage pointer mapping g({right arrow over (R)} 1 , . . . ,{right arrow over (R)} m ,{right arrow over (P)} {right arrow over (C)} ,{right arrow over (S)} {right arrow over (D)} ,{right arrow over (C)},{right arrow over (D)}):Z N   d(m+4) F→Z N   d ;    I. a specification of the registers that accept input from the host platform;    J. a number k of registers not accepting input from the host platform, such that 0≦k≦m;    K. a register transition mapping h({right arrow over (R)} 1 , . . . ,{right arrow over (R)} m , {right arrow over (P)} {right arrow over (C)} ,{right arrow over (S)} {right arrow over (D)} ,{right arrow over (C)},{right arrow over (D)}):Z N   d(m+4) →Z N   kd ;    L. a storage transition mapping q({right arrow over (R)} 1 , . . . ,{right arrow over (R)} m ,{right arrow over (P)} {right arrow over (C)} ,{right arrow over (S)} {right arrow over (D)} ,{right arrow over (S)} D ,{right arrow over (C)},{right arrow over (D)}):Z N   d(m+4) →Z N   d ;    M. a specification for initializing P and S; and    N. a specification for where input is entered, including: 
 through at least one register,  
 through at least one storage space S,  
 through an initial contents of an instruction space P, or  
 through an initial contents of the at least storage space S.  
   
   
   
       48 . A method of initializing a register machine comprising the steps of: 
 A. specifying initial values of {right arrow over (R)} 1 , . . . ,{right arrow over (R)} m ,{right arrow over (C)},{right arrow over (D)};    B. optionally specifying values for at least one storage cell {right arrow over (S)} {right arrow over (D)}  in S;    C. specifying elements in P; and    D. computing values of {right arrow over (P)} {right arrow over (C)}  and {right arrow over (S)} {right arrow over (D)}.      
   
   
       49 . A method of using a register machine, comprising the steps of: 
 A. initializing the register machine;    B. computing a next instruction pointer: {right arrow over (C)}′=f({right arrow over (R)} 1 , . . . ,{right arrow over (R)} m ,{right arrow over (P)} {right arrow over (C)} ,{right arrow over (S)} {right arrow over (D)} ,{right arrow over (C)},{right arrow over (D)});    C. computing a next storage pointer: {right arrow over (D)}′=g({right arrow over (R)} 1  . . . ,{right arrow over (R)} m ,{right arrow over (P)}{right arrow over (C)},{right arrow over (S)} {right arrow over (D)} ,{right arrow over (C)},{right arrow over (D)});    D. computing a value to be written to a current storage cell: {right arrow over (S)}′=q({right arrow over (R)} 1 , . . . ,{right arrow over (R)} m ,{right arrow over (P)} {right arrow over (C)} ,{right arrow over (S)} {right arrow over (D)} ,{right arrow over (C)},{right arrow over (D)});    E. computing the register transition mapping: ({right arrow over (R)} j , . . . ,{right arrow over (R)} j     k   )=h({right arrow over (R)} 1 , . . . ,{right arrow over (R)} m , {right arrow over (P)} {right arrow over (C)} ,{right arrow over (S)} {right arrow over (D)} ,{right arrow over (C)},{right arrow over (D)}), where j i , . . . ,j k  specify the registers which the register machine may change;    F. setting {right arrow over (S)} {right arrow over (D)} ={right arrow over (S)}′, {right arrow over (C)}={right arrow over (C)}′, and {right arrow over (D)}={right arrow over (D)}′;    G. computing {right arrow over (P)} {right arrow over (C)}  and {right arrow over (S)} {right arrow over (D)}  using input from a host; and    H. repeating steps (B)-(G) until a halting condition is satisfied.    
   
   
       50 . The method as claimed in  claim 48 , further comprising: 
 I. specifying a register dedicated to output of movement direction, using an integer y such that 0<y≦m, and an integer z such that 0<z≦d;    J. specifying a register dedicated as output to a Turing platform; and    K. specifying a register dedicated as input from a Turing platform, wherein each storage unit is a vector in Z N   d .    
   
   
       51 . A method of using a register machine M on a host O comprising the steps of: 
 A. initializing a register machine;    B. initializing a Turing platform;    C. reading, by T, a storage cell at which its finite control is located;    D. writing, by T, a contents of the storage cell to a specified register of M;    E. writing, by O, to a remaining specified input registers of M;    F. computing the next instruction pointer: {right arrow over (C)}′=f ({right arrow over (R)} 1 , . . . ,{right arrow over (R)} m ,{right arrow over (P)} {right arrow over (C)} ,{right arrow over (S)} {right arrow over (D)} ,{right arrow over (C)},{right arrow over (D)});    G. computing the next storage pointer: {right arrow over (D)}′=g({right arrow over (R)} 1 , . . . ,{right arrow over (R)} m ,{right arrow over (P)} {right arrow over (C)} ,{right arrow over (S)} {right arrow over (D)} ,{right arrow over (C)},{right arrow over (D)});    H. computing the value to be written to the current storage cell: {right arrow over (S)}′=q({right arrow over (R)} 1 , . . . ,{right arrow over (R)} m ,{right arrow over (P)} {right arrow over (C)} ,{right arrow over (S)} {right arrow over (D)} ,{right arrow over (C)},{right arrow over (D)});    I. computing the register transition mapping: ({right arrow over (R)} j     1   , . . . ,{right arrow over (R)} j     k   )=h({right arrow over (R)} 1 , . . . ,{right arrow over (R)} m ,{right arrow over (P)} {right arrow over (C)} ,{right arrow over (S)} {right arrow over (D)} ,{right arrow over (C)},{right arrow over (D)}) where j 1 , . . . ,j k  specify the registers which the register machine may change;    J. setting {right arrow over (S)} {right arrow over (D)} ={right arrow over (S)}′, {right arrow over (C)}={right arrow over (C)}′, and {right arrow over (D)}={right arrow over (D)}′;    K. computing {right arrow over (P)} {right arrow over (C)}  and {right arrow over (S)} {right arrow over (D)} ;    L. reading, by T, from the readable register of M;    M. writing, by T, a new cell value to storage;    N. reading, by T, from a second readable register of M its direction of movement;    O. moving the finite control of T one of left, right, and not at all;    P. checking by O to see if a halting condition has occurred; and    Q. repeating steps (C)-(P).    
   
   
       52 . A method of symbolically composing f:Z N   m →Z N   d  with h 1 , . . . , h k :Z N   d     i   →Z N   c     i   , producing the mapping f(h 1 (x e(1,1) , . . . ,x e(1,d     1   ), . . . ,x e(k,d     k)   )),  
     
       
         
           
             
               
                 ∑ 
                 
                   i 
                   = 
                   1 
                 
                 k 
               
               ⁢ 
               
                 c 
                 i 
               
             
             = 
             m 
           
         
       
     
     comprising the steps of: 
 A. acquiring a specification of index selections e(1,1), . . . , e(1, d 1 ), . . . , e(k,1), . . . , e(k,d k ) deciding how variables are used in the composition;  
 B. initializing a vector (a 1 , . . . ,a m ) to (0, . . . ,0);  
 C. performing, for every i from 0 to N m −1 
 1. For every j from k to 1 compute h j (a e(j,1) , . . . ,a e(j,d     j     ) ) do: 
 a. setting t fh (a 1 , . . . , a m )=f (h 1 , . . . , h k );  
 b. increment a vectorized index (a 1 , . . . ,a m ).  
 
 
 
   
   
       53 . A method of symbolically composing h 1 , . . . , h k  with f producing the mapping  
       (h 1 (f e′(1,1) (x 1 , . . . ,x m ), . . . ,f e′(1,c     1     ) (x 1 , . . . ,x m ),x e(1,1) , . . . ,x e(1,d     1     ) ), . . . , h k (f e′(k,1) (x 1 , . . . ,x m ), . . . ,f e′(k,c     k     ) (x e(k,1 ), . . . ,x e(k,d     k     ) )),  comprising the steps of:    A. acquiring a specification of index selections e′(1,1), . . . , e′(1,c   i   ), . . . , e′(k,1), . . . ,e′(k, c k ) deciding how mapping components are used in the composition;    B. acquiring a specification of index selections e(1,1), . . . ,e(1, d 1 ), . . . ,e(k,1), . . . ,e(k, d k ) deciding how variables are used;    C. setting a vector (a 1 , . . . ,a m ) to (0, . . . ,0);    D. For every i from 0 to N m −1 do: 
 1. For every j from k to 1 compute h j (f e′(j,1) , . . . ,f e′(j,c     j     ) ,x e(j,1) , . . . , x e(j,d     j     ) ); 
 a. Setting t hf (a 1 , . . . ,a m )=(h 1 , . . . ,h k ).  
 
   b. Increment the vectorized index (a 1 , . . . ,a m ).    
   
   
       54 . A method of specifying a pattern of parametrized encryption of multivariate mappings with other multivariate mappings comprising the steps of: 
 A. selecting a number of mapping components c i  to be grouped together, c i ≧1, for all l successive groups of components, covering all components in a mapping only once;    B. selecting a number of variables c i  to be grouped together, c i ≧1, for all k−l successive groups of variables, covering all variables in a mapping only once;    C. selecting a group of variables g i , l<g i ≦k, to be used as “parameter”, or explicitly selecting no such “parameter” for all k successive groups of components and variables;    D. selecting groups of mapping components to be encrypted;    E. selecting groups of variables to be used in encrypted form; and    F. selecting equality restrictions to be placed on components in the key quadruples.    
   
   
       55 . A method of generating keys for parametrized multivariate encryption of multivariate mappings, comprising the steps of: 
 A. determining an appropriate representation for the keys;    B. defining for an i th  key quadruple that is to do parametrized encryption/decryption two temporary N c     i     +c     gi   ×(c i +1) arrays R and S;    C. defining for an i th  key quadruple that is to do non-parametrized encryption/decryption two temporary N c     i   ×(c i +1) arrays R and S;    D. repeating steps (A)-(C) for all i quadruples;    E. defining a temporary polynomial f to translate from base-N vectors to base-N c     i    with c i  components;    F. permuting a ring Z N     c       i   , and simultaneously translating the permutation and its inverse to the field Z c     i     N ;    G. repeating step (F) in all N c     gi    times while recording data, for key quadruples that are to do parametrized encryption/decryption; and    H. repeating steps (E)-(G) of generating permutations for every key quadruple.    
   
   
       56 . The method as claimed in  claim 55 , wherein the mappings to be encrypted are expressed using polynomials, further comprising the step of computing encryption and decryption mappings by interpolation, using at least a portion of R and S as interpolation data and using a i (x), once for each unique key quadruple that is to be generated.  
   
   
       57 . The method as claimed in  claim 55 , further comprising the step of restricting a new set of key quadruples according to a pattern used for encryption.  
   
   
       58 . The method as claimed in  claim 55 , further comprising the step of setting all key quadruples that are to do neither encryption nor decryption to the identity mapping.  
   
   
       59 . A method of encrypting multivariate mappings with parametrized multivariate mappings, comprising the steps of: 
 A. determining appropriate mapping representation for the encryption;    B. symbolically substituting each group of variables {right arrow over (w)} i−l  to be decrypted in a parametrized manner with s i ({right arrow over (w)} i−l , {right arrow over (w)} g     i     −l );    C. symbolically substituting each group of variables {right arrow over (w)} i−l  to be decrypted in a non-parametrized manner with s i ({right arrow over (w)} i−l );    D. symbolically composing each group of mapping components {right arrow over (v)} i  to be encrypted in a parametrized manner with r i ({right arrow over (v)} i , {right arrow over (w)} g     i     −l ); and    E. symbolically composing each group of mapping components {right arrow over (v)} i  to be encrypted in a non-parametrized manner with r i ({right arrow over (v)} i ).    
   
   
       60 . A method of specifying an encryption pattern for parametrized encryption of a register machine, comprising the steps of: 
 A. defining a pattern of parametrized encryption;    B. setting all c i =d for a mapping doing computations of the register machine;    C. marking at least one register affected by a register transition mapping as plaintext registers;    D. marking a next instruction pointer and next storage pointer mappings as plaintext mappings;    E. marking key quadruples for the marked registers as not to be encrypted/decrypted;    F. marking the register transition mapping for non-parametric encryption;    G. marking the storage cell mapping q for parametric encryption; and    H. marking at least one “cell” in the storage space as plaintext “cells”.    
   
   
       61 . A method of key generation for parametrically encrypting a register machine, comprising the steps of: 
 A. determining a representation for keys;    B. defining, for a key quadruple that is to do parametrized encryption/decryption on storage cells, two temporary N d+d ×(d+1) arrays R and S;    C. defining for an i th  key quadruple that is to do non-parametrized encryption/decryption on register variables two temporary N d ×(d+1) arrays R and S;    D. defining a temporary polynomial to translate from base N d  to base-N vectors with d components;    E. permuting a ring Z N     d   , and simultaneously translating the permutation and its inverse to a field Z N   d ;    F. setting the permutations to the identity mapping for the cells in the storage mapping marked as unencrypted;    G. repeating step (F) in all N d  times, except for cells in the storage mapping marked as unencrypted, while recording data, for the key quadruples that are to do parametrized encryption/decryption on the storage mapping;    H. permuting the ring Z N     d   , and simultaneously translating the permutation and its inverse to the field Z N   d ; and    I. repeating the permuting step (H) for every key quadruple that is to encrypt a register transition mapping.    
   
   
       62 . The method as claimed in  claim 61 , wherein mappings are represented using polynomials, further comprising the step of: 
 computing i th  encryption and decryption mappings using in all 2d polynomial interpolations using R and S and a base-translation function f for all i quadruples.    
   
   
       63 . The method as claimed in  claim 60 , further comprising: 
 determining an appropriate representation for an encryption of the register machine; and    encrypting the register machine.    
   
   
       64 . The method as claimed in  claim 61 , further comprising the step of acquiring an set of key quadruples for use compositions.  
   
   
       65 . The method as claimed in  claim 10 , wherein the steps (A)-(E) are performed by a computer.  
   
   
       66 . The method as claimed in  claim 13 , wherein the steps (A)-(D) are performed by a computer.  
   
   
       67 . The method as claimed in  claim 14 , wherein the steps (A)-(F) are performed by a computer.