Search Results

Documents authored by Boneh, Dan

Document
DOI: 10.4230/LIPIcs.AFT.2023.18
Revisiting the Nova Proof System on a Cycle of Curves

Authors: Wilson D. Nguyen, Dan Boneh, and Srinath Setty

Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)

Abstract
Nova is an efficient recursive proof system built from an elegant folding scheme for (relaxed) R1CS statements. The original Nova paper (CRYPTO'22) presented Nova using a single elliptic curve group of order p. However, for improved efficiency, the implementation of Nova alters the scheme to use a 2-cycle of elliptic curves. This altered scheme is only described in the code and has not been proven secure. In this work, we point out a soundness vulnerability in the original implementation of the 2-cycle Nova system. To demonstrate this vulnerability, we construct a convincing Nova proof for the correct evaluation of 2^{75} rounds of the Minroot VDF in only 116 milliseconds. We then present a modification of the 2-cycle Nova system and formally prove its security. The modified system also happens to be more efficient than the original implementation. In particular, the modification eliminates an R1CS instance-witness pair from the recursive proof. The implementation of Nova has now been updated to use our optimized and secure system. In addition, we show that the folding mechanism at the core of Nova is malleable: given a proof for some statement z, an adversary can construct a proof for a related statement z', at the same depth as z, without knowledge of the witness for z'.
Cite as

Wilson D. Nguyen, Dan Boneh, and Srinath Setty. Revisiting the Nova Proof System on a Cycle of Curves. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 18:1-18:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{nguyen_et_al:LIPIcs.AFT.2023.18,
  author =	{Nguyen, Wilson D. and Boneh, Dan and Setty, Srinath},
  title =	{{Revisiting the Nova Proof System on a Cycle of Curves}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{18:1--18:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.18},
  URN =		{urn:nbn:de:0030-drops-192076},
  doi =		{10.4230/LIPIcs.AFT.2023.18},
  annote =	{Keywords: Cryptographic Protocols, Recursive Proof Systems, Folding, Vulnerability}
}
Document
DOI: 10.4230/LIPIcs.AFT.2023.26
Post-Quantum Single Secret Leader Election (SSLE) from Publicly Re-Randomizable Commitments

Authors: Dan Boneh, Aditi Partap, and Lior Rotem

Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)

Abstract
A Single Secret Leader Election (SSLE) enables a group of parties 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. At a later time, the elected leader should be able to publicly reveal her identity and prove that she is the elected leader. The election process itself should work properly even if many registered users are passive and do not send any messages. SSLE is used to strengthen the security of proof-of-stake consensus protocols by ensuring that the identity of the block proposer remains unknown until the proposer publishes a block. Boneh, Eskandarian, Hanzlik, and Greco (AFT'20) defined the concept of an SSLE and gave several constructions. Their most efficient construction is based on the difficulty of the Decision Diffie-Hellman problem in a cyclic group. In this work we construct the first efficient SSLE protocols based on the standard Learning With Errors (LWE) problem on integer lattices, as well as the Ring-LWE problem. Both are believed to be post-quantum secure. Our constructions generalize the paradigm of Boneh et al. by introducing the concept of a re-randomizable commitment (RRC). We then construct several post-quantum RRC schemes from lattice assumptions and prove the security of the derived SSLE protocols. Constructing a lattice-based RRC scheme is non-trivial, and may be of independent interest.
Cite as

Dan Boneh, Aditi Partap, and Lior Rotem. Post-Quantum Single Secret Leader Election (SSLE) from Publicly Re-Randomizable Commitments. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 26:1-26:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{boneh_et_al:LIPIcs.AFT.2023.26,
  author =	{Boneh, Dan and Partap, Aditi and Rotem, Lior},
  title =	{{Post-Quantum Single Secret Leader Election (SSLE) from Publicly Re-Randomizable Commitments}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{26:1--26:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.26},
  URN =		{urn:nbn:de:0030-drops-192158},
  doi =		{10.4230/LIPIcs.AFT.2023.26},
  annote =	{Keywords: Consensus, Leader Election, Post-Quantum, Lattice Cryptography, Blockchain}
}
Document
DOI: 10.4230/LIPIcs.AFT.2023.29
Vector Commitments with Efficient Updates

Authors: Ertem Nusret Tas and Dan Boneh

Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)

Abstract
Dynamic vector commitments that enable local updates of opening proofs have applications ranging from verifiable databases with membership changes to stateless clients on blockchains. In these applications, each user maintains a relevant subset of the committed messages and the corresponding opening proofs with the goal of ensuring a succinct global state. When the messages are updated, users are given some global update information and update their opening proofs to match the new vector commitment. We investigate the relation between the size of the update information and the runtime complexity needed to update an individual opening proof. Existing vector commitment schemes require that either the information size or the runtime scale linearly in the number k of updated state elements. We construct a vector commitment scheme that asymptotically achieves both length and runtime that is sublinear in k, namely k^ν and k^{1-ν} for any ν ∈ (0,1). We prove an information-theoretic lower bound on the relation between the update information size and runtime complexity that shows the asymptotic optimality of our scheme. While in practice, the construction is not yet competitive with Verkle commitments, our approach may point the way towards more performant vector commitments.
Cite as

Ertem Nusret Tas and Dan Boneh. Vector Commitments with Efficient Updates. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 29:1-29:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{tas_et_al:LIPIcs.AFT.2023.29,
  author =	{Tas, Ertem Nusret and Boneh, Dan},
  title =	{{Vector Commitments with Efficient Updates}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{29:1--29:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.29},
  URN =		{urn:nbn:de:0030-drops-192184},
  doi =		{10.4230/LIPIcs.AFT.2023.29},
  annote =	{Keywords: Vector commitments, stateless clients}
}
Document
DOI: 10.4230/DagSemProc.09141.1
09141 Abstracts Collection – Web Application Security

Authors: Dan Boneh, Ulfar Erlingsson, Martin Johns, and Benjamin Livshits

Published in: Dagstuhl Seminar Proceedings, Volume 9141, Web Application Security (2010)

Abstract
From 29th March to 3rd April 2009 the Dagstuhl Seminar 09141 Web Application Security was held in Schloss Dagstuhl – Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar are put together in this paper. Links to full papers (if available) are provided in the corresponding seminar summary document.
Cite as

Dan Boneh, Ulfar Erlingsson, Martin Johns, and Benjamin Livshits. 09141 Abstracts Collection – Web Application Security. In Web Application Security. Dagstuhl Seminar Proceedings, Volume 9141, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{boneh_et_al:DagSemProc.09141.1,
  author =	{Boneh, Dan and Erlingsson, Ulfar and Johns, Martin and Livshits, Benjamin},
  title =	{{09141 Abstracts Collection – Web Application Security}},
  booktitle =	{Web Application Security},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9141},
  editor =	{Dan Boneh and Ulfar Erlingsson and Martin Johns and Benjamin Livshits},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09141.1},
  URN =		{urn:nbn:de:0030-drops-27263},
  doi =		{10.4230/DagSemProc.09141.1},
  annote =	{Keywords: Web applications, Security, Ajax, Web 2.0, Analysis for security, Browser design, Distributed applications}
}
Document
DOI: 10.4230/DagSemProc.09141.2
09141 Executive Summary – Web Application Security

Authors: Dan Boneh, Ulfar Erlingsson, Martin Johns, and Benjamin Livshits

Published in: Dagstuhl Seminar Proceedings, Volume 9141, Web Application Security (2010)

Abstract
Web applications are ubiquitous nowadays. Consequently, the field of Web application security is of ever rising significance. This Dagstuhl seminar was conducted to assemble researchers active in the domain to gain a first comprehensive overview of this young discipline in security research. From a content perspective, the topic was explored in a great variety of directions, including for instance Web browser-based security measures, language-based techniques, software engineering centric methods, run-time enforcement, static analysis, or formal approaches.
Cite as

Dan Boneh, Ulfar Erlingsson, Martin Johns, and Benjamin Livshits. 09141 Executive Summary – Web Application Security. In Web Application Security. Dagstuhl Seminar Proceedings, Volume 9141, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{boneh_et_al:DagSemProc.09141.2,
  author =	{Boneh, Dan and Erlingsson, Ulfar and Johns, Martin and Livshits, Benjamin},
  title =	{{09141 Executive Summary – Web Application Security}},
  booktitle =	{Web Application Security},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9141},
  editor =	{Dan Boneh and Ulfar Erlingsson and Martin Johns and Benjamin Livshits},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09141.2},
  URN =		{urn:nbn:de:0030-drops-27258},
  doi =		{10.4230/DagSemProc.09141.2},
  annote =	{Keywords: Web applications, Security, Ajax, Web 2.0, Analysis for security, Browser design, Distributed applications}
}
Document
DOI: 10.4230/DagSemProc.07381.1
07381 Abstracts Collection – Cryptography

Authors: Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer

Published in: Dagstuhl Seminar Proceedings, Volume 7381, Cryptography (2008)

Abstract
From 16.09.2007 to 21.09.2007 the Dagstuhl Seminar 07381 ``Cryptography'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer. 07381 Abstracts Collection – Cryptography. In Cryptography. Dagstuhl Seminar Proceedings, Volume 7381, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{blomer_et_al:DagSemProc.07381.1,
  author =	{Bl\"{o}mer, Johannes and Boneh, Dan and Cramer, Ronald and Maurer, Ueli},
  title =	{{07381 Abstracts Collection – Cryptography}},
  booktitle =	{Cryptography},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7381},
  editor =	{Johannes Bl\"{o}mer and Dan Boneh and Ronald Cramer and Ueli Maurer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07381.1},
  URN =		{urn:nbn:de:0030-drops-12935},
  doi =		{10.4230/DagSemProc.07381.1},
  annote =	{Keywords: Cryptography, information security, public-key cryptography, cryptographic protocols, security proofs}
}
Document
DOI: 10.4230/DagSemProc.07381.2
07381 Executive Summary - Cryptography

Authors: Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer

Published in: Dagstuhl Seminar Proceedings, Volume 7381, Cryptography (2008)

Abstract
The topics covered in the seminar spanned most areas of cryptography, in one way or another, both in terms of the types of schemes (public-key cryptography, symmetric cryptography, hash functions and other cryptographic functions, multi-party protocols, etc.) and in terms of the mathematical methods and techniques used (algebra, number theory, elliptic curves, probability theory, information theory, combinatorics, quantum theory, etc.). The range of applications addressed in the various talks was broad, ranging from secure communication, key management, authentication, digital signatures and payment systems to e-voting and Internet security. While the initial plan had been to focus more exclusively on public-key cryptography, it turned out that this sub-topic branches out into many other areas of cryptography and therefore the organizers decided to expand the scope, emphasizing quality rather than close adherence to public-key cryptography. This decision turned out to be a wise one. What was common to almost all the talks is that rigorous mathematical proofs for the security of the presented schemes were given. In fact, a central topic of many of the talks were proof methodologies for various contexts.
Cite as

Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer. 07381 Executive Summary - Cryptography. In Cryptography. Dagstuhl Seminar Proceedings, Volume 7381, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{blomer_et_al:DagSemProc.07381.2,
  author =	{Bl\"{o}mer, Johannes and Boneh, Dan and Cramer, Ronald and Maurer, Ueli},
  title =	{{07381 Executive Summary - Cryptography}},
  booktitle =	{Cryptography},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7381},
  editor =	{Johannes Bl\"{o}mer and Dan Boneh and Ronald Cramer and Ueli Maurer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07381.2},
  URN =		{urn:nbn:de:0030-drops-12928},
  doi =		{10.4230/DagSemProc.07381.2},
  annote =	{Keywords: Cryptography, information security, public-key cryptography, cryptographic protocols, security proofs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact