31 Search Results for "Aggarwal, Divesh"

Volume

LIPIcs, Volume 304

5th Conference on Information-Theoretic Cryptography (ITC 2024)

ITC 2024, August 14-16, 2024, Stanford, CA, USA

Editors: Divesh Aggarwal

Document
DOI: 10.4230/LIPIcs.STACS.2026.57
Improving Lagarias-Odlyzko Algorithm for Average-Case Subset Sum: Modular Arithmetic Approach

Authors: Antoine Joux and Karol Węgrzycki

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Lagarias and Odlyzko (J.ACM 1985) proposed a polynomial-time algorithm for solving "almost all" instances of the Subset Sum problem with n integers of size Ω(Γ_LO), where log₂(Γ_LO) > n² log₂(γ) and γ is a parameter of the lattice basis reduction (γ > √{4/3} for LLL). The algorithm of Lagarias and Odlyzko is a cornerstone of cryptography. However, the theoretical guarantee on the density of feasible instances has remained unimproved for almost 40 years. In this paper, we propose an algorithm that solves "almost all" instances of Subset Sum with integers of size Ω(√{Γ_LO}) after a single call to lattice reduction. Additionally, our approach allows solving the Subset Sum problem for multiple targets, whereas the previous method could handle only one target per call to lattice basis reduction. We introduce a modular arithmetic approach to the Subset Sum problem, leveraging lattice reduction to solve a linear system modulo a suitably large prime. By analyzing the lengths of the LLL-reduced basis vectors of both the primal and dual lattices simultaneously, we show that density guarantees can be improved.
Cite as

Antoine Joux and Karol Węgrzycki. Improving Lagarias-Odlyzko Algorithm for Average-Case Subset Sum: Modular Arithmetic Approach. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 57:1-57:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{joux_et_al:LIPIcs.STACS.2026.57,
  author =	{Joux, Antoine and W\k{e}grzycki, Karol},
  title =	{{Improving Lagarias-Odlyzko Algorithm for Average-Case Subset Sum: Modular Arithmetic Approach}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{57:1--57:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle 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.2026.57},
  URN =		{urn:nbn:de:0030-drops-255462},
  doi =		{10.4230/LIPIcs.STACS.2026.57},
  annote =	{Keywords: Average-Case Analysis, Subset Sum, Lattice Reduction, LLL}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.15
How to Use Nondeterminism in Cryptography

Authors: Marshall Ball and Peter Crawford-Kahrl

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

Abstract
Nondeterministic reductions have yielded powerful results in the theory of computational complexity, yet are effectively useless in a cryptographic context. The reason for this is simple, a nondeterministic polynomial time adversary can trivially break almost any cryptographic primitive by simply guessing the "key." In order to use this powerful nondeterministic tool kit in the cryptographic context, we initiate the study of cryptography against adversaries with limited nondeterminism: polynomial time nondeterministic algorithms that are restricted to just a few bits of nondeterminism. We demonstrate that limited nondeterministic security is sufficient to prove two foundational results that have eluded our grasp for decades: dream hardness amplification, and extracting ω(log n) hardcore bits.
Cite as

Marshall Ball and Peter Crawford-Kahrl. How to Use Nondeterminism in Cryptography. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ball_et_al:LIPIcs.ITCS.2026.15,
  author =	{Ball, Marshall and Crawford-Kahrl, Peter},
  title =	{{How to Use Nondeterminism in Cryptography}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{15:1--15:22},
  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.15},
  URN =		{urn:nbn:de:0030-drops-253024},
  doi =		{10.4230/LIPIcs.ITCS.2026.15},
  annote =	{Keywords: limited nondeterminism, cryptography, computational complexity, hardness amplification, pseudorandom generators, hardcore bits}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.11
Classical and Quantum Polynomial Freiman-Ruzsa Algorithms

Authors: Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt, and Tom Gur

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

Abstract
We prove algorithmic versions of the polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Annals of Mathematics, 2025) in additive combinatorics. In particular, we give classical and quantum polynomial-time algorithms that, for A ⊆ 𝔽₂ⁿ with doubling constant K, learn an explicit description of a subspace V ⊆ 𝔽₂ⁿ of size |V| ≤ |A| such that A can be covered by K^C translates of V, for a universal constant C > 1.
Cite as

Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt, and Tom Gur. Classical and Quantum Polynomial Freiman-Ruzsa Algorithms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 11:1-11:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.ITCS.2026.11,
  author =	{Arunachalam, Srinivasan and Castro-Silva, Davi and Dutt, Arkopal and Gur, Tom},
  title =	{{Classical and Quantum Polynomial Freiman-Ruzsa Algorithms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{11:1--11:8},
  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.11},
  URN =		{urn:nbn:de:0030-drops-252987},
  doi =		{10.4230/LIPIcs.ITCS.2026.11},
  annote =	{Keywords: Additive combinatorics, sublinear algorithms}
}
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
DOI: 10.4230/LIPIcs.ITCS.2026.68
Fourier Sparsity of Delta Functions and Matching Vector PIRs

Authors: Fatemeh Ghasemi and Swastik Kopparty

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

Abstract
In this paper we study a basic and natural question about Fourier analysis of Boolean functions, which has applications to the study of Matching Vector based Private Information Retrieval (PIR) schemes. For integers m,r, define a delta function on {0,1}^r ⊆ ℤ_m^r to be a function f: ℤ_m^r → C if f(0) = 1 and f(x) = 0 for all nonzero Boolean x. The basic question that we study is how small can the Fourier sparsity of a delta function be; namely, how sparse can such an f be in the Fourier basis? In addition to being intrinsically interesting and natural, such questions arise naturally while studying "S-decoding polynomials" for the known matching vector families. Finding S-decoding polynomials of reduced sparsity - which corresponds to finding delta functions with low Fourier sparsity - would improve the current best PIR schemes. We show nontrivial upper and lower bounds on the Fourier sparsity of delta functions. Our proofs are elementary and clean. These results imply limitations on improvements to the Matching Vector PIR schemes simply by finding better S-decoding polynomials. In particular, there are no S-decoding polynomials which can make Matching Vector PIRs based on the known matching vector families achieve polylogarithmic communication for constantly many servers. Many interesting questions remain open.
Cite as

Fatemeh Ghasemi and Swastik Kopparty. Fourier Sparsity of Delta Functions and Matching Vector PIRs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 68:1-68:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ghasemi_et_al:LIPIcs.ITCS.2026.68,
  author =	{Ghasemi, Fatemeh and Kopparty, Swastik},
  title =	{{Fourier Sparsity of Delta Functions and Matching Vector PIRs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{68:1--68:22},
  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.68},
  URN =		{urn:nbn:de:0030-drops-253556},
  doi =		{10.4230/LIPIcs.ITCS.2026.68},
  annote =	{Keywords: Fourier Sparsity, Matching Vectors, Private Information Retrieval}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.6
QSETH Strikes Again: Finer Quantum Lower Bounds for Lattice Problem, Strong Simulation, Hitting Set Problem, and More

Authors: Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, and Florian Speelman

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

Abstract
Despite the wide range of problems for which quantum computers offer a computational advantage over their classical counterparts, there are also many problems for which the best known quantum algorithm provides a speedup that is only quadratic, or even subquadratic. Such a situation could also be desirable if we don't want quantum computers to solve certain problems fast - say problems relevant to post-quantum cryptography. When searching for algorithms and when analyzing the security of cryptographic schemes, we would like to have evidence that these problems are difficult to solve on quantum computers; but how do we assess the exact complexity of these problems? For most problems, there are no known ways to directly prove time lower bounds, however it can still be possible to relate the hardness of disparate problems to show conditional lower bounds. This approach has been popular in the classical community, and is being actively developed for the quantum case [Aaronson et al., 2020; Buhrman et al., 2021; Harry Buhrman et al., 2022; Andris Ambainis et al., 2022]. In this paper, by the use of the QSETH framework [Buhrman et al., 2021] we are able to understand the quantum complexity of a few natural variants of CNFSAT, such as parity-CNFSAT or counting-CNFSAT, and also are able to comment on the non-trivial complexity of approximate versions of counting-CNFSAT. Without considering such variants, the best quantum lower bounds will always be quadratically lower than the equivalent classical bounds, because of Grover’s algorithm; however, we are able to show that quantum algorithms will likely not attain even a quadratic speedup for many problems. These results have implications for the complexity of (variations of) lattice problems, the strong simulation and hitting set problems, and more. In the process, we explore the QSETH framework in greater detail and present a useful guide on how to effectively use the QSETH framework.
Cite as

Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, and Florian Speelman. QSETH Strikes Again: Finer Quantum Lower Bounds for Lattice Problem, Strong Simulation, Hitting Set Problem, and More. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2025.6,
  author =	{Chen, Yanlin and Chen, Yilei and Kumar, Rajendra and Patro, Subhasree and Speelman, Florian},
  title =	{{QSETH Strikes Again: Finer Quantum Lower Bounds for Lattice Problem, Strong Simulation, Hitting Set Problem, and More}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{6:1--6:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.6},
  URN =		{urn:nbn:de:0030-drops-243723},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.6},
  annote =	{Keywords: Quantum conditional lower bounds, Fine-grained complexity, Lattice problems, Quantum strong simulation, Hitting set problem, QSETH}
}
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
DOI: 10.4230/LIPIcs.CCC.2025.30
Online Condensing of Unpredictable Sources via Random Walks

Authors: Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
A natural model of a source of randomness consists of a long stream of symbols X = X_1∘…∘X_t, with some guarantee on the entropy of X_i conditioned on the outcome of the prefix x_1,… ,x_{i-1}. We study unpredictable sources, a generalization of the almost Chor-Goldreich (CG) sources considered in [Doron et al., 2023]. In an unpredictable source X, for a typical draw of x ∼ X, for most i-s, the element x_i has a low probability of occurring given x_1,… ,x_{i-1}. Such a model relaxes the often unrealistic assumption of a CG source that for every i, and every x_1,… ,x_{i-1}, the next symbol X_i has sufficiently large entropy. Unpredictable sources subsume all previously considered notions of almost CG sources, including notions that [Doron et al., 2023] failed to analyze, and including those that are equivalent to general sources with high min entropy. For a lossless expander G = (V,E) with m = log |V|, we consider a random walk V_0,V_1,…,V_t on G using unpredictable instructions that have sufficient entropy with respect to m. Our main theorem is that for almost all the steps t/2 ≤ i ≤ t in the walk, the vertex V_i is close to a distribution with min-entropy at least m-O(1). As a result, we obtain seeded online condensers with constant entropy gap, and seedless (deterministic) condensers outputting a constant fraction of the entropy. In particular, our condensers run in space comparable to the output entropy, as opposed to the size of the stream, and even when the length t of the stream is not known ahead of time. As another corollary, we obtain a new extractor based on expander random walks handling lower entropy than the classic expander based construction relying on spectral techniques [Gillman, 1998]. As our main technical tool, we provide a novel analysis covering a key case of adversarial random walks on lossless expanders that [Doron et al., 2023] fails to address. As part of the analysis, we provide a "chain rule for vertex probabilities". The standard chain rule states that for every x ∼ X and i, Pr(x_1,… ,x_i) = Pr[X_i = x_i|X_[1,i-1] = x_1,… ,x_{i-1}] ⋅ Pr(x_1,… ,x_{i-1}). If W(x₁,… ,x_i) is the vertex reached using x₁,… ,x_i, then the chain rule for vertex probabilities essentially states that the same phenomena occurs for a typical x: Pr [V_i = W(x_1,… ,x_i)] ≲ Pr[X_i = x_i|X_[1,i-1] = x_1,… ,x_{i-1}] ⋅ Pr[V_{i-1} = W(x_1,… ,x_{i-1})], where V_i is the vertex distribution of the random walk at step i using X.
Cite as

Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman. Online Condensing of Unpredictable Sources via Random Walks. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.CCC.2025.30,
  author =	{Doron, Dean and Moshkovitz, Dana and Oh, Justin and Zuckerman, David},
  title =	{{Online Condensing of Unpredictable Sources via Random Walks}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.30},
  URN =		{urn:nbn:de:0030-drops-237243},
  doi =		{10.4230/LIPIcs.CCC.2025.30},
  annote =	{Keywords: Randomness Extractors, Expander Graphs}
}
Document
Survey
DOI: 10.4230/TGDK.3.1.3
Uncertainty Management in the Construction of Knowledge Graphs: A Survey

Authors: Lucas Jarnac, Yoan Chabot, and Miguel Couceiro

Published in: TGDK, Volume 3, Issue 1 (2025). Transactions on Graph Data and Knowledge, Volume 3, Issue 1

Abstract
Knowledge Graphs (KGs) are a major asset for companies thanks to their great flexibility in data representation and their numerous applications, e.g., vocabulary sharing, Q&A or recommendation systems. To build a KG, it is a common practice to rely on automatic methods for extracting knowledge from various heterogeneous sources. However, in a noisy and uncertain world, knowledge may not be reliable and conflicts between data sources may occur. Integrating unreliable data would directly impact the use of the KG, therefore such conflicts must be resolved. This could be done manually by selecting the best data to integrate. This first approach is highly accurate, but costly and time-consuming. That is why recent efforts focus on automatic approaches, which represent a challenging task since it requires handling the uncertainty of extracted knowledge throughout its integration into the KG. We survey state-of-the-art approaches in this direction and present constructions of both open and enterprise KGs. We then describe different knowledge extraction methods and discuss downstream tasks after knowledge acquisition, including KG completion using embedding models, knowledge alignment, and knowledge fusion in order to address the problem of knowledge uncertainty in KG construction. We conclude with a discussion on the remaining challenges and perspectives when constructing a KG taking into account uncertainty.
Cite as

Lucas Jarnac, Yoan Chabot, and Miguel Couceiro. Uncertainty Management in the Construction of Knowledge Graphs: A Survey. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 1, pp. 3:1-3:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{jarnac_et_al:TGDK.3.1.3,
  author =	{Jarnac, Lucas and Chabot, Yoan and Couceiro, Miguel},
  title =	{{Uncertainty Management in the Construction of Knowledge Graphs: A Survey}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:48},
  ISSN =	{2942-7517},
  year =	{2025},
  volume =	{3},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.1.3},
  URN =		{urn:nbn:de:0030-drops-233733},
  doi =		{10.4230/TGDK.3.1.3},
  annote =	{Keywords: Knowledge reconciliation, Uncertainty, Heterogeneous sources, Knowledge graph construction}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.14
The More the Merrier! On Total Coding and Lattice Problems and the Complexity of Finding Multicollisions

Authors: Huck Bennett, Surendra Ghentiyala, and Noah Stephens-Davidowitz

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

Abstract
We show a number of connections between two types of search problems: (1) the problem of finding an L-wise multicollision in the output of a function; and (2) the problem of finding two codewords in a code (or two vectors in a lattice) that are within distance d of each other. Specifically, we study these problems in the total regime, in which L and d are chosen so that such a solution is guaranteed to exist, though it might be hard to find. In more detail, we study the total search problem in which the input is a function 𝒞 : [A] → [B] (represented as a circuit) and the goal is to find L ≤ ⌈A/B⌉ distinct elements x_1,…, x_L ∈ A such that 𝒞(x_1) = ⋯ = 𝒞(x_L). The associated complexity classes Polynomial Multi-Pigeonhole Principle ((A,B)-PMPP^L) consist of all problems that reduce to this problem. We show close connections between (A,B)-PMPP^L and many celebrated upper bounds on the minimum distance of a code or lattice (and on the list-decoding radius). In particular, we show that the associated computational problems (i.e., the problem of finding two distinct codewords or lattice points that are close to each other) are in (A,B)-PMPP^L, with a more-or-less smooth tradeoff between the distance d and the parameters A, B, and L. These connections are particularly rich in the case of codes, in which case we show that multiple incomparable bounds on the minimum distance lie in seemingly incomparable complexity classes. Surprisingly, we also show that the computational problems associated with some bounds on the minimum distance of codes are actually hard for these classes (for codes represented by arbitrary circuits). In fact, we show that finding two vectors within a certain distance d is actually hard for the important (and well-studied) class PWPP = (B²,B)-PMPP² in essentially all parameter regimes for which an efficient algorithm is not known, so that our hardness results are essentially tight. In fact, for some d (depending on the block length, message length, and alphabet size), we obtain both hardness and containment. We therefore completely settle the complexity of this problem for such parameters and add coding problems to the short list of problems known to be complete for PWPP. We also study (A,B)-PMPP^L as an interesting family of complexity classes in its own right, and we uncover a rich structure. Specifically, we use recent techniques from the cryptographic literature on multicollision-resistant hash functions to (1) show inclusions of the form (A,B)-PMPP^L ⊆ (A',B')-PMPP^L' for certain non-trivial parameters; (2) black-box separations between such classes in different parameter regimes; and (3) a non-black-box proof that (A,B)-PMPP^L ∈ FP if (A',B')-PMPP^L' ∈ FP for yet another parameter regime. We also show that (A,B)-PMPP^L lies in the recently introduced complexity class Polynomial Long Choice for some parameters.
Cite as

Huck Bennett, Surendra Ghentiyala, and Noah Stephens-Davidowitz. The More the Merrier! On Total Coding and Lattice Problems and the Complexity of Finding Multicollisions. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bennett_et_al:LIPIcs.ITCS.2025.14,
  author =	{Bennett, Huck and Ghentiyala, Surendra and Stephens-Davidowitz, Noah},
  title =	{{The More the Merrier! On Total Coding and Lattice Problems and the Complexity of Finding Multicollisions}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{14:1--14: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.14},
  URN =		{urn:nbn:de:0030-drops-226424},
  doi =		{10.4230/LIPIcs.ITCS.2025.14},
  annote =	{Keywords: Multicollisions, Error-correcting codes, Lattices}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.7
Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography

Authors: Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen

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

Abstract
We study a novel question about nonlocal quantum state discrimination: how well can non-communicating - but entangled - players distinguish between different distributions over quantum states? We call this task simultaneous state indistinguishability. Our main technical result is to show that the players cannot distinguish between each player receiving independently-chosen Haar random states versus all players receiving the same Haar random state. We show that this question has implications to unclonable cryptography, which leverages the no-cloning principle to build cryptographic primitives that are classically impossible to achieve. Understanding the feasibility of unclonable encryption, one of the key unclonable primitives, satisfying indistinguishability security in the plain model has been a major open question in the area. So far, the existing constructions of unclonable encryption are either in the quantum random oracle model or are based on new conjectures. We leverage our main result to present the first construction of unclonable encryption satisfying indistinguishability security, with quantum decryption keys, in the plain model. We also show other implications to single-decryptor encryption and leakage-resilient secret sharing. These applications present evidence that simultaneous Haar indistinguishability could be useful in quantum cryptography.
Cite as

Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen. Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ananth_et_al:LIPIcs.ITCS.2025.7,
  author =	{Ananth, Prabhanjan and Kaleoglu, Fatih and Yuen, Henry},
  title =	{{Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{7:1--7:23},
  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.7},
  URN =		{urn:nbn:de:0030-drops-226352},
  doi =		{10.4230/LIPIcs.ITCS.2025.7},
  annote =	{Keywords: Quantum, Haar, unclonable encryption}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.2
Improved Lower Bounds for 3-Query Matching Vector Codes

Authors: Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, and Sidhant Saraogi

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

Abstract
A Matching Vector (MV) family modulo a positive integer m ≥ 2 is a pair of ordered lists U = (u_1, ⋯, u_K) and V = (v_1, ⋯, v_K) where u_i, v_j ∈ ℤ_m^n with the following property: for any i ∈ [K], the inner product ⟨u_i, v_i⟩ = 0 mod m, and for any i ≠ j, ⟨u_i, v_j⟩ ≠ 0 mod m. An MV family is called r-restricted if inner products ⟨u_i, v_j⟩, for all i,j, take at most r different values. The r-restricted MV families are extremely important since the only known construction of constant-query subexponential locally decodable codes (LDCs) are based on them. Such LDCs constructed via matching vector families are called matching vector codes. Let MV(m,n) (respectively MV(m, n, r)) denote the largest K such that there exists an MV family (respectively r-restricted MV family) of size K in ℤ_m^n. Such a MV family can be transformed in a black-box manner to a good r-query locally decodable code taking messages of length K to codewords of length N = m^n. For small prime m, an almost tight bound MV(m,n) ≤ O(m^{n/2}) was first shown by Dvir, Gopalan, Yekhanin (FOCS'10, SICOMP'11), while for general m, the same paper established an upper bound of O(m^{n-1+o_m(1)}), with o_m(1) denoting a function that goes to zero when m grows. For any arbitrary constant r ≥ 3 and composite m, the best upper bound till date on MV(m,n,r) is O(m^{n/2}), is due to Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14).In a breakthrough work, Alrabiah, Guruswami, Kothari and Manohar (STOC'23) implicitly improve this bound for 3-restricted families to MV(m, n, 3) ≤ O(m^{n/3}). In this work, we present an upper bound for r = 3 where MV(m,n,3) ≤ m^{n/6 +O(log n)}, and as a result, any 3-query matching vector code must have codeword length of N ≥ K^{6-o(1)}.
Cite as

Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, and Sidhant Saraogi. Improved Lower Bounds for 3-Query Matching Vector Codes. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aggarwal_et_al:LIPIcs.ITCS.2025.2,
  author =	{Aggarwal, Divesh and Dutta, Pranjal and Li, Zeyong and Obremski, Maciej and Saraogi, Sidhant},
  title =	{{Improved Lower Bounds for 3-Query Matching Vector Codes}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{2:1--2: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.2},
  URN =		{urn:nbn:de:0030-drops-226308},
  doi =		{10.4230/LIPIcs.ITCS.2025.2},
  annote =	{Keywords: Locally Decodable Codes, Matching Vector Families}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ITC.2024
LIPIcs, Volume 304, ITC 2024, Complete Volume

Authors: Divesh Aggarwal

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

Abstract
LIPIcs, Volume 304, ITC 2024, Complete Volume
Cite as

5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 1-232, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Proceedings{aggarwal:LIPIcs.ITC.2024,
  title =	{{LIPIcs, Volume 304, ITC 2024, Complete Volume}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{1--232},
  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},
  URN =		{urn:nbn:de:0030-drops-205075},
  doi =		{10.4230/LIPIcs.ITC.2024},
  annote =	{Keywords: LIPIcs, Volume 304, ITC 2024, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ITC.2024.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Divesh Aggarwal

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aggarwal:LIPIcs.ITC.2024.0,
  author =	{Aggarwal, Divesh},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{0:i--0:xii},
  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.0},
  URN =		{urn:nbn:de:0030-drops-205087},
  doi =		{10.4230/LIPIcs.ITC.2024.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
  • Refine by Type
  • 30 Document/PDF
  • 12 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 5 2026
  • 7 2025
  • 14 2024
  • 1 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 8 Aggarwal, Divesh
  • 3 Obremski, Maciej
  • 3 Stephens-Davidowitz, Noah
  • 2 Chen, Yanlin
  • 2 Kumar, Rajendra
  • Show More...

  • Refine by Series/Journal
  • 28 LIPIcs
  • 1 OASIcs
  • 1 TGDK

  • Refine by Classification
  • 8 Security and privacy → Information-theoretic techniques
  • 5 Theory of computation → Computational complexity and cryptography
  • 4 Security and privacy → Cryptography
  • 4 Theory of computation → Cryptographic primitives
  • 3 Theory of computation → Cryptographic protocols
  • Show More...

  • Refine by Keyword
  • 3 Lattices
  • 2 Communication Complexity
  • 2 Shortest Vector Problem
  • 1 Additive combinatorics
  • 1 Aggregation
  • 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