Server-assisted secure exponentiation

Abstract

In one embodiment, a method for secure computation, includes receiving in a server, over a communication channel from a device external to the server a request to perform a modular exponentiation operation in which an exponent of the operation comprises a secret value, wherein the secret value is not provided to the server, and at least two parameters that encode the secret value in accordance with a polynomial or matrix homomorphic encryption of the secret value computed by the device, and performing in the server, in response to the request, a homomorphic exponentiation using the at least two parameters received from the device without decrypting the secret value in the server, so as to generate an output that is indicative of a result of the modular exponentiation operation.

1 . A method for secure key exchange between first and second peer devices, the first and second peer devices respectively holding a first secret value a and a second secret value b, the method comprising:
 computing in the first peer device an encryption of the first secret value a so as to generate encryption parameters that encode the first secret value;   conveying the encryption parameters over a communication channel to a server which does not have access to either of the first and second secret values a and b;   computing and conveying to the second peer device a first base value g a  equal to a public value g raised to a first power equal to the first secret value a, such that the first base value is raised by the second peer device to a second power equal to the second secret value b in order to generate a session key g ab ;   receiving in the server a second base value g b  computed by the second peer device by raising the public value g to the second power;   computing a homomorphic exponentiation in the server using the encryption parameters and the second base value g b , so as to generate an output HE(g ab ) that is indicative of the session key;   conveying the output from the server to the first peer device over the communication channel;   applying in the first peer device a polynomial or matrix homomorphic decryption to the output conveyed by the server in order to recover the session key g ab ; and   encrypting and decrypting communications between the first and second peer devices using the session key.   
     
     
         2 . The method according to  claim 1 , wherein the server computes the homomorphic exponentiation without decrypting either of the first and second secret values. 
     
     
         3 . The method according to  claim 1 , and comprising:
 applying a polynomial or matrix homomorphic encryption in the first peer device to a third base value g v , which is equal to the public value g raised to a secret exponent v, thereby generating further parameters (R G ,U G ) that encode the third base value; and   conveying, from the first peer to the second peer, the further parameters (R G ,U G ), which are applied by the second peer device in calculating the homomorphic exponentiation HE(g bv ) of the third base value raised to the second power,   wherein computing the homomorphic exponentiation in the server comprises applying the homomorphic exponentiation of the third base value raised to the second power HE(g bv ) together with the encryption parameters and the second base value g b  in generating the output.   
     
     
         4 . The method according to  claim 1 , wherein computing the first base value g a  comprises computing the first base value in the server using the encryption parameters computed and conveyed by the first peer device. 
     
     
         5 . The method according to  claim 4 , wherein computing the encryption in the first peer device comprises generating the encryption parameters R′ a , U′ a  and g t  for use by the server in computing g a , such that U′ a =a−tR′ a . 
     
     
         6 . The method according to  claim 1 , wherein computing the encryption in the first peer device comprises computing a key pair (x, g x ), wherein x is a secret value, by storing a plurality of pairs of component values (X j , g X     j    mod N), selecting a subset of the pairs, and computing x as a sum of the values X j  over the subset, and g x  as a product of the values g X     j    mod N over the subset. 
     
     
         7 . An apparatus, comprising:
 a communication interface, which is configured to receive, over a communication channel from a device external to the apparatus:
 a request to perform a modular exponentiation operation in which an exponent of the operation comprises a secret value, wherein the secret value is not provided to the server; and 
 at least two parameters that encode the secret value in accordance with a polynomial or matrix homomorphic encryption of the secret value computed by the device; and 
   a processor, which is configured to perform, in response to the request, a homomorphic exponentiation using the at least parameters received from the device without decrypting the secret value in the apparatus, so as to generate an output that is indicative of a result of the modular exponentiation operation.   
     
     
         8 . The apparatus according to  claim 7 , wherein the output comprises the result of the modular exponentiation operation in plaintext. 
     
     
         9 . The apparatus according to  claim 7 , wherein the output comprises a pair of output values, the pair of output values being decrypted by the device using a polynomial or matrix homomorphic decryption to recover the result of the modular exponentiation operation. 
     
     
         10 . The apparatus according to  claim 9 , wherein the polynomial homomorphic encryption uses two secret random large numbers as polynomial roots in computing the at least two parameters, and wherein the communication interface further receives from the device a sum and a product of the roots, and wherein the processor is configured to apply the sum and the product in computing the modular homomorphic exponentiation. 
     
     
         11 . The apparatus according to  claim 9 , wherein the result of the modular exponentiation operation is a session key for use in encrypted communications between the device and a peer device, and wherein a base of the modular exponentiation operation requested by the device comprises a public value raised to a secret exponent held by the peer device. 
     
     
         12 . A system for secure key exchange, the system comprising:
 first and second peer devices, the first and second peer devices respectively holding a first secret value a and a second secret value b; and   a server which does not have access to either of the first and second secret values a and b,   wherein the first peer device is configured to compute an encryption of the first secret value a so as to generate encryption parameters that encode the first secret value and to convey the encryption parameters over a communication channel to a server, and   wherein the second peer device is configured to receive a first base value g a  equal to a public value g raised to a first power equal to the first secret value a, and   wherein the second peer device is configured to raise the first base value to a second power equal to the second secret value b in order to generate a session key g ab , and to compute a second base value g b  by raising the public value g to the second power and to provide the second base value to the server, and   wherein the server is configured to compute a homomorphic exponentiation using the encryption parameters and the second base value g b , so as to generate an output HE(g ab ) that is indicative of the session key and to convey the output to the first peer device over the communication channel, and   wherein the first peer device is configured to apply a polynomial or matrix homomorphic decryption to the output conveyed by the server in order to recover the session key g ab  and to encrypt and decrypt communications with the second peer device using the session key.   
     
     
         13 . The system according to  claim 12 , wherein the server is configured to compute the homomorphic exponentiation without decrypting either of the first and second secret values. 
     
     
         14 . The system according to  claim 12 , wherein the first peer device is configured to apply the polynomial or matrix homomorphic encryption to a third base value g v , which is equal to the public value g raised to a secret exponent v, thereby generating further parameters (R G ,U G ) that encode the third base value, and to convey the further parameters to the second peer, and
 wherein the second peer is configured to apply the further parameters (R G ,U G ) in calculating the homomorphic exponentiation HE(g bv ) of the third base value raised to the second power, and   wherein the server is configured to apply the homomorphic exponentiation of the third base value raised to the second power HE(g bv ) together with the encryption parameters and the second base value g b  in generating the output.   
     
     
         15 . The system according to  claim 12 , wherein the server is configured to compute the first base value using the encryption parameters computed and conveyed by the first peer device. 
     
     
         16 . The system according to  claim 15 , wherein the encryption parameters computed by the first peer device and conveyed to the server comprise R′ a , U′ a  and g t , such that U′ a =a−tR′ a . 
     
     
         17 . The system according to  claim 12 , wherein the first peer device is configured to compute a key pair (x, g x ), wherein x is a secret value, by storing a plurality of pairs of component values (X j , g X     j    mod N), selecting a subset of the pairs, and computing x as a sum of the values X j  over the subset, and g x  as a product of the values g X     j    mod N over the subset.