Patent Publication Number: US-11394525-B2

Title: Cryptography device having secure provision of random number sequences

Description:
BACKGROUND OF THE INVENTION 
     The present invention generally relates to cryptography devices, and more particularly to cryptography devices that avoid manipulation of secret data, such as keys and random number generator seeds, in plaintext to thereby be more resilient to side-channel attacks including white-box attacks designed to discern such secret data. 
     Broadly, cryptography provides mechanisms by which a private plaintext message may be protected from being divulged by converting the message into a ciphertext that may only be deciphered, i.e., converted back into the plaintext by specific persons or entities that are privy to a secret key required for performing the deciphering operation. 
     Two major categories of cryptography are shared secret cryptography and private-key-public-key cryptography (herein, simply referred to as public key cryptography). The former includes the Digital Encryption Standard (DES) and the Advanced Encryption Standard (AES). The latter includes Rivest-Shamir-Adleman (RSA). 
     In shared secret cryptography the encrypting party and the decrypting party share a secret key (herein, the shared secret key) that is used to both encrypt and decrypt a message. In public key cryptography, the recipient of a ciphertext message, i.e., the decrypting party, has a private key or secret key required to decipher ciphertext messages encoded with the public key. In other words, there is an association between a particular private key and a particular public key; they form a key pair. The public key is made available to anyone who wishes to send an encoded message (a ciphertext message) whereas the corresponding secret key is kept secret by the intended recipient of messages. 
     Traditionally, cryptography relied on a message being turned into a ciphertext, that only sender and recipient would know the required keys, and that the encryption and decryption processes would not be available for a nefarious person trying to discern the secret message. Keys were protected by not giving access to the machines that were used to decrypt a text. The endpoints of a communication is trusted and the communication channel between the endpoints is protected by turning messages into ciphertext that cannot be decrypted without access to the required decryption key. This is referred to as black-box cryptography. 
     However, there are situations where the cryptography device has to be made available on open devices to a party that not necessarily should have access to the cryptography key. For example, in a digital rights management (DRM) scenario a publisher may wish to make a DRM protected work available to a subscriber. As long as the subscriber satisfies the terms of the subscription, the work is available. However, at the end of a subscription term, the subscriber should not have access to the work. 
     The open nature of these systems, which may be referred to as white-box environments—whether PCs, tablets, or smart phones—renders the cryptography software extremely vulnerable to attack because the attacker has complete control of the execution platform and of the software implementation itself. The attacker can easily analyze the binary code of the cryptography application and, for example, memory pages used for temporary storage during the execution by intercepting system calls, tampering with the binary or execution files. Such manipulation may, for example, be performed using debuggers and hardware emulation tools. 
     These attacks include trace execution, examination of intermediate results, and access to keys located in memory as well as performance of static analysis on the cryptography software and alteration of sub-computations for perturbation analysis. 
     Generally, countermeasures aimed to protect against such attacks in a white-box environment are referred to as white-box countermeasures. 
     If the work is protected through cryptography, the decryption key may be provided on the subscriber&#39;s cryptography device, e.g., a mobile device such as a mobile telephone, in a manner that it can be used by the device to decrypt the work without revealing either the key or the algorithm to the subscriber. The key might be hidden in some way inside the code implementing the decryption algorithm may be obfuscated so that it is very difficult to determine any information about the value of key. Cryptographic countermeasures in a white-box environment are referred to as white-box cryptography. 
     White-box cryptography was first described by Chow et al. in [Chow AES] Stanley Chow, et al.,  White - Box Cryptography and an AES Implementation , in  Proceedings of the  9 th    International Workshop on Selected Areas in Cryptography  (SAC 2002), volume 2595 of  Lecture Notes in Computer Science , pp. 250-270. Springer, 2002 and in [Chow DES] Stanley Chow, et al.,  White - Box Cryptography DES Implementation for DRM applications , in  Proceedings of the ACM Workshop on Security and Digital Rights Management  (DRM 2002), volume 2696 of  Lecture Notes in Computer Science , pp. 1-15. Springer, 2002. [Chow AES] and [Chow DES] are both incorporated herein by reference in their entireties. 
     However, hitherto, all practical white-box cryptography approaches have been broken. Therefore, there is still an unmet need to provide cryptography devices that protect cryptographic keys from being divulged. 
     Random numbers are frequently used in cryptographic operations. For example, to introduce a bit more obfuscation into a calculation, the calculation may introduce a random value. Another example in which random numbers are used is ElGamal encryption. ElGamal is an example of public key encryption. To create a public key, the key generator selects a random number. Many algorithms involving random number sequences, require the sequences to be deterministic, i.e., reproducible. 
     Other uses of random numbers in white-box cryptography include challenge-response protocols in which the challenge is created using a random number, the generation of nonce vales in ECDSA (Elliptic Curve Digital Signature Algorithm) signatures, random number masks (in white-box countermeasures), and random padding of signatures and encrypted values. 
     Pseudo random number generators typically operate using a seed value. See e.g., Elaine Barker and John Kelsey,  Recommendation for Random Number Generation Using Deterministic Random Bit Generators , NIST Special Publication 800-90A, NIST, January 2012. That seed value presents a vulnerability to the underlying cryptographic scheme. 
     From the foregoing it will be apparent that there is still a need for improving the security of devices that rely on white-box cryptography by providing a secure mechanism for generating deterministic pseudorandom number sequences. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a schematic illustration of a mobile device optionally connected over a network to one or more servers from which the mobile device may obtain materials which it would perform cryptographic operations on, for example, for obtaining access to digital rights management protected content. 
         FIG. 2  is a schematic illustration of a cryptography device, e.g., a mobile device such as a mobile telephone or tablet. 
         FIG. 3  is a schematic illustration of programs and data stored in a memory of the cryptography device of  FIG. 2 . 
         FIG. 4  is a high-level schematic illustration of a mobile device having a white-box cryptography module program listing that may be stored in the memory of a cryptography device as illustrated in  FIG. 3  and which performs a cryptographic operation, e.g., an Advanced Encryption Standard (AES) decryption, to obtain access to a message obtained from a server. 
         FIG. 5  is a diagram illustrating basic concept of pseudorandom sequence generation. 
         FIG. 6  is a flowchart of an exemplary deterministic pseudorandom number generator. 
         FIG. 7  is a diagram illustrating the generation of a random number sequence using n+p multivariate quadratic polynomials such that then first polynomials have quadratic monomials and no linear terms. 
         FIG. 8  is a diagram illustrating an alternative embodiment for generation of a random number sequence using n+p multivariate quadratic polynomials such that the n first polynomials are multivariate quadratic polynomials with or without linear terms. 
         FIG. 9  is a diagram illustrating a second alternative embodiment for generation of a random number sequence. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     In the following detailed description, reference is made to the accompanying drawings that show, by way of illustration, specific embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the invention. It is to be understood that the various embodiments of the invention, although different, are not necessarily mutually exclusive. For example, a particular feature, structure, or characteristic described herein in connection with one embodiment may be implemented within other embodiments without departing from the spirit and scope of the invention. In addition, it is to be understood that the location or arrangement of individual elements within each disclosed embodiment may be modified without departing from the spirit and scope of the invention. The following detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the appended claims, appropriately interpreted, along with the full range of equivalents to which the claims are entitled. In the drawings, like numerals refer to the same or similar functionality throughout the several views. 
     In an embodiment of the invention, a cryptographic device, e.g., a mobile telephone, a tablet, or a personal computer executes a white-box cryptography mechanism incorporating a deterministic random number generator in which the random number generator seed value is not manipulated in plaintext on the cryptographic device. 
       FIG. 1  is a schematic illustration of a network  111  connecting a cryptographic device  103 , e.g., a mobile telephone, a tablet, or a personal computer, to one or more remote servers  113 . The cryptographic device  103  is operated by a user  101  who interacts with one of the servers  113  via a web browser window  105  of a web browser. In the example scenario illustrated in  FIG. 1 , the cryptographic device provides the cryptographic operations on behalf of the user  101 , e.g., to decrypt messages, e.g., message C  115 , which may correspond to a plaintext message M, and which is received from the remote server  113   a . The messages may be a DRM protected content, such as a computer program or a music library. While not always used in such scenarios, deterministic random number generation is used in some protocols, for example, in challenge-response protocols in which the challenge is generated using a pseudo random generator. 
     While  FIG. 1  provides an illustration of one scenario in which cryptography may play an important role; there are many other important uses for cryptography. Thus, the technology described herein is not limited in its application to the usage example illustrated in  FIG. 1 . 
     In one embodiment, discussed in conjunction with  FIGS. 5 through 9 , a cryptographic device  103  receives an encrypted random-number-generation seed value from a secure environment  701  ( FIGS. 7-9 ) and generates an encrypted random number sequence from the encrypted seed and decrypts the result to obtain a decrypted random number sequence as if the random number sequence had been generated from the plaintext seed corresponding to the encrypted seed value. 
       FIG. 2  is a schematic illustration of a cryptography device  103 , for example, a mobile telephone, tablet, or personal computer. The cryptography device  103  may include a processor  201  connected via a bus  202  to a random access memory (RAM)  203 , a read-only memory (ROM)  204 , and a non-volatile memory (NVM)  205 . The cryptography device  103  further includes an input/output interface  207  for connecting the processor  201 , again typically via the bus  202 , to a connector  211  by which the cryptography device  103  may be connected to an antenna  211  by which the cryptography device  103  may connect to various forms of wireless networks, e.g., wide-area networks, WiFi networks, or mobile telephony networks. Alternatively, the cryptography device  103  may connect to networks via wired network connections such as Ethernet. 
     The ROM  204  and/or NVM  205  may include computer programs  301  as is illustrated in  FIG. 3 . While it is here depicted that the computer programs  301  are all co-located in the ROM  204  or the NVM  205 , in actual practice there is no such restriction as programs may be spread out over multiple memories and even temporarily installed in RAM  203 . Furthermore, the portable security device  109  itself may include multiple ROMs or NVMs. The programs  301  include operating system programs  219  as well as application programs loaded onto the cryptography device  103 . 
     In a preferred embodiment, the programs include a white-box cryptography mechanism  213 . While depicted in  FIG. 3  as a distinct module  213 , in many implementations a white-box cryptography mechanism may be implemented as a number of tables, which, for the purpose of obfuscation, may be scattered about in the memory  205 . Such implementation details are outside the scope of this document. 
     The cryptography mechanism  213  of the cryptography device  103 , implements one or more cryptography functions (CF)  215 , which may be implemented as a number of computation blocks  217 . 
     The ROM  204  or NVM  205  may also contain private data, such as a secret key  221 , stored either in its basic form or in derived quantities. While in many white-box cryptography mechanisms the shared secret is stored on the cryptography device  103 , in a preferred embodiment, the shared secret is not stored on the cryptography device  103 . The details of the secret key  221  stored and used in conjunction with the white-box cryptography mechanism  213  is described in greater detail below. 
     Thus, the cryptography device  103  may receive a document, a message, or an encrypted program as the encrypted message C  115  via the connector  211 . The processor  201 , by executing instructions of the cryptography module  213 , may decrypt the document/message using the secret key  221  according to the mechanism described herein below. 
       FIG. 4  is a high level schematic illustration illustrating a prior art embodiment white-box cryptography mechanism. A service provider  413  (analogous to the service provider  113  of  FIG. 1 ) may provide an encrypted message M  415  to the cryptography device  403  (analogous to device  103  of  FIG. 1 ). The message  415  is encrypted using a key K  417  known to both the service provider  413  and the cryptography device  403 . In the case of shared secret cryptography, the key K  417  is a shared secret. In the case of public key cryptography, the key  417  is a public/private key pair where the service provider  413  is possession of the public key and the cryptography device  403  is in possession of the private key. 
     A white-box cryptography mechanism  419  executing on the cryptography device  403  decrypts the message  415  using the shared secret  417  stored on the cryptography device  403 . In a prior art white-box cryptography mechanism  419 , the cryptography algorithms may be implemented as set of tables stored in memory with the shared secret  417  hidden within these tables. 
     Patent application entitled “Cryptography Device Having Improved Security Against Side-Channel Attacks” of the same inventors describes a mechanism for using homomorphic encryption in the context of white-box cryptography. This mechanism makes use of a deterministic random sequence to improve the security of the cryptographic processes employed therein. As the random sequence generation is one factor in providing security to the cryptography mechanism, it is important to protect the security of the random sequence generation mechanism. 
     Pseudorandom number sequences are typically generated from a seed.  FIG. 5  is a flowchart illustrating the basics of random sequence generation. The seed value  501  is input to a random sequence generator  503 . The random sequence generator uses the seed value to generate one or more random sequences  505 . In other words, one seed value may be used to generate multiple sequences. 
     One mechanism for doing so is to provide an internal state  507 , which is used by an output function to compute each random sequence  505 . The internal state  507  is updated by an update function  509 . On each invocation of the random sequence generator  503 , the update function  509  generates a new internal state. The seed  501  is used to initialize the internal state  507 . 
     An output function  511  uses the internal state  507  to compute each random sequence  505 . 
     According to embodiments—illustrated in  FIG. 7 ,  FIG. 8 , and  FIG. 9 —the seed, the security of which is important to protecting the overall security of a cryptographic mechanism that uses random sequences, is not handled in plaintext. 
     Consider first, without considering cryptographic protection of the seed, an algorithm for generating a deterministic pseudorandom number sequence without consideration for protection of the seed. One such algorithm is illustrated in the flow chart of  FIG. 6 , which includes four phases:
         Parameter definition   Provisioning   Initialization   Calls to obtain deterministic random sequence.       

     Parameter Definition 
     First, a few parameters may be defined, including n, the number of elements in the internal state, S, and the p, the number of elements in the output pseudorandom number sequence, step  601 . 
     Provisioning 
     Next, in the provisioning phase, n+p multivariate polynomials Q j  in n variables denoted by Q 1 (x 1 , . . . , x n ), . . . , Q n+p (x 1 , . . . , x n )=Q 1 (x), . . . , Q n+p (x) are defined, step  603 . The polynomials Q are used to (1) update the internal state, S, and to calculate the output deterministic random sequence, O, where O is a sequence of p pseudorandom numbers. Each polynomial Q j  accepts the n values of the internal state S i  as input parameters. 
     The n first multivariate polynomials Q j  are used to update the internal state (i.e., to compute S i+1 ) and the p remaining multivariate polynomials are used to output a pseudorandom value, O i . 
     While there are many possibilities for the polynomials Q, preferred embodiments include the following cases:
         Case 1. (illustrated in  FIG. 7 ) Q is an n+p multivariate quadratic polynomials such that the n first polynomials have quadratic monomials and no linear terms (and the p remaining polynomials are multivariate quadratic polynomials with or without linear terms)   Case 2. (illustrated in  FIG. 8 ), which is a general case of Case 1, Q is an n+p multivariate quadratic polynomials such that the n first polynomials are multivariate quadratic polynomials with or without linear terms (and the p remaining polynomials are multivariate quadratic polynomials with or without linear terms)       

     Thus, for both Case 1 and Case 2, for the embodiments of  FIG. 7  and  FIG. 8 , respectively, the functions Q 1 (x), . . . , Q n (x) have the form: 
     
       
         
           
             
               Q 
               k 
             
             = 
             
               
                 ∑ 
                 
                   i 
                   , 
                   j 
                 
               
               ⁢ 
               
                 
                   λ 
                   
                     i 
                     , 
                     j 
                   
                 
                 ⁢ 
                 
                   x 
                   i 
                 
                 ⁢ 
                 
                   x 
                   j 
                 
               
             
           
         
       
     
     For Case 1, the embodiment of  FIG. 7 , the functions Q n+1 (x), . . . , Q p (x) have the form: 
     
       
         
           
             
               Q 
               k 
             
             = 
             
               
                 ∑ 
                 
                   i 
                   , 
                   j 
                 
               
               ⁢ 
               
                 
                   λ 
                   
                     i 
                     , 
                     j 
                   
                 
                 ⁢ 
                 
                   x 
                   i 
                 
                 ⁢ 
                 
                   x 
                   j 
                 
               
             
           
         
       
     
     I.e., for the embodiment of  FIG. 7 , all the Q i  functions have the same form. 
     For Case 2, the embodiment of  FIG. 8 , the functions Q n+1 (x), . . . , Q p (x) have the form: 
               Q   k     =         ∑     i   ,   j       ⁢       λ     i   ,   j       ⁢     x   i     ⁢     x   j         +       ∑   i     ⁢       α   i     ⁢     x   i                 
The coefficients λ i,j  and α i  are set by a provisioning server, e.g., the secure environment  701  of  FIG. 7  and  FIG. 8 .
 
     The embodiment of  FIG. 9 , key switch, may be a variant of either Case 1 or Case 2. Thus, the form of the Q i  functions for that embodiments depends on whether it is a variant of Case 1 or Case 2. 
     Next, a seed vector having 2n values is received, step  605 . In an alternative embodiment, the provisioning phase may also include provisioning the cryptographic device with any required constants. An example of the latter is illustrated in  FIG. 8   
     As is discussed in greater detail here in below, in preferred embodiments, the seed vector is encrypted in a secure environment prior to being provisioned to a cryptographic device  103 . 
     In preferred embodiments, the seed vector SD is encrypted using the ElGamal homomorphic encryption system, described in [Elgamal] T. Elgamal,  A public key cryptosystem and a signature scheme based on discrete logarithms , IEEE Transactions on Information Theory (Vol. 31, Issue. 4, July 1985). Details of ElGamal encryption are provided herein below. 
     Being a homomorphic encryption system, ElGamal provides the mechanism of allowing computations to be performed on encrypted values such that a decryption of the computation result is the same as the performance of the same calculation on corresponding plaintext values. Consider a quantity x, which encrypted in to a value y and a function ƒ(x). If the homomorphic property holds over f(x), then ƒ(x)=decrypt (y). This allows computations to be performed on decrypted values with the computation result eventually obtained through a decryption operation. 
     Initialization of the Internal State 
     From the seed vector, an initial internal state, S 0 , is initialized having n values, which are selected from the 2n values of the seed vector, step  607 . Details of one embodiment for the selection process is described in conjunction with  FIG. 7 . 
     Calls to Obtain a Deterministic Random Sequence O i    
     Internal State Update Function: When the cryptographic device  103  receives a call to calculate a new output deterministic random sequence O, the cryptographic device first updates the internal state S i  applies the polynomials Q j  to the previous internal state S i−1 , step  609 . 
     Each internal state member S i [j] is set to the value:
 
 S   i [ j ]= Q   j ( S   i−1 [1], . . . , S   i−n [ n ])
 
     Output Function, Step 1: Next, an encrypted output vector O is calculated, step  611 . As discussed herein above, for state i, p output values are produced in the output sequence O. At Step 1 (the encrypted output vector), the jth output value O i [j] is determined using the n+j th polynomial Q using the current internal state (S i ) as inputs:
 
 O   i [ j ]= Q   n+j ( S   i [1], . . . , S   i [ n ])
 
     Output Function, Step 2: As each input value S i  is a ciphertext value, the members O i  of the output vector are also ciphertext. These values O i  are therefore decrypted, step  613 , into a plaintext result V i . As discussed in greater detail below, there are several different options for performing the decryption. 
       FIG. 7  is an illustration of a mechanism for generating a random sequence in which a seed is provided by a secure environment  701 . In an embodiment of the mechanism of  FIG. 7  the seed is provided by the secure environment  701  and is not manipulated in cleartext by the cryptography device  103  thereby reducing the risk of attacks against the seed. The mechanism includes the following steps:
         Encrypting seed values in a secure environment   Provisioning cryptographic device with
           Encrypted seed values   Additional constants (Case 2, illustrated in  FIG. 8 )   
           Selecting initial internal state from seed value using an initial value   Updating the internal state   Generating encrypted intermediate output based on the internal state   Decrypting the encrypted intermediate output into a plaintext deterministic random sequence       

     Provisioning the Cryptographic Device with Seed Values 
     In one embodiment, the secure environment  701  may be an application server that provisions the white-box enabled cryptography algorithm, e.g., a server  113  of  FIG. 1 . A white-box cryptography algorithm  213 , e.g., an implementation of FHE protected cryptographic mechanism as described in the patent application “Cryptography Device Having Improved Security Against Side-Channel Attacks” of the same inventors, requires the use of a random sequence and provides an initial value (IV) in a call to getRandom(R), call  706 . 
     As is described hereinbelow, the getRandom( ) function  703 , selects an initial internal state (S 0 ) from an homomorphically encrypted seed value SD  721 , step  713 , provisioned by the secure environment  701 , step  720 . 
     The seed value SD may be generated based on some parameters. For example, one option is to use another random number generator in a secure environment to create a random value parameter. That random number generator should not be the same as pseudo random number generator of getRandom( )  703 . As discussed in greater detail hereinbelow, the seed value SD is provided in encrypted form and never used directly in plaintext on the cryptography device  103 . Alternatively, the cryptographic device  103  is pre-provisioned by the secure environment  701  with the seed value SD. 
     In one embodiment, the encryption of the seed value vector SD relies on homomorphic encryption, e.g., ElGamal encryption or a modification thereto (as described herein below). The homomorphic encryption to generate the seed vector SD may be performed by a homomorphic encryption procedure  715 . 
     ElGamal encryption is based on the algebraic concept of a cyclic ring G∈GF(p) of prime order q having a generator g. In preferred embodiments, p is a prime number of at least 2048 bits. Further, in preferred embodiments, the order q is a prime number of at least 200 bits. 
     The ElGamal secret key is x∈Z q *, i.e., in {1, . . . , q−1}. 
     The corresponding public key is the value h=g x , together with the cyclic ring, G, the generator, g, and the order of the ring, q. 
     To encrypt a value, the encrypting party selects a second value r∈Z q *, wherein r is typically a random value, and creates the ciphertext c=(c 1 , c 2 ) corresponding to a plaintext message m, by:
 
( c   1   ,c   2 )=( g   r   ,m*h   r )
 
     The input to the homomorphic encryption procedure  715  is a set of 2n messages, messages m=(m 1 , . . . , m 2n )  717 . Each message m i  is selected from Z q *. 
     The seed vector, SD, which the cryptographic device  103  is provisioned with by the secure environment  701 , is a sequence of ciphertexts having 2n elements:
 
 SD =( SD   1   ·SD   2   , . . . ,SD   2n )
 
where n is an arbitrary number. In practice n may not be very large; a practical upper limit for small cryptography devices may be 32.
 
     In a preferred embodiment each message m i    717  is a static value that is randomly selected for a particular deployment of the white-box cryptography mechanism described in  FIG. 7 , i.e., a particular cryptographic device  103 . The secure environment  701  may generate, randomly, the messages m i  and link them to a particular app on a particular cryptography device  103 . 
     The homographic encryption procedure  715  of the secure environment  701 , using ElGamal encryption, creates an encrypted sequence SD  719  from the messages m=(m 1 , . . . ,m 2n )  717  and the public key of the cryptographic device  103 , as follows: 
               SD   1     =     (       g   r     ,       m   1     *     h   r         )                   SD   2     =     (       g   r     ,       m   2     *     h   r         )               …               SD     2   ⁢   n       =     (       g   r     ,       m     2   ⁢   n       *     h   r         )           
wherein, the ElGamal public key of the cryptographic device  103  is the tuple (h,G,g,q) as described hereinabove.
 
     In general, the ElGamal scheme is homomorphic under multiplication, e.g., 
     
       
         
           
             
                 
             
             ⁢ 
             
               
                 
                   SD 
                   1 
                 
                 * 
                 
                   SD 
                   2 
                 
               
               = 
               
                 
                   ( 
                   
                     
                       
                         g 
                         r 
                       
                       * 
                       
                         g 
                         r 
                       
                     
                     , 
                     
                         
                     
                     ⁢ 
                     
                       
                         ( 
                         
                           
                             m 
                             1 
                           
                           * 
                           
                             h 
                             r 
                           
                         
                         ) 
                       
                       * 
                       
                         ( 
                         
                           
                             m 
                             2 
                           
                           * 
                           
                             h 
                             r 
                           
                         
                         ) 
                       
                     
                   
                   ) 
                 
                 = 
                 
                   ( 
                   
                     
                       g 
                       
                         2 
                         ⁢ 
                         r 
                       
                     
                     , 
                     
                         
                     
                     ⁢ 
                     
                       
                         m 
                         1 
                       
                       ⁢ 
                       
                         m 
                         2 
                       
                       ⁢ 
                       
                         h 
                         
                           2 
                           ⁢ 
                           r 
                         
                       
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
               
                 ( 
                 
                   
                     SD 
                     1 
                   
                   * 
                   
                     SD 
                     2 
                   
                 
                 ) 
               
               * 
               
                 ( 
                 
                   
                     SD 
                     3 
                   
                   * 
                   
                     SD 
                     4 
                   
                 
                 ) 
               
             
             = 
             
               
                 ( 
                 
                   
                     
                       g 
                       
                         2 
                         ⁢ 
                         r 
                       
                     
                     * 
                     
                       g 
                       
                         2 
                         ⁢ 
                         r 
                       
                     
                   
                   , 
                   
                       
                   
                   ⁢ 
                   
                     
                       ( 
                       
                         
                           m 
                           1 
                         
                         ⁢ 
                         
                           m 
                           2 
                         
                         * 
                         
                           h 
                           
                             2 
                             ⁢ 
                             r 
                           
                         
                       
                       ) 
                     
                     * 
                     
                       ( 
                       
                         
                           m 
                           3 
                         
                         ⁢ 
                         
                           m 
                           4 
                         
                         * 
                         
                           h 
                           
                             2 
                             ⁢ 
                             r 
                           
                         
                       
                       ) 
                     
                   
                 
                 ) 
               
               = 
               
                 ( 
                 
                   
                     g 
                     
                       4 
                       ⁢ 
                       r 
                     
                   
                   , 
                   
                       
                   
                   ⁢ 
                   
                     
                       m 
                       1 
                     
                     ⁢ 
                     
                       m 
                       2 
                     
                     ⁢ 
                     
                       m 
                       3 
                     
                     ⁢ 
                     
                       m 
                       4 
                     
                     ⁢ 
                     
                       h 
                       
                         4 
                         ⁢ 
                         r 
                       
                     
                   
                 
                 ) 
               
             
           
         
       
     
     and so on. 
     While the ElGamal scheme is homomorphic under multiplication, in the general case the ElGamal scheme is not homomorphic under addition. However, when the random exponent r is the same for two ciphertexts, the homomorphic property holds also for addition in some sense with respect to those two ciphertexts, e.g., the following computed value is a correct ElGamal ciphertext:
 
( g   r ,( m   1   h   r ))+( g   r ,( m   2   h   r ))=( g   r ,( m   1   +m   2 )* h   r )
 
wherein,
 
( g   r ,( m   1   +m   2 )* h   r )
 
is an ElGamal ciphertext corresponding to the plaintext of the addition m 1 +m 2 . For two ciphertexts (g r , m 1 h r ) and (g r , m 2 h r ), multiplication is as follows:
 
( g   r ,( m   1   h   r ))*( g   r ,( m   2   h   r ))=( g   2r ,( m   1   *m   2 )* h   2r )
 
     Thus, if R is the ciphertext exponent, which is updated on each operation, then for addition R=r both before and after the addition operation. However, for multiplication, R=r before the multiplication operation and R=2r after the multiplication operation. 
     In an alternative embodiment, a modified version of ElGamal encryption, which has similar properties to those described above, is used. In this modified version the following encodings are used: 
     
       
         
           
             
               SDM 
               1 
             
             = 
             
               ( 
               
                 
                   h 
                   r 
                 
                 , 
                 
                   
                     m 
                     1 
                   
                   * 
                   
                     g 
                     r 
                   
                 
               
               ) 
             
           
         
       
       
         
           
             
               SDM 
               2 
             
             = 
             
               ( 
               
                 
                   h 
                   r 
                 
                 , 
                 
                   
                     m 
                     2 
                   
                   * 
                   
                     g 
                     r 
                   
                 
               
               ) 
             
           
         
       
       
         
           … 
         
       
       
         
           
             
               SDM 
               
                 2 
                 ⁢ 
                 n 
               
             
             = 
             
               ( 
               
                 
                   h 
                   r 
                 
                 , 
                 
                   
                     m 
                     
                       2 
                       ⁢ 
                       n 
                     
                   
                   * 
                   
                     g 
                     r 
                   
                 
               
               ) 
             
           
         
       
     
     This modified ElGamal encryption scheme allows for implementing a trapdoor key that may be used at the end of the process of transferring the encrypted seed values to the cryptography device  103 , referred to as SDM to differentiate from seed values encrypted using the standard ElGamal, i.e., SD. 
     Preferably, the value of the messages m=(m 1 , . . . ,m 2n )  717  do not deliberately contain any redundancy. Rather, it is preferred that the values for the messages m=(m 1 , . . . ,m 2n )  717  are selected randomly because if a value m i  had some relationship to another value m j , an attacker could base an attack on the knowledge of the ratio m i /m j . To further strengthen the resilience against attacks based on the ratio m i /m j , the messages m=(m 1 , . . . ,m 2n )  717  may be constructed as products of a sequence of random values and a secret element k, e.g.:
 
 m   i =randomValue( )* k  
 
     The encrypted seed values SD (or SDM)  719  are transferred to the cryptography device  103 , step  720 . Thus, the cryptography device  103  has been provisioned with the vector (SD=SD 1 , . . . , SD 2n )  721 , which corresponds to the SD vector  719 . 
     Additional Provisioning for Case 2 
     In an alternative embodiment illustrated in  FIG. 8  (and referred to herein as Case 2), the cryptography device  103  is provisioned with a constant vector C  801 , step  803 , which is used when the output generation function includes linear terms. 
     Selecting an Initial Internal State (S 0 ) from a Seed Value Vector and an Initial Value (IV) 
     To obtain a random sequence, a function, getRandom ( )  703  is called by the cryptography device  103  to generate a random sequence based on an initial value (IV). Specifically, a random sequence consumer  705  calls getRandom( ), step  706 . A random sequence O is returned from getRandom( ), step  709 . 
     The random sequence consumer  705 , which may be a decryption algorithm called from a computation block  217  of the cryptography function  215  of the white-box cryptography mechanism  213 , calls getRandom( )  703  with an initial IV, step  706 . IV may be computed from parameters such as time or the message being encrypted. 
     The value IV may be passed as an argument to the function getRandom( )  703 , alternative mechanisms may be used for providing the value IV. 
     The function getRandom( )  703  is defined as a Deterministic Random Number Generator. In other words, from a specific initial value, IV, a reproducible random sequence is produced. That initial value IV is used in conjunction with a seed value, SD  721 , provided externally from the cryptography device  103 , e.g., from a secure environment  701 . 
     The getRandom(IV) function  703  uses an internal state S, to (1) compute a new internal state, S i ,  727  by an update function  729  based on the i−1th internal state, S i−1 , and, and, (2) compute an i-th output random sequence, O i    723 , using the updated internals state, S i , by a generation function  725 . The internal state S i  is composed of n ciphertexts, S i =(S i [1], . . . , S i [n]). The index i is incremented each time a new output sequence O i  is produced, e.g., on subsequent calls to the function getRandom ( )  703 . 
     The seed values SD (or SDM)  721  are used by the getRandom(IV) function  703  of the cryptography device  103  together with the initial value (IV)  711  to compute an initial internal state, S 0    728 , i.e., (S 0 [1], . . . , S 0 [n]). The initial state  728  is selected from the 2n SD (or SDM)  721  ciphertexts, using the initial value (IV)  711  by:
 
 S   0 =( S   0 [1], . . . , S   0 [ n ])
 
 S   0 =( S   0 [1]= SD   1+IV     1     *n   , . . . ,S   0 [ n ]= SD   n+IV     n     *n )
 
(SDM i  substituted for SD i  in alternative embodiments using the modified ElGamal scheme).
 
     As there are 2 n  possible values for IV, there are 2 n  possible initial values for the initial state, S 0 . 
     Update of Internal State, S i    
     Upon each call the getRandom( )  703 , the index counter i for the internal state S i  is incremented, step  707 . Thus, on the first call, the internal state is S 1 . The index counter is reset when a new initial internal state S 0  is selected from the SD  721  values, i.e., i is set to 0, step  728 . 
     As discussed herein above, the update function  729  and generation function  725  are formed by n+p multivariate polynomials in n variables denoted by Q 1 (x 1 , . . . , x n ), . . . , Q n+p (x 1 , . . . , x n )=Q 1 (x), . . . , Q n+p (x). The n first multivariate polynomials are used to update the internal state (i.e., to compute S i  from S i−1 ) and the p remaining multivariate polynomials are used to output a pseudorandom intermediate ciphertext output value, O i    734 , which subsequently optionally decrypted into a final output value V i    723 . 
     Thus, the update function  729 , updates the internal state S i [1], . . . , S i [n] using n polynomials Q i (x 1 , . . . , x n ), . . . , Q n (x 1 , . . . , x n ) of either of the forms described hereinabove, i.e., 
     
       
         
           
             
               
                 S 
                 i 
               
               ⁡ 
               
                 [ 
                 1 
                 ] 
               
             
             = 
             
               
                 Q 
                 1 
               
               ⁡ 
               
                 ( 
                 
                   
                     
                       S 
                       
                         i 
                         - 
                         1 
                       
                     
                     ⁡ 
                     
                       [ 
                       1 
                       ] 
                     
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   … 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       S 
                       
                         i 
                         - 
                         1 
                       
                     
                     ⁡ 
                     
                       [ 
                       n 
                       ] 
                     
                   
                 
                 ) 
               
             
           
         
       
       
         
           … 
         
       
       
         
           
             
               
                 S 
                 i 
               
               ⁡ 
               
                 [ 
                 n 
                 ] 
               
             
             = 
             
               
                 Q 
                 n 
               
               ⁡ 
               
                 ( 
                 
                   
                     
                       S 
                       
                         i 
                         - 
                         1 
                       
                     
                     ⁡ 
                     
                       [ 
                       1 
                       ] 
                     
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   … 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       S 
                       
                         i 
                         - 
                         1 
                       
                     
                     ⁡ 
                     
                       [ 
                       n 
                       ] 
                     
                   
                 
                 ) 
               
             
           
         
       
     
     Given the ElGamal encryption scheme in which an encryption is in the form (g r ,m*h y ), wherein the random value r was kept constant over the computation of all the seed value ciphertexts SD i  the application of the update polynomials Q i  changes the value r from one state S i  to the next state S i+1 . Specifically, for the two first update polynomial alternatives given above (i.e., polynomials of degree 2), if for a state S i−1  the random factor has the value r, the ElGamal random factor for state S i  is 2r, whereas for the general case (polynomials of degree d), the random value changes from r to d*r. 
     Accordingly, the update function  729  tracks the value r for each new internal state S i . 
     Output Generation Function  725 —Step One  733 : Compute Intermediate Ciphertext Output Values, O 
     The output generation function  725  is composed of two steps: Step One  733 , to compute intermediate ciphertext output values, O i ,  734  corresponding to the ultimate plaintext output values, V i    723 , and Step Two  735 : to optionally or partially decrypt the intermediate ciphertext output values O i  into the plaintext values V i . Step One  733  uses the internal state S i , which is output from the update function  729 , to compute the next ciphertext intermediate output value O i    734 , where O i  is a vector of output values; O i =(O i [1], . . . , O i [ p ]). 
     Case 1—Monomials of Degree 2 (Illustrated in  FIG. 7 ) 
     For Case 1, the first output, O 1 , has the form:
 
 O   1 =( O   1 [1]=( g   2     2     r   ,m′   1,1   ·g   2     2     r ) where, m′   1,1   =Q   n+1 ( S   1 [1], . . . , S   1 [ n ])
 
. . .
 
 O   1 [ p ]=( g   2     2     r   ,m′   p,1   ·g   2     2     r ) where, m′   1 [ p ]= Q   n+p ( S   1 [1], . . . , S   1 [ n ]))
 
     For Case 1 ( FIG. 7 ), the ith output, has the form:
 
 O   i =( O   i [1]=( g   2     i+1     r   ,m′   i [1]· g   2     i+1     r ) where, m′   i [1]= Q   n+1 ( S   i [1], . . . , S   i [ n ])
 
. . .
 
 O   i [ p ]=( g   2     i+1     r   ,m′   1 [ p ]· g   2     i+1     r ) where, m′   i [ p ]= Q   n+p ( S   i [1], . . . , S   i [ n ])
 
     Since the polynomials are monomials of degree 2, it is possible to evaluate the polynomials Q n+1 (x 1 , . . . , x n ), . . . , Q n+p (x 1 , . . . , x n ) over ciphertext values while maintaining values for the value r in the output such that the outputs O i , which also are ElGamal ciphertexts where O i  is the c2 value in a c=(c 1 , c 2 )=(g r ,m*h r ), have uniform values for r. In other words, at the end of the process, the value of the value r for all the output values O i  have the same value r and that value r is the same as the value r for the update function  729 . 
     The index i is the request number, i.e., an ever-increasing counter. For each request, the random r as used in the ElGamal encryption is incremented by r i+i =2*r i . Therefore, exponent in the ElGamal encryption becomes 2 i+1 *r as in g 2     i+1     r , m′ i [p]*g 2     i+1     r , for example. 
     Case 2: Multivariate Quadratic Polynomials (Illustrated in  FIG. 8 ) 
     In Case 2, the polynomials Q i  used by the output generation function  733 ′ are multivariate quadratic polynomials, e.g., for each variable there is a quadratic term and a linear term. 
     Consider the ElGamal encryption format:
 
 c =( c   1   ,c   2 )=( g   r   ,m*h   r )
 
     For illustrative purposes, let&#39;s use here R in lieu of r:
 
 c =( c   1   ,c   2 )=( g   R   ,m*h   R )
 
     The linear term of each polynomial Q i  can be computed on ciphertexts. The random value R of the resulting ciphertext is the same as the random value r of the input. On the other hand, the quadratic term of every polynomial, also computed on the ciphertexts, have a random value that is twice the random r of the input and twice the value for the linear term, i.e., the exponent is 2R=2r. 
     Therefore, for i=n+1, . . . , n+p, we have:
 
 Q   i ( x   1   , . . . ,x   n )= A   i ( x   1   , . . . ,x   n )+ B   i ( x   1   , . . . ,x   n )
 
     where A i  is a polynomial with monomials of degree 2 only and B i  is a linear polynomial. The partial evaluation of the polynomial Q j (x 1 , . . . ,x n ) over the state S i  provides two ciphered values: (g 2R , A i (S i [1], . . . , S i [n])*h 2R ) and (g R , B i (S i [1], . . . , S i [n])*h R ) 
     At round i+1, the value of R is expected to be 2 i r of the input ciphertexts SD i  used to select the initial internal state S 0 . 
     In an alternative embodiment, rather than computing (g R , B i (S i [1], . . . , S i [n])*h R ), a slightly different value is computed. Specifically, consider the knowledge of the ciphertext value (g R , B i (S i [1], . . . , S i [n])*h R ), the counter i, and a constant “ciphertext” C i =(g 2     i     r , (constant i *h r ) 2     i   ). From those values, it is possible to compute
 
( B   j ( S   i [1], . . . , S   i [ n ])* h   R )*((constant i )* h   r ) 2     i    
 
then, after the conclusion of Step One  733 ′ of the output generation step  735 ′, for Case 2 ( FIG. 8 ), for the first generation of an intermediate ciphertext output vector, i=1:
 
     
       
         
           
             
               
                 O 
                 1 
               
               ⁡ 
               
                 [ 
                 1 
                 ] 
               
             
             = 
             
               
                 
                   ( 
                   
                     
                       g 
                       
                         
                           2 
                           2 
                         
                         ⁢ 
                         r 
                       
                     
                     , 
                     
                       
                         
                           m 
                           1 
                           ′ 
                         
                         ⁡ 
                         
                           [ 
                           1 
                           ] 
                         
                       
                       * 
                       
                         g 
                         
                           
                             2 
                             2 
                           
                           ⁢ 
                           r 
                         
                       
                     
                   
                   ) 
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 where 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   
                     m 
                     1 
                     ′ 
                   
                   ⁡ 
                   
                     [ 
                     1 
                     ] 
                   
                 
               
               = 
               
                 
                   
                     
                       A 
                       
                         n 
                         + 
                         1 
                       
                     
                     ⁢ 
                     
                         
                     
                     ( 
                     
                       
                         
                           S 
                           1 
                         
                         ⁡ 
                         
                           [ 
                           1 
                           ] 
                         
                       
                       ⁢ 
                       
                           
                       
                       , 
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         
                           S 
                           1 
                         
                         ⁡ 
                         
                           [ 
                           n 
                           ] 
                         
                       
                     
                     ) 
                   
                   + 
                   
                     
                       
                         B 
                         
                           n 
                           + 
                           1 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             
                               S 
                               1 
                             
                             ⁡ 
                             
                               [ 
                               1 
                               ] 
                             
                           
                           ⁢ 
                           
                               
                           
                           , 
                           … 
                           ⁢ 
                           
                               
                           
                           , 
                           
                             
                               S 
                               1 
                             
                             ⁡ 
                             
                               [ 
                               n 
                               ] 
                             
                           
                         
                         ) 
                       
                     
                     * 
                     
                       constant 
                       1 
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     … 
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                       
                         O 
                         1 
                       
                       ⁡ 
                       
                         [ 
                         p 
                         ] 
                       
                     
                   
                 
                 = 
                 
                   
                     
                       ( 
                       
                         
                           g 
                           
                             
                               2 
                               2 
                             
                             ⁢ 
                             r 
                           
                         
                         , 
                         
                             
                         
                         ⁢ 
                         
                           
                             
                               m 
                               1 
                               ′ 
                             
                             ⁡ 
                             
                               [ 
                               p 
                               ] 
                             
                           
                           * 
                           
                             g 
                             
                               
                                 2 
                                 2 
                               
                               ⁢ 
                               r 
                             
                           
                         
                       
                       ) 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     where 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         m 
                         1 
                         ′ 
                       
                       ⁡ 
                       
                         [ 
                         p 
                         ] 
                       
                     
                   
                   = 
                   
                     
                       
                         A 
                         
                           n 
                           + 
                           p 
                         
                       
                       ⁢ 
                       
                           
                       
                       ( 
                       
                         
                           
                             S 
                             1 
                           
                           ⁡ 
                           
                             [ 
                             1 
                             ] 
                           
                         
                         ⁢ 
                         
                             
                         
                         , 
                         … 
                         ⁢ 
                         
                             
                         
                         , 
                         
                           
                             S 
                             1 
                           
                           ⁡ 
                           
                             [ 
                             n 
                             ] 
                           
                         
                       
                       ) 
                     
                     + 
                     
                       
                         
                           B 
                           
                             n 
                             + 
                             p 
                           
                         
                         ⁡ 
                         
                           ( 
                           
                             
                               
                                 S 
                                 1 
                               
                               ⁡ 
                               
                                 [ 
                                 1 
                                 ] 
                               
                             
                             ⁢ 
                             
                                 
                             
                             , 
                             … 
                             ⁢ 
                             
                                 
                             
                             , 
                             
                               
                                 S 
                                 1 
                               
                               ⁡ 
                               
                                 [ 
                                 n 
                                 ] 
                               
                             
                           
                           ) 
                         
                       
                       * 
                       
                         constant 
                         1 
                       
                     
                   
                 
               
             
           
         
       
     
     For Case 2, For an update i, output values are as follows: 
                 O   i     ⁡     [   1   ]       =         (       g       2     i   +   1       ⁢   r       ,         m   i   ′     ⁡     [   1   ]       *     g       2     i   +   1       ⁢   r           )     ⁢           ⁢   where   ⁢           ⁢       m   i   ′     ⁡     [   1   ]         =           A     n   +   1       ⁢           (         S   i     ⁡     [   1   ]       ⁢           ,   …   ⁢           ,       S   i     ⁡     [   n   ]         )     +         B     n   +   1       ⁡     (         S   i     ⁡     [   1   ]       ⁢           ,   …   ⁢           ,       S   i     ⁡     [   n   ]         )       *     constant   i     ⁢     
     ⁢           ⁢   …   ⁢     
     ⁢       O   i     ⁡     [   p   ]           =         (       g       2     i   +   1       ⁢   r       ,           ⁢         m   1   ′     ⁡     [   p   ]       *     g       2     i   +   1       ⁢   r           )     ⁢           ⁢   where   ⁢           ⁢       m   1   ′     ⁡     [   p   ]         =         A     n   +   p       ⁢           (         S   i     ⁡     [   1   ]       ⁢           ,   …   ⁢           ,       S   i     ⁡     [   n   ]         )     +         B     n   +   p       ⁡     (         S   i     ⁡     [   1   ]       ⁢           ,   …   ⁢           ,       S   i     ⁡     [   n   ]         )       *     constant   i                     
where, the values constant i  are related to the constants C 1 , . . . , C n    801  are received by the cryptography device  103  from the server, transmission  803  ( FIG. 8 ). In a preferred embodiment, the multiplication with the constant values C 1 , . . . , C 2    801  is performed using an obfuscated function.
 
     The above operations are on ElGamal ciphertexts. Therefore, the sequential operations track the value of the random value r used in ElGamal encryption. If we denote R as being the value of the random value r for the resulting ciphertext, the relationship between R and r is as follows:
         If the homomorphic operation is multiplication:
 
( g   r   ,m   1   *h   r )*( g   r   ,m   2   *h   r )=( g   2r   ,m   1   m   2   *h   2r )
   Therefore, R=2r   If the homomorphic operation is addition:
 
( g   r   ,m   1   *h   r )*( g   r   ,m   2   *h   r )=( g   r   ,m   1   m   2   *h   r )
   Therefore, R=r       

     Output Generation Function, Step Two  735 : Decryption of the Output 
     The output of Step One  733  is computed using ElGamal encrypted values as its inputs. Therefore, the outputs O i , which may be considered intermediate output values, from Step One  733  are also ElGamal ciphertexts. These outputs are optionally or partially decrypted or subjected to other processing in Step Two  735 . 
     There are three different alternative approaches, which may be selected depending on the requirements of a particular intended use of the output: 
     1. The output values are decrypted within the Random Sequence Generator  703  using a Fully Homomorphic Encryption Scheme or a Somewhat Homomorphic Encryption Scheme. Of course, the decryption must match the encryption scheme used for the inputs to Step One  733 . 
     2. The output values O i  from Step One  733  are re-encrypted using a trapdoor re-encryption mechanism. Re-encryption is described herein above in conjunction with  FIG. 6  in which a ciphertext encrypted using fully homomorphic encryption n is re-encrypted for a new key. Such mechanisms are described in [BBS] Blaze, M., Bleumer, G., Strauss, M.: Divertible protocols and atomic proxy cryptography. EUROCRYPT 1998 (incorporated herein by reference). 
     3. The value is partially decrypted using a distributed decryption mechanism. 
     Consider these in turn. 
     Case 1: Local Decryption 
     One possibility is to use F(S)HE (Fully (Somewhat Fully) Homomorphic Encryption) to perform the decryption step. The data does not need to be expressed in a bitwise manner since only multiplication, and addition/subtraction are needed. Then, better performances than in the general case can be achieved. 
     In that case, the final step is the decryption of the F(S)HE scheme which means that the decryption key has to be embedded and obfuscated in the code. A “tracer” can be used to avoid unexpected decryption (as described herein above). 
     Case II: Re-encryption with Alternate Key 
     In this embodiment, the getRandom( ) function  703  has a trapdoor key. However, the getRandom( ) function  703  does not have the key for decryption. In one embodiment, the technique of Blazer, Bleumer, and Strauss (BBS) ([Blaze] Matt Blaze, G. Bleumer, and M. Strauss. Divertible protocols and atomic proxy cryptography. In Proceedings of Eurocrypt &#39;98, volume 1403, pages 127-144, 1998 (incorporated herein by reference)) is used to re-encrypt the output series O from one secret key to another without manipulation of the series O in plaintext. 
     BBS is based on the ElGamal cryptosystem and includes the notion of a “re-encryption key” RK A→B . Using RK A→B , the getRandom( ) function  703  can re-encrypt from one secret key to another without ever learning the plaintext. 
     G is an algebraic ring of prime order q and having a generator g. 
     SK A =aϵZ q *randomly selected. 
     PK A =g a    
     SK B =bϵZ q *randomly selected. 
     PK B =g b    
     RK A→B =b/a=b*a −1  mod q 
     Encryption of mϵG with random rϵZ q *:c A =(g ar , m*g r ) 
     Re-encryption using c and RK A→B : 
     
       
         
           
             
               C 
               B 
             
             = 
             
               
                 ( 
                 
                   
                     
                       ( 
                       
                         g 
                         ar 
                       
                       ) 
                     
                     
                       RK 
                       
                         A 
                         → 
                         B 
                       
                     
                   
                   , 
                   
                     m 
                     * 
                     
                       g 
                       r 
                     
                   
                 
                 ) 
               
               = 
               
                 
                   ( 
                   
                     
                       
                         ( 
                         
                           g 
                           ar 
                         
                         ) 
                       
                       
                         b 
                         a 
                       
                     
                     , 
                     
                       m 
                       * 
                       
                         g 
                         r 
                       
                     
                   
                   ) 
                 
                 = 
                 
                   ( 
                   
                     
                       g 
                       br 
                     
                     , 
                     
                       m 
                       * 
                       
                         g 
                         r 
                       
                     
                   
                   ) 
                 
               
             
           
         
       
     
     where m is one of the output messages O i [j]. 
     Thus, the intermediate output values O i  [j] is a ciphertext in the modified version of ElGamal wherein the seed values have been encrypted as:
 
 SDM   i =( h   r   ,m   i   *g   r )
 
     Consider, the SDM i , values to have been encrypted with the secret key SK A , then:
 
 O   i [ j ]=( g   ar   ,m   i [ j ]* g   r )
 
     In an alternative embodiment, the re-encryption scheme uses the mechanism described by [AFGH] Ateniese, Fu, Green &amp; Hohenberger,  Improved Proxy Re - Encryption Schemes with Applications to Secure Distributed Storage , ACM Transactions on Information and System Security (TISSEC), Volume 9 Issue 1, February 2006, Pages 1-30 (incorporated herein by reference). The [AFGH] scheme is based on bilinear maps. One main advantage of the [AFGH] scheme is that the trapdoor is unidirectional whereas the trapdoor of [BB S] is bidirectional. Another advantage of the [AFGH] scheme is that it is collusion-resistant. 
     Case III: Distributed Decryption 
     There are mechanisms for distributing a decryption key x over d parties such that decryption requires the cooperation of all (or a subset) of the parties. In one example of this distributed decryption technique, to decrypt the outputs O i  from Step One  733  relies on the following:
 
 x=x   1   +x   2   + . . . +x   d  
 
 h=h   1   *h   2   * . . . *h   d   =g   x   =g   x     1     *g   x     2     * . . . *g   x     d    
 
 c =( g   r   ,m*h   r )
 
where, c is one of the output values O i .
 
     The secret key x is defined as x=x 1 +x 2 + . . . x d  and the corresponding public key h is defined as h==g x ×g x1 ·g x2  . . . g xd =h 1 *h 2 * . . . *h d    
     If c=(c 1 ,c 2 )=(g R , h R *m), one device (for example the first one) in the distributed decryption computes a partial decrypted ciphertext: c′=(c 1 , c 2 /(g R ) x1 )=(c 1 , c/(h 1   R )) and returns the partial result c′. 
     The output is c′ and the corresponding secret key for c′ is x′=x 2 + . . . x d . c″=(c′ 1 ,c′ 2 /(g R ) x2 ). The next decryption device computes its portion of the decryption: c″=(c′ 1 , c′ 2 /(g R ) x     2   ). 
     The final decryption result, after all the decryption devices have performed their partial decryptions is the plaintext m. 
     Thus, one party, e.g., the cryptographic device  903  may request several servers to perform the partial decryptions based on those servers&#39; respective portion of the key, respectively. After all the servers have been made to decrypt, the final result is obtained. 
     Case IV: Decryption with Key Switch. 
     In an alternative to Case I (wherein the output is decrypted within the boundary of the deterministic random number generator (in  FIG. 7 , the getRandom( ) function), the homomorphic encryption is replaced with a key switch option illustrated in  FIG. 9 . 
     The Provisioning phase ( FIG. 6 ) includes an additional step of generating, in the secure environment  701 , a set of candidate keys (CandidateKeys), step  901 , from which a subset is selected for computing updated output values, as described below. The set of candidate keys are defined as:
 
CandidateKeys={( h   y     1     ,g   y     1   ), . . . ,( h   y     l     ,g   y     l   )}
 
     The CandidateKeys set is provided to the cryptography device  103 , step  903 , and stored thereon,  905 . 
     During the Execution phase a subset, CandidateKeysSubset, is selected from the CandidateKeys set, step  907 . The subset contains at least two elements. The cryptographic device  103  also selects a coefficient set {a i }, one coefficient for each element in the CandidateKeysSubset. 
     From the CandidateKeysSubset two key switch factors, Δhy and Δgy are computed, step  909 , as follows: 
     
       
         
           
             
               Δ 
               ⁢ 
               
                   
               
               ⁢ 
               hy 
             
             = 
             
               
                 ∏ 
                 
                   
                     elements 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     yi 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     in 
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   CandidateKeysSubset 
                 
               
               ⁢ 
               
                 
                   ( 
                   
                     h 
                     yi 
                   
                   ) 
                 
                 
                   a 
                   i 
                 
               
             
           
         
       
       
         
           
             
               Δ 
               ⁢ 
               
                   
               
               ⁢ 
               gy 
             
             = 
             
               
                 ∏ 
                 
                   
                     elements 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     yi 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     in 
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   CandidateKeysSubset 
                 
               
               ⁢ 
               
                 
                   ( 
                   
                     g 
                     yi 
                   
                   ) 
                 
                 
                   a 
                   i 
                 
               
             
           
         
       
     
     The output values O i [j]  911  are obtained in the same manner as illustrated in and discussed herein above in conjunction with  FIG. 7 , step  733  or  FIG. 8 , step  733 ′ and steps that precede  733 / 733 ′. Note, the general case for O i [j] is
 
 O   i [ p ]= g   2     i+1     r   ,m′   i [ p ]* h   2     i+1     r )
 
     An updated output value O′ i [j] is computed, step  913 :
 
 O   i [ p ]= g   2     i+1     r   *Δgy,m′   i [ p ]* h   2     i+1     r   *Δhy )
 
     The corresponding secret key is:
 
key= x+Σa   i   y   i  
 
     The updated O′ i [j] values are decrypted using the secret key, key, step  915 , to produce the final output V i . 
     From the foregoing, the improvement of the security of a cryptography device operating in a white box environment and storing secret material, specifically, the seed for a deterministic random number generator, is apparent. This improvement to cryptography devices is provided by enabling the cryptography devices to use homomorphic encryption to perform cryptographic operations requiring random number sequences in a manner that does not use the seed to the random number generator in a plaintext format. 
     The method is described herein above as using ElGamal encryption. However, in an alternative embodiment another homomorphic encryption scheme, e.g., the  Fully Homomorphic Scheme  of Gentry, as described in greater detail in Craig Gentry,  Fully Homomorphic Encryption Using Ideal Lattices , in Proceedings of the forty-first annual ACM symposium on Theory of computing (STOC &#39;09), pp. 169-178. ACM, 2009. 
     Although specific embodiments of the invention have been described and illustrated, the invention is not to be limited to the specific forms or arrangements of parts so described and illustrated. The invention is limited only by the claims.