Ivan Visconti

TCS Journal 2023 Journal Article

Doubly adaptive zero-knowledge proofs

• Vincenzo Botta
• Ivan Visconti

In [TCC 2009 and JoC 2011] Lindell and Zarosim defined adaptive-corruption zero knowledge giving to the environment the power to perform post-execution corruption only. Moreover, their zero-knowledge proof system does not enjoy adaptive-input selection since it crucially relies on fixing the inputs already at the onset of the protocol. In this paper, we propose a new definition of adaptive-corruption zero-knowledge proofs that more naturally fits the setting that benefits from adaptive-input selection. We allow the non-rewindable environment to corrupt the prover adaptively based on its visibility of the messages exchanged so far. Then we show a zero-knowledge proof system for NP that is doubly adaptive (i. e. , it enjoys adaptive-corruption under our stronger notion and adaptive-input selection) matching the same assumptions and round complexity of classical zero-knowledge proofs.

STOC Conference 2014 Conference Paper

Black-box non-black-box zero knowledge

• Vipul Goyal
• Rafail Ostrovsky
• Alessandra Scafuro
• Ivan Visconti

FOCS Conference 2013 Conference Paper

Simultaneous Resettability from One-Way Functions

• Kai-Min Chung
• Rafail Ostrovsky
• Rafael Pass
• Ivan Visconti

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.

FOCS Conference 2012 Conference Paper

Constructing Non-malleable Commitments: A Black-Box Approach

• Vipul Goyal
• Chen-Kuei Lee
• Rafail Ostrovsky
• Ivan Visconti

We propose the first black-box construction of non-malleable commitments according to the standard notion of non-malleability with respect to commitment. Our construction additionally only requires a constant number of rounds and is based only on (black-box use of) one-way functions. Prior to our work, no black-box construction of non-malleable commitments was known (except for relaxed notions of security) in any (polynomial) number of rounds based on any cryptographic assumption. This closes the wide gap existent between black-box and non-black-box constructions for the problem of non-malleable commitments. Our construction relies on (and can be seen as a generalization of) the recent non-malleable commitment scheme of Goyal (STOC 2011). We also show how to get black-box constructions for a host of other cryptographic primitives. We extend our construction to get constant-round concurrent non-malleable commitments, constant-round multi-party coin tossing, and non-malleable statistically hiding commitments (satisfying the notion of non-malleability with respect to opening). All of the mentioned results make only a black-box use of one-way functions. Our primary technical contribution is a novel way of implementing the proof of consistency typically required in the constructions of non-malleable commitments (and other related primitives). We do this by relying on ideas from the ``zero-knowledge from secure multi-party computation" paradigm of Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2007). We extend in a novel way this ``computation in the head" paradigm (which can be though of as bringing powerful error-correcting codes into purely computational setting). To construct a non-malleable commitment scheme, we apply our computation in the head techniques to the recent (constant-round) construction of Goyal. Along the way, we also present a simplification of the construction of Goyal where a part of the protocol is implemented in an information theoretic manner. Such a simplification is crucial for getting a black-box construction. This is done by making use of pair wise-independent hash functions and strong randomness extractors. We show that our techniques have multiple applications, as elaborated in the paper. Hence, we believe our techniques might be useful in other settings in future.

TCS Journal 2007 Journal Article

Hybrid commitments and their applications to zero-knowledge proof systems

• Dario Catalano
• Ivan Visconti

We introduce the notion of hybrid trapdoor commitment schemes. Intuitively a hybrid trapdoor commitment scheme is a primitive which can be either an unconditionally binding commitment scheme or a trapdoor commitment scheme depending on the distribution of commitment parameters. Moreover, such two possible distributions are computationally indistinguishable. Hybrid trapdoor commitments are related but different with respect to mixed commitments (introduced by Damgård and Nielsen at Crypto 2002). In particular hybrid trapdoor commitments can either be polynomially trapdoor commitments or unconditionally binding commitments, while mixed commitments can be either trapdoor commitments or extractable commitments. In this paper we show that strong notions (e. g. , simulation sound, multi-trapdoor) of hybrid trapdoor commitments admit constructions based on the sole assumption that one-way functions exist as well as efficient constructions based on standard number-theoretic assumptions. To further stress the difference between hybrid and mixed commitments, we remark here that mixed commitments seem to require stronger theoretical assumptions (and the known number-theoretic constructions are less efficient). Our main result, is to show how to construct concurrent and simulation-sound zero-knowledge proof systems (in contrast to the arguments recently presented in [I. Damgård, Efficient concurrent zero-knowledge in the auxiliary string model, in: Advances in Cryptology — Eurocrypt’00, in: Lecture Notes in Computer Science, vol. 1807, Springer-Verlag, 2000, pp. 418–430; P. MacKenzie, K. Yang, On simulation-sound trapdoor commitments, in: Advances in Cryptology — Eurocrypt’04, in: Lecture Notes in Computer Science, vol. 3027, Springer-Verlag, 2004, pp. 382–400; R. Gennaro, Multi-trapdoor commitments and their applications to proofs of knowledge secure under concurrent man-in-the-middle attacks, in: Advances in Cryptology — Crypto’04, in: Lecture Notes in Computer Science, vol. 3152, Springer-Verlag, 2004, pp. 220–236]) in the common reference string model. We crucially use hybrid trapdoor commitments since we present general constructions based on the sole assumption that one-way functions exist and very efficient constructions based on number-theoretic assumptions.

MFCS Conference 2006 Conference Paper

On Non-Interactive Zero-Knowledge Proofs of Knowledge in the Shared Random String Model

• Giuseppe Persiano
• Ivan Visconti

Abstract In this paper we study the notion of a Double-Round NIZ- KPK in the SRS model. In a Double-Round NIZKPK prover and verifier have access to the same random string Σ and, in addition, the prover is allowed to send one message to the verifier before Σ is made available. The verifier needs not to reply to this message. The random string and initial prover message can then be used in any polynomial number of proofs each consisting of a single message. We show how to construct Double-Round non-malleable NIZKPKs in the SRS model by only requiring the existence of one-way trapdoor permutations. In contrast, regular NIZKPKs require the existence of cryptosystems with an extra density property, called dense secure cryptosystems. We then show that Double-Round NIZKPKs can replace one-round NIZKPKs in the design of secure protocols. The replacement has no significant effect on the round complexity of the larger protocol but it removes the need of the existence of dense secure cryptosystems. We give examples of cryptographic constructions that use one-round NIZKPKs and that are improved when using Double-Round NIZKPKs: 1) the construction of 3-round resettable zero-knowledge arguments in the UPK model [EUROCRYPT 2001]; 2) the construction of a constant-round ( n – 1)-secure simulatable coin-flipping protocol [EUROCRYPT 2003].