White-box implementations with garbled circuits

#Various exemplary embodiments disclosed herein relate generally to white-box implementations of cryptographic functions using garbled circuits.

#White-box cryptography is aimed at protecting secret keys from being disclosed in a software implementation of a cryptographic or secure function. In such a context, it is assumed that the attacker (usually a “legitimate” user or malicious software) may also control the execution environment of the software implementation. This is in contrast with the more traditional security model where the attacker is only given a black-box access (i.e., inputs/outputs) to the cryptographic function under consideration.

#The main idea of white-box implementations is to rewrite a key-instantiated version so that all information related to the key is hidden in the software implementation of the cryptographic or secure function. In other words, for each secret key, a key-customized software is implemented so that the key input is unnecessary. In other embodiments, the secret key may be an input to the white-box implementation. In such a case the key may be encoded.

#In order to better understand various exemplary embodiments, reference is made to the accompanying drawings, wherein:

#FIG. 1 illustrates a garbled OR gate; and

#FIG. 2 illustrates a gate that has m input bits and n output bits.

#To facilitate understanding, identical reference numerals have been used to designate elements having substantially the same or similar structure and/or substantially the same or similar function.

#The description and drawings illustrate the principles of the invention. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the principles of the invention and are included within its scope. Furthermore, all examples recited herein are principally intended expressly to be for pedagogical purposes to aid the reader in understanding the principles of the invention and the concepts contributed by the inventor(s) to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions. Additionally, the term, “or,” as used herein, refers to a non-exclusive or (i.e., and/or), unless otherwise indicated (e.g., “or else” or “or in the alternative”). Also, the various embodiments described herein are not necessarily mutually exclusive, as some embodiments can be combined with one or more other embodiments to form new embodiments.

#In its basic version, Yao's protocol (a.k.a. garbled circuits) allows for the two-party evaluation of a function ƒ(x1,x2) in the presence of semi-honest adversaries. The protocol is run between the input owners (ai denotes the private input of user i). At the end of the protocol, the value of ƒ(a1,a2) is obtained, but no party learns more than what is revealed from this output value.