Protocol Labs Research is now PL R&D — visit plrd.org →
Protocol Labs Research
About
People
Research
Groups Areas Talks Publications Tutorials
Outreach
Blog
Cryptography

Modern cryptography plays an integral role in every aspect of online and electronic security, including providing evidence you’re speaking to the intended party and hindering spying on the subsequent communication. Cutting-edge cryptography tools will allow the creation of incredibly strong evidence that general information processing has been performed in a privacy-preserving and trustless way.

Publications

View all PL Research publications
2023-08-30 / Report
Filecoin Proof of Useful Space
This document provides a simple formal definition of Proof of Space (taken from the academic literature) and an informal definition of persistent and useful space (needed for Filecoin). It describes construction details and a security proof for the Stacked-DRGs proof of space (SDR), and goes into how SDR is used in Filecoin.
Irene Giacomelli , Luca Nizzardo
Cryptonet
Cryptography
2023-03-21 / Report
SpaceVDF: Verifiable delay functions using cryptographic satellites
In this document we aim to evaluate how VDF algorithms based on physical limits can be implemented in satellites and which physical properties / or roles of physics we can utilize to guarantee the passage of time.
Yonatan Winetraub, Elad Sagi, Yan Michalevsky, Chhi'mèd Künzang , Jonathan Gross
Cryptography
2023-03-16 / Report
LURK: Lambda, the ultimate recursive knowledge
We introduce Lurk, a new LISP-based programming language for zk-SNARKs. Traditional approaches to programming over zero-knowledge proofs require compiling the desired computation into a flat circuit, imposing serious constraints on the size and complexity of computations that can be achieved in practice.
Nada Amin, John Burnham, François Garillot, Rosario Gennaro , Chhi'mèd Künzang , Daniel Rogozin, Cameron Wong
Cryptography
2023-02-13 / Report
tlock: Practical timelock encryption from threshold BLS
We present a practical construction and implementation of timelock encryption, in which a ciphertext is guaranteed to be decryptable only after some specified time has passed. We employ an existing threshold network, the League of Entropy, implementing threshold BLS [BLS01, B03] in the context of Boneh and Franklin’s identity-based encryption (IBE).
Nicolas Gailly , Kelsey Melissaris, Yolan Romailler
Cryptonet
Cryptography
2022-11-01 / Report
Structure-preserving compilers from new notions of obfuscations
The dream of software obfuscation is to take programs, as they are, and then compile them into obfuscated versions that hide their secret inner workings. In this work we investigate notions of obfuscations weaker than virtual black-box (VBB) but which still allow obfuscating cryptographic primitives preserving their original functionalities as much as possible.
Matteo Campanelli , Danilo Francati, Claudio Orlandi
Cryptonet
Cryptography
2022-09-09 / Report
Impossibilities in succinct arguments: Black-box extraction and more
The celebrated result by Gentry and Wichs established a theoretical barrier for succinct non-interactive arguments (SNARGs), showing that for (expressive enough) hard-on-average languages we must assume non-falsifiable assumptions. We further investigate those barriers by showing new negative and positive results related to extractability and to the preprocessing model.
Matteo Campanelli , Chaya Ganesh, Hamidreza Khoshakhlagh, Janno Siim
Cryptonet
Cryptography
2022-09-08 / Report
Curve trees: Practical and transparent zero-knowledge accumulators
In this work we propose a new accumulator construction and efficient ways to prove knowledge of some element in a set without leaking anything about the element. This problem arises in several applications including privacy-preserving distributed ledgers (e.
Matteo Campanelli , Mathias Hall-Andersen
Cryptonet
Cryptography
2022-08-30 / Conference paper
Encryption to the future: A paradigm for sending secret messages to future (anonymous) committees
A number of recent works have constructed cryptographic protocols with flavors of adaptive security by having a randomly-chosen anonymous committee run at each round. Since most of these protocols are stateful, transferring secret states from past committees to future, but still unknown, committees is a crucial challenge.
Asiacrypt 2022 / 2022.12.05 / Taipei, Taiwan
Matteo Campanelli , Bernardo David, Hamidreza Khoshakhlagh, Anders Konring, Jesper Buus Nielsen
Cryptonet
Cryptography
2022-07-06 / Report
Caulk: Lookup arguments in sublinear time
We present position-hiding linkability for vector commitment schemes: one can prove in zero knowledge that one or m values that comprise commitment cm all belong to the vector of size N committed to in C.
Arantxa Zapico, Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Anca Nitulescu , Mark Simkin
Cryptonet
Cryptography
2022-07-06 / Report
Linear-map vector commitments and their practical applications
Vector commitments (VC) are a cryptographic primitive that allow one to commit to a vector and then “open” some of its positions efficiently. Vector commitments are increasingly recognized as a central tool to scale highly decentralized networks of large size and whose content is dynamic.
Matteo Campanelli , Anca Nitulescu , Carla Ràfols, Alexandros Zacharakis, Arantxa Zapico
Cryptonet
Cryptography
2022-07-06 / Conference paper
What makes Fiat–Shamir zkSNARKs (updatable SRS) simulation extractable?
We show that three popular universal zero-knowledge SNARKs (Plonk, Sonic, and Marlin) are updatable SRS simulation extractable NIZKs and signatures of knowledge (SoK) out-of-the-box avoiding any compilation overhead. Towards this we generalize results for the Fiat–Shamir (FS) transformation, which turns interactive protocols into signature schemes, non-interactive proof systems, or SoK in the random oracle model (ROM).
SCN 2022 / 2022.09.12 / Amalfi, Italy
Chaya Ganeshe, Hamidreza Khoshakhlagh, Markulf Kohlweiss, Anca Nitulescu , Michal Zajac
Cryptonet
Cryptography
2022-06-02 / Report
On the impossibility of algebraic vector commitments in pairing-free groups
Vector Commitments allow one to (concisely) commit to a vector of messages so that one can later (concisely) open the commitment at selected locations. In the state of the art of vector commitments, algebraic constructions have emerged as a particularly useful class, as they enable advanced properties, such as stateless updates, subvector openings and aggregation, that are for example unknown in Merkle-tree-based schemes.
Dario Catalano , Dario Fiore, Rosario Gennaro , Emmanuele Giunta
Cryptonet
Cryptography
2022-04-08 / Report
Witness-authenticated key exchange revisited: Improved models, simpler constructions, extensions to groups
We revisit the notion of Witness Authenticated Key Exchange (WAKE) where a party can be authenticated through a generic witness to an NP statement. We point out shortcomings of previous definitions, protocols and security proofs in Ngo et al.
Matteo Campanelli , Rosario Gennaro , Kelsey Melissaris, Luca Nizzardo
Cryptonet
Cryptography , Distributed systems
2021-09-27 / Conference paper
MyOPE: Malicious security for oblivious polynomial evaluation
Oblivious Polynomial Evaluation (OPE) schemes are interactive protocols between a sender with a private polynomial and a receiver with a private evaluation point where the receiver learns the evaluation of the polynomial in their point and no additional information.
SCN 2022 / 2022.09.12 / Amalfi, Italy
Malika Izabachène, Anca Nitulescu , Paola de Perthuis, David Pointcheval
Cryptonet
Cryptography
2021-09-21 / Conference paper
Count me in! Extendability for threshold ring signatures
Ring signatures enable a signer to sign a message on behalf of a group anonymously, without revealing her identity. Similarly, threshold ring signatures allow several signers to sign the same message on behalf of a group; while the combined signature reveals that some threshold t of the group members signed the message, it does not leak anything else about the signers’ identities.
PKC 2022 / 2022.03.08 / Virtual
Diego Aranha, Mathias Hall-Anderson, Anca Nitulescu , Elena Pagnin, Sophia Yakoubov
Cryptonet
Cryptography
2021-05-13 / Conference paper
SnarkPack: Practical SNARK aggregation
Zero-knowledge SNARKs (zk-SNARKs) are non-interactive proof systems with short and efficiently verifiable proofs. zk-SNARKs are widely used in decentralised systems to address privacy and scalability concerns. One of the main applications is the blockchain, were SNARKs are used to prove computations with private inputs and reduce on-chain footprint verification and transaction sizes.
Financial Cryptography and Data Security 2022 / 2022.05.02 / St George's, Grenada
Nicolas Gailly , Mary Maller, Anca Nitulescu
Cryptonet
Cryptography
2021-03-18 / Report
Rinocchio: SNARKs for ring arithmetic
Succinct non-interactive arguments of knowledge (SNARKs) enable non-interactive efficient verification of NP computations and admit short proofs. However, all current SNARK constructions assume that the statements to be proven can be efficiently represented as either Boolean or arithmetic circuits over finite fields.
Chaya Ganesh, Anca Nitulescu , Eduardo Soria-Vazquez
Cryptonet
Cryptography
2020-12-05 / Report
Incrementally aggregatable vector commitment techniques and applications to verifiable decentralized storage
Vector commitments with subvector openings (SVC) [Lai-Malavolta, Boneh-Bunz-Fisch; CRYPTO’19] allow one to open a committed vector at a set of positions with an opening of size independent of both the vector’s length and the number of opened positions.
Advances in Cryptology – ASIACRYPT 2020 / 2020.12.05
Matteo Campanelli , Dario Fiore, Nicola Greco , Dimitris Kolonelos, Luca Nizzardo
Cryptonet
Cryptography , Distributed systems
2020-11-17 / Conference paper
Subversion-resilient enhanced privacy ID
Anonymous attestation for secure hardware platforms leverages tailored group signature schemes and assumes the hardware to be trusted. Yet, there is an increasing concern on the trustworthiness of hardware components and embedded systems.
Cryptographers’ Track at the RSA Conference / 2022.02.07 / San Francisco, CA, USA
Antonio Faonio, Dario Fiore, Luca Nizzardo , Claudio Soriente
Cryptonet
Cryptography
2020-10-21 / Conference paper
Winkle: foiling long-range attacks in proof-of-stake systems
Winkle protects any validator-based byzantine fault tolerant consensus mechanisms, such as those used in modern Proof-of-Stake blockchains, against long-range attacks where old validators’ signature keys get compromised. Winkle is a decentralized secondary layer of client-based validation, where a client includes a single additional field into a transaction that they sign: a hash of the previously sequenced block.
AFT '20: 2nd ACM Conference on Advances in Financial Technologies / 2020.10.21 / New York, NY, USA
Sarah Azouvi , George Danezis, Valeria Nikolaenko
ConsensusLab
Cryptography
2020-04-08 / Conference paper
MonZa: Fast maliciously secure two party computation on Z_{2^k}
In this paper we present a new 2-party protocol for secure computation over rings of the form Z2k. As many recent efficient MPC protocols supporting dishonest majority, our protocol consists of a heavier (input-independent) pre-processing phase and a very efficient online stage.
IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC) / 2020.05.04 / Edinburgh, Scotland
Dario Catalano , Mario Di Raimondo, Dario Fiore, Irene Giacomelli
Cryptonet
Cryptography
2020-03-03 / Conference paper
SoK: Tools for game theoretic models of security for cryptocurrencies
Cryptocurrencies have garnered much attention in recent years, both from the academic community and industry. One interesting aspect of cryptocurrencies is their explicit consideration of incentives at the protocol level, which has motivated a large body of work, yet many open problems still exist and current systems rarely deal with incentive related problems well.
Cryptoeconomic Systems / 2020.03.07 / Cambridge, MA, USA
Sarah Azouvi , Alexander Hicks
ConsensusLab
Cryptography
2020-01-15 / Conference paper
Single secret leader election
In a Single Secret Leader Election (SSLE), a group of participants aim to randomly choose exactly one leader from the group with the restriction that the identity of the leader will be known to the chosen leader and nobody else.
ACM Advances in Financial Technologies 2020 / 2020.10.21
Dan Boneh, Saba Eskandarian, Lucjan Hanzlik, Nicola Greco
Cryptonet
Cryptography
2019-10-02 / Conference paper
Efficient UC commitment extension with homomorphism for free (and applications)
Homomorphic universally composable (UC) commitments allow for the sender to reveal the result of additions and multiplications of values contained in commitments without revealing the values themselves while assuring the receiver of the correctness of such computation on committed values.
Advances in Cryptology – ASIACRYPT 2019 / 2019.10.02
Ignacio Cascudo, Ivan Damgård, Bernardo David, Nico Döttling, Rafael Dowsley, Irene Giacomelli
Cryptonet
Cryptography
2019-08-24 / Conference paper
PLONK: Permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge
zk-SNARK constructions that utilize an updatable universal structured reference string remove one of the main obstacles in deploying zk-SNARKs[GKM + ]. The important work of Maller et al. [MBKM19] presented Sonic-the first potentially practical zk-SNARK with fully succinct verification for general arithmetic circuits with such an SRS.
Stanford Blockchain Conference / 2020.02.19 / Stanford, CA, USA
Ariel Gabizon , Zachary J Williamson, Oana Ciobotaru
Cryptonet , CryptoComputeLab
Cryptography
2019-05-29 / Report
AuroraLight: Improved prover efficiency and SRS size in a Sonic-like system
Using ideas from the recent Aurora zk-STARK of Ben-Sasson et al. [BCR + 19], we present a zk-SNARK with a universal and updatable SRS similar to the recent construction of Maller et al.
Ariel Gabizon
Cryptonet , CryptoComputeLab
Cryptography
2018-10-15 / Report
Scaling proof-of-replication for Filecoin mining
A proof-of-replication (PoRep) is a proof system that a server can use to demonstrate to a network in a publicly verifiable way that it is dedicating unique resources to storing one or more replicas of a data file.
Ben Fisch , Joseph Bonneau , Nicola Greco , Juan Benet
Cryptonet
Cryptography , Distributed systems
2018-07-14 / Report
PoReps: Proofs of space on useful data
A proof-of-replication (PoRep) is an interactive proof system in which a prover defends a publicly verifiable claim that it is dedicating unique resources to storing one or more retrievable replicas of a data file.
Ben Fisch
Cryptonet , CryptoComputeLab
Cryptography , Distributed systems
2017-07-27 / Report
Power fault tolerance
Byzantine Fault Tolerance (BFT) accounts for faults as the number of faulty nodes and is thus cumbersome to apply to many modern decentralized systems. We introduce the Power Fault Tolerance (PFT) model, which reframes BFT in terms of participants’ influence over the outcome of a protocol, instead of the number of nodes.
Protocol Labs
Cryptonet , CryptoComputeLab
Cryptography , Distributed systems
2017-07-27 / Report
Proof of replication
We introduce Proof-of-Replication (PoRep), a new kind of Proof-of-Storage, that can be used to prove that some data D has been replicated to its own uniquely dedicated physical storage. Enforcing unique physical copies enables a verifier to check that a prover is not deduplicating multiple copies of D into the same storage space.
Juan Benet , David Dalrymple , Nicola Greco
Cryptonet
Cryptography , Distributed systems
2017-07-19 / Report
Filecoin: A decentralized storage network
The internet is in the middle of a revolution: centralized proprietary services are being replaced with decentralized open ones; trusted parties replaced with verifiable computation; brittle location addresses replaced with resilient content addresses; inefficient monolithic services replaced with peer-to-peer algo-rithmic markets.
Protocol Labs
Cryptonet , CryptoComputeLab
Cryptography , Distributed systems
2014-07-15 / Report
Filecoin: A cryptocurrency operated file storage network
Filecoin is a distributed electronic currency similar to Bitcoin. Unlike Bitcoin’s computation-only proof-of-work, Filecoin’s proof-of-work function includes a proof-of-retrievability component, which requires nodes to prove they store a particular file. The Filecoin network forms an entirely distributed file storage system, whose nodes are incentivized to store as much of the entire network’s data as they can.
Protocol Labs
Cryptonet , CryptoComputeLab