A SYSTEM AND METHODS FOR PROTECTING KEYS USING GARBLED CIRCUITS

Abstract

The subject matter discloses a computerized system, comprising a computerized device communicating with a third party server, that comprises a memory unit that stores a representation of a Boolean circuit and a processing unit for calculating a result of the Boolean circuit according to a string used as input for the Boolean circuit and calculating a first predefined function on the result of the Boolean circuit. The system also comprises a first auxiliary server communicating with the computerized device, the first auxiliary server comprises a processing unit for calculating a second predefined function on the result of the Boolean circuit received from the computerized device and a second auxiliary server communicating with the computerized device comprises a processing unit for comparing the result of the first predefined function and the result of the second predefined function.

Claims

1. A computerized system, comprising: a computerized device communicating with a third party server, the computerized device comprises: a memory unit that stores a representation of a Boolean circuit; a processing unit configured to calculate a result of the Boolean circuit according to a string used as an input for the Boolean circuit and to calculate a first predefined function on the result of the Boolean circuit; a first auxiliary server communicating with the computerized device, the first auxiliary server comprises a processing unit configured to calculate a second predefined function on the result of the Boolean circuit received from the computerized device; and a second auxiliary server communicating with the computerized device comprises a processing unit configured to compare the result of the first predefined function and the result of the second predefined function.

2. The system of claim 1, wherein the computerized device comprises a random string generator configured to generate a pseudo-random string used as the input to the Boolean circuit.

3. The system of claim 1, wherein the predefined function is a hash function.

4. The system of claim 1, wherein the computerized device comprises an encryption unit configured to encrypt the string using an encryption key and a communication interface for transmitting the encrypted string to the second auxiliary server.

5. The system of claim 4, wherein the computerized device comprises a multi-party computation module configured to split the encryption key such that a first share of the encryption key is stored at the computerized device and a second share of the encryption key is stored at the first auxiliary server.

6. The system of claim 5, wherein the second auxiliary server comprises a decryption unit configured to decrypt the encrypted string received from the computerized device using the first share of the encryption key received from the computerized device and the second share of the encryption key received from the first auxiliary server.

7. The system of claim 6, wherein the processing unit of the second auxiliary server is also configured to calculate the Boolean circuit using the decrypted string.

8. The system of claim 7, wherein the processing unit of the second auxiliary server is also configured to calculate a third predefined function on the result of the Boolean circuit calculated at the second auxiliary server.

9. The system of claim 8, wherein the processing unit of the second auxiliary server is also configured to compare the result of the third predefined function with the result of the first predefined function.

10-13. (canceled)

14. A method of computing a function, comprising: generating a random string used as a seed of a garbled circuit; transmitting two different byproducts of the garbled circuit from a computerized device to two a first auxiliary server and a second auxiliary server; performing a computation, by the first auxiliary server, using the byproduct received from the computerized device to provide a byproduct of the other auxiliary server and sends the output of the computation to the other auxiliary server; and comparing, by the second auxiliary server, the byproduct received from the computerized device and the byproduct received from the first auxiliary server.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0016] Some embodiments of the invention are herein described, by way of example only, with reference to the accompanying drawings. With specific reference now to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of embodiments of the invention. In this regard, the description taken with the drawings makes apparent to those skilled in the art how embodiments of the invention may be practiced.

[0017] In the drawings:

[0018] Referring to FIG. 1, is a functional diagram disclosing a system designed for a mobile device and a server to securely compute a function of their joint input, using the an auxiliary server to provide an actively secure computation.

[0019] Referring to FIG. 2, demonstrates a method for securely computing the result of a computation on two pieces of data, one held by the mobile device and one by a server. The method utilizes a second (auxiliary) server to compute the desired result, which is returned to the mobile device;

[0020] Referring to FIG. 3, is a functional diagram discloses a system designed to prove a computerized device identity to a third party server via an authentication process conducted by at least two auxiliary servers, according to exemplary embodiments of the present invention

[0021] Referring to FIG. 4, demonstrates a method of an authentication process between a computerized device and a third party server by utilizing two auxiliary servers to prove the computerized device's eligibility to connect, according to exemplary embodiments of the present invention;

[0022] Referring to FIG. 5, demonstrates a computerized device that communicates with a third party server, according to exemplary embodiments of the present invention;

[0023] Referring to FIG. 6, demonstrates a method of comparing a Boolean circuit calculation results, by a second auxiliary server, in order to prove the identity of a computerized device, according to exemplary embodiments of the present invention;

[0024] Referring to FIG. 7, demonstrates a method of exchanging a Boolean circuit calculation results, between a computerized device and two auxiliary servers, in order to prove the identity of the computerized device and the validity of its identification, according to exemplary embodiments of the present invention.

DESCRIPTION OF THE INVENTION

[0025] The subject matter discloses a computerized system and method for authenticating a computerized device communicating with a third party, such as an application server. The computerized system comprises at least two auxiliary servers communicating with the computerized device and components residing at the two auxiliary servers configured to perform the method described in details below. The method comprises a multi-party computation (MPC) performed between the computerized device and one of the auxiliary servers, using a random string to solve a Boolean circuit represented by a software model, sending information, sometimes encrypted, between the computerized device and the auxiliary servers, and verifying the authenticity of the computerized device by one of the auxiliary servers. Referring to FIG. 1, that discloses a system designed to enable a computerized mobile device and a server to securely compute an arbitrary function of their joint input, using an auxiliary second server to enable the computation to be performed in an actively secure manner, according to exemplary embodiments of the present invention. The system of the disclosed subject matter contains a computerized device 320, a server 510 and an auxiliary server 520. The computerized device 320 and the two servers 510, 520 calculate the output of a Boolean circuit. The Boolean circuit may be a set of interconnected Boolean circuits. The Boolean circuit may be implemented as Yao's garbled circuits or any other equivalent desired by a person skilled in the art.

[0026] In some exemplary cases, the server 510 comprises a communication interface 241, configured to manage and implement communication to and from the server 510. The communication interface 241 enables communication with the second auxiliary server 520 via communication process 95 and with the computerized device 320 via communication process 97. Similarly, the second auxiliary server 520 comprises communication interface 242 to perform communication functionalities similar to those of communication interface 241.

[0027] The server 510 may also comprise a circuit processing module 211 utilized to generate a garbled circuit representation for a given string, for example a random string received from the computerized device 320. The given string may be used as a seed to generate the Boolean circuit representation. In some other cases, the circuit processing module 211 may also be used to calculate a hash value of a secret received by one of the auxiliary servers 510, 520 of the system or by the computerized device 320. Similarly, the second auxiliary server 520 comprises a circuit processing module 212 to generate a Boolean circuits in a similar manner performed by the circuit processing module 211. The circuit processing module 211 also manages other calculation processes associated with the Boolean circuit such as calculation of the Boolean circuit result or hash the value of the Boolean circuit result. Other functions may be applied on the result of the Boolean circuit, for example reversible or irreversible functions, as long as the functions are predefined.

[0028] The server 510 also comprises a circuit module manager 221 to associate the Boolean circuit representation, or any other string, received at the server, with the computerized device that sent the string. For example, when a random string for generating the Boolean circuit representation is sent from the computerized device 320 to the server 510, the circuit module manager 221 identifies the string, associates the string with the computerized device that sent the string and stores it. Similarly, the second auxiliary server 520 comprises a circuit module manager 222 operating in a similar manner to the identification process and performs the same actions performed by the circuit module manager 221.

[0029] The server 510 also comprises a Communication Manager 231 to save and store addresses of the identified entities that communicate with the server 510 such as computerized devices or/and auxiliary servers, and to control the communications with them. For example, when a certain string or data needs to be transmitted to a specific server or to any computerized device, the Communication Manager 231 associates the data needed to be transmitted with the address of the target server or computerized device and transmits the string or data to the target via Communication Interface 210 that performs the transmissions. Similarly, the second auxiliary server 520 comprises a Communication Interface 232 performing communication management in a similar manner to those performed by the Communication Manager 231.

[0030] The server 510 also comprises a Secret Repository 241 configured to store secrets received by the server, for example in cases any calculation results are sent by the Computerized Device 320 as part of the computation process. The server 510 stores the received calculation result at the Secret Repository 241. Similarly, the second auxiliary server 520 comprises a Secret Repository 242 that saves secrete in a similar manner to the secret saving actions performed by the Communication Manager 241.

[0031] Referring to FIG. 2, demonstrates a method for securely computing an arbitrary function on data held by the computerized device and a server, according to exemplary embodiments of the present invention. For simplicity and clarity purposes the process described in FIG. 2 shall be referred hereafter to Main Protocol. The computerized device may be a mobile device assumed to be constrained in terms of its communication abilities and computation resources, such as bandwidth. The method securely computes a function F(x1,x2), where x1 is data held by the computerized device and x2 is data held by the server. The method requires very little communication costs from the point of view of the computerized device.

[0032] Step 301 discloses initiating the computation process of Computerized Device 430 by generating a random string at the Computerized Device 430. The random string is used as a seed to generate the garbled circuit, and hence will be a pre-defined length to avoid exhaustive search, for example 128 bits.

[0033] Step 302 discloses generating of the Boolean circuit representation, for example garbled circuits, utilizing the random string generated on step 301 as the seed.

[0034] Step 303 discloses calculating the hash value using the Garbled Boolean circuit generated on step 302. The hash value is denoted as h1 for simplicity and clarity of the disclosure. The hash function used by the computerized device may be the same hash function later performed by at least one of the two auxiliary servers. Examples of hash functions are SHA-1, SHA-2 and SHA-3.

[0035] Step 304 discloses transmitting the hash value of the Garbled Boolean circuit marked as h1, and the garbled labels corresponding to input data x1 to the auxiliary server 520.

[0036] Step 305 discloses transmitting the random string generated in step 301 from the computerized device 430 to the first server 510. Then, in step 307, the first server 510 uses the random string received from the computerized device 430 as a seed to generate a Garbled Boolean circuit. Then, in step 308 the first server 510 sends the Garbled Boolean circuit and the garbled label corresponding to x2 to the auxiliary server 520.

[0037] Step 308 discloses the second auxiliary server 540 calculating the hash value from the Garbled Boolean circuit received from the first auxiliary server 530. The hash value calculated by the second auxiliary server 540 is denoted as h2. Then, in step 309, the second auxiliary server 540 compares h1 received from computerized device 430 to h2 calculated at step 308 and if the strings are not equal, the process is aborted. If the strings are equal, the auxiliary server 520 evaluates the garbled circuit as shown in step 316 to obtain the result c. The value c is the result of computation of the garbled circuit performed by the auxiliary server 520. Then, in step 317, the computation result c is returned to the computing device 320.

Application of Main Protocol to Authentication Application

[0038] Referring to FIG. 3 that discloses a system designed to enable a computerized mobile device to prove its identity to a third party server via an authentication process conducted by at least two auxiliary servers communicating with the computerized device, according to exemplary embodiments of the present invention. The third party server is defined as a computerized module configured to provide information, service or specific results to one or more clients, users and subscribers. The system of the disclosed subject matter contains a computerized device 320 that communicates with the third party server 710, a first auxiliary server 510 and a second auxiliary server 520. The authentication process is assumed to be the application of a keyed Pseudo-Random Function (PRF) to a shared string. This is a common authentication mechanism. Two advantages arise from the use of the main protocol above to this situation: [0039] No alterations in terms of the operation of the third party server 710 are needed compared to existing embodiments. [0040] The secret key k is no longer needed to be held on the mobile device 320, since it is split between the mobile device 320 and the first auxiliary server S1 510.

[0041] In some exemplary cases, the first auxiliary server 510 comprises a communication interface 241, configured to manage and implement communication to and from the first auxiliary server 510. The communication interface 241 enables communication with the second auxiliary server 520 via communication process 95 and with the computerized device 320 via communication process 97. Similarly, the second auxiliary server 520 comprises communication interface 242 to perform communication functionalities similar to those of communication interface 241.

[0042] Referring to FIG. 4, demonstrates a method of an authentication process between a computerized device and a third party server by utilizing two auxiliary servers to prove the computerized device's eligibility to connect, according to exemplary embodiments of the present invention. In this process, the computerized device 320, the auxiliary server 510 and the third party server 710 share an encryption key in the following fashion: The computerized device 320, holds a first share of the cryptographic key, third party server 710 holds the whole encryption key and the auxiliary server 510 holds another share of the encryption key such that the key share held by the auxiliary server 510 and the key share held by the computerized device 320 can be used to execute a whole key similar to the key stored at the third party server 710. For the purposes of example we use k=k1 XOR k2 in what follows, but other splitting techniques are obvious to those skilled in the art.

[0043] The authentication method for the third party server comprises the following steps:

[0044] Step 240 discloses an initiation of the process by the computerized device 320 requesting the third party server 710 to start the authentication process. This is assumed to be a standard login request, or HTTP request, as specified in whatever legacy authentication service the present invention is to be layered on top of.

[0045] Then, in step 245 a process takes place between the computerized device 320 and the third party server 710 to agree on a shared message s. Agreement on the shared message s is assumed to be a standard process, as specified by whatever legacy authentication service the present invention is to be used with. The message s could contain random data produced by the mobile device, and/or random data produced by the third party server, and/or could involve a unique text, a timestamp, or any other information the two entities agree to utilize as a message.

[0046] Then in step 250 the computerized device 320 sends the shared message s that was agreed upon with third party server 710, to the auxiliary server 510.

[0047] In step 250 the mobile device 320, the first auxiliary server 51, and the second auxiliary server S2 engage in the Main Protocol described above to securely compute the output of the function

c=F_s (k1,k2)=PRF(k1 XOR k2, s).

[0048] As a result of this protocol the mobile device obtains the value c.

[0049] Then, in step 280, the computerized device 320 sends the value c obtained from executing the Main Protocol to the third party server 710.

[0050] Step 285 discloses a calculation process performed by third party server 710. Third party server calculates the c value with a pseudorandom function utilizing the key and the message agreed with from the computerized device 320 as disclosed in step 245.

c=PRF(k, s)

[0051] Then, in step 290, the third party server compares the c value of the pseudorandom function calculated in step 285 and the one received in step 280 from the computerized device 320 and if the results are equal authentication process has succeeded and the computerized device 320 is eligible to connect to the third party sever 710.

[0052] Referring to FIG. 5, demonstrates a computerized device that communicates with a third party server, according to exemplary embodiments of the present invention. The computerized device may communicate with the third party server for cases such as purchasing on the internet, approving transactions, signing on documents and the like. The Computerized Device 310 contains a circuit processing module 120 that calculates a result of Boolean circuits that may implement Yao's garbled circuits or any other equivalent method. The circuit processing module 120 calculates the Boolean circuit according to an input of a random string generated by the random string generator 140. For example, in case a result of a Boolean circuit needs to be calculated as a part of an authentication process controlled by this exemplary system, the circuit processing module 120 receives an input string, calculates the result and transmits it to the corresponded component in the authentication process disclosed above.

[0053] The Computerized Device 310 also contains a cryptographic computing module 130 utilized for multiple encryption operations the system may perform, for example calculating hash values or encrypting secrets. The Computerized Device 310 also contains a secret repository 110 to store the secrets or any data that is considered sensitive or confidential, for example an input key generated by the random string generator 140. The Computerized Device 310 also contains a server communication manager 150 that associates the data needed to be transmitted to the auxiliary servers or third party server 720, with the address of the target auxiliary servers or a third party server 720. Thus, in multiple cases when a certain data needs to be transmitted to a specific server, for example first auxiliary server, and a different data needs to be sent to second auxiliary server, the communication manager 150 sends the relevant data to the right server.

[0054] The Computerized Device 310 also contain device communication interface 160 that communicates with other components in the system, for example a third party server 720. The Computerized Device 310 also contains Random string generator 140 to produce a random string that can be used as the input for calculating a Boolean circuit result, for example, in a case a Boolean circuit needs to be calculated by the circuit processing device 120, the Random string generator 140 generates a string and transmits it to the circuit processing device 120 to be used as the input seed of this calculation.

[0055] Referring to FIG. 6, demonstrates a method of enabling a computerized device to prove its identity to a third party server, according to exemplary embodiments of the present invention. The method disclosed in FIG. 6 is performed by the auxiliary server. The method initiates in step 810, in which the auxiliary server receives a hashed value of a Garbled Boolean circuit calculation, performed by the computerized device. The computerized device calculates the Garbled Boolean circuit according to a random string generated at the computerized device. Then, in step 820, the auxiliary server receives a hash value from the First Server. The hash value is a result of a hash function applied on the calculation of a Boolean circuit calculated by the First Server. Then, in step 830, the Auxiliary server calculates a hash value from the result of the Garbled Boolean circuit calculation received from the First Server in step 820. Then, in step 840, the Second Auxiliary Server compares the hash value of the result of the Boolean circuit calculation received from First Auxiliary Server to the hashed result received from the computerized device. Then, in case the comparison in step 840 shows that the two hashed strings, the one received from the computerized device and the hash preformed on the Boolean circuited results received from First Auxiliary Server are identical, step 850 is performed, in which the Auxiliary Server receives garbled labels corresponding to key share from First Server. Then, in step 860, the Auxiliary Server receives a garbled labels corresponding to key share and an encrypted random string from the Computerized Device. Then, in step 870, the Second Auxiliary Server decrypts the encrypted random string received from the Computerized Device using the key shares received from the Computerized Device and from the First Auxiliary Server. Then, in step 880, the Second Auxiliary Server calculates the Boolean circuit using the decrypted random string that was decrypted in step 870. In step 890 the Second Auxiliary Server compares the hash calculation result, preformed in step 880, to the hash received from First Auxiliary Server and the hash received from the Computerized Device.

[0056] Referring to FIG. 7, which demonstrates a method of exchanging of a Garbled Boolean circuit, between a computerized device and two auxiliary servers, in order to prove the identity of the computerized device and the validity of its identification, according to exemplary embodiments of the present invention. The method disclosed in FIG. 7 is performed by the Computerized Device. The method comprises the following steps: In step 910, a Computerized Device generates a random string by a random string generator module controlled by or located at the Computerized Device. Step 920 discloses the Computerized Device generating a Garbled Boolean circuit by utilizing the random string generated in step 910 as a seed. Then, in step 930, the computerized device calculates a hash value of the garbled Boolean circuit using an input string. The garbled Boolean circuit is represented by software, hardware or firmware in the Computerized Device.

[0057] Step 940 discloses the Computerized Device sending the hashed result and the garbled labels corresponding to the key share to the auxiliary server. Then, in step 950, the Computerized Device sends the random string generated in step 910 to the first server. Step 960 discloses the Computerized Device receives the result of evaluation of the garbled circuit from the auxiliary server. Then, in step 970, the Computerized Device sends the result of the main protocol to the third party server.

[0058] While the disclosure has been described with reference to exemplary embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted for elements thereof without departing from the scope of the invention. In addition, many modifications may be made to adapt a particular situation or material to the teachings without departing from the essential scope thereof. Therefore, it is intended that the disclosed subject matter not be limited to the particular embodiment disclosed as the best mode contemplated for carrying out this invention, but only by the claims that follow.