1,720,978 research outputs found
On the Existence of Extractable One-Way Functions
Full text linkA function f is extractable if it is possible to algorithmically “extract,” from any adversarial program
that outputs a value y in the image of f, a preimage of y. When combined with hardness properties
such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard knowledge assumption on certain functions.
We make two headways in the study of the existence of extractable one-way functions (EOWFs). On
the negative side, we show that if there exist indistinguishability obfuscators for a certain class of circuits then there do not exist EOWFs where extraction works for any adversarial program with auxiliary-input of unbounded polynomial length.
On the positive side, for adversarial programs with bounded auxiliary-input (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (e.g., sub-exponential hardness of Learning with Errors). We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zeroknowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially the same assumptions
On Non-Black-Box Simulation and the Impossibility of Approximate Obfuscation
Full text linkThe introduction of a non-black-box simulation technique by Barak (FOCS 2001) has been a major landmark in cryptography, breaking the previous barriers of black-box impossibility. Barak's technique has given rise to various powerful applications and is a key component in all known protocols with non-black-box simulation. We present the first non-black-box simulation technique that does not rely on Barak's technique (or on nonstandard assumptions). Invoking this technique, we obtain new and improved protocols resilient to various resetting attacks. These improvements include weaker computational assumptions and better round complexity. A prominent feature of our technique is its compatibility with rewinding techniques from classic black-box zero-knowledge protocols. The combination of rewinding with non-black-box simulation has proven instrumental in coping with challenging goals such as simultaneously resettable zero-knowledge, proofs of knowledge, and resettable security from one-way functions. While previous works required tailored modifications to Barak's technique, we give a general recipe for combining our technique with rewinding. This yields simplified resettable protocols in the above settings, as well as improvements in round complexity and required computational assumptions. The main ingredient in our technique is a new impossibility result for general program obfuscation. The results extend the impossibility result of Barak et al. (CRYPTO 2001) to the case of obfuscation with approximate functionality, thus settling a question left open by Barak et al. In the converse direction, we show a generic transformation from any resettably sound zero-knowledge protocol to a family of functions that cannot be obfuscated.Check Point Institute for Information SecurityIsrael Science Foundation (Grant 20006317)Fulbright ProgramIBM Research (Ph.D. Fellowship
Indistinguishability Obfuscation from Functional Encryption
No full textIndistinguishability 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
On the Cryptographic Hardness of Finding a Nash Equilibrium
Full text linkWe prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguisha-bility obfuscation and injective one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which finding Nash equilibrium is known to be complete. Previous proposals for basing PPAD-hardness on program obfuscation considered a strong “virtual black-box ” notion that is subject to severe limitations and is unlikely to be realizable for the programs in question. In contrast, for indistinguishability obfuscation no such limitations are known, and recently, several candidate constructions of indistinguishability obfuscation were suggested based on different hardness assumptions on multilinear maps. Our result provides further evidence of the intractability of finding a Nash equilibrium, one that is extrinsic to the evidence presented so far.
Indistinguishability Obfuscation: From Approximate to Exact
Full text linkWe 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.National Science Foundation (U.S.) (Grant CNS-1350619)National Science Foundation (U.S.) (Grant CNS-1414119
On the existence of extractable one-way functions
Full text linkA function f is extractable if it is possible to algorithmically “extract,” from any adversarial program that outputs a value y in the image of f, a preimage of y. When combined with hardness properties such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard knowledge assumption on certain functions. We make two headways in the study of the existence of extractable one-way functions (EOWFs). On the negative side, we show that if there exist indistinguishability obfuscators for a certain class of circuits then there do not exist EOWFs where extraction works for any adversarial program with auxiliary-input of unbounded polynomial length. On the positive side, for adversarial programs with bounded auxiliary-input (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (e.g., sub-exponential hardness of Learning with Errors). We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zeroknowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially th
3-Message Zero Knowledge Against Human Ignorance
Full text linkThe notion of Zero Knowledge has driven the field of cryptography since its conception over thirty years ago. It is well established that two-message zero-knowledge protocols for NP do not exist, and that four-message zero-knowledge arguments exist under the minimal assumption of one-way functions. Resolving the precise round complexity of zero-knowledge has been an outstanding open problem for far too long.
In this work, we present a three-message zero-knowledge argument system with soundness against uniform polynomial-time cheating provers. The main component in our construction is the recent delegation protocol for RAM computations (Kalai and Paneth, TCC 2016B and Brakerski, Holmgren and Kalai, ePrint 2016). Concretely, we rely on a three-message variant of their protocol based on a key-less collision-resistant hash functions secure against uniform adversaries as well as other standard primitives.
More generally, beyond uniform provers, our protocol provides a natural and meaningful security guarantee against real-world adversaries, which we formalize following Rogaway’s “human-ignorance” approach (VIETCRYPT 2006): in a nutshell, we give an explicit uniform reduction from any adversary breaking the soundness of our protocol to finding collisions in the underlying hash function.National Science Foundation (U.S.) (Award CNS-1350619)National Science Foundation (U.S.) (Award CNS-1413964
Složitost Vyhledávacích Problémů s Jednoznačným Řešením
No full textMeggido and Papadimitriou [Theor. Comput. Sci., 1991] introduced the class TFNP of search problems for which a solution always exists and is polynomially verifiable. In this thesis, we study the possibility of reducing different problems into problems in TFNP. The property which is in common for problems, for which we study the reducibility to TFNP, is that all instances of these problems have a unique solution (if there is any solution present). In the first part of this thesis, we study a problem called ARRIVAL, which was intro- duced by Dohrau, Gärtner, Kohler, Matoušek and Welzl [A Journey Through Discrete Mathemathics: A Tribute to Jiří Matoušek, 2017]. ARRIVAL is the following decisional problem: Given a graph in which a train is moving according to prescribed rules does the train arrive to a given vertex? We first improve the result of Dohrau et al. who showed that the problem is in NP ∩ coNP. We show that there exists a unique certificate for being in the language and, thus, prove that it lies in UP ∩ coUP. We also study the search version of the ARRIVAL problem, which asks for the tran- script of number of traversals for each edge. It was known that the search version lies in PLS, which was proven by Karthik C. S. [Inf. Process. Lett., 2017]. We improve this result by showing a reduction from...Meggido a Papadimitriou [Theor. Comput. Sci., 1991] definovali třídu TFNP, která je tvořena vyhledávacími problémy, pro které řešení vždy existuje a lze je testovat v polynomiálním čase. V této práci studujeme, zdali lze různé problémy redukovat na problémy z TFNP. Problémy, jejichž redukovatelnost do TFNP studujeme, mají společnou vlastnost, že všechny jejich instance mají jednoznačné řešení (pokud nějaké řešení vůbec existuje). V první části této práce studujeme problém zvaný ARRIVAL, který se poprvé ob- jevil v článku Dohrau, Gärtner, Kohler, Matoušek a Welzl [A Journey Through Discrete Mathemathics: A tribute to Jiří Matoušek, 2017]. ARRIVAL je následující rozhodovací problém: Máme dán orientovaný graf, po kterém se pohybuje vláček podle předepsaných pravidel, a ptáme se, jestli vláček někdy dojede do předem určeného vrcholu. Prvně vylepšíme výsledek Dohrau a kol., kteří ukázali, že tento problém je v NP ∩ coNP. Ukážeme, že existuje jednoznačný certifikát pro náležení do jazyka a tedy dokážeme, že ARRIVAL je v UP ∩ coUP. Dále budeme studovat vyhledávací variantu problému ARRIVAL, při které máme určit kolikrát vláček projel po každé hraně grafu. Jak ukázal Karthik C. S. [Inf. Process. Lett., 2017], vyhledávací varianta ARRIVAL je ve třídě PLS. My tento výsledek vylepšíme a ukážeme redukci z problému...Computer Science Institute of Charles UniversityInformatický ústav Univerzity KarlovyMatematicko-fyzikální fakultaFaculty of Mathematics and Physic
The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator
Full text linkIn this paper we show that the existence of general indistinguishability obfuscators conjectured in a few recent works implies, somewhat counterintuitively, strong impossibility results for virtual black box obfuscation. In particular, we show that indistinguishability obfuscation for all circuits implies:
* The impossibility of average-case virtual black box obfuscation with auxiliary input for any circuit family with super-polynomial pseudo-entropy. Such circuit families include all pseudo-random function families, and all families of encryption algorithms and randomized digital signatures that generate their required coin flips pseudo-randomly. Impossibility holds even when the auxiliary input depends only on the public circuit family, and not the specific circuit in the family being obfuscated.
* The impossibility of average-case virtual black box obfuscation with a universal simulator (with or without any auxiliary input) for any circuit family with super-polynomial pseudo-entropy.
These bounds significantly strengthen the impossibility results of Goldwasser and Kalai (STOC 2005).Accepted manuscrip
On the Complexity of Search Problems with a Unique Solution
No full textMeggido and Papadimitriou [Theor. Comput. Sci., 1991] introduced the class TFNP of search problems for which a solution always exists and is polynomially verifiable. In this thesis, we study the possibility of reducing different problems into problems in TFNP. The property which is in common for problems, for which we study the reducibility to TFNP, is that all instances of these problems have a unique solution (if there is any solution present). In the first part of this thesis, we study a problem called ARRIVAL, which was intro- duced by Dohrau, Gärtner, Kohler, Matoušek and Welzl [A Journey Through Discrete Mathemathics: A Tribute to Jiří Matoušek, 2017]. ARRIVAL is the following decisional problem: Given a graph in which a train is moving according to prescribed rules does the train arrive to a given vertex? We first improve the result of Dohrau et al. who showed that the problem is in NP ∩ coNP. We show that there exists a unique certificate for being in the language and, thus, prove that it lies in UP ∩ coUP. We also study the search version of the ARRIVAL problem, which asks for the tran- script of number of traversals for each edge. It was known that the search version lies in PLS, which was proven by Karthik C. S. [Inf. Process. Lett., 2017]. We improve this result by showing a reduction from..
- …
