2 Search Results for "Bronfman, Liron"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.62
Improved Rate for Non-Malleable Codes and Time-Lock Puzzles

Authors: Cody Freitag, Ilan Komargodski, Manu Kondapaneni, and Jad Silbak

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Non-malleable codes allow a sender to transmit a message to a receiver, while providing a "best-possible" integrity guarantee to ensure that no attacker - who cannot already decode the message - can meaningfully tamper the message in transit. If tampered, the received message should either be invalid or unrelated to the original message. Non-malleable time-lock puzzles (TLPs) are a special case of non-malleable codes for bounded polynomial-depth tampering with very efficient encoding. In this work, we give generic techniques for constructing non-malleable codes and non-malleable TLPs with improved rate, which captures the ratio of a message’s length to its encoding length. A key contribution of our work is identifying a security notion for non-malleability, which we term "CCA-hiding", sufficient for our compilers. CCA-hiding is a relaxation of CCA-security for encryption or commitments to the fine-grained setting of codes, and requires that the encoded message remains hidden, even given a decoding oracle for any other codeword. Intriguingly, CCA-hiding does not imply non-malleability in the fine-grained setting, as is the case for encryption and commitments. Using our new techniques, we give the following constructions: - Rate-1 CCA-hiding TLPs in the plain model. - Rate-1 non-malleable codes for bounded polynomial-depth tampering in the auxiliary-input random oracle model (AI-ROM). - Rate-(1/2) non-malleable TLPs in the AI-ROM.
Cite as

Cody Freitag, Ilan Komargodski, Manu Kondapaneni, and Jad Silbak. Improved Rate for Non-Malleable Codes and Time-Lock Puzzles. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 62:1-62:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{freitag_et_al:LIPIcs.ITCS.2026.62,
  author =	{Freitag, Cody and Komargodski, Ilan and Kondapaneni, Manu and Silbak, Jad},
  title =	{{Improved Rate for Non-Malleable Codes and Time-Lock Puzzles}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{62:1--62:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.62},
  URN =		{urn:nbn:de:0030-drops-253490},
  doi =		{10.4230/LIPIcs.ITCS.2026.62},
  annote =	{Keywords: Non-malleable codes, Time-lock puzzles}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.30
PCPs and Instance Compression from a Cryptographic Lens

Authors: Liron Bronfman and Ron D. Rothblum

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Modern cryptography fundamentally relies on the assumption that the adversary trying to break the scheme is computationally bounded. This assumption lets us construct cryptographic protocols and primitives that are known to be impossible otherwise. In this work we explore the effect of bounding the adversary’s power in other information theoretic proof-systems and show how to use this assumption to bypass impossibility results. We first consider the question of constructing succinct PCPs. These are PCPs whose length is polynomial only in the length of the original NP witness (in contrast to standard PCPs whose length is proportional to the non-deterministic verification time). Unfortunately, succinct PCPs are known to be impossible to construct under standard complexity assumptions. Assuming the sub-exponential hardness of the learning with errors (LWE) problem, we construct succinct probabilistically checkable arguments or PCAs (Kalai and Raz 2009), which are PCPs in which soundness is guaranteed against efficiently generated false proofs. Our PCA construction is for every NP relation that can be verified by a small-depth circuit (e.g., SAT, clique, TSP, etc.) and in contrast to prior work is publicly verifiable and has constant query complexity. Curiously, we also show, as a proof-of-concept, that such publicly-verifiable PCAs can be used to derive hardness of approximation results. Second, we consider the notion of Instance Compression (Harnik and Naor, 2006). An instance compression scheme lets one compress, for example, a CNF formula φ on m variables and n ≫ m clauses to a new formula φ' with only poly(m) clauses, so that φ is satisfiable if and only if φ' is satisfiable. Instance compression has been shown to be closely related to succinct PCPs and is similarly highly unlikely to exist. We introduce a computational analog of instance compression in which we require that if φ is unsatisfiable then φ' is effectively unsatisfiable, in the sense that it is computationally infeasible to find a satisfying assignment for φ' (although such an assignment may exist). Assuming the same sub-exponential LWE assumption, we construct such computational instance compression schemes for every bounded-depth NP relation. As an application, this lets one compress k formulas ϕ₁,… ,ϕ_k into a single short formula ϕ that is effectively satisfiable if and only if at least one of the original formulas was satisfiable.
Cite as

Liron Bronfman and Ron D. Rothblum. PCPs and Instance Compression from a Cryptographic Lens. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bronfman_et_al:LIPIcs.ITCS.2022.30,
  author =	{Bronfman, Liron and Rothblum, Ron D.},
  title =	{{PCPs and Instance Compression from a Cryptographic Lens}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.30},
  URN =		{urn:nbn:de:0030-drops-156269},
  doi =		{10.4230/LIPIcs.ITCS.2022.30},
  annote =	{Keywords: PCP, Succinct Arguments, Instance Compression}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2022

  • Refine by Author
  • 1 Bronfman, Liron
  • 1 Freitag, Cody
  • 1 Komargodski, Ilan
  • 1 Kondapaneni, Manu
  • 1 Rothblum, Ron D.
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Interactive proof systems

  • Refine by Keyword
  • 1 Instance Compression
  • 1 Non-malleable codes
  • 1 PCP
  • 1 Succinct Arguments
  • 1 Time-lock puzzles

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact