Succinct Randomized Encodings
The notion of a Randomized Encoding coined by members of the Computer Science Department at the Istrael Institute of Technology «Technion» Yuval Ishai and Eyal Kushilevitz [IK00]. Randomized Encoding allows to represent a “complex” function f(x) by a “simpler” randomized mapping f^(x) whose output distribution on an input x encodes the value of f^(x). Main question: how encode “complex” functions f(x) by “simple” functions f^(x)? Yuval Ishai and Eyal Kushilevitz consider three notions of efficiency for Randomized Encodings f^(x) of f(x) :
- Succinct Randomized Encodings.
- Compact Randomized Encodings.
- Sublinear Randomized Encodings.
In work with Succinct Randomized Encodings main task: the time required to compute f^(x). [BGL+15]
Succinct Randomized Encodings is work of next researches:
- Nir Bitansky (Massachusetts Institute of Technology);
- Sanjam Garg (University of California, Berkeley);
- Huijia Lin (University of California, Santa Barbara);
- Rafael Pass (Cornell University);
- Sidharth Telang (Cornell University).
Given the description:
- time T^ to compute the encoding f^(x) ;
- time T required to compute f(x) .
Given time T^ is significantly smaller than the time T . Decoding time, in contrast, would be as large as T . Encoding function f^(x) is represented by a succinct program such as П :
The time T^ only depends on its space complexity, as well as the size of its input, output, and description. The scheme guarantees computational privacy of П and is based on indistinguishability obfuscation (iO) for a relatively simple circuit class, for which there exist instantiations based on polynomial hardness assumptions on multi-linear maps. [BV15a]
Then invoked Succinct Randomized Encodings to obtain several strong applications, including:
- Succinct indistinguishability obfuscation, where the obfuscated program iO(П) computes the same function as П for inputs x of apriori-bounded size. Obfuscating П is roughly as fast as encoding the computation of П on any such input x . Here creators of encodings also require subexponentially-secure indistinguishability obfuscation for circuits.
- Succinct functional encryption, where a functional decryption key corresponding to П allows decrypting П(x) from encryptions of any plaintext x of apriori-bounded size. Key derivation is as fast as encoding the corresponding computation.
- Succinct reusable garbling, a stronger form of randomized encodings where any number of inputs x can be encoded separately of П, independently of П's time and space complexity.
- Publicly-veriable 2-message delegation where verifying the result of a long computation given by П and input x is as fast as encoding the corresponding computation. Creators of encodings also show how to transform any 2-message delegation scheme to an essentially non-interactive system where the verier message is reusable.
At the heart of algorithm techniques is a generic method of compressing a piecemeal garbled computation, without revealing anything about the secret randomness utilized for garbling.
Succinctness features that differentiate Succinct Randomized Encodings from basic algorithm Randomized Encodings:
- Dependence on the output length. The size of basic Randomized Encodings grows with the output of the underlying computation. Such dependence can be easily shown to be inherent as long as we require simulation-based security (using a standard incompressibility argument). Nevertheless, this dependence can be removed if we settle for a weaker indistinguishability-based guarantee saying that Randomized Encodings of two computations leading to the same output are indistinguishable. This guarantee, in fact, suffices, and allows removing output-dependence, in all of the applications above, except for the multiparty application (which requires simulation on its own).
- Multiparty computation. Algorithm of Succinct Randomized Encodings reduce the communication overhead from depending on the circuit size required to compute a multiparty function to depending on the space required to compute , which can be much smaller. Succinct Randomized Encodings allow in addition to shift the work load to one party (the decoder) that obtains the output, without inducing extra rounds.
- Optimizing Decoding Time. Ideally the complexity of decoding should be as close as possible to that of the original computation. In Succinct Randomized Encodings show how to optimize Randomized Encodings to improve decoding time.
Cryptographic primitives and/or protocols
Security of the Succinct Scheme: an Overview:
- Generate mapping function. Name this step is Garb.
- Encode values on every steps. Name this step is Encode.
- Evaluation decryption time. Name this step is Eval.
Different models of computation:
- Classes of deterministic algorithms of fixed polynomial size. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently. Algorithms include:
- Classes of randomized algorithms. Formally, the algorithm's performance will be a random variable determined by the random bits; thus either the running time, or the output (or both) are random variables. Authors define analogously these classes for their corresponding randomized algorithms.
- Classes of (arbitrary) polynomial-sized algorithms. Authors define corresponding classes of arbitrary polynomial size.
- Classes of well-formed algorithms. In order to avoid repeating the definitions for different classes of machines, Succinct Randomized Encodings provides definitions for general classes of algorithms that can be instantiated with specific classes. In particular, Succinct Randomized Encodings will work with classes of algorithms that are well-formed.
Succinct Randomized Encodings may sometimes save in communication and computation altogether. One of the first demonstrated applications of Succinct Randomized Encodings was to achieve such savings in multi-party computation (MPC). MPC solutions explicitly utilize the same circuit representing a function f(x) and the overhead they incur, e.g. in communication, may depend on the circuit size. When the function f(x) is succinctly represented by a programП, it may have the parties compute first a Succinct Randomized Encodig f^(x), and only decode at the end, thereby making communication overhead proportional to the smaller circuit that computes f^(x).
Under commonly believed complexity-theoretic assumptions, perfectly-private randomized encodings for all of П are unlikely to be computable too fast, e.g. in fixed polynomial time. In contrast, restricting attention to privacy against computationally-bounded adversaries, no lower bounds or barriers are known. In fact, succinct indis-tinguishability obfuscation (iO) for any model of computation (e.g., iO for Turing machines) would directly imply corresponding succinct randomized encod-ings. Still, constructions of succinct iO, or direct constructions of succinct randomized encodings are based on considerably strong computational assumptions:
- Extractable witness encryption [GGSW13];
- Succinct non-interactive arguments [GW11]:
- Differing-inputs obfuscation [ABG+13].
In the language of these assumptions are not efficiently-falsifiable; furthermore, in some cases they have been shown implausible.
Demonstration the power of Succinct Randomized Encodings in several applications:
- Application 1: Succinct Indistinguishability Obfuscation. Succinct iO for bounded-space computations. In-distinguishability here means that the (succinct) obfuscations of two programs that have the same output and running time on all inputs x of some apriori-bounded length n are computationally indistinguishable. The construction is based on subexponential iO, whereas any form of succinct iO realized so far [ABG+13] relies on differing-inputs obfuscation in conjunction with succinct non-interactive arguments (which already entail strong succinctness properties); as mentioned before, these are considered very strong up to implausible in certain settings.
- Application 2: Succinct Functional Encryption and Reusable Garbling. The recent leap in the study of obfuscation has brought with it a corresponding leap in functional encryption (FE). Today, (indistinguishability-based) functional encryption for all circuits can be constructed from iO, or even from concrete (and efficiently falsifiable) assumptions on composite order multilinear graded-encodings. For models of computation with succinct representa-tions, we may hope to have Succinct Randomized Encodings, where a secret key skП , allowing to decryption П(х) from an encryption of х , can be computed faster than the running time of П. However, here the state-of-art was similar to succinct randomized encodings, or succinct iO , requiring essentially the same strong (non-falsifiable) assumptions. Based on existing non-succinct functional encryption schemes, show that Succinct Randomized Encodings can be constructed without relying on sub-exponentially hard primitives.
- Application 3: Publicly Verifiable Delegation and succinct NIZKs. Succinct randomized encodings directly imply a one-round delegation scheme for polynomial-time computations with bounded space complexity. A main feature of the scheme is public-verifiability, meaning that given the verifier’s message anyone can verify the proof from the prover, without requiring any secret verification state. Previous publicly-verifiable schemes relied on strong knowledge assumptions or proven secure only in the random oracle model. Another prominent feature of the scheme is that it guarantees in-put privacy for the verifier. The delegation scheme is based only on randomized encodings (and one-way functions), and thus as explained above, can be based only on polynomial assumptions.
- Other Applications. Authors of Succinct Randomized Encodings reinspect additional previous applications of (non-succinct) randomized encodings and note the resulting succinctness features.
- Deterministic algorithm
- Indistinguishability obfuscation (iO)
- Multi-party computation (MPC)
- NC class
- Polynomial time
- Random-access machine (RAM)
- Randomized algorithm
- Exponential time
- Turing machine (TM)
Go to Bibliography
Maltseva N. A.