@article{scafuro_2022, title={Black-Box Anonymous Commit-and-Prove}, volume={13409}, ISBN={["978-3-031-14790-6"]}, ISSN={["1611-3349"]}, DOI={10.1007/978-3-031-14791-3_26}, abstractNote={Commit-and-prove is a building block that allows a party to commit to a secret input and then later prove something about it. This is a pillar of many cryptographic protocols and especially the ones underlying anonymous systems. In anonymous systems, often there is a set of public commitments, and a prover wants to prove a property about one of the inputs committed in the set, while hiding which one. This latter property gives the prover anonymity within the set. Currently, there are numerous commit-and-prove protocols in the anonymous setting from various computational and setup assumptions. However, all such approaches are non-black-box in the cryptographic primitive. In fact, there exists no anonymous black-box construction of commit-and-prove protocols, under any computational or setup assumption. This is despite the fact that, when anonymity is not required, black-box commit-and-prove protocols are well known. Is this inherent in the anonymous setting? In this paper we provide a partial answer to the above question by constructing the first (one-time) black-box commit-and-prove protocol in the anonymous setting. We do so by first introducing a new primitive that we call Partially Openable Commitment (POC), and instantiating it in a black-box way from a Random Oracle. Next we show a black-box commit-and-prove protocol based on POC. From a theoretical standpoint, our result reduces the gap between known black-box feasibility results in the non-anonymous setting and the anonymous setting. From a practical standpoint, we show that our protocol can be very efficient for certain relations of interest.}, journal={SECURITY AND CRYPTOGRAPHY FOR NETWORKS (SCN 2022)}, author={Scafuro, Alessandra}, year={2022}, pages={591–614} }
 @article{daza_haque_scafuro_zacharakis_zapico_2022, title={Mutual Accountability Layer: Accountable Anonymity Within Accountable Trust}, volume={13301}, ISBN={["978-3-031-07688-6"]}, ISSN={["1611-3349"]}, DOI={10.1007/978-3-031-07689-3_24}, abstractNote={Anonymous cryptographic primitives reduce the traces left by users when they interact over a digital platform. But they also prevent a platform owner from holding users accountable for malicious behaviour. Revocable anonymity offers a compromise by allowing only the manager of the digital platform to de-anonymize a user's activities when necessary. However, a misbehaving manager can abuse their de-anonymization power by de-anonymizing activities without the user's awareness. Although previous works mitigate this issue by distributing the de-anonymization power across several entities, there is no comprehensive and formal treatment where both accountability and non-frameability (i.e., the inability to falsely accuse a party of misbehavior) for both the user and the manager are explicitly defined and provably achieved. In this paper we formally define mutual accountability: a user can be held accountable for her otherwise anonymous digital actions and a manager is held accountable for every de-anonymization attempt. Also, no honest party can be framed regardless of what malicious parties do. In contrast with previous work, we do not distribute the de-anonymization power across entities, instead, we decouple the power of de-anonymization from the power of monitoring de-anonymization attempts. This allows for greater flexibility, particularly in the choice of the monitoring entities. We show that our framework can be instantiated generically from threshold encryption schemes and succinct non-interactive zero-knowledge. We also show that the highly-efficient threshold group signature scheme by Camenisch et al. (SCN'20) can be modified and extended to instantiate our framework.}, journal={CYBER SECURITY, CRYPTOLOGY, AND MACHINE LEARNING}, author={Daza, Vanesa and Haque, Abida and Scafuro, Alessandra and Zacharakis, Alexandros and Zapico, Arantxa}, year={2022}, pages={318–336} }
 @article{scafuro_zhang_2021, title={One-Time Traceable Ring Signatures}, volume={12973}, ISBN={["978-3-030-88427-7"]}, ISSN={["1611-3349"]}, DOI={10.1007/978-3-030-88428-4_24}, abstractNote={A ring signature allows a party to sign messages anonymously on behalf of a group, which is called ring. Traceable ring signatures are a variant of ring signatures that limits the anonymity guarantees, enforcing that a member can sign anonymously at most one message per tag. Namely, if a party signs two different messages for the same tag, it will be de-anomymized. This property is very useful in decentralized platforms to allow members to anonymously endorse statements in a controlled manner.In this work we introduce one-time traceable ring signatures, where a member can sign anonymously only one message. This natural variant suffices in many applications for which traceable ring signatures are useful, and enables us to design a scheme that only requires a few hash evaluations and outperforms existing (non one-time) schemes.Our one-time traceable ring signature scheme presents many advantages: it is fast, with a signing time of less than 1 s for a ring of \(2^{10}\) signers (and much less for smaller rings); it is post-quantum resistant, as it only requires hash evaluations; it is extremely simple, as it requires only a black-box access to a generic hash function (modeled as a random oracle) and no other cryptographic operation is involved. From a theoretical standpoint our scheme is also the first anonymous signature scheme based on a black-box access to a symmetric-key primitive. All existing anonymous signatures are either based on specific hardness assumptions (e.g., LWE, SIS, etc.) or use the underlying symmetric-key primitive in a non-black-box way, i.e., they leverage the circuit representation of the primitive.}, journal={COMPUTER SECURITY - ESORICS 2021, PT II}, author={Scafuro, Alessandra and Zhang, Bihan}, year={2021}, pages={481–500} }
 @article{baldimtsi_madathil_scafuro_zhou_2020, title={Anonymous Lottery In The Proof-of-Stake Setting}, ISSN={["2374-8303"]}, DOI={10.1109/CSF49147.2020.00030}, abstractNote={When Proof-of-Stake (PoS) underlies a consensus protocol, parties who are eligible to participate in the protocol are selected via a public selection function that depends on the stake they own. Identity and stake of the selected parties must then be disclosed in order to allow verification of their eligibility, and this can raise privacy concerns. In this paper, we present a modular approach for addressing the identity leaks of selection functions, decoupling the problem of implementing an anonymous selection of the participants, from the problem of implementing others task, e.g. consensus. We present an ideal functionality for anonymous selection that can be more easily composed with other protocols. We then show an instantiation of our anonymous selection functionality based on the selection function of Algorand.}, journal={2020 IEEE 33RD COMPUTER SECURITY FOUNDATIONS SYMPOSIUM (CSF 2020)}, author={Baldimtsi, Foteini and Madathil, Varun and Scafuro, Alessandra and Zhou, Linfeng}, year={2020}, pages={318–333} }
 @article{goldwasser_ostrovsky_scafuro_sealfon_2018, title={Population Stability: Regulating Size in the Presence of an Adversary}, DOI={10.1145/3212734.3212747}, abstractNote={We introduce a new coordination problem in distributed computing that we call the population stability problem. A system of agents each with limited memory and communication, as well as the ability to replicate and self-destruct, is subjected to attacks by a worst-case adversary that can at a bounded rate (1) delete agents chosen arbitrarily and (2) insert additional agents with arbitrary initial state into the system. The goal is perpetually to maintain a population whose size is within a constant factor of the target size N. The problem is inspired by the ability of complex biological systems composed of a multitude of memory-limited individual cells to maintain a stable population size in an adverse environment. Such biological mechanisms allow organisms to heal after trauma or to recover from excessive cell proliferation caused by inflammation, disease, or normal development. We present a population stability protocol in a communication model that is a synchronous variant of the population model of Angluin et al. In each round, pairs of agents selected at random meet and exchange messages, where at least a constant fraction of agents is matched in each round. Our protocol uses three-bit messages and ω(log^2 N) states per agent. We emphasize that our protocol can handle an adversary that can both insert and delete agents, a setting in which existing approximate counting techniques do not seem to apply. The protocol relies on a novel coloring strategy in which the population size is encoded in the variance of the distribution of colors. Individual agents can locally obtain a weak estimate of the population size by sampling from the distribution, and make individual decisions that robustly maintain a stable global population size.}, journal={PODC'18: PROCEEDINGS OF THE 2018 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING}, author={Goldwasser, Shafi and Ostrovsky, Rafail and Scafuro, Alessandra and Sealfon, Adam}, year={2018}, pages={397–406} }
 @inbook{jafargholi_scafuro_wichs_2017, title={Adaptively Indistinguishable Garbled Circuits}, ISBN={9783319705026 9783319705033}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-319-70503-3_2}, DOI={10.1007/978-3-319-70503-3_2}, abstractNote={A garbling scheme is used to garble a circuit C and an input x in a way that reveals the output C(x) but hides everything else. An adaptively secure scheme allows the adversary to specify the input x after seeing the garbled circuit. Applebaum et al. (CRYPTO '13) showed that in any garbling scheme with adaptive simulation-based security, the size of the garbled input must exceed the output size of the circuit. Here we show how to circumvent this lower bound and achieve significantly better efficiency under the minimal assumption that one-way functions exist by relaxing the security notion from simulation-based to indistinguishability-based. We rely on the recent work of Hemenway et al. (CRYPTO '16) which constructed an adaptive simulation-based garbling scheme under one-way functions. The size of the garbled input in their scheme is as large as the output size of the circuit plus a certain pebble complexity of the circuit, where the latter is (e.g.,) bounded by the space complexity of the computation. By building on top of their construction and adapting their proof technique, we show how to remove the output size dependence in their result when considering indistinguishability-based security. As an application of the above result, we get a symmetric-key functional encryption based on one-way functions, with indistinguishability-based security where the adversary can obtain an unbounded number of function secret keys and then adaptively a single challenge ciphertext. The size of the ciphertext only depends on the maximal pebble complexity of each of the functions but not on the number of functions or their circuit size.}, booktitle={Theory of Cryptography}, publisher={Springer International Publishing}, author={Jafargholi, Zahra and Scafuro, Alessandra and Wichs, Daniel}, year={2017}, pages={40–71} }
 @inbook{baldimtsi_papadopoulos_papadopoulos_scafuro_triandopoulos_2017, title={Server-Aided Secure Computation with Off-line Parties}, ISBN={9783319664019 9783319664026}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-319-66402-6_8}, DOI={10.1007/978-3-319-66402-6_8}, abstractNote={Online social networks (OSNs) allow users to jointly compute on each other’s data (e.g., profiles, geo-locations, etc.). Privacy issues naturally arise in this setting due to the sensitive nature of the exchanged information. Ideally, nothing about a user’s data should be revealed to the OSN provider or non-friends, and even her friends should only learn the output of a specific computation. A natural approach for achieving these strong privacy guarantees is via secure multi-party computation (MPC). However, existing MPC-based approaches do not capture two key properties of OSN setting: Users does not need to be online while their friends query the OSN server on their data; and, once uploaded, user’s data can be repeatedly queried by the server on behalf of user’s friends. In this work, we present two concrete MPC constructions that achieve these properties. The first is an adaptation of garbled circuits that converts inputs under different keys to ones under the same key, and the second is based on 2-party mixed protocols and involves a novel 2-party re-encryption module. Using state- of-the-art cryptographic tools, we provide a proof-of-concept implementation of our schemes for two concrete use cases, overall validating their efficiency and efficacy in protecting privacy in OSNs.}, booktitle={Computer Security – ESORICS 2017}, publisher={Springer International Publishing}, author={Baldimtsi, Foteini and Papadopoulos, Dimitrios and Papadopoulos, Stavros and Scafuro, Alessandra and Triandopoulos, Nikos}, year={2017}, pages={103–123} }
 @article{mohassel_rosulek_scafuro_2017, title={Sublinear Zero-Knowledge Arguments for RAM Programs}, volume={10210}, ISBN={["978-3-319-56619-1"]}, ISSN={["1611-3349"]}, DOI={10.1007/978-3-319-56620-7_18}, abstractNote={We describe a new succinct zero-knowledge argument protocol with the following properties. The prover commits to a large data-set M, and can thereafter prove many statements of the form $$\exists w : \mathcal {R}_i(M,w)=1$$ , where $$\mathcal {R}_i$$ is a public function. The protocol is succinct in the sense that the cost for the verifier (in computation & communication) does not depend on |M|, not even in any initialization phase In each proof, the computation/communication cost for both the prover and the verifier is proportional only to the running time of an oblivious RAM program implementing $$\mathcal {R}_i$$ (in particular, this can be sublinear in |M|). The only costs that scale with |M| are the computational costs of the prover in a one-time initial commitment to M. Known sublinear zero-knowledge proofs either require an initialization phase where the work of the verifier is proportional to |M| and are therefore sublinear only in an amortized sense, or require that the computational cost for the prover is proportional to |M| upon each proof. Our protocol uses efficient crypto primitives in a black-box way and is UC-secure in the global, non-programmable random oracle, hence it does not rely on any trusted setup assumption.}, journal={ADVANCES IN CRYPTOLOGY - EUROCRYPT 2017, PT I}, author={Mohassel, Payman and Rosulek, Mike and Scafuro, Alessandra}, year={2017}, pages={501–531} }
 @inbook{hemenway_jafargholi_ostrovsky_scafuro_wichs_2016, title={Adaptively Secure Garbled Circuits from One-Way Functions}, ISBN={9783662530146 9783662530153}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-662-53015-3_6}, DOI={10.1007/978-3-662-53015-3_6}, abstractNote={A garbling scheme is used to garble a circuit C and an input x in a way that reveals the output C(x) but hides everything else. In many settings, the circuit can be garbled off-line without strict efficiency constraints, but the input must be garbled very efficiently on-line, with much lower complexity than evaluating the circuit. Yao's garbling scheme [31] has essentially optimal on-line complexity, but only achieves selective security, where the adversary must choose the input x prior to seeing the garbled circuit. It has remained an open problem to achieve adaptive security, where the adversary can choose x after seeing the garbled circuit, while preserving on-line efficiency. In this work, we modify Yao's scheme in a way that allows us to prove adaptive security under one-way functions. In our main instantiation we achieve on-line complexity only proportional to the width w of the circuit. Alternatively we can also get an instantiation with on-line complexity only proportional to the depth d (and the output size) of the circuit, albeit incurring in a $$2^{O(d)}$$ security loss in our reduction. More broadly, we relate the on-line complexity of adaptively secure garbling schemes in our framework to a certain type of pebble complexity of the circuit. As our main tool, of independent interest, we develop a new notion of somewhere equivocal encryption, which allows us to efficiently equivocate on a small subset of the message bits.}, booktitle={Advances in Cryptology – CRYPTO 2016}, publisher={Springer Berlin Heidelberg}, author={Hemenway, Brett and Jafargholi, Zahra and Ostrovsky, Rafail and Scafuro, Alessandra and Wichs, Daniel}, year={2016}, pages={149–178} }
 @inbook{bellare_fuchsbauer_scafuro_2016, title={NIZKs with an Untrusted CRS: Security in the Face of Parameter Subversion}, ISBN={9783662538890 9783662538906}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-662-53890-6_26}, DOI={10.1007/978-3-662-53890-6_26}, abstractNote={Motivated by the subversion of "trusted" public parameters in mass-surveillance activities, this paper studies the security of NIZKs in the presence of a maliciously chosen common reference string. We provide definitions for subversion soundness, subversion witness indistinguishability and subversion zero knowledge. We then provide both negative and positive results, showing that certain combinations of goals are unachievable but giving protocols to achieve other combinations.}, booktitle={Advances in Cryptology – ASIACRYPT 2016}, publisher={Springer Berlin Heidelberg}, author={Bellare, Mihir and Fuchsbauer, Georg and Scafuro, Alessandra}, year={2016}, pages={777–804} }
 @inbook{ciampi_persiano_scafuro_siniscalchi_visconti_2016, title={Online/Offline OR Composition of Sigma Protocols}, ISBN={9783662498958 9783662498965}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-662-49896-5_3}, DOI={10.1007/978-3-662-49896-5_3}, abstractNote={Proofs of partial knowledge allow a prover to prove knowledge of witnesses for k out of n instances of NP languages. Cramer, Schoenmakers and Damgård [10] provided an efficient construction of a 3-round public-coin witness-indistinguishable (k, n)-proof of partial knowledge for any NP language, by cleverly combining n executions of $$\varSigma $$ -protocols for that language. This transform assumes that all n instances are fully specified before the proof starts, and thus directly rules out the possibility of choosing some of the instances after the first round. Very recently, Ciampi et al. [6] provided an improved transform where one of the instances can be specified in the last round. They focus on (1, 2)-proofs of partial knowledge with the additional feature that one instance is defined in the last round, and could be adaptively chosen by the verifier. They left as an open question the existence of an efficient (1, 2)-proof of partial knowledge where no instance is known in the first round. More in general, they left open the question of constructing an efficient (k, n)-proof of partial knowledge where knowledge of all n instances can be postponed. Indeed, this property is achieved only by inefficient constructions requiring NP reductions [19]. In this paper we focus on the question of achieving adaptive-input proofs of partial knowledge. We provide through a transform the first efficient construction of a 3-round public-coin witness-indistinguishable (k, n)-proof of partial knowledge where all instances can be decided in the third round. Our construction enjoys adaptive-input witness indistinguishability. Additionally, the proof of knowledge property remains also if the adversarial prover selects instances adaptively at last round as long as our transform is applied to a proof of knowledge belonging to the widely used class of proofs of knowledge described in [9, 21]. Since knowledge of instances and witnesses is not needed before the last round, we have that the first round can be precomputed and in the online/offline setting our performance is similar to the one of [10]. Our new transform relies on the DDH assumption (in contrast to the transforms of [6, 10] that are unconditional).}, booktitle={Advances in Cryptology – EUROCRYPT 2016}, publisher={Springer Berlin Heidelberg}, author={Ciampi, Michele and Persiano, Giuseppe and Scafuro, Alessandra and Siniscalchi, Luisa and Visconti, Ivan}, year={2016}, pages={63–92} }
 @inbook{ciampi_persiano_scafuro_siniscalchi_visconti_2016, place={Berlin Heidelberg}, series={Lecture Notes in Computer Science}, title={Improved OR-Composition of Sigma-Protocols}, ISBN={9783662490983 9783662490990}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-662-49099-0_5}, DOI={10.1007/978-3-662-49099-0_5}, abstractNote={In [18] Cramer, Damgård and Schoenmakers (CDS) devise an OR-composition technique for $$\varSigma $$ -protocols that allows to construct highly-efficient proofs for compound statements. Since then, such technique has found countless applications as building block for designing efficient protocols.}, booktitle={Theory of Cryptography. TCC 2016}, publisher={Springer}, author={Ciampi, Michele and Persiano, Giuseppe and Scafuro, Alessandra and Siniscalchi, Luisa and Visconti, Ivan}, year={2016}, pages={112–141}, collection={Lecture Notes in Computer Science} }
 @inbook{ostrovsky_scafuro_venkitasubramanian_2015, title={Resettably Sound Zero-Knowledge Arguments from OWFs - The (Semi) Black-Box Way}, ISBN={9783662464939 9783662464946}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-662-46494-6_15}, DOI={10.1007/978-3-662-46494-6_15}, abstractNote={We construct a constant round resettably-sound zero knowledge argument of knowledge based on black-box use of any one-way function. Resettable-soundness was introduced by Barak, Goldreich, Goldwasser and Lindell [FOCS 01] and is a strengthening of the soundness requirement in interactive proofs demanding that soundness should hold even if the malicious prover is allowed to "reset" and "restart" the verifier. In their work they show that resettably-sound ZK arguments require nonblack- box simulation techniques, and also provide the first construction based on the breakthrough simulation technique of Barak [FOCS 01]. All known implementations of Barak's non-black-box technique required non-black-box use of a collision-resistance hash-function (CRHF). Very recently, Goyal, Ostrovsky, Scafuro and Visconti [STOC 14] showed an implementation of Barak's technique that needs only blackbox access to a collision-resistant hash-function while still having a nonblack- box simulator. (Such a construction is referred to as semi blackbox.) Plugging this implementation in the compiler due to Barak et al. yields the first resettably-sound ZK arguments based on black-box use of CRHFs. However, from the work of Chung, Pass and Seth [STOC 13] and Bitansky and Paneth [STOC 13], we know that resettably-sound ZK arguments can be constructed from non-black-box use of any one-way function (OWF), which is the minimal assumption for ZK arguments. Hence, anatural question iswhether it ispossible to construct resettablysound zero-knowledge arguments from black-box use of any OWF only. In this work we provide a positive answer to this question thus closing the gap between black-box and non-black-box constructions for resettably-sound ZK arguments.}, booktitle={Theory of Cryptography}, publisher={Springer Berlin Heidelberg}, author={Ostrovsky, Rafail and Scafuro, Alessandra and Venkitasubramanian, Muthuramakrishnan}, year={2015}, pages={345–374} }
 @inbook{ostrovsky_richelson_scafuro_2015, title={Round-Optimal Black-Box Two-Party Computation}, ISBN={9783662479995 9783662480007}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-662-48000-7_17}, DOI={10.1007/978-3-662-48000-7_17}, abstractNote={In [Eurocrypt 2004] Katz and Ostrovsky establish the exact round complexity of secure two-party computation with respect to black-box proofs of security. They prove that 5 rounds are necessary for secure two-party protocols (4-round are sufficient if only one party receives the output) and provide a protocol that matches such lower bound. The main challenge when designing such protocol is to parallelize the proofs of consistency provided by both parties – necessary when security against malicious adversaries is considered– in 4 rounds. Toward this goal they employ specific proofs in which the statement can be unspecified till the last round but that require non-black-box access to the underlying primitives. A rich line of work [1, 9, 11, 13, 24] has shown that the non-black-box use of the cryptographic primitive in secure two-party computation is not necessary by providing black-box constructions matching basically all the feasibility results that were previously demonstrated only via non-black-box protocols. All such constructions however are far from being round optimal. The reason is that they are based on cut-and-choose mechanisms where one party can safely take an action only after the other party has successfully completed the cut-and-choose phase, therefore requiring additional rounds. A natural question is whether round-optimal constructions do inherently require non-black-box access to the primitives, and whether the lower bound shown by Katz and Ostrovsky can only be matched by a non-black-box protocol. In this work we show that round-optimality is achievable even with only black-box access to the primitives. We provide the first 4-round black-box oblivious transfer based on any enhanced trapdoor permutation. Plugging a parallel version of our oblivious transfer into the black-box non-interactive secure computation protocol of [12] we obtain the first round-optimal black-box two-party protocol in the plain model for any functionality.}, booktitle={Lecture Notes in Computer Science}, publisher={Springer Berlin Heidelberg}, author={Ostrovsky, Rafail and Richelson, Silas and Scafuro, Alessandra}, year={2015}, pages={339–358} }
 @inbook{ostrovsky_rao_scafuro_visconti_2013, title={Revisiting Lower and Upper Bounds for Selective Decommitments}, ISBN={9783642365935 9783642365942}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-642-36594-2_31}, DOI={10.1007/978-3-642-36594-2_31}, abstractNote={In [6,7], Dwork et al. posed the fundamental question of existence of commitment schemes that are secure against selective opening attacks (SOA, for short). In [2] Bellare, Hofheinz, and Yilek, and Hofheinz in [13] answered it affirmatively by presenting a scheme which is based solely on the non-black-box use of a one-way permutation needing a super-constant number of rounds. This result however opened other challenging questions about achieving a better round complexity and obtaining fully black-box schemes using underlying primitives and code of the adversary in a black-box manner.Recently, in TCC 2011, Xiao ([23]) investigated on how to achieve (nearly) optimal SOA-secure commitment schemes where optimality is in the sense of both the round complexity and the black-box use of cryptographic primitives. The work of Xiao focuses on a simulation-based security notion of SOA. Moreover, the various results in [23] focus only on either parallel or concurrent SOA.In this work we first point out various issues in the claims of [23] that actually re-open several of the questions left open in [2,13]. Then, we provide new lower bounds and concrete constructions that produce a very different state-of-the-art compared to the one claimed in [23].}, booktitle={Theory of Cryptography}, publisher={Springer Berlin Heidelberg}, author={Ostrovsky, Rafail and Rao, Vanishree and Scafuro, Alessandra and Visconti, Ivan}, year={2013}, pages={559–578} }
 @inbook{damgård_scafuro_2013, title={Unconditionally Secure and Universally Composable Commitments from Physical Assumptions}, ISBN={9783642420443 9783642420450}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-642-42045-0_6}, DOI={10.1007/978-3-642-42045-0_6}, abstractNote={We present a constant-round unconditional black-box compiler that transforms any ideal (i.e., statistically-hiding and statistically-binding) straight-line extractable commitment scheme, into an extractable and equivocal commitment scheme, therefore yielding to UC-security [9]. We exemplify the usefulness of our compiler by providing two (constant-round) instantiations of ideal straight-line extractable commitment based on (malicious) PUFs [36] and stateless tamper-proof hardware tokens [26], therefore achieving the first unconditionally UC-secure commitment with malicious PUFs and stateless tokens, respectively. Our constructions are secure for adversaries creating arbitrarily malicious stateful PUFs/tokens.Previous results with malicious PUFs used either computational assumptions to achieve UC-secure commitments or were unconditionally secure but only in the indistinguishability sense [36]. Similarly, with stateless tokens, UC-secure commitments are known only under computational assumptions [13,24,15], while the (not UC) unconditional commitment scheme of [23] is secure only in a weaker model in which the adversary is not allowed to create stateful tokens.Besides allowing us to prove feasibility of unconditional UC-security with (malicious) PUFs and stateless tokens, our compiler can be instantiated with any ideal straight-line extractable commitment scheme, thus allowing the use of various setup assumptions which may better fit the application or the technology available.}, booktitle={Advances in Cryptology - ASIACRYPT 2013}, publisher={Springer Berlin Heidelberg}, author={Damgård, Ivan and Scafuro, Alessandra}, year={2013}, pages={100–119} }
 @inbook{ostrovsky_scafuro_visconti_wadia_2013, title={Universally Composable Secure Computation with (Malicious) Physically Uncloneable Functions}, ISBN={9783642383472 9783642383489}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-642-38348-9_41}, DOI={10.1007/978-3-642-38348-9_41}, abstractNote={Physically Uncloneable Functions (PUFs) [28] are noisy physical sources of randomness. As such, they are naturally appealing for cryptographic applications, and have caught the interest of both theoreticians and practitioners. A major step towards understanding and securely using PUFs was recently taken in [Crypto 2011] where Brzuska, Fischlin, Schröder and Katzenbeisser model PUFs in the Universal Composition (UC) framework of Canetti [FOCS 2001]. A salient feature of their model is that it considers trusted PUFs only; that is, PUFs which have been produced via the prescribed manufacturing process and are guaranteed to be free of any adversarial influence. However, this does not accurately reflect real-life scenarios, where an adversary could be able to create and use malicious PUFs. The goal of this work is to extend the model proposed in [Crypto 2011] in order to capture such a real-world attack. The main contribution of this work is the study of the Malicious PUFs model. To this end, we first formalize the notion of “malicious” PUFs, and extend the UC formulation of Brzuska et al. to allow the adversary to create PUFs with arbitrary adversarial behaviour. Then, we provide positive results in this, more realistic, model. We show that, under computational assumptions, it is possible to UC-securely realize any functionality.}, booktitle={Advances in Cryptology – EUROCRYPT 2013}, publisher={Springer Berlin Heidelberg}, author={Ostrovsky, Rafail and Scafuro, Alessandra and Visconti, Ivan and Wadia, Akshay}, year={2013}, pages={702–718} }
 @inbook{scafuro_visconti_2012, title={On Round-Optimal Zero Knowledge in the Bare Public-Key Model}, ISBN={9783642290107 9783642290114}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-642-29011-4_11}, DOI={10.1007/978-3-642-29011-4_11}, abstractNote={In this paper we revisit previous work in the BPK model and point out subtle problems concerning security proofs of concurrent and resettable zero knowledge ( $\mathsf{c}{\mathcal{ZK}}$ and ${\mathsf{r}{\mathcal{ZK}}}$ , for short). Our analysis shows that the ${\mathsf c}{\mathcal{ZK}}$ and ${\mathsf{r}}{\mathcal{ZK}}$ simulations proposed for previous (in particular all round-optimal) protocols are distinguishable from real executions. Therefore some of the questions about achieving round optimal ${\mathsf{c}}{\mathcal{ZK}}$ and ${\mathsf{r}\mathcal{ZK}}$ in the BPK model are still open. We then show our main protocol, $\Pi_{\mathsf{c}{\mathcal{ZK}}}$ , that is a round-optimal concurrently sound $\mathsf{c}\mathcal{ZK}$ argument of knowledge (AoK, for short) for NP under standard complexity-theoretic assumptions. Next, using complexity leveraging arguments, we show a protocol $\Pi_{\mathsf{r}\mathcal{ZK}}$ that is round-optimal and concurrently sound ${\mathsf{r}}{\mathcal{ZK}}$ for NP. Finally we show that ${\Pi_{\mathsf{c}\mathcal{ZK}}}$ and $\Pi_{{\mathsf{r}}{\mathcal{ZK}}}$ can be instantiated efficiently through transformations based on number-theoretic assumptions. Indeed, starting from any language admitting a perfect Σ-protocol, they produce concurrently sound protocols ${\bar \Pi_{\mathsf{c}\mathcal{ZK}}}$ and $\bar \Pi_{\mathsf{r}\mathcal{ZK}}$ , where ${\bar \Pi_{\mathsf{c}\mathcal{ZK}}}$ is a round-optimal $\mathsf{c}\mathcal{ZK}\mathsf{AoK}$ , and ${\bar \Pi}_{{\mathsf{r}{\mathcal{ZK}}}}$ is a 5-round ${\mathsf{r}}{\mathcal{ZK}}$ argument. The ${\mathsf{r}}{\mathcal{ZK}}$ protocols are mainly inherited from the ones of Yung and Zhao [31].}, booktitle={Advances in Cryptology – EUROCRYPT 2012}, publisher={Springer Berlin Heidelberg}, author={Scafuro, Alessandra and Visconti, Ivan}, year={2012}, pages={153–171} }
 @inbook{cho_ostrovsky_scafuro_visconti_2012, title={Simultaneously Resettable Arguments of Knowledge}, ISBN={9783642289132 9783642289149}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-642-28914-9_30}, DOI={10.1007/978-3-642-28914-9_30}, abstractNote={In this work, we study simultaneously resettable arguments of knowledge. As our main result, we show a construction of a constant-round simultaneously resettable witness-indistinguishable argument of knowledge (simres $\mathcal{WI}$ AoK, for short) for any NP language. We also show two applications of simres $\mathcal{WI}$ AoK: the first constant-round simultaneously resettable zero-knowledge argument of knowledge in the Bare Public-Key Model; and the first simultaneously resettable identification scheme which follows the knowledge extraction paradigm.}, booktitle={Theory of Cryptography}, publisher={Springer Berlin Heidelberg}, author={Cho, Chongwon and Ostrovsky, Rafail and Scafuro, Alessandra and Visconti, Ivan}, year={2012}, pages={530–547} }
 @inbook{armknecht_sadeghi_scafuro_visconti_wachsmann_2010, title={Impossibility Results for RFID Privacy Notions}, ISBN={9783642176968 9783642176975}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-642-17697-5_3}, DOI={10.1007/978-3-642-17697-5_3}, abstractNote={RFID systems have become increasingly popular and are already used in many real-life applications. Although very useful, RFIDs introduce privacy risks since they carry identifying information that can be traced. Hence, several RFID privacy models have been proposed. However, they are often incomparable and in part do not reflect the capabilities of real-world adversaries. Recently, Paise and Vaudenay presented a general RFID security and privacy model that abstracts and unifies most previous approaches. This model defines mutual authentication (between RFID tags and readers) and several privacy notions that capture adversaries with different tag corruption behavior and capabilities. In this paper, we revisit the model proposed by Paise and Vaudenay and investigate some subtle issues such as tag corruption aspects. We show that in their formal definitions tag corruption discloses the temporary memory of tags and leads to the impossibility of achieving both mutual authentication and any reasonable notion of RFID privacy in their model. Moreover, we show that the strongest privacy notion (narrow-strong privacy) cannot be achieved simultaneously with reader authentication even under the strong assumption that tag corruption does not disclose temporary tag states. Further, we show other impossibility results that hold if the adversary can manipulate an RFID tag such that it resets its state or when tags are stateless. Although our results are shown on the privacy definition by Paise and Vaudenay, they give insight to the difficulties of setting up a mature security and privacy model for RFID systems that aims at fulfilling the sophisticated requirements of real-life applications.}, booktitle={Transactions on Computational Science XI}, publisher={Springer Berlin Heidelberg}, author={Armknecht, Frederik and Sadeghi, Ahmad-Reza and Scafuro, Alessandra and Visconti, Ivan and Wachsmann, Christian}, year={2010}, pages={39–63} }
 @inbook{d’arco_scafuro_visconti_2009, title={Revisiting DoS Attacks and Privacy in RFID-Enabled Networks}, ISBN={9783642054334 9783642054341}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-642-05434-1_9}, DOI={10.1007/978-3-642-05434-1_9}, abstractNote={Vaudenay presented in [ASIACRYPT 2007] a general RFID security and privacy model that abstracts some previous works in a single, concise, and much more understandable framework. He introduced eight distinct notions of privacy, corresponding to adversaries of different strength, and proved some possibility and impossibility results for such privacy notions. However, some interesting problems as: 1) achieving stronger privacy using low-cost tags (i.e., tags that usually can not perform public-key cryptography), 2) achieving stronger privacy in presence of side-channel attacks (e.g., DoS attacks, detection of the outputs of identification protocols), and 3) achieving stronger privacy under standard complexity-theoretic assumptions, are still left open. In this paper, we address the above problems and give two contributions. First of all we show that Vaudenay’s privacy notions are impossible to achieve in presence of DoS attacks. Therefore, we extend the model to better reflect the real-world scenario, where these attacks are easy to mount (e.g., by physically destroying/making inactive tags). More precisely, we refine Vaudenay’s privacy model to deal with DoS and DoS-like attacks, and introduce an additional privacy notion, referred to as semi-destructive privacy, which takes into account hardware features of some real-world tags. Then, we show an efficient RFID protocol that, by only using symmetric-key cryptography, satisfies the notion of semi-destructive privacy, under standard complexity-theoretic assumptions.}, booktitle={Algorithmic Aspects of Wireless Sensor Networks}, publisher={Springer Berlin Heidelberg}, author={D’Arco, Paolo and Scafuro, Alessandra and Visconti, Ivan}, year={2009}, pages={76–87} }