Search Results

Documents authored by Bhushan, Kaartik

Document
DOI: 10.4230/LIPIcs.ITC.2024.2
Communication Complexity vs Randomness Complexity in Interactive Proofs

Authors: Benny Applebaum, Kaartik Bhushan, and Manoj Prabhakaran

Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)

Abstract
In this work, we study the interplay between the communication from a verifier in a general private-coin interactive protocol and the number of random bits it uses in the protocol. Under worst-case derandomization assumptions, we show that it is possible to transform any I-round interactive protocol that uses ρ random bits into another one for the same problem with the additional property that the verifier’s communication is bounded by O(I⋅ ρ). Importantly, this is done with a minor, logarithmic, increase in the communication from the prover to the verifier and while preserving the randomness complexity. Along the way, we introduce a new compression game between computationally-bounded compressor and computationally-unbounded decompressor and a new notion of conditioned efficient distributions that may be of independent interest. Our solutions are based on a combination of perfect hashing and pseudorandom generators.
Cite as

Benny Applebaum, Kaartik Bhushan, and Manoj Prabhakaran. Communication Complexity vs Randomness Complexity in Interactive Proofs. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{applebaum_et_al:LIPIcs.ITC.2024.2,
  author =	{Applebaum, Benny and Bhushan, Kaartik and Prabhakaran, Manoj},
  title =	{{Communication Complexity vs Randomness Complexity in Interactive Proofs}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-333-1},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{304},
  editor =	{Aggarwal, Divesh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.2},
  URN =		{urn:nbn:de:0030-drops-205103},
  doi =		{10.4230/LIPIcs.ITC.2024.2},
  annote =	{Keywords: Interactive Proof Systems, Communication Complexity, Hash Functions, Pseudo-Random Generators, Compression}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.14
Homomorphic Indistinguishability Obfuscation and Its Applications

Authors: Kaartik Bhushan, Venkata Koppula, and Manoj Prabhakaran

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
In this work, we propose the notion of homomorphic indistinguishability obfuscation (HiO) and present a construction based on subexponentially-secure iO and one-way functions. An HiO scheme allows us to convert an obfuscation of circuit C to an obfuscation of C'∘C, and this can be performed obliviously (that is, without knowing the circuit C). A naïve solution would be to obfuscate C'∘iO(C). However, if we do this for k hops, then the size of the final obfuscation is exponential in k. HiO ensures that the size of the final obfuscation remains polynomial after repeated compositions. As an application, we show how to build function-hiding hierarchical multi-input functional encryption and homomorphic witness encryption using HiO.
Cite as

Kaartik Bhushan, Venkata Koppula, and Manoj Prabhakaran. Homomorphic Indistinguishability Obfuscation and Its Applications. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bhushan_et_al:LIPIcs.ITCS.2024.14,
  author =	{Bhushan, Kaartik and Koppula, Venkata and Prabhakaran, Manoj},
  title =	{{Homomorphic Indistinguishability Obfuscation and Its Applications}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.14},
  URN =		{urn:nbn:de:0030-drops-195429},
  doi =		{10.4230/LIPIcs.ITCS.2024.14},
  annote =	{Keywords: Program Obfuscation, Homomorphisms}
}
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