Refresh When You Wake Up: Proactive Threshold Wallets with Offline Devices

Conference paperRefereed Workshop
Yashvanth Kondi, Bernardo Magri, Claudio Orlandi and Omer Shlomovits
IEEE Security and Privacy Conference (S&P '21)
Publication year: 2021

Abstract: Proactive security is the notion of defending a distributed system against an attacker who compromises different devices through its lifetime, but no more than a threshold number of them at any given time. The emergence of threshold wallets for more secure cryptocurrency custody warrants an efficient proactivization protocol tailored to this setting. While many proactivization protocols have been devised and studied in the literature, none of them have communication patterns ideal for threshold wallets. In particular a (t,n) threshold wallet is designed to have t parties jointly sign a transaction (of which only one may be honest) whereas even the best current proactivization protocols require at least an additional thonest parties to come online simultaneously to refresh the system.

In this work we formulate the notion of refresh with offline devices, where any tparties (no honest majority) may proactivize the system at any time and the remaining nt offline parties can non-interactively “catch up” at their leisure. However due to the inherent unfairness of dishonest majority MPC, many subtle issues arise in realizing this pattern. We discuss these challenges, yet give a highly efficient protocol to upgrade a number of standard (2,n) threshold signature schemes to proactive security with offline refresh. Our approach involves a threshold signature internal to the system itself, carefully interleaved with the larger threshold signing. We design our protocols so that they can augment existing implementations of threshold wallets for immediate use– we show that proactivization does not have to interfere with their native mode of operation.

Our proactivization technique is compatible with Schnorr, EdDSA, and even sophisticated ECDSA protocols, while requiring no extra assumptions. By implementation we show that proactivizing two different recent (2,n) ECDSA protocols incurs only 14% and 24% computational overhead respectively, less than 200 bytes, and no extra round of communication.

Category / Keywords: cryptographic protocols / threshold cryptography; key management; digital signatures; oblivious transfer

Reparo: Publicly Verifiable Layer to Repair Blockchains

Conference paper
Sri Aravinda Krishnan Thyagarajan, Adithya Bhat, Bernardo Magri, Daniel Tschudi and Aniket Kate
Proceedings of the 25th Financial Cryptography and Data Security Conference, 2021 (to appear)
Publication year: 2020

Although blockchains aim for immutability as their core feature, several instances have exposed the harms with perfect immutability. The permanence of illicit content inserted in Bitcoin poses a challenge to law enforcement agencies like Interpol, and millions of dollars are lost in buggy smart contracts in Ethereum. A line of research then spawned on Redactable blockchains with the aim of solving the problem of redacting illicit contents from both permissioned and permissionless blockchains. However, all the existing proposals follow the build-new-chain approach for redactions, and cannot be integrated with existing systems like Bitcoin and Ethereum.
We present Reparo, a generic protocol that acts as a publicly verifiable layer on top of any blockchain to perform repairs, ranging from fixing buggy contracts to removing illicit contents from the chain. Reparo facilitates additional functionalities for blockchains while maintaining the same provable security guarantee; thus, Reparo can be integrated with existing blockchains and start performing repairs on the pre-existent data. Any system user may propose a repair and a deliberation process ensues resulting in a decision that complies with the repair policy of the chain and is publicly verifiable.
Our Reparo layer can be easily tailored to different consensus requirements, does not require heavy cryptographic machinery and can, therefore, be efficiently instantiated in any permission-ed or -less setting. We demonstrate it by giving efficient instantiations of Reparo on top of Ethereum (with PoS and PoW), Bitcoin, and Cardano. Moreover, we evaluate Reparo with Ethereum mainnet and show that the cost of fixing several prominent smart contract bugs is almost negligible. For instance, the cost of repairing the prominent Parity Multisig wallet bug with Reparo is as low as 0.000000018% of the Ethers that can be retrieved after the fix.

Minting Mechanisms for Proof-of-Stake Blockchains

Conference paper
Dominic Deuber, Nico Döttling, Bernardo Magri, Giulio Malavolta and Sri Aravinda Krishnan Thyagarajan
ACNS '20 (to appear)
Publication year: 2020

Abstract: Permissionless blockchain systems, such as Bitcoin, rely on users using their computational power to solve a puzzle in order to achieve a consensus. To incentivise users in maintaining the system, newly minted coins are assigned to the user who solves this puzzle. A hardware race that has hence ensued among the users, has had a detrimental impact on the environment, with enormous energy consumption and increased global carbon footprint. On the other hand, proof of stake systems incentivise coin hoarding as players maximise their utility by holding their stakes. As a result, existing cryptocurrencies do not mimic the day-to-day usability of a fiat currency, but are rather regarded as cryptoassets or investment vectors.

In this work we initiate the study of minting mechanisms in cryptocurrencies as a primitive on its own right, and as a solution to prevent coin hoarding we propose a novel minting mechanism based on waiting-time first-price auctions. Our main technical tool is a protocol to run an auction over any blockchain. Moreover, our protocol is the first to securely implement an auction without requiring a semi-trusted party, i.e., where every miner in the network is a potential bidder. Our approach is generically applicable and we show that it is incentive-compatible with the underlying blockchain, i.e., the best strategy for a player is to behave honestly. Our proof-of-concept implementation shows that our system is efficient and scales to tens of thousands of bidders.

Category / Keywords: cryptographic protocols / Blockchain, Cryptocurrencies, Auction

Cryptographic Reverse Firewalls for Interactive Proof Systems

Conference paper
Chaya Ganesh, Bernardo Magri and Daniele Venturi
The 47th International Colloquium on Automata, Languages and Programming. (ICALP 2020)
Publication year: 2020

We study interactive proof systems (IPSes) in a strong adversarial setting where the machines of honest parties might be corrupted and under control of the adversary. Our aim is to answer the following, seemingly paradoxical, questions:

  •  Can Peggy convince Vic of the veracity of an NP statement, without leaking any information about the witness even in case Vic is malicious and Peggy does not trust her computer?
  • Can we avoid that Peggy fools Vic into accepting false statements, even if Peggy is malicious and Vic does not trust her computer?

At EUROCRYPT 2015, Mironov and Stephens-Davidowitz introduced cryptographic reverse firewalls (RFs) as an attractive approach to tackling such questions.
Intuitively, a RF for Peggy/Vic is an external party that sits between Peggy/Vic and the outside world and whose scope is to sanitize Peggy’s/Vic’s incoming and outgoing messages in the face of subversion of her/his computer, e.g. in order to destroy subliminal channels.

In this paper, we put forward several natural security properties for RFs in the concrete setting of IPSes. As our main contribution, we construct efficient RFs for different IPSes derived from a large class of Sigma protocols that we call malleable. A nice feature of our design is that it is completely transparent, in the sense that our RFs can be directly applied to already deployed IPSes, without the need to re-implement them.

Afgjort: A Partially Synchronous Finality Layer for Blockchains

Conference paperRefereed Workshop
Thomas Dinsdale-Young, Bernardo Magri, Christian Matt, Jesper Buus Nielsen and Daniel Tschudi
The Twelfth Conference on Security and Cryptography for Networks (SCN 2020)
Publication year: 2020

Abstract: Most existing blockchains either rely on a Nakamoto-style of consensus, where the chain can fork and produce rollbacks, or on a committee-based Byzantine fault tolerant (CBFT) consensus, where no rollbacks are possible. While the latter ones offer better consistency, the former can be more efficient, tolerate more corruptions, and offer better availability during bad network conditions. To achieve the best of both worlds, we initiate the formal study of finality layers. Such a finality layer can be combined with a Nakamoto-style blockchain and periodically declare blocks as final, preventing rollbacks beyond final blocks.

As conceptual contributions, we identify the following properties to be crucial for a finality layer: finalized blocks form a chain (chain-forming), all parties agree on the finalized blocks (agreement), the last finalized block does not fall too far behind the last block in the underlying blockchain (updated), and all finalized blocks at some point have been on the chain adopted by at least k honest parties (k-support).

As technical contributions, we propose two variants of a finality layer protocol. The first variant satisfies all of the aforementioned requirements (with k=1) when combined with an arbitrary blockchain that satisfies the usual common-prefix, chain-growth, and chain-quality properties. The second one needs an additional, mild assumption on the underlying blockchain, but is more efficient and satisfies k=n/3-support. We prove both of them secure in the setting with t<n/3 Byzantine parties and a partially synchronous network. We finally show that t<n/3 is optimal for partially synchronous finality layers.

Category / Keywords: cryptographic protocols / blockchain, finality, Byzantine agreement

Paper presented at the PENCIL workshop co-located with EuroCrypt 2019

Redactable Blockchain in the Permissionless Setting

Conference paperInvited Talk
Dominic Deuber, Bernardo Magri and Sri Aravinda Krishnan Thyagarajan
40th IEEE Symposium on Security and Privacy (IEEE S&P 2019)
Publication year: 2019

Bitcoin is an immutable permissionless blockchain system that has been extensively used as a public bulletin board by many different applications that heavily relies on its immutability. However, Bitcoin’s immutability is not without its fair share of demerits. Interpol exposed the existence of harmful and potentially illegal documents, images and links in the Bitcoin blockchain, and since then there have been several qualitative and quantitative analysis on the types of data currently residing in the Bitcoin blockchain.
Although there is a lot of attention on blockchains, surprisingly the previous solutions proposed for data redaction in the permissionless setting are far from feasible, and require additional trust assumptions. Hence, the problem of harmful data still poses a huge challenge for law enforcement agencies like Interpol (Tziakouris, IEEE S&P’18).

We propose the first efficient redactable blockchain for the permissionless setting that is easily integrable into Bitcoin, and that does not rely on heavy cryptographic tools or trust assumptions. Our protocol uses a consensus-based voting and is parameterised by a policy that dictates the requirements and constraints for the redactions; if a redaction gathers enough votes the operation is performed on the chain. As an extra feature, our protocol offers public verifiability and accountability for the redacted chain. Moreover, we provide formal security definitions and proofs showing that our protocol is secure against redactions that were not agreed by consensus. Additionally, we show the viability of our approach with a proof-of-concept implementation that shows only a tiny overhead in the chain validation of our protocol when compared to an immutable one.

Public Immunization against Complete Subversion without Random Oracles

Conference paper
Giuseppe Ateniese, Danilo Francati, Bernardo Magri amd Daniele Venturi
ACNS '19
Publication year: 2019

We seek constructions of general-purpose immunizers that take arbitrary cryptographic primitives, and transform them into ones that withstand a powerful “malicious but proud” adversary, who attempts to break security by possibly subverting the implementation of all algorithms (including the immunizer itself!), while trying not to be detected. This question is motivated by the recent evidence of cryptographic schemes being intentionally weakened, or designed together with hidden backdoors, e.g. with the scope of mass surveillance.

Our main result is a subversion-secure immunizer in the plain model (assuming collision-resistant hashing), that works for a fairly large class of deterministic primitives, i.e. cryptoschemes where a secret (but  tamperable) random source is used to generate the keys and the public parameters, whereas all other algorithms are deterministic. The immunizer relies on an additional independent source of public randomness, which is used to sample a public seed. While the public source is untamperable, the subversion of all other algorithms is allowed to depend on it.

Previous work in the area only obtained subversion-secure immunization for very restricted classes of primitives, often in weaker models of subversion and relying on random oracles, or by leveraging a higher number of independent random sources.

Secure Outsourcing of Cryptographic Circuits Manufacturing

Conference paper
Giuseppe Ateniese, Aggelos Kiayias, Bernardo Magri, Yiannis Tselekounis and Daniele Venturi
The 12th International Conference on Provable Security (ProvSec 2018)
Publication year: 2018

The fabrication process of integrated circuits (ICs) is complex and requires the use of off-shore foundries to lower the costs and to have access to leading-edge manufacturing facilities. Such an outsourcing trend leaves the possibility of inserting malicious circuitry (a.k.a. hardware Trojans) during the fabrication process, causing serious security issues. Hardware Trojans are very hard and expensive to detect and can disrupt the entire circuit or covertly leak sensitive information. In this paper, we propose a formal model for assessing the security of ICs whose fabrication has been outsourced to an untrusted off-shore manufacturer. We assume that the IC specification and design are trusted but the fabrication facility(ies) may be untrusted. Our objective is to stop Trojans from releasing sensitive information to the outside while still using its circuitry for day-to-day operations. We also provide two different methodologies for constructing compilers relying on verifiable computation (VC) schemes and secure multiparty computation (MPC) protocols with certain properties. Suitable VC schemes, with the properties we require, were recently constructed, e.g., by Parno et al. (Oakland ’13), and by Fiore, Gennaro, and Pastro (CCS ’14). Similarly, many MPC protocols readily comply (or can be easily adapted to comply) with our requirements. By allowing manufacturers to use off-shore fabrication facilities, we ensure a high degree of competition among suppliers, thus providing lower cost without hindering innovation or access to leading-edge microelectronics.

A Family of FDH Signature Schemes Based on the Quadratic Residuosity Assumption

Conference paper
Giuseppe Ateniese, Katharina Fech, Bernardo Magri
19th International Conference on Cryptology in India (IndoCrypt 2018)
Publication year: 2018

Signature schemes are arguably the most crucial cryptographic primitive, and devising tight security proofs for signature schemes is an important endeavour, as it immediately impacts the feasibility of deployment in real world applications. Hash-then-sign signature schemes in the Random Oracle Model, such as RSA-FDH, and Rabin-Williams variants are among the fastest schemes to date, but that unfortunately do not enjoy tight security proofs based on the one-wayness of their trapdoor function; instead, all known tight proofs rely on variants of the (non-standard) Φ-Hiding assumption.
As our main contribution, we introduce a family of hash-then-sign signature schemes, inspired by a lossy trapdoor function from Freeman et al. (JoC’ 13), that is tightly secure under the Quadratic Residuosity assumption. Our first scheme has the property of having unique signatures, while the second scheme is deterministic with an extremely fast signature verification, requiring at most 3 modular multiplications.

Redactable Blockchain - or - Rewriting History in Bitcoin and Friends

Conference paper
Giuseppe Ateniese, Bernardo Magri, Daniele Venturi and Ewerton R. Andrade
IEEE Euro Security & Privacy conference, 2017
Publication year: 2017

We put forward a new framework that makes it possible to re-write and/or compress the content of any number of blocks in decentralized services exploiting the blockchain technology. As we argue, there are several reasons to prefer an editable blockchain, spanning from the necessity to remove improper content and the possibility to support applications requiring re-writable storage, to “the right to be forgotten”.

Our approach generically leverages so-called chameleon hash functions (Krawczyk and Rabin, NDSS ’00), which allow to efficiently determine hash collisions given a secret trapdoor information. We detail how to integrate a chameleon hash function in virtually any blockchain-based technology, for both cases where the power of redacting the blockchain content is in the hands of a single trusted entity and where such a capability is distributed among several distrustful parties (as is the case in Bitcoin).

We also report on a proof-of-concept implementation of a redactable blockchain, building on top of Nakamoto’s Bitcoin core. The implementation only requires minimal changes to the way current client software interprets information stored in the blockchain and to the current blockchain, block, or transaction structures. Moreover, our experiments show that the overhead imposed by a redactable blockchain is small compared to the case of an immutable one.

Subversion-Resilient Signature Schemes

Conference paper
Giuseppe Ateniese, Bernardo Magri and Daniele Venturi
CCS '15, Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Pages 364-375
Publication year: 2015

We provide a formal treatment of security of digital signatures against subversion attacks (SAs). Our model of subversion generalizes previous work in several directions, and is inspired by the proliferation of software attacks (e.g., malware and buffer overflow attacks), and by the recent revelations of Edward Snowden about intelligence agencies trying to surreptitiously sabotage cryptographic algorithms. The main security requirement we put forward demands that a signature scheme should remain unforgeable even in the presence of an attacker applying SAs (within a certain class of allowed attacks) in a fully-adaptive and continuous fashion. Previous notions—e.g., security against algorithm-substitution attacks introduced by Bellare et al. (CRYPTO ’14) for symmetric encryption—were non-adaptive and non-continuous.

In this vein, we show both positive and negative results for constructing subversion-resilient signature schemes. — Negative results. As our main negative result, we show that a broad class of randomized schemes is unavoidably insecure against SAs, even if using just a single bit of randomness. This improves upon earlier work that was only able to attack schemes with larger randomness space. When designing our attack we consider undetectability to be an explicit adversarial goal, meaning that the end-users (even the ones knowing the signing key) should not be able to detect that the signature scheme was subverted. — Positive results. We complement the above negative results by showing that signature schemes with unique signatures are subversion-resilient against all attacks that meet a basic undetectability requirement. A similar result was shown by Bellare et al. for symmetric encryption, who proved the necessity to rely on stateful schemes; in contrast unique signatures are stateless, and in fact they are among the fastest and most established digital signatures available.

We finally show that it is possible to devise signature schemes secure against arbitrary tampering with the computation, by making use of an un-tamperable cryptographic reverse firewall (Mironov and Stephens-Davidowitz, EUROCRYPT ’15), i.e., an algorithm that “sanitizes” any signature given as input (using only public information). The firewall we design allows to successfully protect so-called re-randomizable signature schemes (which include unique signatures).

While our study is mainly theoretical, due to its strong practical motivation, we believe that our results have important implications in practice and might influence the way digital signature schemes are selected or adopted in standards and protocols.

Certified Bitcoins

Conference paper
Giuseppe Ateniese, Antonio Faonio, Bernardo Magri and Breno de Medeiros
ACNS '14, Applied Cryptography and Network Security, Volume 8479 of the series Lecture Notes in Computer Science, Pages 80-96
Publication year: 2014

Bitcoin is a peer-to-peer (p2p) electronic cash system that uses a distributed timestamp service to record transactions in a public ledger (called the Blockchain). A critical component of Bitcoin’s success is the decentralized nature of its architecture, which does not require or even support the establishment of trusted authorities. Yet the absence of certification creates obstacles to its wider acceptance in e-commerce and official uses. We propose a certification system for Bitcoin that offers: a) an opt-in guarantee to send and receive bitcoins only to/ from certified users; b) control of creation of bitcoins addresses (certified users) by trusted authorities. Our proposal may encourage the adoption of Bitcoin in different scenarios that require an officially recognized currency, such as tax payments—often an integral part of e-commerce transactions.