7 Search Results for "Polychroniadou, Antigoni"

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
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.66
Brief Announcement: Single-Round Broadcast: Impossibility, Feasibility, and More

Authors: Zhelei Zhou, Bingsheng Zhang, Hong-Sheng Zhou, and Kui Ren

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Broadcast is a fundamental primitive that plays an important role in secure Multi-Party Computation (MPC) area. In this work, we revisit the broadcast with selective abort (hereafter, short for broadcast) proposed by Goldwasser and Lindell (DISC 2002; JoC 2005) and study the round complexity of broadcast under different setup assumptions. Our findings are summarized as follows: - We formally prove that 1-round broadcast is impossible under various widely-used setup assumptions (e.g., plain model, random oracle model, and common reference string model, etc.), even if we consider the static security and the stand-alone framework. More concretely, we formalize a notion called consistent oracle to capture these setups, and prove that our impossibility holds under the consistent oracle. Our impossibility holds in both honest majority setting and dishonest majority setting. - We show that 1-round broadcast protocol is possible in the Universal Composition (UC) framework, by assuming stateful trusted hardwares. Our protocol can be proven secure against all-but-one adaptive and malicious corruptions. We bypass our impossibility result since our stateful trusted hardwares do not satisfy the definition of consistent oracle. - We provide an application of 1-round broadcast: we construct the first 1-round multiple-verifier zero-knowledge (which is a special case of MPC) protocol, without assuming the broadcast hybrid world.
Cite as

Zhelei Zhou, Bingsheng Zhang, Hong-Sheng Zhou, and Kui Ren. Brief Announcement: Single-Round Broadcast: Impossibility, Feasibility, and More. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 66:1-66:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zhou_et_al:LIPIcs.DISC.2025.66,
  author =	{Zhou, Zhelei and Zhang, Bingsheng and Zhou, Hong-Sheng and Ren, Kui},
  title =	{{Brief Announcement: Single-Round Broadcast: Impossibility, Feasibility, and More}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{66:1--66:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.66},
  URN =		{urn:nbn:de:0030-drops-248838},
  doi =		{10.4230/LIPIcs.DISC.2025.66},
  annote =	{Keywords: Broadcast, Security with abort, Round optimality}
}
Document
DOI: 10.4230/LIPIcs.ITC.2025.6
MetaDORAM: Info-Theoretic Distributed ORAM with Less Communication

Authors: Brett Hemenway Falk, Daniel Noble, and Rafail Ostrovsky

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
A Distributed Oblivious RAM is a multi-party protocol that securely implements a RAM functionality on secret-shared inputs and outputs. This paper presents two information-theoretically secure DORAMs whose communication costs are asymptotic improvements over the state of the art. Let n be the number of memory locations and let d be the bit-length of each location. The first, MetaDORAM1, is statistically secure, with n^{-ω(1)} leakage. It has amortized O(log_b(n) d + b ω(1) log(n) + log³(n)/log(log(n))) bits of communication per memory access. Here, b ≥ 2 is a free parameter and ω(1) is any super-constant function (in n). The most communication-efficient prior statistically secure DORAM was that of Abraham et al (PKC 2017), which has cost O(log_b(n) d + b ω(1) log_b(n) log²(n)). MetaDORAM1 is a Θ(ω(1) log(log(n)))-factor improvement over the work of Abraham et al whenever d = O(log²(n)). The second protocol, MetaDORAM2, achieves perfect security. It has amortized communication cost O(log_b(n)d + b log(n) + log³(n)/log(log(n))) where, again, b ≥ 2 is a free parameter. The best prior perfectly secure DORAM is that of Chan et al (ASIACRYPT 2018) which has communication cost O(log(n) d + log³(n)). MetaDORAM2 is therefore a Ω(log(log(n)))-factor improvement over the DORAM of Chan et al under any parameter range (by setting b = log(n)) and is a Θ(log(n))-factor improvement for d = Ω(n^ε) for any constant ε > 0 (by setting b = d/log(n)). Our work is the first perfectly secure DORAM with sub-logarithmic communication overhead. MetaDORAM2 comes at the cost of a once-off (for any given n) setup phase which requires exponential (in n) computation. Both DORAMs are in the 3-party setting with security against 1 semi-honest, static corruption. By a trivial transformation, these can be transformed, respectively, into statistically and perfectly secure active 3-server ORAM protocols secure against 1 corrupt server, with the same communication costs. These multi-server ORAM protocols are likewise asymptotic improvements over the state of the art.
Cite as

Brett Hemenway Falk, Daniel Noble, and Rafail Ostrovsky. MetaDORAM: Info-Theoretic Distributed ORAM with Less Communication. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{falk_et_al:LIPIcs.ITC.2025.6,
  author =	{Falk, Brett Hemenway and Noble, Daniel and Ostrovsky, Rafail},
  title =	{{MetaDORAM: Info-Theoretic Distributed ORAM with Less Communication}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.6},
  URN =		{urn:nbn:de:0030-drops-243560},
  doi =		{10.4230/LIPIcs.ITC.2025.6},
  annote =	{Keywords: ORAM, MPC, DORAM, multi-server ORAM, active ORAM}
}
Document
DOI: 10.4230/LIPIcs.ITC.2025.7
Linear-Time Secure Merge in O(loglog n) Rounds

Authors: Mark Blunk, Paul Bunn, Samuel Dittmer, Steve Lu, and Rafail Ostrovsky

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
The problem of Secure Merge consists of combining two sorted lists (which are either held separately by two parties, or secret-shared among two or more parties), and outputting a single merged (sorted) list, secret-shared among all parties. Just as insecure algorithms for comparison-based sorting are slower than merging (i.e., for lists of size n, Θ(n log n) versus Θ(n)), we explore whether an analogous separation exists for secure protocols; namely, if there exist techniques for performing secure merge that are more performant than simply invoking secure sort. We answer this question affirmatively by constructing a secure merge protocol with optimal Θ(n) communication and computation, and Θ(log log n) rounds of communication. Our results are based solely on black-box use of basic secure primitives, such as secure comparison and secure shuffle. Since two-party secure primitives require computational assumptions, while three-party do not, our protocols achieve these bounds against semi-honest adversaries via a computationally secure two-party (resp. an information-theoretically secure three-party) secure merge protocol. Secure sort is a fundamental building block used in many MPC protocols, e.g., various private set intersection protocols and oblivious RAM protocols. More efficient secure sort can lead to concrete improvements in the overall run-time. Since secure sort can often be replaced by secure merge - as inputs (from different participating players) can be presorted - an efficient secure merge protocol has wide applicability. There are also a range of applications in the field of secure databases, including secure database joins, as well as updatable database storage and search, whereby secure merge can be used to insert new entries into an existing (sorted) database. In building our secure merge protocol, we develop several subprotocols that may be of independent interest. For example, we develop a protocol for secure asymmetric merge (when one list is much larger than the other).
Cite as

Mark Blunk, Paul Bunn, Samuel Dittmer, Steve Lu, and Rafail Ostrovsky. Linear-Time Secure Merge in O(loglog n) Rounds. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blunk_et_al:LIPIcs.ITC.2025.7,
  author =	{Blunk, Mark and Bunn, Paul and Dittmer, Samuel and Lu, Steve and Ostrovsky, Rafail},
  title =	{{Linear-Time Secure Merge in O(loglog n) Rounds}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.7},
  URN =		{urn:nbn:de:0030-drops-243573},
  doi =		{10.4230/LIPIcs.ITC.2025.7},
  annote =	{Keywords: Secure Merge, Secure Sort, Secure Databases, Private Set Intersection}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.90
Polynomial Size, Short-Circuit Resilient Circuits for NC

Authors: Yael Tauman Kalai and Raghuvansh R. Saxena

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

Abstract
We show how to convert any circuit of poly-logarithmic depth and polynomial size into a functionally equivalent circuit of polynomial size (and polynomial depth) that is resilient to adversarial short-circuit errors. Specifically, the resulting circuit computes the same function even if up to ε d gates on every root-to-leaf path are short-circuited, i.e., their output is replaced with the value of one of its inputs, where d is the depth of the circuit and ε > 0 is a fixed constant. Previously, such a result was known for formulas (Kalai-Lewko-Rao, FOCS 2012). It was also known how to convert general circuits to error resilient ones whose size is quasi-polynomial in the size of the original circuit (Efremenko et al. STOC 2022). The reason both these works do not extend to our setting is that there may be many paths from the root to a given gate, and the resilient circuits needs to "remember" a lot of information about these paths, which causes it to be large. Our main idea is to reduce the amount of this information at the cost of increasing the depth of the resilient circuit.
Cite as

Yael Tauman Kalai and Raghuvansh R. Saxena. Polynomial Size, Short-Circuit Resilient Circuits for NC. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 90:1-90:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{taumankalai_et_al:LIPIcs.ITCS.2025.90,
  author =	{Tauman Kalai, Yael and Saxena, Raghuvansh R.},
  title =	{{Polynomial Size, Short-Circuit Resilient Circuits for NC}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{90:1--90:18},
  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.90},
  URN =		{urn:nbn:de:0030-drops-227181},
  doi =		{10.4230/LIPIcs.ITCS.2025.90},
  annote =	{Keywords: Error-resilient computation, short-circuit errors}
}
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
DOI: 10.4230/LIPIcs.ITC.2023.7
Phoenix: Secure Computation in an Unstable Network with Dropouts and Comebacks

Authors: Ivan Damgård, Daniel Escudero, and Antigoni Polychroniadou

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)

Abstract
We consider the task of designing secure computation protocols in an unstable network where honest parties can drop out at any time, according to a schedule provided by the adversary. This type of setting, where even honest parties are prone to failures, is more realistic than traditional models, and has therefore gained a lot of attention recently. Our model, Phoenix, enables a new approach to secure multiparty computation with dropouts, allowing parties to drop out and re-enter the computation on an adversarially-chosen schedule and without assuming that these parties receive the messages that were sent to them while being offline - features that are not available in the existing models of Sleepy MPC (Guo et al., CRYPTO '19), Fluid MPC (Choudhuri et al., CRYPTO '21 ) and YOSO (Gentry et al. CRYPTO '21). Phoenix does assume an upper bound on the number of rounds that an honest party can be off-line - otherwise protocols in this setting cannot guarantee termination within a bounded number of rounds; however, if one settles for a weaker notion, namely guaranteed output delivery only for honest parties who stay on-line long enough, this requirement is not necessary. In this work, we study the settings of perfect, statistical and computational security and design MPC protocols in each of these scenarios. We assume that the intersection of online-and-honest parties from one round to the next is at least 2t+1, t+1 and 1 respectively, where t is the number of (actively) corrupt parties. We show the intersection requirements to be optimal. Our (positive) results are obtained in a way that may be of independent interest: we implement a traditional stable network on top of the unstable one, which allows us to plug in any MPC protocol on top. This approach adds a necessary overhead to the round count of the protocols, which is related to the maximal number of rounds an honest party can be offline. We also present a novel, perfectly secure MPC protocol in the preprocessing model that avoids this overhead by following a more "direct" approach rather than first building a stable network and then using existing protocols. We introduce our network model in the UC-framework, show that the composition theorem still holds, and prove the security of our protocols within this setting.
Cite as

Ivan Damgård, Daniel Escudero, and Antigoni Polychroniadou. Phoenix: Secure Computation in an Unstable Network with Dropouts and Comebacks. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{damgard_et_al:LIPIcs.ITC.2023.7,
  author =	{Damg\r{a}rd, Ivan and Escudero, Daniel and Polychroniadou, Antigoni},
  title =	{{Phoenix: Secure Computation in an Unstable Network with Dropouts and Comebacks}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.7},
  URN =		{urn:nbn:de:0030-drops-183355},
  doi =		{10.4230/LIPIcs.ITC.2023.7},
  annote =	{Keywords: Secure Multiparty Computation, Unstable Networks}
}
  • Refine by Type
  • 7 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 5 2025
  • 1 2023

  • Refine by Author
  • 2 Ostrovsky, Rafail
  • 1 Blunk, Mark
  • 1 Bunn, Paul
  • 1 Damgård, Ivan
  • 1 Dittmer, Samuel
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 2 Security and privacy → Cryptography
  • 2 Theory of computation → Communication complexity
  • 1 Computing methodologies → Distributed algorithms
  • 1 Security and privacy → Database and storage security
  • 1 Security and privacy → Information-theoretic techniques
  • Show More...

  • Refine by Keyword
  • 1 Broadcast
  • 1 DORAM
  • 1 Error-resilient computation
  • 1 MPC
  • 1 Non-malleable codes
  • 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