Abstract. The 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 it 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 non-standard 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 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 function-ality; thus, settling a question left open by Barak et al.. In the converse direction, we show a generic transformation
Abstract. The 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 it 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 non-standard 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 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 function-ality; thus, settling a question left open by Barak et al.. In the converse direction, we show a generic transformation
The 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.
The 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 techniques were subsequently extended and have given rise to various powerful applications. We present the first non-black-box simulation technique that does not rely on Barak's technique (or on nonstandard assumptions). Our technique is based on essentially different tools: it does not invoke universal arguments, nor does it rely on collision-resistant hashing. Instead, the main ingredient we use is the impossibility of general program obfuscation (Barak et al., CRYPTO 2001). Using our technique, we construct a new resettably-sound zero-knowledge (rsZK) protocol. rsZK protocols remain sound even against cheating provers that can repeatedly reset the verifier to its initial state and random tape. Indeed, for such protocols black-box simulation is impossible. Our rsZK protocol is the first to be based solely on semi-honest oblivious transfer and does not rely on collision-resistant hashing; in addition, our protocol does not use PCP machinery. In the converse direction, we show a generic transformation from any rsZK protocol to a family of functions that cannot be obfuscated.
We present a new zero-knowledge argument protocol by relying on the non-black-box simulation technique of Barak (FOCS'01). Similar to the protocol of Barak, ours is public-coin, is based on the existence of collision-resistant hash functions, and, is not based on "rewinding techniques" but rather uses non-black-box simulation. However in contrast to the protocol of Barak, our protocol is secure even if there are any unbounded (polynomial) number of concurrent sessions. This gives us the first construction of public-coin concurrent zero-knowledge. Prior to our work, Pass, Tseng and Wikstrom (SIAM J. Comp. 2011) had shown that using black-box simulation, getting a construction for even public-coin parallel zero-knowledge is impossible.
Resettable-security, introduced by Canetti, Goldreich, Goldwasser and Micali (STOC'00), considers the security of cryptographic two-party protocols (in particular zero-knowledge arguments) in a setting where the attacker may “reset” or “rewind” one of the players. The strongest notion of resettable security, simultaneous resettability, introduced by Barak, Goldreich, Goldwasser and Lindell (FOCS'01), requires resettable security to hold for both parties: in the context of zero-knowledge, both the soundness and the zero-knowledge conditions remain robust to resetting attacks. To date, all known constructions of protocols satisfying simultaneous resettable security rely on the existence of ZAPs; constructions of ZAPs are only known based on the existence of trapdoor permutations or number-theoretic assumptions. In this paper, we provide a new method for constructing protocols satisfying simultaneous resettable security while relying only on the minimal assumption of one-way functions. Our key results establish, assuming only one-way functions: Every language in NP has an ω(1)-round simultaneously resettable witness indistinguishable argument system; Every language in NP has a (polynomial-round) simultaneously resettable zero-knowledge argument system. The key conceptual insight in our technique is relying on black-box impossibility results for concurrent zero-knowledge to achieve resettable-security.
Encryption of data is fundamental to secure communication in the modern world. Beyond encryption of data lies obfuscation, i.e., encryption of functionality. It is well-known that the most powerful means of obfuscating classical programs, so-called ``black-box obfuscation',' is provably impossible [Barak et al '12]. However, several recent results have yielded candidate schemes that satisfy a definition weaker than black-box, and yet still have numerous applications. In this work, we initialize the rigorous study of obfuscating programs via quantum-mechanical means. We define notions of quantum obfuscation which encompass several natural variants. The input to the obfuscator can describe classical or quantum functionality, and the output can be a circuit description or a quantum state. The obfuscator can also satisfy one of a number of obfuscation conditions: black-box, information-theoretic black-box, indistinguishability, and best possible; the last two conditions come in three variants: perfect, statistical, and computational. We discuss many applications, including CPA-secure quantum encryption, quantum fully-homomorphic encryption, and public-key quantum money. We then prove several impossibility results, extending a number of foundational papers on classical obfuscation to the quantum setting. We prove that quantum black-box obfuscation is impossible in a setting where adversaries can possess more than one output of the obfuscator. In particular, generic transformation of quantum circuits into black-box-obfuscated quantum circuits is impossible. We also show that statistical indistinguishability obfuscation is impossible, up to an unlikely complexity-theoretic collapse. Our proofs involve a new tool: chosen-ciphertext-secure encryption of quantum data, which was recently shown to be possible assuming quantum-secure one-way functions exist [Alagic et al '16].
In this work, we show how to use the positive results on succinct argument systems to prove impossibility results on leakage-resilient black-box zero knowledge. This recently proposed notion of zero knowledge deals with an adversary that can make leakage queries on the state of the prover. Our result holds for black-box simulation only and we also give some insights on the non-black-box case. Additionally, we show that, for several functionalities, leakage-resilient multi-party computation is impossible (regardless of the number of players and even if just one player is corrupted). More in details, we achieve the above results by extending a technique of [Nielsen, Venturi, Zottarel – PKC 13] to prove lower bounds for leakage-resilient security. Indeed, we use leakage queries to run an execution of a communication-efficient protocol in the head of the adversary. Moreover, to defeat the black-box simulator we connect the above technique for leakage resilience to security against reset attacks. Our results show that the open problem of [Ananth, Goyal, Pandey – Crypto 14] (i.e., continual leakage-resilient proofs without a common reference string) has a negative answer when security through black-box simulation is desired. Moreover our results close the open problem of [Boyle et al. – STOC 12] for the case of black-box simulation (i.e., the possibility of continual leakage-resilient secure computation without a leak-free interactive preprocessing).