7 Search Results for "Prabhakaran, Manoj M."

Document
DOI: 10.4230/LIPIcs.ITCS.2026.76
Ideal Private Simultaneous Messages Schemes and Their Applications

Authors: Keitaro Hiwatashi and Reo Eriguchi

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

Abstract
Private Simultaneous Messages (PSM) is a minimal model for secure computation, where two parties, Alice and Bob, have private inputs x,y and a shared random string. Each of them sends a single message to an external party, Charlie, who can compute f(x,y) for a public function f but learns nothing else. The problem of narrowing the gap between upper and lower bounds on the communication complexity of PSM has been widely studied, but the gap still remains exponential. In this work, we study the communication complexity of PSM from a different perspective and introduce a special class of PSM, referred to as ideal PSM, in which each party’s message length attains the minimum, that is, their messages are taken from the same domain as inputs. We initiate a systematic study of ideal PSM with a complete characterization, several positive results, and applications. First, we provide a characterization of the class of functions that admit ideal PSM, based on permutation groups acting on the input domain. This characterization allows us to derive asymptotic upper bounds on the total number of such functions and a complete list for small domains. We also present several infinite families of functions of practical interest that admit ideal PSM. Interestingly, by simply restricting the input domains of these ideal PSM schemes, we can recover most of the existing PSM schemes that achieve the best known communication complexity in various computation models. As applications, we show that these ideal PSM schemes yield novel communication-efficient PSM schemes for functions with sparse or dense truth-tables and those with low-rank truth-tables. Furthermore, we obtain a PSM scheme for general functions that improves the constant factor in the dominant term of the best known communication complexity. An additional advantage is that our scheme simplifies the existing construction by avoiding the hierarchical design of internally invoking PSM schemes for smaller functions.
Cite as

Keitaro Hiwatashi and Reo Eriguchi. Ideal Private Simultaneous Messages Schemes and Their Applications. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 76:1-76:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hiwatashi_et_al:LIPIcs.ITCS.2026.76,
  author =	{Hiwatashi, Keitaro and Eriguchi, Reo},
  title =	{{Ideal Private Simultaneous Messages Schemes and Their Applications}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{76:1--76:23},
  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.76},
  URN =		{urn:nbn:de:0030-drops-253633},
  doi =		{10.4230/LIPIcs.ITCS.2026.76},
  annote =	{Keywords: secure computation, private simultaneous messages, communication complexity}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.2
Zero-Knowledge Authenticator for Blockchain: Policy-Private and Obliviously Updateable

Authors: Kostas Kryptos Chalkias, Deepak Maram, Arnab Roy, Joy Wang, and Aayush Yadav

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
Transaction details and participant identities on the blockchain are often publicly exposed. In this work, we posit that blockchain’s transparency should not come at the cost of privacy. To that end, we introduce zero-knowledge authenticators (zkAt), a new cryptographic primitive for privacy-preserving authentication on public blockchains. zkAt utilizes zero-knowledge proofs to enable users to authenticate transactions, while keeping the underlying authentication policies private. Prior solutions for such policy-private authentication required the use of threshold signatures, which can only hide the threshold access structure itself. In comparison, zkAt provides privacy for arbitrarily complex authentication policies, and offers a richer interface even within the threshold access structure by, for instance, allowing for the combination of signatures under distinct signature schemes. In order to construct zkAt, we design a compiler that transforms the popular Groth16 non-interactive zero knowledge (NIZK) proof system into a NIZK with equivocable verification keys, a property that we define in this work. Then, for any zkAt constructed using proof systems with this new property, we show that all public information must be independent of the policy, thereby achieving policy-privacy. Next, we give an extension of zkAt, called zkAt^+ wherein, assuming a trusted authority, policies can be updated obliviously in the sense that a third-party learns no new information when a policy is updated by the policy issuer. We also give a theoretical construction for zkAt^+ using recursive NIZKs, and explore the integration of zkAt into modern blockchains. Finally, to evaluate their feasibility, we implement both our schemes for a specific threshold access structure. Our findings show that zkAt achieves comparable performance to traditional threshold signatures, while also attaining privacy for significantly more complex policies with very little overhead.
Cite as

Kostas Kryptos Chalkias, Deepak Maram, Arnab Roy, Joy Wang, and Aayush Yadav. Zero-Knowledge Authenticator for Blockchain: Policy-Private and Obliviously Updateable. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kryptoschalkias_et_al:LIPIcs.AFT.2025.2,
  author =	{Kryptos Chalkias, Kostas and Maram, Deepak and Roy, Arnab and Wang, Joy and Yadav, Aayush},
  title =	{{Zero-Knowledge Authenticator for Blockchain: Policy-Private and Obliviously Updateable}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.2},
  URN =		{urn:nbn:de:0030-drops-247218},
  doi =		{10.4230/LIPIcs.AFT.2025.2},
  annote =	{Keywords: Blockchain privacy, authentication schemes, threshold wallets, zero knowledge proofs}
}
Document
DOI: 10.4230/OASIcs.Manzini.7
Algorithms for Computing Very Large BWTs: a Short Survey

Authors: Diego Díaz-Domínguez, Lavinia Egidi, Veronica Guerrini, Felipe A. Louza, and Giovanna Rosone

Published in: OASIcs, Volume 131, The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday (2025)

Abstract
The Burrows-Wheeler Transform (BWT) is a fundamental string transformation that, although initially introduced for data compression, has been extensively utilized across various domains, including text indexing and pattern matching within large datasets. Although the BWT construction is linear, the constants make the task impractical for large datasets, and as highlighted by Ferragina et al. [Paolo Ferragina et al., 2012], "to use it, one must first build it!". Thus, the construction of the BWT remains a significant challenge. For these reasons, during the past three decades there has been a succession of new algorithms for its construction using techniques that work in external memory or that use text compression. In this survey, we revise some of the most important advancements and tools presented in the past years for computing large BWTs exploiting external memory or text compression approaches without using additional information about the data.
Cite as

Diego Díaz-Domínguez, Lavinia Egidi, Veronica Guerrini, Felipe A. Louza, and Giovanna Rosone. Algorithms for Computing Very Large BWTs: a Short Survey. In The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 131, pp. 7:1-7:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{diazdominguez_et_al:OASIcs.Manzini.7,
  author =	{D{\'\i}az-Dom{\'\i}nguez, Diego and Egidi, Lavinia and Guerrini, Veronica and Louza, Felipe A. and Rosone, Giovanna},
  title =	{{Algorithms for Computing Very Large BWTs: a Short Survey}},
  booktitle =	{The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday},
  pages =	{7:1--7:28},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-390-4},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{131},
  editor =	{Ferragina, Paolo and Gagie, Travis and Navarro, Gonzalo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Manzini.7},
  URN =		{urn:nbn:de:0030-drops-239151},
  doi =		{10.4230/OASIcs.Manzini.7},
  annote =	{Keywords: Burrows-Wheeler transform, Extended Burrows-Wheeler transform, external memory, text compression, longest common prefix}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.72
Card-Based Protocols Imply PSM Protocols

Authors: Kazumasa Shinagawa and Koji Nuida

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Card-based cryptography is the art of cryptography using a deck of physical cards. While this area is known as a research area of recreational cryptography and is recently paid attention in educational purposes, there is no systematic study of the relationship between card-based cryptography and the other "conventional" cryptography. This paper establishes the first generic conversion from card-based protocols to private simultaneous messages (PSM) protocols, a special kind of secure multiparty computation. Our compiler supports "simple" card-based protocols, which is a natural subclass of finite-runtime protocols. The communication complexity of the resulting PSM protocol depends on how many cards are opened in total in all possible branches of the original card-based protocol. This result shows theoretical importance of such "opening complexity" of card-based protocols, which had not been focused in this area. As a consequence, lower bounds for PSM protocols imply those for simple card-based protocols. In particular, if there exists no PSM protocol with subexponential communication complexity for a function f, then there exists no simple card-based protocol with subexponential opening complexity for the same f.
Cite as

Kazumasa Shinagawa and Koji Nuida. Card-Based Protocols Imply PSM Protocols. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 72:1-72:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{shinagawa_et_al:LIPIcs.STACS.2025.72,
  author =	{Shinagawa, Kazumasa and Nuida, Koji},
  title =	{{Card-Based Protocols Imply PSM Protocols}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{72:1--72:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.72},
  URN =		{urn:nbn:de:0030-drops-228975},
  doi =		{10.4230/LIPIcs.STACS.2025.72},
  annote =	{Keywords: Card-based cryptography, private simultaneous messages}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.56
Incompressible Functional Encryption

Authors: Rishab Goyal, Venkata Koppula, Mahesh Sreekumar Rajasree, and Aman Verma

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

Abstract
Incompressible encryption (Dziembowski, Crypto'06; Guan, Wichs, Zhandry, Eurocrypt'22) protects from attackers that learn the entire decryption key, but cannot store the full ciphertext. In incompressible encryption, the attacker must try to compress a ciphertext within pre-specified memory bound S before receiving the secret key. In this work, we generalize the notion of incompressibility to functional encryption. In incompressible functional encryption, the adversary can corrupt non-distinguishing keys at any point, but receives the distinguishing keys only after compressing the ciphertext to within S bits. An important efficiency measure for incompressible encryption is the ciphertext-rate (i.e., rate = |m|/|ct|). We give many new results for incompressible functional encryption for circuits, from minimal assumption of (non-incompressible) functional encryption, with 1) ct-rate-1/2 and short secret keys, 2) ct-rate-1 and large secret keys. Along the way, we also give a new incompressible attribute-based encryption for circuits from standard assumptions, with ct-rate-1/2 and short secret keys. Our results achieve optimal efficiency, as incompressible attribute-based/functional encryption with ct-rate-1 as well as short secret keys has strong barriers for provable security from standard assumptions. Moreover, our assumptions are minimal as incompressible attribute-based/functional encryption are strictly stronger than their non-incompressible counterparts.
Cite as

Rishab Goyal, Venkata Koppula, Mahesh Sreekumar Rajasree, and Aman Verma. Incompressible Functional Encryption. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 56:1-56:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{goyal_et_al:LIPIcs.ITCS.2025.56,
  author =	{Goyal, Rishab and Koppula, Venkata and Rajasree, Mahesh Sreekumar and Verma, Aman},
  title =	{{Incompressible Functional Encryption}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{56:1--56:22},
  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.56},
  URN =		{urn:nbn:de:0030-drops-226849},
  doi =		{10.4230/LIPIcs.ITCS.2025.56},
  annote =	{Keywords: functional encryption, attribute-based encryption, incompressible encryption}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.ICALP.2018.103
Brief Announcement: On Secure m-Party Computation, Commuting Permutation Systems and Unassisted Non-Interactive MPC

Authors: Navneet Agarwal, Sanat Anand, and Manoj Prabhakaran

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
A fundamental problem in the theory of secure multi-party computation (MPC) is to characterize functions with more than 2 parties which admit MPC protocols with information-theoretic security against passive corruption. This question has seen little progress since the work of Chor and Ishai (2001), which demonstrated difficulties in resolving it. In this work, we make significant progress towards resolving this question in the important case of aggregating functionalities, in which m parties P1,...,Pm hold inputs x1,...,xm and an aggregating party P0 must learn f(x1,...,xm). We give a necessary condition and a slightly stronger sufficient condition for f to admit a secure protocol. Both the conditions are stated in terms of an algebraic structure we introduce called Commuting Permutations Systems (CPS), which may be of independent combinatorial interest. When our sufficiency condition is met, we obtain a perfectly secure protocol with minimal interaction, that fits the model of Non-Interactive MPC or NIMPC (Beimel et al., 2014), but without the need for a trusted party to generate correlated randomness. We define Unassisted Non-Interactive MPC (UNIMPC) to capture this variant. We also present an NIMPC protocol for all functionalities, which is simpler and more efficient than the one given in the prior work.
Cite as

Navneet Agarwal, Sanat Anand, and Manoj Prabhakaran. Brief Announcement: On Secure m-Party Computation, Commuting Permutation Systems and Unassisted Non-Interactive MPC. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 103:1-103:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ICALP.2018.103,
  author =	{Agarwal, Navneet and Anand, Sanat and Prabhakaran, Manoj},
  title =	{{Brief Announcement: On Secure m-Party Computation, Commuting Permutation Systems and Unassisted Non-Interactive MPC}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{103:1--103:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.103},
  URN =		{urn:nbn:de:0030-drops-91079},
  doi =		{10.4230/LIPIcs.ICALP.2018.103},
  annote =	{Keywords: Secure Multi-Party Computation, Combinatorial Characterization, Latin Hypercube, Permutation Hypercube Complex}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.88
Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound

Authors: Manoj M. Prabhakaran and Vinod M. Prabhakaran

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

Abstract
In this work we introduce a new information-theoretic complexity measure for 2-party functions, called Rényi information complexity. It is a lower-bound on communication complexity, and has the two leading lower-bounds on communication complexity as its natural relaxations: (external) information complexity and logarithm of partition complexity. These two lower-bounds had so far appeared conceptually quite different from each other, but we show that they are both obtained from Rényi information complexity using two different, but natural relaxations: 1. The relaxation of Rényi information complexity that yields information complexity is to change the order of Rényi mutual information used in its definition from infinity to 1. 2. The relaxation that connects Rényi information complexity with partition complexity is to replace protocol transcripts used in the definition of Rényi information complexity with what we term "pseudotranscripts", which omits the interactive nature of a protocol, but only requires that the probability of any transcript given inputs x and y to the two parties, factorizes into two terms which depend on x and y separately. While this relaxation yields an apparently different definition than (log of) partition function, we show that the two are in fact identical. This gives us a surprising characterization of the partition bound in terms of an information-theoretic quantity. We also show that if both the above relaxations are simultaneously applied to Rényi information complexity, we obtain a complexity measure that is lower-bounded by the (log of) relaxed partition complexity, a complexity measure introduced by Kerenidis et al. (FOCS 2012). We obtain a sharper connection between (external) information complexity and relaxed partition complexity than Kerenidis et al., using an arguably more direct proof. Further understanding Rényi information complexity (of various orders) might have consequences for important direct-sum problems in communication complexity, as it lies between communication complexity and information complexity.
Cite as

Manoj M. Prabhakaran and Vinod M. Prabhakaran. Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 88:1-88:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{prabhakaran_et_al:LIPIcs.ICALP.2016.88,
  author =	{Prabhakaran, Manoj M. and Prabhakaran, Vinod M.},
  title =	{{R\'{e}nyi Information Complexity and an Information Theoretic Characterization of the Partition Bound}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{88:1--88: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.88},
  URN =		{urn:nbn:de:0030-drops-61970},
  doi =		{10.4230/LIPIcs.ICALP.2016.88},
  annote =	{Keywords: Information Complexity, Communication Complexity, R\'{e}nyi Mutual Information}
}
  • Refine by Type
  • 7 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 4 2025
  • 1 2018
  • 1 2016

  • Refine by Author
  • 1 Agarwal, Navneet
  • 1 Anand, Sanat
  • 1 Díaz-Domínguez, Diego
  • 1 Egidi, Lavinia
  • 1 Eriguchi, Reo
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 1 Security and privacy → Authentication
  • 1 Security and privacy → Cryptography
  • 1 Security and privacy → Information-theoretic techniques
  • 1 Security and privacy → Mathematical foundations of cryptography
  • 1 Security and privacy → Privacy-preserving protocols
  • Show More...

  • Refine by Keyword
  • 2 private simultaneous messages
  • 1 Blockchain privacy
  • 1 Burrows-Wheeler transform
  • 1 Card-based cryptography
  • 1 Combinatorial Characterization
  • 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