7 Search Results for "Con, Roni"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.19
Limitations to Computing Quadratic Functions on Reed-Solomon Encoded Data

Authors: Keller Blackwell and Mary Wootters

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

Abstract
We study the problem of low-bandwidth non-linear computation on Reed-Solomon encoded data. Given an [n,k] Reed-Solomon encoding of a message vector 𝐟 ∈ 𝔽_q^k, and a polynomial g ∈ 𝔽_q[X₁, X₂, …, X_k], a user wishing to evaluate g(𝐟) is given local query access to each codeword symbol. The query response is allowed to be the output of an arbitrary function evaluated locally on the codeword symbol, and the user’s aim is to minimize the total information downloaded in order to compute g(𝐟). This problem has been studied before for linear functions g; in this work we initiate the study of non-linear functions by starting with quadratic monomials. For q = p^e and distinct i,j ∈ [k], we show that any scheme evaluating the quadratic monomial g_{i,j} := X_i X_j must download at least 2 log₂(q-1) - 3 bits of information when p is an odd prime, and at least 2log₂(q-2) -4 bits when p = 2. When k = 2, our result shows that one cannot do significantly better than the naive bound of k log₂(q) bits, which is enough to recover all of 𝐟. This contrasts sharply with prior work for low-bandwidth evaluation of linear functions g(𝐟) over Reed-Solomon encoded data, for which it is possible to substantially improve upon this bound [Venkatesan Guruswami and Mary Wootters, 2016; Tamo et al., 2018; Shutty and Wootters, 2021; Kiah et al., 2024; Con and Tamo, 2022]. Some proofs have been omitted from this extended abstract; the full version can be found at [Keller Blackwell and Mary Wootters, 2025].
Cite as

Keller Blackwell and Mary Wootters. Limitations to Computing Quadratic Functions on Reed-Solomon Encoded Data. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 19:1-19:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blackwell_et_al:LIPIcs.ITCS.2026.19,
  author =	{Blackwell, Keller and Wootters, Mary},
  title =	{{Limitations to Computing Quadratic Functions on Reed-Solomon Encoded Data}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{19:1--19: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.19},
  URN =		{urn:nbn:de:0030-drops-253064},
  doi =		{10.4230/LIPIcs.ITCS.2026.19},
  annote =	{Keywords: Distributed computation, Reed-Solomon codes}
}
Document
DOI: 10.4230/LIPIcs.ITC.2025.3
Leakage-Resilience of Shamir’s Secret Sharing: Identifying Secure Evaluation Places

Authors: Jihun Hwang, Hemanta K. Maji, Hai H. Nguyen, and Xiuyu Ye

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

Abstract
Can Shamir’s secret-sharing protect its secret even when all shares are partially compromised? For instance, repairing Reed-Solomon codewords, when possible, recovers the entire secret in the corresponding Shamir’s secret sharing. Yet, Shamir’s secret sharing mitigates various side-channel threats, depending on where its "secret-sharing polynomial" is evaluated. Although most evaluation places yield secure schemes, none are known explicitly; even techniques to identify them are unknown. Our work initiates research into such classifier constructions and derandomization objectives. In this work, we focus on Shamir’s scheme over prime fields, where every share is required to reconstruct the secret. We investigate the security of these schemes against single-bit probes into shares stored in their native binary representation. Technical analysis is particularly challenging when dealing with Reed-Solomon codewords over prime fields, as observed recently in the code repair literature. Furthermore, ensuring the statistical independence of the leakage from the secret necessitates the elimination of any subtle correlations between them. In this context, we present: 1) An efficient algorithm to classify evaluation places as secure or vulnerable against the least-significant-bit leakage. 2) Modulus choices where the classifier above extends to any single-bit probe per share. 3) Explicit modulus choices and secure evaluation places for them. On the way, we discover new bit-probing attacks on Shamir’s scheme, revealing surprising correlations between the leakage and the secret, leading to vulnerabilities when choosing evaluation places naïvely. Our results rely on new techniques to analyze the security of secret-sharing schemes against side-channel threats. We connect their leakage resilience to the orthogonality of square wave functions, which, in turn, depends on the 2-adic valuation of rational approximations. These techniques, novel to the security analysis of secret sharings, can potentially be of broader interest.
Cite as

Jihun Hwang, Hemanta K. Maji, Hai H. Nguyen, and Xiuyu Ye. Leakage-Resilience of Shamir’s Secret Sharing: Identifying Secure Evaluation Places. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hwang_et_al:LIPIcs.ITC.2025.3,
  author =	{Hwang, Jihun and Maji, Hemanta K. and Nguyen, Hai H. and Ye, Xiuyu},
  title =	{{Leakage-Resilience of Shamir’s Secret Sharing: Identifying Secure Evaluation Places}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{3:1--3:20},
  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.3},
  URN =		{urn:nbn:de:0030-drops-243531},
  doi =		{10.4230/LIPIcs.ITC.2025.3},
  annote =	{Keywords: Shamir’s secret sharing, leakage resilience, physical bit probing, secure evaluation places, secure modulus choice, square wave families, LLL algorithm, Fourier analysis}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.102
Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem

Authors: Ittai Rubinstein

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In the trace reconstruction problem, one is given many outputs (called traces) of a noise channel applied to the same input message x, and is asked to recover the input message. Common noise channels studied in the context of trace reconstruction include the deletion channel which deletes each bit w.p. δ, the insertion channel which inserts a G_j i.i.d. uniformly distributed bits before each bit of the input message (where G_j is i.i.d. geometrically distributed with parameter σ) and the symmetry channel which flips each bit of the input message i.i.d. w.p. γ. De et al. and Nazarov and Peres [De et al., 2017; Nazarov and Peres, 2017] showed that any string x can be reconstructed from exp(O(n^{1/3})) traces. Holden et al. [Holden et al., 2018] adapted the techniques used to prove this upper bound, to construct an algorithm for average-case trace reconstruction from the insertion-deletion channel with a sample complexity of exp(O(log^{1/3} n)). However, it is not clear how to apply their techniques more generally and in particular for the recent worst-case upper bound of exp(Õ(n^{1/5})) shown by Chase [Chase, 2021] for the deletion channel. We prove a general reduction from the average-case to smaller instances of a problem similar to worst-case and extend Chase’s upper-bound to this problem and to symmetry and insertion channels as well. Using this reduction and generalization of Chase’s bound, we introduce an algorithm for the average-case trace reconstruction from the symmetry-insertion-deletion channel with a sample complexity of exp(Õ(log^{1/5} n)).
Cite as

Ittai Rubinstein. Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 102:1-102:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{rubinstein:LIPIcs.ICALP.2023.102,
  author =	{Rubinstein, Ittai},
  title =	{{Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{102:1--102:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel 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.2023.102},
  URN =		{urn:nbn:de:0030-drops-181542},
  doi =		{10.4230/LIPIcs.ICALP.2023.102},
  annote =	{Keywords: Trace Reconstruction, Synchronization Channels, Computational Learning Theory, Computational Biology}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.105
Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel

Authors: Ittai Rubinstein

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Two of the most common models for channels with synchronisation errors are the Binary Deletion Channel with parameter p (BDC_p) - a channel where every bit of the codeword is deleted i.i.d with probability p, and the Poisson Repeat Channel with parameter λ (PRC_λ) - a channel where every bit of the codeword is repeated Poisson(λ) times. Previous constructions based on synchronisation strings yielded codes with rates far lower than the capacities of these channels [Con and Shpilka, 2019; Guruswami and Li, 2018], and the only efficient construction to achieve capacity on the BDC at the time of writing this paper is based on the far more advanced methods of polar codes [Tal et al., 2021]. In this work, we present a new method for concatenating synchronisation codes and use it to construct simple and efficient encoding and decoding algorithms for both channels with nearly optimal rates.
Cite as

Ittai Rubinstein. Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 105:1-105:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rubinstein:LIPIcs.ICALP.2022.105,
  author =	{Rubinstein, Ittai},
  title =	{{Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{105:1--105:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.105},
  URN =		{urn:nbn:de:0030-drops-164466},
  doi =		{10.4230/LIPIcs.ICALP.2022.105},
  annote =	{Keywords: Error Correcting Codes, Algorithmic Coding Theory, Binary Deletion Channel}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.50
Nonlinear Repair Schemes of Reed-Solomon Codes.

Authors: Roni Con and Itzhak Tamo

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
The problem of repairing linear codes and, in particular, Reed Solomon (RS) codes has attracted a lot of attention in recent years due to their extreme importance to distributed storage systems. In this problem, a failed code symbol (node) needs to be repaired by downloading as little information as possible from a subset of the remaining nodes. By now, there are examples of RS codes that have efficient repair schemes, and some even attain the cut-set bound. However, these schemes fall short in several aspects; they require a considerable field extension degree. They do not provide any nontrivial repair scheme over prime fields. Lastly, they are all linear repairs, i.e., the computed functions are linear over the base field. Motivated by these and by a question raised in [Guruswami and Wootters, 2017] on the power of nonlinear repair schemes, we study the problem of nonlinear repair schemes of RS codes. Our main results are the first nonlinear repair scheme of RS codes with asymptotically optimal repair bandwidth (asymptotically matching the cut-set bound). Specifically, we show that almost all 2 dimensional RS codes over prime fields (for large enough prime) are asymptotically MSR codes. This is the first example of a nonlinear repair scheme of any code and also the first example that a nonlinear repair scheme can outperform all linear ones. Moreover, we construct several RS codes over prime fields that exhibits efficient repair properties. We also show that unlike the problem of repairing RS codes over field extensions, over prime fields, one can not achieve the cut-set bound with equality. Concretely, by using ideas from additive combinatorics, we improve the cut-set bound by an additive factor, hence showing that every node must transmit more bits than the cut-set bound during a repair. Lastly, we discuss the implications of our results on repairing RS codes for leakage-resilient of Shamir’s secret sharing scheme over prime fields.
Cite as

Roni Con and Itzhak Tamo. Nonlinear Repair Schemes of Reed-Solomon Codes.. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, p. 50:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{con_et_al:LIPIcs.ITCS.2022.50,
  author =	{Con, Roni and Tamo, Itzhak},
  title =	{{Nonlinear Repair Schemes of Reed-Solomon Codes.}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{50:1--50:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.50},
  URN =		{urn:nbn:de:0030-drops-156462},
  doi =		{10.4230/LIPIcs.ITCS.2022.50},
  annote =	{Keywords: Exact repair problem, Reed-Solomon codes, Cut-set bound, Regenerating codes}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.54
Candidate Tree Codes via Pascal Determinant Cubes

Authors: Inbar Ben Yaacov, Gil Cohen, and Anand Kumar Narayanan

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
Tree codes are combinatorial structures introduced by Schulman [Schulman, 1993] as key ingredients in interactive coding schemes. Asymptotically-good tree codes are long known to exist, yet their explicit construction remains a notoriously hard open problem. Even proposing a plausible construction, without the burden of proof, is difficult and the defining tree code property requires structure that remains elusive. To the best of our knowledge, only one candidate appears in the literature, due to Moore and Schulman [Moore and Schulman, 2014]. We put forth a new candidate for an explicit asymptotically-good tree code. Our construction is an extension of the vanishing rate tree code by Cohen-Haeupler-Schulman [Cohen et al., 2018], and its correctness relies on a conjecture that we introduce on certain Pascal determinants indexed by the points of the Boolean hypercube. Furthermore, using the vanishing distance tree code by Gelles et al. [Gelles et al., 2016] enables us to present a construction that relies on an even weaker assumption. We furnish evidence supporting our conjecture through numerical computation, combinatorial arguments from planar path graphs and based on well-studied heuristics from arithmetic geometry.
Cite as

Inbar Ben Yaacov, Gil Cohen, and Anand Kumar Narayanan. Candidate Tree Codes via Pascal Determinant Cubes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 54:1-54:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{benyaacov_et_al:LIPIcs.APPROX/RANDOM.2021.54,
  author =	{Ben Yaacov, Inbar and Cohen, Gil and Narayanan, Anand Kumar},
  title =	{{Candidate Tree Codes via Pascal Determinant Cubes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{54:1--54:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.54},
  URN =		{urn:nbn:de:0030-drops-147474},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.54},
  annote =	{Keywords: Tree codes, Sparse polynomials, Explicit constructions}
}
  • Refine by Type
  • 7 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2025
  • 1 2023
  • 2 2022
  • 1 2021

  • Refine by Author
  • 2 Con, Roni
  • 2 Rubinstein, Ittai
  • 1 Ben Yaacov, Inbar
  • 1 Blackwell, Keller
  • 1 Cohen, Gil
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 3 Mathematics of computing → Coding theory
  • 2 Theory of computation → Error-correcting codes
  • 1 Security and privacy → Cryptanalysis and other attacks
  • 1 Theory of computation → Cryptographic primitives
  • 1 Theory of computation → Sample complexity and generalization bounds

  • Refine by Keyword
  • 3 Reed-Solomon codes
  • 1 Algorithmic Coding Theory
  • 1 Binary Deletion Channel
  • 1 Computational Biology
  • 1 Computational Learning Theory
  • 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