3 Search Results for "Kattis, Assimakis"

Document
DOI: 10.4230/LIPIcs.ITCS.2025.23
Accumulation Without Homomorphism

Authors: Benedikt Bünz, Pratyush Mishra, Wilson Nguyen, and William Wang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
Accumulation schemes are a simple yet powerful primitive that enable highly efficient constructions of incrementally verifiable computation (IVC). Unfortunately, all prior accumulation schemes rely on homomorphic vector commitments whose security is based on public-key assumptions. It is an interesting open question to construct efficient accumulation schemes that avoid the need for such assumptions. In this paper, we answer this question affirmatively by constructing an accumulation scheme from non-homomorphic vector commitments which can be realized from solely symmetric-key assumptions (e.g., Merkle trees). We overcome the need for homomorphisms by instead performing spot-checks over error-correcting encodings of the committed vectors. Unlike prior accumulation schemes, our scheme only supports a bounded number of accumulation steps. We show that such bounded-depth accumulation still suffices to construct proof-carrying data (a generalization of IVC). We also demonstrate several optimizations to our PCD construction which greatly improve concrete efficiency.
Cite as

Benedikt Bünz, Pratyush Mishra, Wilson Nguyen, and William Wang. Accumulation Without Homomorphism. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 23:1-23:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bunz_et_al:LIPIcs.ITCS.2025.23,
  author =	{B\"{u}nz, Benedikt and Mishra, Pratyush and Nguyen, Wilson and Wang, William},
  title =	{{Accumulation Without Homomorphism}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{23:1--23:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.23},
  URN =		{urn:nbn:de:0030-drops-226510},
  doi =		{10.4230/LIPIcs.ITCS.2025.23},
  annote =	{Keywords: Proof-carrying data, incrementally verifiable computation, accumulation schemes}
}
Document
DOI: 10.4230/LIPIcs.AFT.2024.6
Analyzing and Benchmarking ZK-Rollups

Authors: Stefanos Chaliasos, Itamar Reif, Adrià Torralba-Agell, Jens Ernstberger, Assimakis Kattis, and Benjamin Livshits

Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)

Abstract
As blockchain technology continues to transform the realm of digital transactions, scalability has emerged as a critical issue. This challenge has spurred the creation of innovative solutions, particularly Layer 2 scalability techniques like rollups. Among these, ZK-Rollups are notable for employing Zero-Knowledge Proofs to facilitate prompt on-chain transaction verification, thereby improving scalability and efficiency without sacrificing security. Nevertheless, the intrinsic complexity of ZK-Rollups has hindered an exhaustive evaluation of their efficiency, economic impact, and performance. This paper offers a theoretical and empirical examination aimed at comprehending and evaluating ZK-Rollups, with particular attention to ZK-EVMs. We conduct a qualitative analysis to break down the costs linked to ZK-Rollups and scrutinize the design choices of well-known implementations. Confronting the inherent difficulties in benchmarking such intricate systems, we introduce a systematic methodology for their assessment, applying our method to two prominent ZK-Rollups: Polygon zkEVM and zkSync Era. Our research provides initial findings that illuminate trade-offs and areas for enhancement in ZK-Rollup implementations, delivering valuable insights for future research, development, and deployment of these systems.
Cite as

Stefanos Chaliasos, Itamar Reif, Adrià Torralba-Agell, Jens Ernstberger, Assimakis Kattis, and Benjamin Livshits. Analyzing and Benchmarking ZK-Rollups. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chaliasos_et_al:LIPIcs.AFT.2024.6,
  author =	{Chaliasos, Stefanos and Reif, Itamar and Torralba-Agell, Adri\`{a} and Ernstberger, Jens and Kattis, Assimakis and Livshits, Benjamin},
  title =	{{Analyzing and Benchmarking ZK-Rollups}},
  booktitle =	{6th Conference on Advances in Financial Technologies (AFT 2024)},
  pages =	{6:1--6:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-345-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{316},
  editor =	{B\"{o}hme, Rainer and Kiffer, Lucianna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.6},
  URN =		{urn:nbn:de:0030-drops-209420},
  doi =		{10.4230/LIPIcs.AFT.2024.6},
  annote =	{Keywords: Zero-Knowledge Proofs, ZK-Rollups, Benchmarking, Blockchain Scalability}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.45
Lower Bounds for Differential Privacy from Gaussian Width

Authors: Assimakis Kattis and Aleksandar Nikolov

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
We study the optimal sample complexity of a given workload of linear queries under the constraints of differential privacy. The sample complexity of a query answering mechanism under error parameter alpha is the smallest n such that the mechanism answers the workload with error at most alpha on any database of size n. Following a line of research started by Hardt and Talwar [STOC 2010], we analyze sample complexity using the tools of asymptotic convex geometry. We study the sensitivity polytope, a natural convex body associated with a query workload that quantifies how query answers can change between neighboring databases. This is the information that, roughly speaking, is protected by a differentially private algorithm, and, for this reason, we expect that a "bigger" sensitivity polytope implies larger sample complexity. Our results identify the mean Gaussian width as an appropriate measure of the size of the polytope, and show sample complexity lower bounds in terms of this quantity. Our lower bounds completely characterize the workloads for which the Gaussian noise mechanism is optimal up to constants as those having asymptotically maximal Gaussian width. Our techniques also yield an alternative proof of Pisier's Volume Number Theorem which also suggests an approach to improving the parameters of the theorem.
Cite as

Assimakis Kattis and Aleksandar Nikolov. Lower Bounds for Differential Privacy from Gaussian Width. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kattis_et_al:LIPIcs.SoCG.2017.45,
  author =	{Kattis, Assimakis and Nikolov, Aleksandar},
  title =	{{Lower Bounds for Differential Privacy from Gaussian Width}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{45:1--45:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.45},
  URN =		{urn:nbn:de:0030-drops-72368},
  doi =		{10.4230/LIPIcs.SoCG.2017.45},
  annote =	{Keywords: differential privacy, convex geometry, lower bounds, sample complexity}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2024
  • 1 2017

  • Refine by Author
  • 2 Kattis, Assimakis
  • 1 Bünz, Benedikt
  • 1 Chaliasos, Stefanos
  • 1 Ernstberger, Jens
  • 1 Livshits, Benjamin
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Security and privacy → Cryptography
  • 1 Theory of computation → Cryptographic protocols

  • Refine by Keyword
  • 1 Benchmarking
  • 1 Blockchain Scalability
  • 1 Proof-carrying data
  • 1 ZK-Rollups
  • 1 Zero-Knowledge Proofs
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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