Dr Gennaro Avitabile

Signature-based witness encryption (SWE) is a recently proposed notion that allows to encrypt a message with respect to a tag T and a set of signature verification keys. The resulting ciphertext can only be decrypted by a party who holds at least k different valid signatures w.r.t. T and k different verification keys out of the n keys specified at encryption time. Natural applications of this primitive involve distributed settings (e.g., blockchains), where multiple parties sign predictable messages, such as polling or randomness beacons. However, known SWE schemes without trusted setup have ciphertexts that scale linearly in the number of verification keys. This quickly becomes a major bottleneck as the system gets more distributed and the number of parties increases.Towards showing the feasibility of SWE with ciphertext size sub-linear in the number of keys, we give a construction based on indistinguishability obfuscation (iO) for Turing machines and strongly puncturable signatures (SPS).

At CRYPTO '94, Cramer, Damgard, and Schoenmakers introduced a general technique for constructing honest-verifier zero-knowledge proofs of partial knowledge (PPK), where a prover Alice wants to prove to a verifier Bob she knows tau witnesses for tau claims out of k claims without revealing the indices of those tau claims. Their solution starts from a base honest-verifier zero-knowledge proof of knowledge Sigma and requires to run in parallel k execution of the base protocol, giving a complexity of O(k gamma(Sigma)), where gamma(Sigma) is the communication complexity of the base protocol. However, modern practical scenarios require communication-efficient zero-knowledge proofs tailored to handle partial knowledge in specific application-dependent formats. In this paper, we propose a technique to compose a large class of Sigma-protocols for atomic statements into Sigma-protocols for PPK over formulae in conjunctive normal form (CNF) that overlap, in the sense that there is a common subset of literals among all clauses of the formula. In such formulae, the statement is expressed as a conjunction of m clauses, each of which consists of a disjunction of k literals (i.e., each literal is an atomic statement) and & ell; literals are shared among clauses. The prover, for a threshold parameter tau 1 providing improvements over state-of-the-art constructions.

Several countries adopted the Google & Apple exposure notification system (GAEN) to slow the spread of the SARS-CoV-2 virus down. GAEN promised to guarantee security and privacy through a decentralized approach. In this paper, we report several relevant privacy and integrity threats in GAEN, including new attacks. GAEN's security issues are not inherent risks of contact tracing systems. Indeed, we also propose a system named Pronto-B2 which enjoys a much better resilience with respect to mass surveillance and replay attacks.

We study the inherent limitations of additive accumulators and updatable vector commitments (VCs) with constant-size digest (i.e., independent of the number of committed elements). Specifically, we prove two lower bounds on the expected number of membership proofs that must be updated when a single element is added (or updated) in such data structures. Our results imply that when the digest bit length approaches the concrete security level, then the expected number of proofs invalidated due to an append operation for a digest committing to n elements is nearly maximal: n − negl(λ) in the case of exponential-size universes, and n − o(n) for super-polynomial universes. Our results have significant implications for stateless blockchain designs relying on constant-size VCs, suggesting that the overhead of frequent proof updates may offset the benefits of reducing global state storage.

A Timed Commitment (TC) with time parameter t is hiding for time at most t, that is, commitments can be force-opened by any third party within time t. In addition to various cryptographic assumptions, the security of all known TC schemes relies on the sequentiality assumption of repeated squarings in hidden-order groups. The repeated squaring assumption is therefore a security bottleneck. In this work, we give a black-box construction of TCs from any time-lock puzzle (TLP) by additionally relying on one-way permutations and collision-resistant hashing. Currently, TLPs are known from (a) the specific repeated squaring assumption, (b) the general (necessary) assumption on the existence of worst-case non-parallelizing languages and indistinguishability obfuscation, and (c) any iteratively sequential function and the hardness of the circular small-secret LWE problem. The latter admits a plausibly post-quantum secure instantiation. Hence, thanks to the generality of our transform, we get i) the first TC whose timed security is based on the existence of non-parallelizing languages and ii) the first TC that is plausibly post-quantum secure. We first define quasi publicly-verifiable TLPs (QPV-TLPs) and construct them from any standard TLP in a black-box manner without relying on any additional assumptions. Then, we devise a black-box commit-and-prove system to transform any QPV-TLPs into a TC.

Threshold ring signatures are digital signatures that allow t parties to sign a message while hiding their identity in a larger set of n users called "ring". Recently, Aranha et al. [PKC 2022] introduced the notion of extendable threshold ring signatures (ETRS). ETRS allow one to update, in a non-interactive manner, a threshold ring signature on a certain message so that the updated signature has a greater threshold, and/or an augmented set of potential signers. An application of this primitive is anonymous count me in. A first signer creates a ring signature with a sufficiently large ring announcing a proposition in the signed message. After such cause becomes public, other parties can anonymously decide to support that proposal by producing an updated signature. Crucially, such applications rely on partial signatures being posted on a publicly accessible bulletin board since users may not know/trust each other. In this paper, we first point out that even if anonymous count me in was suggested as an application of ETRS, the anonymity notion proposed in the previous work is insufficient in many application scenarios. Indeed, the existing notion guarantees anonymity only against adversaries who just see the last signature, and are not allowed to access the "full evolution" of an ETRS. This is in stark contrast with applications where partial signatures are posted in a public bulletin board. We therefore propose stronger anonymity definitions and construct a new ETRS that satisfies such definitions. Interestingly, while satisfying stronger anonymity properties, our ETRS asymptotically improves on the two ETRS presented in prior work [PKC 2022] in terms of both time complexity and signature size. Our ETRS relies on extendable non-interactive witness-indistinguishable proof of knowledge (ENIWI PoK), a novel technical tool that we formalize and construct, and that may be of independent interest. We build our constructions from pairing groups under the SXDH assumption.

Recently, there has been great interest towards constructing efficient zero-knowledge proofs for practical languages. In this work, we focus on proofs for threshold relations, in which the prover is required to prove knowledge of witnesses for k out of l statements. The main contribution of our work is an efficient and modular transformation that starting from a large class of Sigma-protocols and a corresponding threshold relation R-k,R-l, provides an efficient Sigma-protocol for R-k,R-l with improved communication complexity w.r.t. prior results. Our transformation preserves statistical/perfect honest-verifier zero knowledge.

In this work we show that an adversary can attack the integrity of contact tracing systems based on Google-Apple Exposure Notifications (GAEN) by leveraging blockchain technology. We show that through smart contracts there can be an on-line market where infected individuals interested in monetizing their status can upload to the servers of the GAEN-based systems some keys (i.e., TEKs) chosen by a non-infected adversary. In particular, the infected individual can anonymously and digitally trade the upload of TEKs without a mediator and without running risks of being cheated. This vulnerability can therefore be exploited to generate large-scale fake exposure notifications of at-risk contacts with serious consequences (e.g., jeopardizing parts of the health system, affecting results of elections, imposing the closure of schools, hotels or factories). As main contribution, we design a smart contract with two collateral deposits that works, in general, on GAEN-based systems. We then also suggest the design of a more sophisticated smart contract, using DECO, that could be used to attack in a different way GAEN-based systems (i.e., this second smart contract can succeed even in case GAEN systems are repaired making ineffective the first smart contract). Our work shows how to realize with GAEN-based systems (in particular with Immuni and SwissCovid), the terrorist attack to decentralized contact tracing systems envisioned by Vaudenay.

Combining verifiable computation with optimistic approaches is a promising direction to scale blockchain applications. The basic idea consists of saving computations by avoiding the verification of proofs unless there are complaints. A key tool to design systems in the above direction has been recently proposed by Seres, Glaeser and Bonneau [FC’24] who formalized the concept of a Naysayer proof: an efficient to verify proof disproving a more demanding to verify original proof. In this work, we discuss the need of rewarding naysayer provers, the risks deriving from front-running attacks, and the failures of generic approaches trying to defeat them. Next, we introduce the concept of verifiable delayed naysayer proofs and show a construction leveraging proofs of sequential work, without relying on any additional infrastructure.

Traceable ring signatures enhance ring signatures by adding an accountability layer. Specifically, if a party signs two different messages within the protocol, their identity is revealed. Another desirable feature is extendability. In particular, extendable threshold ring signatures (ETRS) allow to non-interactively update already finalized signatures by enlarging the ring or the set of signers. Combining traceability and extendability in a single scheme is unexplored and would offer a new tool for privacy-preserving voting schemes in scenarios where the voters are not known in advance. In this paper, we show how to reconcile both properties by introducing and constructing a new cryptographic primitive called Tetris. Notably, our Tetris construction simultaneously achieves a strong flavor of anonymity and linear-size signatures, which is the main technical challenge in existing techniques. To solve this challenge, we develop a new approach to traceability that leads to several conceptual and technical contributions. Among those, we introduce and construct, based on Groth-Sahai proofs, extendable shuffle arguments that can be non-interactively updated by several provers.

The concept of Anamorphic Encryption (Persiano, Phan and Yung, EUROCRYPT’22), aims to enable private communication in settings where the usage of encryption is heavily controlled by a central authority (henceforth called the dictator) who can obtain users’ secret keys. Since then, various works have improved our understanding of AE in several aspects, including its limitations. In this regard, two recent works at CRYPTO’25 constructed various Anamorphic-Resistant Encryption (ARE) schemes, i.e., schemes admitting at most O(log((λ))) O(\log ((λ ))) bits of covert communication. However, those results are still unsatisfactory, each coming with at least one of the following issues: (1) use of cryptographic heavy hammers such as indistinguishability obfuscation (iO); (2) abuse of the original definition to define overly powerful dictators; (3) reliance on the Random Oracle Model (ROM). In particular, proofs in the ROM are controversial as they fail to account for anamorphic schemes making non-black-box usage of the hash function used to instantiate the Random Oracle. In this work, we overcome all of these limitations. First, we describe an anamorphic-resistant encryption scheme approaching practicality by relying only on public-key encryption and Extremely Lossy Functions (ELFs), both known from the (exponential) DDH assumption. Moreover, assuming Fully Unique NIZKs (known from iO), we provide another construction, which we later use to realize the first definitive ARE; that is, a single scheme that simultaneously achieves the strongest level of anamorphic resistance against each of the possible levels of anamorphic security.

Balancing immutability and compliance with regulations stands as a significant challenge in the realm of blockchain technology applications. Due to the increase of data-protection requirements (e.g., the GDPR in the EU), it is essential to address the problem of deleting data from a blockchain without compromising the security and transparency of the blockchain itself. Several works proposed techniques to address the data redaction problem. In their seminal work, Ateniese et al. [EuroS&P 2017] were the first to propose a redactable blockchain. Their approach focuses on permissioned blockchains and they showed how to change the content of a transaction without breaking the chaining among blocks by using special cryptographic hash functions (i.e., chameleon hash functions) and secure multi-party computation. We observe that the redaction technique of Ateniese et al. does not take into account the possibility that the blockchain supports smart contracts and that a redaction of a transaction might leave inconsistencies in the logic of the contracts, making some remaining non-redacted transactions invalid, and, more in general, the state of a smart contract inconsistent with the content of transactions. We find this choice rather limiting since decentralized and publicly verifiable computation guaranteed by smart-contract-enabled blockchains is necessary for modern (i.e., Web3) applications. To overcome the above limitations of the applicability of the redaction techniques of Ateniese et al., we propose a redaction technique with wider applicability that leverages succinct non-interactive arguments of knowledge (SNARKs) to realize what we call a proof-of-consistency.