In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, black-box obfuscation was a proposed
cryptographic primitive which would allow a
computer program
A computer program is a sequence or set of instructions in a programming language for a computer to execute. Computer programs are one component of software, which also includes documentation and other intangible components.
A computer program ...
to be
obfuscated
Obfuscation is the obscuring of the intended meaning of communication by making the message difficult to understand, usually with confusing and ambiguous language. The obfuscation might be either unintentional or intentional (although intent u ...
in a way such that it was impossible to determine anything about it except its input and output behavior. Black-box obfuscation has been proven to be impossible, even in principle.
Impossibility
The unobfuscatable programs
Barak et al. constructed a family of unobfuscatable programs, for which an efficient attacker can always learn more from ''any'' obfuscated code than from black-box access.
Broadly, they start by engineering a special pair of programs that cannot be obfuscated together. For some randomly selected strings
of a fixed, pre-determined length
, define one program to be one that computes
and the other program to one that computes
(Here,
interprets its input as the code for a
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
. The second condition in the definition of
is to prevent the function from being
uncomputable.)
If an efficient attacker only has black-box access, Barak et al. argued, then the attacker only has an exponentially small chance of guessing the password
, and so cannot distinguish the pair of programs from a pair where
is replaced by some program
that always outputs "0". However, if the attacker has access to any obfuscated implementations
of
, then the attacker will find
with probability 1, whereas the attacker will always find
unless
(which should happen with negligible probability). This means that the attacker can always distinguish the pair
from the pair
with obfuscated code access, but not black-box access. Since ''no'' obfuscator can prevent this attack, Barak et al. conclude that no black-box obfuscator for pairs of programs exists.
To conclude the argument, Barak et al. define a third program to implement the functionality of the two previous:
Since equivalently efficient implementations of
can be recovered from one of
by hardwiring the value of
, Barak et al. conclude that
cannot be obfuscated either, which concludes their argument.
Impossible variants of black-box obfuscation and other types of unobfuscable programs
In their paper, Barak et al. also prove the following (conditional to appropriate
cryptographic assumptions):
* There are unobfuscatable
circuits.
* There is no black-box ''approximate'' obfuscator.
* There are unobfuscatable, secure, probabilistic
private-key cryptosystems.
* There are unobfuscatable, secure, deterministic
digital signature
A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature, where the prerequisites are satisfied, gives a recipient very high confidence that the message was created b ...
schemes.
* There are unobfuscatable, secure, deterministic
message authentication
In information security, message authentication or data origin authentication is a property that a message has not been modified while in transit (data integrity) and that the receiving party can verify the source of the message. Message authentica ...
schemes.
* There are unobfuscatable, secure
pseudorandom functions.
* For many protocols that are secure in the
random oracle model
In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time t ...
, the protocol becomes insecure if the random oracle is replaced with an artificial
cryptographic hash function
A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography:
* the probability of a particular n-bit output re ...
; in particular,
Fiat-Shamir schemes can be attacked.
* There are unobfuscatable circuits in
TC0
TC0 is a complexity class used in circuit complexity. It is the first class in the hierarchy of TC classes.
TC0 contains all languages which are decided by Boolean circuits with constant depth and polynomial size, containing only unbounded fan- ...
(that is, constant-depth threshold circuits).
* There are unobfuscatable sampling
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s (in fact, these cannot be obfuscated approximately).
* There is no secure software
watermarking
A watermark is a recognizable image or pattern in paper used to determine authenticity.
Watermark or watermarking may also refer to:
Technology
* Digital watermarking, a technique to embed data in digital audio, images or video
** Audio water ...
scheme.
Weaker variants
In their original paper exploring black-box obfuscation, Barak et al. defined two weaker notions of cryptographic obfuscation which they did not rule out:
indistinguishability obfuscation
In cryptography, indistinguishability obfuscation (abbreviated IO or iO) is a type of software obfuscation with the defining property that obfuscating any two programs that compute the same mathematical function results in programs that cannot b ...
and extractability obfuscation (which they called "differing-inputs obfuscation".) Informally, an indistinguishability obfuscator should convert input programs with the same functionality into output programs such that the outputs cannot be efficiently related to the inputs by a bounded attacker, and an extractability obfuscator should be an obfuscator such that if the efficient attacker ''could'' relate the outputs to the inputs for any two programs, then the attacker could also produce an input such that the two programs being obfuscated produce different outputs. (Note that an extractability obfuscator is necessarily an indistinguishability obfuscator.)
, a candidate implementation of
indistinguishability obfuscation
In cryptography, indistinguishability obfuscation (abbreviated IO or iO) is a type of software obfuscation with the defining property that obfuscating any two programs that compute the same mathematical function results in programs that cannot b ...
is under investigation.
In 2013, Boyle et al. explored several candidate implementations of extractability obfuscation.
References
{{reflist
Software obfuscation
Cryptographic primitives