Jonathan Bootle

Jonathan Bootle

Auto-generated profile, based on publicly available information

Jonathan Bootle

IBM Research Europe

Research Focus & Metrics

Academic Career Length

12Years (2015-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 May 2018
Verified
Conference Paper
Closed access
BBBenedikt Bunz
Benedikt Bunz
JBJonathan Bootle
Jonathan Bootle
DBDan Boneh
Dan Boneh
APAndrew Poelstra
Andrew Poelstra
PWPieter Wuille
Pieter Wuille
GMGreg Maxwell
Greg Maxwell
We propose Bulletproofs, a new non-interactive zero-knowledge proof protocol with very short proofs and without a trusted setup; the proof size is only logarithmic in the witness size. Bulletproofs are especially well suited for efficient range proofs on committed values: they enable proving that a committed value is in a range using only 2 log_2(n)+9 group and field elements, where n is the bit length of the range. Proof generation and verification times are linear in n. Bulletproofs greatly improve on the linear (in n) sized range proofs in existing proposals for confidential transactions in Bitcoin and other cryptocurrencies. Moreover, Bulletproofs supports aggregation of range proofs, so that a party can prove that m commitments lie in a given range by providing only an additive O(log(m)) group elements over the length of a single proof. To aggregate proofs from multiple parties, we enable the parties to generate a single proof without revealing their inputs to each other via a simple multi-party computation (MPC) protocol for constructing Bulletproofs. This MPC protocol uses either a constant number of rounds and linear communication, or a logarithmic number of rounds and logarithmic communication. We show that verification time, while asymptotically linear, is very efficient in practice. The marginal cost of batch verifying 32 aggregated range proofs is less than the cost of verifying 32 ECDSA signatures. Bulletproofs build on the techniques of Bootle et al. (EUROCRYPT 2016). Beyond range proofs, Bulletproofs provide short zero-knowledge proofs for general arithmetic circuits while only relying on the discrete logarithm assumption and without requiring a trusted setup. We discuss many applications that would benefit from Bulletproofs, primarily in the area of cryptocurrencies. The efficiency of Bulletproofs is particularly well suited for the distributed and trustless nature of blockchains. The full version of this article is available on ePrint.

28 April 2016
Verified
Book Chapter
Closed access
PDF file
JBJonathan Bootle
Jonathan Bootle
ACAndrea Cerulli
Andrea Cerulli
PCPyrros Chaidos
Pyrros Chaidos
JGJens Groth
Jens Groth
CPChristophe Petit
Christophe Petit

1 January 2015
Verified
Book Chapter
Open access
PDF file
JBJonathan Bootle
Jonathan Bootle
ACAndrea Cerulli
Andrea Cerulli
PCPyrros Chaidos
Pyrros Chaidos
EGEssam Ghadafi
Essam Ghadafi
JGJens Groth
Jens Groth
CPChristophe Petit
Christophe Petit
Ring signatures and group signatures are prominent cryptographic primitives offering a combination of privacy and authentication. They enable individual users to anonymously sign messages on behalf of a group of users. In ring signatures, the group, i.e. the ring, is chosen in an ad hoc manner by the signer. In group signatures, group membership is controlled by a group manager. Group signatures additionally enforce accountability by providing the group manager with a secret tracing key that can be used to identify the otherwise anonymous signer when needed. Accountable ring signatures, introduced by Xu and Yung (CARDIS 2004), bridge the gap between the two notions. They provide maximal flexibility in choosing the ring, and at the same time maintain accountability by supporting a designated opener that can identify signers when needed. We revisit accountable ring signatures and offer a formal security model for the primitive. Our model offers strong security definitions incorporating protection against maliciously chosen keys and at the same time flexibility both in the choice of the ring and the opener. We give a generic construction using standard tools. We give a highly efficient instantiation of our generic construction in the random oracle model by meticulously combining Camenisch’s group signature scheme (CRYPTO 1997) with a generalization of the one-out-of-many proofs of knowledge by Groth and Kohlweiss (EUROCRYPT 2015). Our instantiation yields signatures of logarithmic size (in the size of the ring) while relying solely on the well-studied decisional Diffie-Hellman assumption. In the process, we offer a number of optimizations for the recent Groth and Kohlweiss one-out-of-many proofs, which may be useful for other applications. Accountable ring signatures imply traditional ring and group signatures. We therefore also obtain highly efficient instantiations of those primitives with signatures shorter than all existing ring signatures as well as existing group signatures relying on standard assumptions.

9 June 2016
Verified
Book Chapter
Open access
PDF file
JBJonathan Bootle
Jonathan Bootle
ACAndrea Cerulli
Andrea Cerulli
PCPyrros Chaidos
Pyrros Chaidos
EGEssam Ghadafi
Essam Ghadafi
JGJens Groth
Jens Groth
Group signatures are a central cryptographic primitive that has received a considerable amount of attention from the cryptographic community. They allow members of a group to anonymously sign on behalf of the group. Membership is overseen by a designated group manager. There is also a tracing authority that can revoke anonymity by revealing the identity of the signer if and when needed, to enforce accountability and deter abuse. For the primitive to be applicable in practice, it needs to support fully dynamic groups, i.e. users can join and leave at any time. In this work we take a close look at existing security definitions for fully dynamic group signatures. We identify a number of shortcomings in existing security definitions and fill the gap by providing a formal rigorous security model for the primitive. Our model is general and is not tailored towards a specific design paradigm and can therefore, as we show, be used to argue about the security of different existing constructions following different design paradigms. Our definitions are stringent and when possible incorporate protection against maliciously chosen keys. In the process, we identify a subtle issue inherent to one design paradigm, where new members might try to implicate older ones by means of back-dated signatures. This is not captured by existing models. We propose some inexpensive fixes for some existing constructions to avoid the issue.

1 August 2019
Verified
Book Chapter
Open access
JBJonathan Bootle
Jonathan Bootle
VLVadim Lyubashevsky
Vadim Lyubashevsky
GSGregor Seiler
Gregor Seiler

24 July 2018
Verified
Book Chapter
Closed access
PDF file
CBCarsten Baum
Carsten Baum
JBJonathan Bootle
Jonathan Bootle
ACAndrea Cerulli
Andrea Cerulli
RPRafael del Pino
Rafael del Pino
JGJens Groth
Jens Groth
VLVadim Lyubashevsky
Vadim Lyubashevsky