The Experts below are selected from a list of 210852 Experts worldwide ranked by ideXlab platform
Nir Bitansky - One of the best experts on this subject based on the ideXlab platform.
-
Indistinguishability Obfuscation from Functional Encryption
Journal of the ACM, 2018Co-Authors: Nir Bitansky, Vinod VaikuntanathanAbstract:Indistinguishability obfuscation (IO) is a tremendous notion, powerful enough to give rise to almost any known cryptographic object. Prior candidate IO constructions were based on specific assumptions on algebraic objects called multi-linear graded encodings. We present a generic construction of Indistinguishability obfuscation from public-key functional encryption with succinct encryption circuits and subexponential security. This shows the equivalence of Indistinguishability obfuscation and public-key functional encryption, a primitive that has previously seemed to be much weaker, lacking the power and the staggering range of applications of Indistinguishability obfuscation. Our main construction can be based on functional encryption schemes that support a single functional key, and where the encryption circuit grows sub-linearly in the circuit-size of the function. We further show that sublinear succinctness in circuit-size for single-key schemes can be traded with sublinear succinctness in the number of keys (also known as the collusion-size) for multi-key schemes. We also show that, under the Learning with Errors assumption, our techniques imply that any Indistinguishability obfuscator can be converted into one where the size of obfuscated circuits is twice that of the original circuit plus an additive overhead that is polynomial in its depth, input length, and the security parameter.
-
perfect structure on the edge of chaos
Theory of Cryptography Conference, 2016Co-Authors: Nir Bitansky, Omer Paneth, Daniel WichsAbstract:We construct trapdoor permutations based on sub-exponential Indistinguishability obfuscation and one-way functions, thereby providing the first candidate that is not based on the hardness of factoring. Our construction shows that even highly structured primitives, such as trapdoor permutations, can be potentially based on hardness assumptions with noisy structures such as those used in candidate constructions of Indistinguishability obfuscation. It also suggest a possible way to construct trapdoor permutations that resist quantum attacks, and that their hardness may be based on problems outside the complexity class $$\text{ SZK } $$ i¾?-- indeed, while factoring-based candidates do not possess such security, future constructions of Indistinguishability obfuscation might. As a corollary, we eliminate the need to assume trapdoor permutations and injective one-way function in many recent constructions based on Indistinguishability obfuscation.
-
Indistinguishability obfuscation from approximate to exact
Theory of Cryptography Conference, 2016Co-Authors: Nir Bitansky, Vinod VaikuntanathanAbstract:We show general transformations from subexponentially-secure approximate Indistinguishability obfuscation IO where the obfuscated circuit agrees with the original circuit on a $$1/2+\epsilon $$ fraction of inputs on a certain samplable distribution, into exact Indistinguishability obfuscation where the obfuscated circuit and the original circuit agree on all inputs. As a step towards our results, which is of independent interest, we also obtain an approximate-to-exact transformation for functional encryption. At the core of our techniques is a method for "fooling" the obfuscator into giving us the correct answer, while preserving the Indistinguishability-based security. This is achieved based on various types of secure computation protocols that can be obtained from different standard assumptions. Put together with the recent results of Canetti, Kalai and Paneth TCC 2015, Pass and Shelat TCC 2016, and Mahmoody, Mohammed and Nemathaji TCC 2016, we show how to convert Indistinguishability obfuscation schemes in various ideal models into exact obfuscation schemes in the plain model.
-
TCC (A1) - Perfect Structure on the Edge of Chaos
Theory of Cryptography, 2015Co-Authors: Nir Bitansky, Omer Paneth, Daniel WichsAbstract:We construct trapdoor permutations based on sub-exponential Indistinguishability obfuscation and one-way functions, thereby providing the first candidate that is not based on the hardness of factoring. Our construction shows that even highly structured primitives, such as trapdoor permutations, can be potentially based on hardness assumptions with noisy structures such as those used in candidate constructions of Indistinguishability obfuscation. It also suggest a possible way to construct trapdoor permutations that resist quantum attacks, and that their hardness may be based on problems outside the complexity class $$\text{ SZK } $$ i¾?-- indeed, while factoring-based candidates do not possess such security, future constructions of Indistinguishability obfuscation might. As a corollary, we eliminate the need to assume trapdoor permutations and injective one-way function in many recent constructions based on Indistinguishability obfuscation.
-
Indistinguishability obfuscation from functional encryption
Foundations of Computer Science, 2015Co-Authors: Nir Bitansky, Vinod VaikuntanathanAbstract:Indistinguishability obfuscation (IO) is a tremendous notion, powerful enough to give rise to almost any known cryptographic object. So far, candidate IO constructions were based on specific assumptions on algebraic objects called multi-linear graded encodings. We present a generic construction of Indistinguishability obfuscation from public-key functional encryption with succinct cipher texts and sub-exponential security. This shows the equivalence of Indistinguishability obfuscation and public-key functional encryption, a primitive that has so far seemed to be much weaker, lacking the power and the staggering range of applications of Indistinguishability obfuscation. As an application, we obtain a new candidate IO construction based on the functional encryption scheme of Garg, Gentry, Halevi, and Zhan dry [Eprint 14] under their assumptions on multi-linear graded encodings. We also show that, under the Learning with Errors assumptions, our techniques imply that any Indistinguishability obfuscator can be converted to one where obfuscated circuits are of linear size in the size of the original circuit plus a polynomial overhead in its depth. Our reduction highlights the importance of cipher text succinctness in functional encryption schemes, which we hope will serve as a pathway to new IO constructions based on solid cryptographic foundations.
Vinod Vaikuntanathan - One of the best experts on this subject based on the ideXlab platform.
-
Indistinguishability Obfuscation from Functional Encryption
Journal of the ACM, 2018Co-Authors: Nir Bitansky, Vinod VaikuntanathanAbstract:Indistinguishability obfuscation (IO) is a tremendous notion, powerful enough to give rise to almost any known cryptographic object. Prior candidate IO constructions were based on specific assumptions on algebraic objects called multi-linear graded encodings. We present a generic construction of Indistinguishability obfuscation from public-key functional encryption with succinct encryption circuits and subexponential security. This shows the equivalence of Indistinguishability obfuscation and public-key functional encryption, a primitive that has previously seemed to be much weaker, lacking the power and the staggering range of applications of Indistinguishability obfuscation. Our main construction can be based on functional encryption schemes that support a single functional key, and where the encryption circuit grows sub-linearly in the circuit-size of the function. We further show that sublinear succinctness in circuit-size for single-key schemes can be traded with sublinear succinctness in the number of keys (also known as the collusion-size) for multi-key schemes. We also show that, under the Learning with Errors assumption, our techniques imply that any Indistinguishability obfuscator can be converted into one where the size of obfuscated circuits is twice that of the original circuit plus an additive overhead that is polynomial in its depth, input length, and the security parameter.
-
Indistinguishability obfuscation from approximate to exact
Theory of Cryptography Conference, 2016Co-Authors: Nir Bitansky, Vinod VaikuntanathanAbstract:We show general transformations from subexponentially-secure approximate Indistinguishability obfuscation IO where the obfuscated circuit agrees with the original circuit on a $$1/2+\epsilon $$ fraction of inputs on a certain samplable distribution, into exact Indistinguishability obfuscation where the obfuscated circuit and the original circuit agree on all inputs. As a step towards our results, which is of independent interest, we also obtain an approximate-to-exact transformation for functional encryption. At the core of our techniques is a method for "fooling" the obfuscator into giving us the correct answer, while preserving the Indistinguishability-based security. This is achieved based on various types of secure computation protocols that can be obtained from different standard assumptions. Put together with the recent results of Canetti, Kalai and Paneth TCC 2015, Pass and Shelat TCC 2016, and Mahmoody, Mohammed and Nemathaji TCC 2016, we show how to convert Indistinguishability obfuscation schemes in various ideal models into exact obfuscation schemes in the plain model.
-
Indistinguishability obfuscation from functional encryption
Foundations of Computer Science, 2015Co-Authors: Nir Bitansky, Vinod VaikuntanathanAbstract:Indistinguishability obfuscation (IO) is a tremendous notion, powerful enough to give rise to almost any known cryptographic object. So far, candidate IO constructions were based on specific assumptions on algebraic objects called multi-linear graded encodings. We present a generic construction of Indistinguishability obfuscation from public-key functional encryption with succinct cipher texts and sub-exponential security. This shows the equivalence of Indistinguishability obfuscation and public-key functional encryption, a primitive that has so far seemed to be much weaker, lacking the power and the staggering range of applications of Indistinguishability obfuscation. As an application, we obtain a new candidate IO construction based on the functional encryption scheme of Garg, Gentry, Halevi, and Zhan dry [Eprint 14] under their assumptions on multi-linear graded encodings. We also show that, under the Learning with Errors assumptions, our techniques imply that any Indistinguishability obfuscator can be converted to one where obfuscated circuits are of linear size in the size of the original circuit plus a polynomial overhead in its depth. Our reduction highlights the importance of cipher text succinctness in functional encryption schemes, which we hope will serve as a pathway to new IO constructions based on solid cryptographic foundations.
-
obfuscation of probabilistic circuits and applications
Theory of Cryptography Conference, 2015Co-Authors: Ran Canetti, Huijia Lin, Stefano Tessaro, Vinod VaikuntanathanAbstract:This paper studies the question of how to define, construct, and use obfuscators for probabilistic programs. Such obfuscators compile a possibly randomized program into a deterministic one, which achieves computationally indistinguishable behavior from the original program as long as it is run on each input at most once. For obfuscation, we propose a notion that extends Indistinguishability obfuscation to probabilistic circuits: It should be hard to distinguish between the obfuscations of any two circuits whose output distributions at each input are computationally indistinguishable, possibly in presence of some auxiliary input. We call the resulting notion probabilistic Indistinguishability obfuscation (pIO).
-
Indistinguishability Obfuscation: from Approximate to Exact.
IACR Cryptology ePrint Archive, 2015Co-Authors: Nir Bitansky, Vinod VaikuntanathanAbstract:We show general transformations from subexponentially-secure approximate Indistinguishability obfuscation (IO) where the obfuscated circuit agrees with the original circuit on a 1/2 + fraction of inputs on a certain samplable distribution, into exact Indistinguishability obfuscation where the obfuscated circuit and the original circuit agree on all inputs. As a step towards our results, which is of independent interest, we also obtain an approximate-to-exact transformation for functional encryption. At the core of our techniques is a method for “fooling” the obfuscator into giving us the correct answer, while preserving the Indistinguishability-based security. This is achieved based on various types of secure computation protocols that can be obtained from different standard assumptions. Put together with the recent results of Canetti, Kalai and Paneth (TCC 2015), Pass and Shelat (TCC 2016), and Mahmoody, Mohammed and Nemathaji (TCC 2016), we show how to convert Indistinguishability obfuscation schemes in various ideal models into exact obfuscation schemes in the plain model.
Jordi Recasens - One of the best experts on this subject based on the ideXlab platform.
-
On the representation of local Indistinguishability operators
Fuzzy Sets and Systems, 2020Co-Authors: Tomasa Calvo, Jordi RecasensAbstract:Abstract This paper studies local Indistinguishability operators, i.e., symmetric and transitive fuzzy relations that do not need to be reflexive. This is an important generalization of global Indistinguishability relations (fuzzy relations satisfying the reflexivity property in addition) because there are interesting families of fuzzy relations that are non-reflexive. One case are decomposable relations, that are generated by a fuzzy subset and contains the t-norms as an important subfamily. Also the relations associated naturally to fuzzy subgroups are local Indistinguishability operators. In this paper these relations will be studied stressing the way they can be generated. A representation theorem will be proved and related to the concepts of extensionality and of fuzzy rough set. Decomposable local Indistinguishability operators will also be studied and related with one-dimensional ones in the sense of the previous representation theorem. The presence of these relations in the study of fuzzy subgroups will also be analyzed.
-
Indistinguishability OPERATORS WITH RESPECT TO DIFFERENT t-NORMS
International Journal of Uncertainty Fuzziness and Knowledge-Based Systems, 2012Co-Authors: Dionís Boixader, Jordi RecasensAbstract:An isomorphism f between two continuous Archimedean t-norms T and T′ transforms a T-Indistinguishability operator E into a T′-Indistinguishability operator f ∘ E and many interesting properties of E are transfered to f ∘ E by f. This paper generalizes this result in order to relate Indistinguishability operators with respect to two non isomorphic continuous Archimedean t-norms. This will allow us to transfer definitions and properties from strict to non-strict Archimedean t-norms and vice versa.
-
T-Indistinguishability operators with respect to ordinal sums
2012 Annual Meeting of the North American Fuzzy Information Processing Society (NAFIPS), 2012Co-Authors: Dionís Boixader, Jordi RecasensAbstract:In this paper we study the class of T-Indistinguishability operators such that the involved t-norm T is an ordinal sum. We show that those T-Indistinguishability operators can be thought of as families of indistinguishabilities with respect to some Archimedean t-norms. An interpretation in terms of hierarchical clustering is provided.
-
Powers of Indistinguishability operators
2012 Annual Meeting of the North American Fuzzy Information Processing Society (NAFIPS), 2012Co-Authors: Gabriel Mattioli, Jordi RecasensAbstract:The application of a t-norm more than one time to the same object can be seen as the modelization of a semantic reinforcement of it. From a mathematical viewpoint, this operation can be seen as powers. Depending on the properties the t-norm fulfills several interesting properties emerge. This work will study what is the effect of the application of powers to Indistinguishability operators, sets of extensionals, upper and lower approximations. It will be proved that there is a tight relation between the powers of an Indistinguishability and their respective sets of extensionals, upper and lower approximations, and how this can be interpreted from a semantic point of view.
-
Finite-valued Indistinguishability operators
International Journal of Approximate Reasoning, 2011Co-Authors: Gaspar Mayor, Jordi RecasensAbstract:Fuzzy equality relations or Indistinguishability operators generalize the concepts of crisp equality and equivalence relations in fuzzy systems where inaccuracy and uncertainty is dealt with. They generate fuzzy granularity and are an essential tool in Computing with Words (CWW). Traditionally, the degree of similarity between two objects is a number between 0 and 1, but in many occasions this assignment cannot be done in such a precise way and the use of Indistinguishability operators valued on a finite set of linguistic labels such as small, very much, etc. would be advisable. Recent advances in the study of finite-valued t-norms allow us to combine this kind of linguistic labels and makes the development of a theory of finite-valued Indistinguishability operators and their application to real problems possible.
Omer Paneth - One of the best experts on this subject based on the ideXlab platform.
-
perfect structure on the edge of chaos
Theory of Cryptography Conference, 2016Co-Authors: Nir Bitansky, Omer Paneth, Daniel WichsAbstract:We construct trapdoor permutations based on sub-exponential Indistinguishability obfuscation and one-way functions, thereby providing the first candidate that is not based on the hardness of factoring. Our construction shows that even highly structured primitives, such as trapdoor permutations, can be potentially based on hardness assumptions with noisy structures such as those used in candidate constructions of Indistinguishability obfuscation. It also suggest a possible way to construct trapdoor permutations that resist quantum attacks, and that their hardness may be based on problems outside the complexity class $$\text{ SZK } $$ i¾?-- indeed, while factoring-based candidates do not possess such security, future constructions of Indistinguishability obfuscation might. As a corollary, we eliminate the need to assume trapdoor permutations and injective one-way function in many recent constructions based on Indistinguishability obfuscation.
-
TCC (A1) - Perfect Structure on the Edge of Chaos
Theory of Cryptography, 2015Co-Authors: Nir Bitansky, Omer Paneth, Daniel WichsAbstract:We construct trapdoor permutations based on sub-exponential Indistinguishability obfuscation and one-way functions, thereby providing the first candidate that is not based on the hardness of factoring. Our construction shows that even highly structured primitives, such as trapdoor permutations, can be potentially based on hardness assumptions with noisy structures such as those used in candidate constructions of Indistinguishability obfuscation. It also suggest a possible way to construct trapdoor permutations that resist quantum attacks, and that their hardness may be based on problems outside the complexity class $$\text{ SZK } $$ i¾?-- indeed, while factoring-based candidates do not possess such security, future constructions of Indistinguishability obfuscation might. As a corollary, we eliminate the need to assume trapdoor permutations and injective one-way function in many recent constructions based on Indistinguishability obfuscation.
-
zaps and non interactive witness Indistinguishability from Indistinguishability obfuscation
Theory of Cryptography Conference, 2015Co-Authors: Nir Bitansky, Omer PanethAbstract:We present new constructions of two-message and one-message witness-indistinguishable proofs (ZAPs and NIWIs). This includes:
-
TCC (2) - ZAPs and Non-Interactive Witness Indistinguishability from Indistinguishability Obfuscation
Theory of Cryptography, 2015Co-Authors: Nir Bitansky, Omer PanethAbstract:We present new constructions of two-message and one-message witness-indistinguishable proofs (ZAPs and NIWIs). This includes:
-
ZAPs and Non-Interactive Witness Indistinguishability from Indistinguishability Obfuscation.
IACR Cryptology ePrint Archive, 2014Co-Authors: Nir Bitansky, Omer PanethAbstract:We present new constructions of two-message and one-message witness-indistinguishable proofs (ZAPs and NIWIs). This includes: • ZAPs (or, equivalently, non-interactive zero-knowledge in the common random string model) from Indistinguishability obfuscation and one-way functions. • NIWIs from Indistinguishability obfuscation and one-way permutations. The previous construction of ZAPs [Dwork and Naor, FOCS 00] was based on trapdoor permutations. The two previous NIWI constructions were based either on ZAPs and a derandomization-type complexity assumption [Barak, Ong, and Vadhan CRYPTO 03], or on a specific number theoretic assumption in bilinear groups [Groth, Sahai, and Ostrovsky, CRYPTO 06]. ∗MIT. Email: nirbitan@csail.mit.edu. Part of this work was done while at Tel Aviv University. †Boston University. Email: omer@bu.edu. Supported by the Simons award for graduate students in theoretical computer science and an NSF Algorithmic foundations grant 1218461.
Ran Canetti - One of the best experts on this subject based on the ideXlab platform.
-
obfuscation of probabilistic circuits and applications
Theory of Cryptography Conference, 2015Co-Authors: Ran Canetti, Huijia Lin, Stefano Tessaro, Vinod VaikuntanathanAbstract:This paper studies the question of how to define, construct, and use obfuscators for probabilistic programs. Such obfuscators compile a possibly randomized program into a deterministic one, which achieves computationally indistinguishable behavior from the original program as long as it is run on each input at most once. For obfuscation, we propose a notion that extends Indistinguishability obfuscation to probabilistic circuits: It should be hard to distinguish between the obfuscations of any two circuits whose output distributions at each input are computationally indistinguishable, possibly in presence of some auxiliary input. We call the resulting notion probabilistic Indistinguishability obfuscation (pIO).
-
Obfuscation of Probabilistic Circuits and Applications.
IACR Cryptology ePrint Archive, 2014Co-Authors: Ran Canetti, Huijia Lin, Stefano Tessaro, Vinod VaikuntanathanAbstract:This paper studies the question of how to define, construct, and use obfuscators for probabilistic programs. Such obfuscators compile a possibly randomized program into a deterministic one, which achieves computationally indistinguishable behavior from the original program as long as it is run on each input at most once. For obfuscation, we propose a notion that extends Indistinguishability obfuscation to probabilistic circuits: It should be hard to distinguish between the obfuscations of any two circuits whose output distributions at each input are computationally indistinguishable, possibly in presence of some auxiliary input. We call the resulting notion probabilistic Indistinguishability obfuscation (pIO). We define several variants of pIO, using different approaches to formalizing the above security requirement, and study non-trivial relations among them. Moreover, we give a construction of one of our pIO variants from sub-exponentially hard Indistinguishability obfuscation (for deterministic circuits) and one-way functions, and conjecture this construction to be a good candidate for other pIO variants. We then move on to show a number of applications of pIO: • We give a general and natural methodology to achieve leveled homomorphic encryption (LHE) from variants of semantically secure encryption schemes and of pIO. In particular, we propose instantiations from lossy and re-randomizable encryption schemes, assuming the two weakest notions of pIO. • We enhance the above constructions to obtain a full-fledged (i.e., non-leveled) FHE scheme under the same (or slightly stronger) assumptions. In particular, this constitutes the first construction of full-fledged FHE that does not rely on encryption with circular security. • Finally, we show that assuming sub-exponentially secure puncturable PRFs computable in NC, sub-exponentially-secure Indistinguishability obfuscation for (deterministic) NC circuits can be bootstrapped to obtain Indistinguishability obfuscation for arbitrary (deterministic) poly-size circuits. ∗Boston University and Tel Aviv University, canetti@bu.edu †UC Santa Barbara, rachel.lin@cs.ucsb.edu ‡UC Santa Barbara, tessaro@cs.ucsb.edu §MIT CSAIL, vinodv@csail.mit.edu
