6 Search Results for "Safavi-Naini, Reihaneh"

Document
DOI: 10.4230/LIPIcs.ITC.2025.8
On the Definition of Malicious Private Information Retrieval

Authors: Bar Alon and Amos Beimel

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

Abstract
A multi-server private information retrieval (PIR) protocol allows a client to obtain an entry of its choice from a database, held by one or more servers, while hiding the identity of the entry from small enough coalitions of servers. In this paper, we study PIR protocols in which some of the servers are malicious and may not send messages according to the pre-described protocol. In previous papers, such protocols were defined by requiring that they are correct, private, and robust to malicious servers, i.e., by listing 3 properties that they should satisfy. However, 40 years of experience in studying secure multiparty protocols taught us that defining the security of protocols by a list of required properties is problematic. In this paper, we rectify this situation and define the security of PIR protocols with malicious servers using the real vs. ideal paradigm. We study the relationship between the property-based definition of PIR protocols and the real vs. ideal definition, showing the following results: - We prove that if we require full security from PIR protocols, e.g., the client outputs the correct value of the database entry with high probability even if a minority of the servers are malicious, then the two definitions are equivalent. This implies that constructions of such protocols that were proven secure using the property-based definition are actually secure under the "correct" definition of security. - We show that if we require security-with-abort from PIR protocols (called PIR protocols with error-detection in previous papers), i.e., protocols in which the user either outputs the correct value or an abort symbol, then there are protocols that are secure under the property-based definition; however, they do not satisfy the real vs. ideal definition, that is, they can be attacked allowing selective abort. This shows that the property-based definition of PIR protocols with security-with-abort is problematic. - We consider the compiler of Eriguchi et al. (TCC 22) that starts with a PIR protocol that is secure against semi-honest servers and constructs a PIR protocol with security-with-abort; this compiler implies the best-known PIR protocols with security-with-abort. We show that applying this compiler does not result in PIR protocols that are secure according to the real vs. ideal definition. However, we prove that a simple modification of this compiler results in PIR protocols that are secure according to the real vs. ideal definition.
Cite as

Bar Alon and Amos Beimel. On the Definition of Malicious Private Information Retrieval. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alon_et_al:LIPIcs.ITC.2025.8,
  author =	{Alon, Bar and Beimel, Amos},
  title =	{{On the Definition of Malicious Private Information Retrieval}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{8:1--8: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.8},
  URN =		{urn:nbn:de:0030-drops-243581},
  doi =		{10.4230/LIPIcs.ITC.2025.8},
  annote =	{Keywords: Private information retrieval, secure multiparty computation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.60
Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets

Authors: Roni Con, Zeyu Guo, Ray Li, and Zihan Zhang

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this paper, we prove that with high probability, random Reed-Solomon codes approach the half-Singleton bound - the optimal rate versus error tradeoff for linear insdel codes - with linear-sized alphabets. More precisely, we prove that, for any ε > 0 and positive integers n and k, with high probability, random Reed-Solomon codes of length n and dimension k can correct (1-ε)n-2k+1 adversarial insdel errors over alphabets of size n+2^{poly(1/ε)}k. This significantly improves upon the alphabet size demonstrated in the work of Con, Shpilka, and Tamo (IEEE TIT, 2023), who showed the existence of Reed-Solomon codes with exponential alphabet size Õ(binom(n,2k-1)²) precisely achieving the half-Singleton bound. Our methods are inspired by recent works on list-decoding Reed-Solomon codes. Brakensiek-Gopi-Makam (STOC 2023) showed that random Reed-Solomon codes are list-decodable up to capacity with exponential-sized alphabets, and Guo-Zhang (FOCS 2023) and Alrabiah-Guruswami-Li (STOC 2024) improved the alphabet-size to linear. We achieve a similar alphabet-size reduction by similarly establishing strong bounds on the probability that certain random rectangular matrices are full rank. To accomplish this in our insdel context, our proof combines the random matrix techniques from list-decoding with structural properties of Longest Common Subsequences.
Cite as

Roni Con, Zeyu Guo, Ray Li, and Zihan Zhang. Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 60:1-60:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{con_et_al:LIPIcs.ICALP.2025.60,
  author =	{Con, Roni and Guo, Zeyu and Li, Ray and Zhang, Zihan},
  title =	{{Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{60:1--60:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.60},
  URN =		{urn:nbn:de:0030-drops-234372},
  doi =		{10.4230/LIPIcs.ICALP.2025.60},
  annote =	{Keywords: coding theory, error-correcting codes, Reed-Solomon codes, insdel, insertion-deletion errors, half-Singleton bound}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.95
Toward Separating QMA from QCMA with a Classical Oracle

Authors: Mark Zhandry

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

Abstract
QMA is the class of languages that can be decided by an efficient quantum verifier given a quantum witness, whereas QCMA is the class of such languages where the efficient quantum verifier only is given a classical witness. A challenging fundamental goal in quantum query complexity is to find a classical oracle separation for these classes. In this work, we offer a new approach towards proving such a separation that is qualitatively different than prior work, and show that our approach is sound assuming a natural statistical conjecture which may have other applications to quantum query complexity lower bounds.
Cite as

Mark Zhandry. Toward Separating QMA from QCMA with a Classical Oracle. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 95:1-95:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zhandry:LIPIcs.ITCS.2025.95,
  author =	{Zhandry, Mark},
  title =	{{Toward Separating QMA from QCMA with a Classical Oracle}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{95:1--95:19},
  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.95},
  URN =		{urn:nbn:de:0030-drops-227230},
  doi =		{10.4230/LIPIcs.ITCS.2025.95},
  annote =	{Keywords: Quantum, Oracle Separations, QMA, QCMA}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.7
Incentive Compatibility of Ethereum’s PoS Consensus Protocol

Authors: Ulysse Pavloff, Yackolley Amoussou-Guenou, and Sara Tucci-Piergiovanni

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
This paper investigates whether following the fork-choice rule in the Ethereum PoS consensus protocol constitutes a Nash equilibrium - i.e., whether the protocol that maintains the canonical chain in Ethereum is incentive-compatible. Specifically, we explore whether selfish participants may attempt to manipulate the fork-choice rule by forking out previous blocks and capturing the rewards associated with those blocks. Our analysis considers two strategies for participants: the obedient strategy, which adheres to the prescribed protocol, and the cunning strategy, which attempts to manipulate the fork-choice rule to gain more rewards. We evaluate the conditions under which selfish participants might deviate from the obedient strategy. We found that, in a synchronous system, following the prescribed fork-choice rule is incentive-compatible. However, in an eventually synchronous system, the protocol is eventually incentive-compatible - that is, only a limited number of proposers will find it profitable to fork the chain during the synchronous period. After this sequence of cunning proposers, subsequent proposers will find it more profitable to follow the protocol.
Cite as

Ulysse Pavloff, Yackolley Amoussou-Guenou, and Sara Tucci-Piergiovanni. Incentive Compatibility of Ethereum’s PoS Consensus Protocol. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{pavloff_et_al:LIPIcs.OPODIS.2024.7,
  author =	{Pavloff, Ulysse and Amoussou-Guenou, Yackolley and Tucci-Piergiovanni, Sara},
  title =	{{Incentive Compatibility of Ethereum’s PoS Consensus Protocol}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.7},
  URN =		{urn:nbn:de:0030-drops-225431},
  doi =		{10.4230/LIPIcs.OPODIS.2024.7},
  annote =	{Keywords: Ethereum PoS, Game Theory, Block Reward}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.7
Leakage-Resilient Secret Sharing in Non-Compartmentalized Models

Authors: Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, and Huaxiong Wang

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Leakage-resilient secret sharing has mostly been studied in the compartmentalized models, where a leakage oracle can arbitrarily leak bounded number of bits from all shares, provided that the oracle only has access to a bounded number of shares when the leakage is taking place. We start a systematic study of leakage-resilient secret sharing against global leakage, where the leakage oracle can access the full set of shares simultaneously, but the access is restricted to a special class of leakage functions. More concretely, the adversary can corrupt several players and obtain their shares, as well as applying a leakage function from a specific class to the full share vector. We explicitly construct such leakage-resilient secret sharing with respect to affine leakage functions and low-degree multi-variate polynomial leakage functions, respectively. For affine leakage functions, we obtain schemes with threshold access structure that are leakage-resilient as long as there is a substantial difference between the total amount of information obtained by the adversary, through corrupting individual players and leaking from the full share vector, and the amount that the reconstruction algorithm requires for reconstructing the secret. Furthermore, if we assume the adversary is non-adaptive, we can even make the secret length asymptotically equal to the difference, as the share length grows. Specifically, we have a threshold scheme with parameters similar to Shamir’s scheme and is leakage-resilient against affine leakage. For multi-variate polynomial leakage functions with degree bigger than one, our constructions here only yield ramp schemes that are leakage-resilient against such leakage. Finally, as a result of independent interest, we show that our approach to leakage-resilient secret sharing also yields a competitive scheme compared with the state-of-the-art construction in the compartmentalized models.
Cite as

Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, and Huaxiong Wang. Leakage-Resilient Secret Sharing in Non-Compartmentalized Models. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.ITC.2020.7,
  author =	{Lin, Fuchun and Cheraghchi, Mahdi and Guruswami, Venkatesan and Safavi-Naini, Reihaneh and Wang, Huaxiong},
  title =	{{Leakage-Resilient Secret Sharing in Non-Compartmentalized Models}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{7:1--7:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.7},
  URN =		{urn:nbn:de:0030-drops-121124},
  doi =		{10.4230/LIPIcs.ITC.2020.7},
  annote =	{Keywords: Leakage-resilient cryptography, Secret sharing scheme, Randomness extractor}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.53
Secret Sharing with Binary Shares

Authors: Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, and Huaxiong Wang

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
Shamir's celebrated secret sharing scheme provides an efficient method for encoding a secret of arbitrary length l among any N <= 2^l players such that for a threshold parameter t, (i) the knowledge of any t shares does not reveal any information about the secret and, (ii) any choice of t+1 shares fully reveals the secret. It is known that any such threshold secret sharing scheme necessarily requires shares of length l, and in this sense Shamir's scheme is optimal. The more general notion of ramp schemes requires the reconstruction of secret from any t+g shares, for a positive integer gap parameter g. Ramp secret sharing scheme necessarily requires shares of length l/g. Other than the bound related to secret length l, the share lengths of ramp schemes can not go below a quantity that depends only on the gap ratio g/N. In this work, we study secret sharing in the extremal case of bit-long shares and arbitrarily small gap ratio g/N, where standard ramp secret sharing becomes impossible. We show, however, that a slightly relaxed but equally effective notion of semantic security for the secret, and negligible reconstruction error probability, eliminate the impossibility. Moreover, we provide explicit constructions of such schemes. One of the consequences of our relaxation is that, unlike standard ramp schemes with perfect secrecy, adaptive and non-adaptive adversaries need different analysis and construction. For non-adaptive adversaries, we explicitly construct secret sharing schemes that provide secrecy against any tau fraction of observed shares, and reconstruction from any rho fraction of shares, for any choices of 0 <= tau < rho <= 1. Our construction achieves secret length N(rho-tau-o(1)), which we show to be optimal. For adaptive adversaries, we construct explicit schemes attaining a secret length Omega(N(rho-tau)). We discuss our results and open questions.
Cite as

Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, and Huaxiong Wang. Secret Sharing with Binary Shares. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 53:1-53:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.ITCS.2019.53,
  author =	{Lin, Fuchun and Cheraghchi, Mahdi and Guruswami, Venkatesan and Safavi-Naini, Reihaneh and Wang, Huaxiong},
  title =	{{Secret Sharing with Binary Shares}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{53:1--53:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.53},
  URN =		{urn:nbn:de:0030-drops-101461},
  doi =		{10.4230/LIPIcs.ITCS.2019.53},
  annote =	{Keywords: Secret sharing scheme, Wiretap channel}
}
  • Refine by Type
  • 6 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2020
  • 1 2019

  • Refine by Author
  • 2 Cheraghchi, Mahdi
  • 2 Guruswami, Venkatesan
  • 2 Lin, Fuchun
  • 2 Safavi-Naini, Reihaneh
  • 2 Wang, Huaxiong
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs

  • Refine by Classification
  • 2 Security and privacy → Cryptography
  • 2 Security and privacy → Information-theoretic techniques
  • 2 Theory of computation → Expander graphs and randomness extractors
  • 1 Computer systems organization → Dependable and fault-tolerant systems and networks
  • 1 Mathematics of computing → Coding theory
  • Show More...

  • Refine by Keyword
  • 2 Secret sharing scheme
  • 1 Block Reward
  • 1 Ethereum PoS
  • 1 Game Theory
  • 1 Leakage-resilient cryptography
  • 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact