3 Search Results for "Mukherjee, Pratyay"

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.ICALP.2017.38
Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13

Authors: Daniel Apon, Nico Döttling, Sanjam Garg, and Pratyay Mukherjee

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
Annihilation attacks, introduced in the work of Miles, Sahai, and Zhandry (CRYPTO 2016), are a class of polynomial-time attacks against several candidate indistinguishability obfuscation (IO) schemes, built from Garg, Gentry, and Halevi (EUROCRYPT 2013) multilinear maps. In this work, we provide a general efficiently-testable property for two single-input branching programs, called partial inequivalence, which we show is sufficient for our variant of annihilation attacks on several obfuscation constructions based on GGH13 multilinear maps. We give examples of pairs of natural NC1 circuits, which - when processed via Barrington's Theorem - yield pairs of branching programs that are partially inequivalent. As a consequence we are also able to show examples of "bootstrapping circuits,'' (albeit somewhat artificially crafted) used to obtain obfuscations for all circuits (given an obfuscator for NC1 circuits), in certain settings also yield partially inequivalent branching programs. Prior to our work, no attacks on any obfuscation constructions for these settings were known.
Cite as

Daniel Apon, Nico Döttling, Sanjam Garg, and Pratyay Mukherjee. Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{apon_et_al:LIPIcs.ICALP.2017.38,
  author =	{Apon, Daniel and D\"{o}ttling, Nico and Garg, Sanjam and Mukherjee, Pratyay},
  title =	{{Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.38},
  URN =		{urn:nbn:de:0030-drops-73814},
  doi =		{10.4230/LIPIcs.ICALP.2017.38},
  annote =	{Keywords: Obfuscation, Multilinear Maps, Cryptanalysis.}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.31
Block-Wise Non-Malleable Codes

Authors: Nishanth Chandran, Vipul Goyal, Pratyay Mukherjee, Omkant Pandey, and Jalaj Upadhyay

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Non-malleable codes, introduced by Dziembowski, Pietrzak, and Wichs (ICS'10) provide the guarantee that if a codeword c of a message m, is modified by a tampering function f to c', then c' either decodes to m or to "something unrelated" to m. In recent literature, a lot of focus has been on explicitly constructing such codes against a large and natural class of tampering functions such as split-state model in which the tampering function operates on different parts of the codeword independently. In this work, we consider a stronger adversarial model called block-wise tampering model, in which we allow tampering to depend on more than one block: if a codeword consists of two blocks c = (c1, c2), then the first tampering function f1 could produce a tampered part c'_1 = f1(c1) and the second tampering function f2 could produce c'_2 = f2(c1, c2) depending on both c2 and c1. The notion similarly extends to multiple blocks where tampering of block ci could happen with the knowledge of all cj for j <= i. We argue this is a natural notion where, for example, the blocks are sent one by one and the adversary must send the tampered block before it gets the next block. A little thought reveals that it is impossible to construct such codes that are non-malleable (in the standard sense) against such a powerful adversary: indeed, upon receiving the last block, an adversary could decode the entire codeword and then can tamper depending on the message. In light of this impossibility, we consider a natural relaxation called non-malleable codes with replacement which requires the adversary to produce not only related but also a valid codeword in order to succeed. Unfortunately, we show that even this relaxed definition is not achievable in the information-theoretic setting (i.e., when the tampering functions can be unbounded) which implies that we must turn our attention towards computationally bounded adversaries. As our main result, we show how to construct a block-wise non-malleable code (BNMC) from sub-exponentially hard one-way permutations. We provide an interesting connection between BNMC and non-malleable commitments. We show that any BNMC can be converted into a nonmalleable (w.r.t. opening) commitment scheme. Our techniques, quite surprisingly, give rise to a non-malleable commitment scheme (secure against so-called synchronizing adversaries), in which only the committer sends messages. We believe this result to be of independent interest. In the other direction, we show that any non-interactive non-malleable (w.r.t. opening) commitment can be used to construct BNMC only with 2 blocks. Unfortunately, such commitment scheme exists only under highly non-standard assumptions (adaptive one-way functions) and hence can not substitute our main construction.
Cite as

Nishanth Chandran, Vipul Goyal, Pratyay Mukherjee, Omkant Pandey, and Jalaj Upadhyay. Block-Wise Non-Malleable Codes. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chandran_et_al:LIPIcs.ICALP.2016.31,
  author =	{Chandran, Nishanth and Goyal, Vipul and Mukherjee, Pratyay and Pandey, Omkant and Upadhyay, Jalaj},
  title =	{{Block-Wise Non-Malleable Codes}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.31},
  URN =		{urn:nbn:de:0030-drops-63102},
  doi =		{10.4230/LIPIcs.ICALP.2016.31},
  annote =	{Keywords: Non-malleable codes, Non-malleable commitments, Block-wise Tampering, Complexity-leveraging}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2017
  • 1 2016

  • Refine by Author
  • 2 Mukherjee, Pratyay
  • 1 Apon, Daniel
  • 1 Chandran, Nishanth
  • 1 Döttling, Nico
  • 1 Freitag, Cody
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Computational complexity and cryptography

  • Refine by Keyword
  • 2 Non-malleable codes
  • 1 Block-wise Tampering
  • 1 Complexity-leveraging
  • 1 Cryptanalysis.
  • 1 Multilinear Maps
  • 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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact