69 Search Results for "Ishai, Yuval"

Document
DOI: 10.4230/LIPIcs.STACS.2026.28
Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank

Authors: Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, and Arina Smirnova

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

Abstract
Proving complexity lower bounds remains a challenging task: currently, we only know how to prove conditional uniform (algorithm) lower bounds and nonuniform (circuit) lower bounds in restricted circuit models. About a decade ago, Williams (STOC 2010) showed how to derive nonuniform lower bounds from uniform upper bounds: roughly, by designing a fast algorithm for checking satisfiability of circuits, one gets a lower bound for this circuit class. Since then, a number of results of this kind have been proved. For example, Jahanjou et al. (ICALP 2015) and Carmosino et al. (ITCS 2016) proved that if NSETH fails, then E^{NP} has series-parallel circuit size ω(n). One can also derive nonuniform lower bounds from nondeterministic uniform lower bounds. Perhaps the most well-known example is the Karp-Lipton theorem (STOC 1980): if Σ₂ ≠ Π₂, then NP ⊄ P/poly. Some recent examples include the following. Nederlof (STOC 2020) proved a lower bound on the matrix multiplication tensor rank under an assumption that TSP cannot be solved faster than in 2ⁿ time. Belova et al. (SODA 2024) proved that there exists an explicit polynomial family of arithmetic circuit size Ω(n^{δ}), for any δ > 0, assuming that MAX-3-SAT cannot be solved faster than in 2ⁿ nondeterministic time. Williams (FOCS 2024) proved an exponential lower bound for ETHR ∘ ETHR circuits under the Orthogonal Vectors conjecture. Whereas all the lower bounds above are proved under strong assumptions that might eventually be refuted, the revealed connections are of great interest and may still give further insights: one may be able to weaken the used assumptions or to construct generators from other fine-grained reductions. In this paper, we continue developing this line of research and show how uniform nondeterministic lower bounds can be used to construct generators of various types of combinatorial objects that are notoriously hard to analyze: Boolean functions of high circuit size, matrices of high rigidity, and tensors of high rank. Specifically, we prove the following. - If, for some ε and k, k-SAT cannot be solved in input-oblivious co-nondeterministic time O(2^{(1/2+ε)n}), then there exists a monotone Boolean function family in coNP of monotone circuit size 2^{Ω(n / log n)}. Combining this with the result above, we get win-win circuit lower bounds: either E^{NP{}} requires series-parallel circuits of size ω(n) or coNP requires monotone circuits of size 2^{Ω(n / log n)}. - If, for all ε > 0, MAX-3-SAT cannot be solved in co-nondeterministic time O(2^{(1 - ε)n}), then there exist small families of matrices with rigidity exceeding the best known constructions as well as small families of three-dimensional tensors of rank n^{1+Δ}, for some Δ > 0.
Cite as

Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, and Arina Smirnova. Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chukhin_et_al:LIPIcs.STACS.2026.28,
  author =	{Chukhin, Nikolai and Kulikov, Alexander S. and Mihajlin, Ivan and Smirnova, Arina},
  title =	{{Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{28:1--28:21},
  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.28},
  URN =		{urn:nbn:de:0030-drops-255177},
  doi =		{10.4230/LIPIcs.STACS.2026.28},
  annote =	{Keywords: computational complexity, circuit complexity, lower bounds, conditional lower bounds, monotone circuits, matrix rigidity, tensor rank, arithmetic circuits, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.76
Ideal Private Simultaneous Messages Schemes and Their Applications

Authors: Keitaro Hiwatashi and Reo Eriguchi

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

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

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

Copy BibTex To Clipboard

@InProceedings{hiwatashi_et_al:LIPIcs.ITCS.2026.76,
  author =	{Hiwatashi, Keitaro and Eriguchi, Reo},
  title =	{{Ideal Private Simultaneous Messages Schemes and Their Applications}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{76:1--76:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.76},
  URN =		{urn:nbn:de:0030-drops-253633},
  doi =		{10.4230/LIPIcs.ITCS.2026.76},
  annote =	{Keywords: secure computation, private simultaneous messages, communication complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.52
Diffie-Hellman Key Exchange from Commutativity to Group Laws

Authors: Dung Hoang Duong, Youming Qiao, and Chuanqi Zhang

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

Abstract
In Diffie-Hellman key exchange, the commutativity of power operations is instrumental in the agreement of keys. Viewing commutativity as a law in abelian groups, we propose Diffie-Hellman key exchange in the group action framework (Brassard-Yung, Crypto'90; Ji-Qiao-Song-Yun, TCC'19), for actions of non-abelian groups with laws. The security of this protocol is shown, following Fischlin, Günther, Schmidt, and Warinschi (IEEE S&P'16), based on a pseudorandom group action assumption. A concrete instantiation is proposed based on the monomial code equivalence problem.
Cite as

Dung Hoang Duong, Youming Qiao, and Chuanqi Zhang. Diffie-Hellman Key Exchange from Commutativity to Group Laws. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{duong_et_al:LIPIcs.ITCS.2026.52,
  author =	{Duong, Dung Hoang and Qiao, Youming and Zhang, Chuanqi},
  title =	{{Diffie-Hellman Key Exchange from Commutativity to Group Laws}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{52:1--52:20},
  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.52},
  URN =		{urn:nbn:de:0030-drops-253396},
  doi =		{10.4230/LIPIcs.ITCS.2026.52},
  annote =	{Keywords: Diffie-Hellman, Key Exchange, Group Laws, Group Actions, Code Equivalence}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.23
Decoding Balanced Linear Codes with Preprocessing

Authors: Andrej Bogdanov, Rohit Chatterjee, Yunqi Li, and Prashant Nalini Vasudevan

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

Abstract
Prange’s information set algorithm is a well-known decoding algorithm for linear codes. It decodes corrupted codewords of most 𝔽₂-linear codes C of message length n up to relative error rate O(log n / n) in poly(n) time. We show that the error rate can be improved to O((log n)² / n), provided: (1) the decoder has access to a polynomial-length advice string that depends on C only, and (2) C is n^{-Ω(1)}-balanced. As a consequence we improve the error tolerance in decoding random linear codes if inefficient preprocessing of the code is allowed. This reveals potential vulnerabilities in cryptographic applications of Learning Noisy Parities with low noise rate. Our main technical result is that the Hamming weight of Hw, where the rows of H are a random sample of short dual codewords, measures the proximity of a received word w to the code in the regime of interest. Given such H as advice, our algorithm corrects errors by locally minimizing this measure. We show that for most codes, the error rate tolerated by our decoder is asymptotically optimal among all algorithms whose decision is based on thresholding Hw for an arbitrary polynomial-size advice matrix H.
Cite as

Andrej Bogdanov, Rohit Chatterjee, Yunqi Li, and Prashant Nalini Vasudevan. Decoding Balanced Linear Codes with Preprocessing. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 23:1-23:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bogdanov_et_al:LIPIcs.ITCS.2026.23,
  author =	{Bogdanov, Andrej and Chatterjee, Rohit and Li, Yunqi and Vasudevan, Prashant Nalini},
  title =	{{Decoding Balanced Linear Codes with Preprocessing}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{23:1--23: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.23},
  URN =		{urn:nbn:de:0030-drops-253107},
  doi =		{10.4230/LIPIcs.ITCS.2026.23},
  annote =	{Keywords: Linear codes, nearest codeword problem, learning parity with noise}
}
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.ITCS.2026.70
Unconditional Pseudorandomness Against Shallow Quantum Circuits

Authors: Soumik Ghosh, Sathyawageeswar Subramanian, and Wei Zhan

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

Abstract
Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity theoretic assumptions. In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove that: - Any quantum state 2-design yields unconditional pseudorandomness against both QNC⁰ circuits with arbitrarily many ancillae and AC⁰∘QNC⁰ circuits with nearly linear ancillae. - Random phased subspace states, where the phases are picked using a 4-wise independent function, are unconditionally pseudoentangled against the above circuit classes. - Any unitary 2-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local QNC⁰ adversaries, even with limited AC⁰ postprocessing. Our results stand in stark contrast to the standard guarantee of the 2-design property, which only ensures that they cannot be distinguished from Haar random ensembles using two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.
Cite as

Soumik Ghosh, Sathyawageeswar Subramanian, and Wei Zhan. Unconditional Pseudorandomness Against Shallow Quantum Circuits. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 70:1-70:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ghosh_et_al:LIPIcs.ITCS.2026.70,
  author =	{Ghosh, Soumik and Subramanian, Sathyawageeswar and Zhan, Wei},
  title =	{{Unconditional Pseudorandomness Against Shallow Quantum Circuits}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{70:1--70:25},
  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.70},
  URN =		{urn:nbn:de:0030-drops-253578},
  doi =		{10.4230/LIPIcs.ITCS.2026.70},
  annote =	{Keywords: quantum pseudorandomness, shallow quantum circuits, pseudorandomness, t-designs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.71
Lower Bounds on FSS from Dynamic Data Structures

Authors: Niv Gilboa and Daniel Weber

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

Abstract
In Function Secret Sharing (FSS), a dealer with a given function f: {0,1}ⁿ → 𝔾 from n bits to a commutative group 𝔾 such that f is in a function class ℱ shares succinct keys with two properties. Evaluating each key separately on a common input x results in additive shares of f(x) and any subset of the keys does not provide information on f. Two-party FSS schemes which are reducible to One-way Functions (OWF) have applications in cryptography, complexity, and in practical data security systems. We establish a two-way transformation between a two-party FSS scheme for a function class ℱ, which is black-box reducible to an OWF, or even black-box reducible to a family of Pseudo-Random Functions (PRF) and a dynamic data structure that supports range queries on ℱ. A data structure of this type enables dynamically adding functions to a multiset of functions F ⊆ ℱ, and answering range queries on the output of F, i.e., returning ∑_{f ∈ F} f(x) for a query x. The data structures are defined in one of several models which abstract RAM. The correspondence together with known lower bounds on the update time and the query time in data structures leads to the first non-trivial lower bounds on FSS schemes which are black-box reducible to PRF. These lower bounds apply to FSS schemes with polynomial key size and include: - For ℱ^d_{box}, the class of all functions which assign a constant group element β ∈ 𝔾 to any input in a specified d-dimensional box and 0 to all other inputs: if the key sharing function, Gen, runs in time polynomial in n and the evaluation function is Eval then: - If d ≥ 2 and 𝔾 = ℤ₂ then Eval’s running time is Ω ((n^{3/2})/(log³ n)). - If d ≥ 2 and 𝔾 is cyclic such that log |𝔾| = (1 + ε) n then Eval’s running time is Ω ((n/(log n)) ²). - If d > 2 is a constant and further, Gen and Eval correspond to operations on data structures in the Oblivious Group Model (this includes all known FSS from OWF techniques), then the product of Eval’s time and the key size is Ω(n^{d-1}). - For ℱ_{mono}, the class of all monomials ax^b ∈ 𝔽_{2ⁿ}[X] such that b ≤ B, assuming n^{ω(1)} ≤ B ≤ 2^{n/4}: if Gen runs in polynomial time, then Eval’s running time is Ω ((n √{log B})/(log² n)).
Cite as

Niv Gilboa and Daniel Weber. Lower Bounds on FSS from Dynamic Data Structures. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 71:1-71:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gilboa_et_al:LIPIcs.ITCS.2026.71,
  author =	{Gilboa, Niv and Weber, Daniel},
  title =	{{Lower Bounds on FSS from Dynamic Data Structures}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{71:1--71: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.71},
  URN =		{urn:nbn:de:0030-drops-253585},
  doi =		{10.4230/LIPIcs.ITCS.2026.71},
  annote =	{Keywords: FSS, Data Structures, Lower Bounds, Black-Box Reductions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.108
The Learning Stabilizers with Noise Problem

Authors: Alexander Poremba, Yihui Quek, and Peter Shor

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

Abstract
Random classical codes have good error correcting properties, and yet they are notoriously hard to decode in practice. Despite many decades of extensive study, the fastest known algorithms still run in exponential time. The Learning Parity with Noise (LPN) problem, which can be seen as the task of decoding a random linear code in the presence of noise, has thus emerged as a prominent hardness assumption with numerous applications in both cryptography and learning theory. Is there a natural quantum analog of the LPN problem? In this work, we introduce the Learning Stabilizers with Noise (LSN) problem, the task of decoding a random stabilizer code in the presence of local depolarizing noise. We give both polynomial-time and exponential-time quantum algorithms for solving LSN in various depolarizing noise regimes, ranging from extremely low noise, to low constant noise rates, and even higher noise rates up to a threshold. Next, we provide concrete evidence that LSN is hard. First, we show that LSN includes LPN as a special case, which suggests that it is at least as hard as its classical counterpart. Second, we prove worst-case to average-case reductions for variants of LSN. We then ask: what is the computational complexity of solving LSN? Because the task features quantum inputs, its complexity cannot be characterized by traditional complexity classes. Instead, we show that the LSN problem lies in a recently introduced (distributional and oracle) unitary synthesis class. Finally, we identify several applications of our LSN assumption, ranging from the construction of quantum bit commitment schemes to the computational limitations of learning from quantum data.
Cite as

Alexander Poremba, Yihui Quek, and Peter Shor. The Learning Stabilizers with Noise Problem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 108:1-108:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{poremba_et_al:LIPIcs.ITCS.2026.108,
  author =	{Poremba, Alexander and Quek, Yihui and Shor, Peter},
  title =	{{The Learning Stabilizers with Noise Problem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{108:1--108:19},
  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.108},
  URN =		{urn:nbn:de:0030-drops-253950},
  doi =		{10.4230/LIPIcs.ITCS.2026.108},
  annote =	{Keywords: Random quantum stabilizer codes, average-case hardness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.28
Linear Time Encodable Binary Code Achieving GV Bound with Linear Time Encodable Dual Achieving GV Bound

Authors: Martijn Brehm and Nicolas Resch

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

Abstract
We initiate the study of what we term "fast good codes" with "fast good duals." Specifically, we consider the task of constructing a binary linear code C ≤ 𝔽₂ⁿ such that both it and its dual C^⟂ : = {x ∈ 𝔽₂ⁿ:∀ c ∈ C, ⟨ x,c⟩ = 0} are asymptotically good (in fact, have rate-distance tradeoff approaching the GV bound), and are encodable in O(n) time. While we believe such codes should find applications more broadly, as motivation we describe how such codes can be used the secure computation task of encrypted matrix-vector product, as studied by Behhamouda et al (CCS 2025). Our main contribution is a construction of such a fast good code with fast good dual. Our construction is inspired by the repeat multiple accumulate (RMA) codes of Divsalar, Jin and McEliece (Allerton, 1998). To create the rate 1/2 code, after repeating each message coordinate, we perform accumulation steps - where first a uniform coordinate permutation is applied, and afterwards the prefix-sum modulo 2 is applied - which are alternated with discrete derivative steps - where again a uniform coordinate permutation is applied, and afterwards the previous two coordinates are summed modulo 2. Importantly, these two operations are inverse of each other. In particular, the dual of the code is very similar, with the accumulation and discrete derivative steps reversed. Our analysis is inspired by a prior analysis of RMA codes due to Ravazzi and Fagnani (IEEE Trans. Info. Theory, 2009). The main idea is to bound the input-output weight-enumerator function: the expected number of messages of a given weight that are encoded into a codeword of a given weight. We face new challenges in controlling the behaviour of the discrete derivative matrix (which can significantly drop the weight of a vector), which we overcome by careful case analysis.
Cite as

Martijn Brehm and Nicolas Resch. Linear Time Encodable Binary Code Achieving GV Bound with Linear Time Encodable Dual Achieving GV Bound. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brehm_et_al:LIPIcs.ITCS.2026.28,
  author =	{Brehm, Martijn and Resch, Nicolas},
  title =	{{Linear Time Encodable Binary Code Achieving GV Bound with Linear Time Encodable Dual Achieving GV Bound}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{28:1--28:19},
  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.28},
  URN =		{urn:nbn:de:0030-drops-253157},
  doi =		{10.4230/LIPIcs.ITCS.2026.28},
  annote =	{Keywords: Binary error-correcting codes, dual codes, fast encoding, repeat-multiple-accumulate codes}
}
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.AFT.2025.5
Blockchain Governance via Sharp Anonymous Multisignatures

Authors: Wonseok Choi, Xiangyu Liu, and Vassilis Zikas

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

Abstract
Electronic voting has occupied a large part of the cryptographic protocols literature. The recent reality of blockchains - in particular, their need for online governance mechanisms - has brought new parameters and requirements to the problem. We identify the key requirements of a blockchain governance mechanism, namely correctness (including eliminative double votes), voter anonymity, and traceability, and investigate mechanisms that can achieve them with minimal interaction and under assumptions that fit the blockchain setting. First, we define a signature-like primitive, which we term sharp anonymous multisignatures (in short, ♯AMS) that tightly meets the needs of blockchain governance. In a nutshell, ♯AMSs allow any set of parties to generate a signature, e.g., on a proposal to be voted upon, which, if posted on the blockchain, hides the identities of the signers/voters but reveals their number. This can be seen as a (strict) generalization of threshold ring signatures (TRS). We next turn to constructing such ♯AMSs and using them in various governance scenarios - e.g., single vote vs. multiple votes per voter. In this direction, although the definition of TRS does not imply ♯AMS, one can compile some existing TRS constructions into ♯AMS. This raises the question: What is the TRS structure that allows such a compilation? To answer the above, we devise templates for TRSs. Our templates encapsulate and abstract the structure that allows for the above compilation - most of the TRS schemes that can be compiled into ♯AMS are, in fact, instantiations of our template. This abstraction makes our template generic for instantiating TRSs and ♯AMSs from different cryptographic assumptions (e.g., DDH, LWE, etc.). One of our templates is based on chameleon hashes, and we explore a framework of lossy chameleon hashes to understand their nature fully. Finally, we turn to how ♯AMS schemes can be used in our applications. We provide fast (in some cases non-interactive) ♯AMS-based blockchain governance mechanisms for a wide spectrum of assumptions on the honesty (semi-honest vs malicious) and availability of voters and proposers.
Cite as

Wonseok Choi, Xiangyu Liu, and Vassilis Zikas. Blockchain Governance via Sharp Anonymous Multisignatures. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{choi_et_al:LIPIcs.AFT.2025.5,
  author =	{Choi, Wonseok and Liu, Xiangyu and Zikas, Vassilis},
  title =	{{Blockchain Governance via Sharp Anonymous Multisignatures}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.5},
  URN =		{urn:nbn:de:0030-drops-247242},
  doi =		{10.4230/LIPIcs.AFT.2025.5},
  annote =	{Keywords: Blockchain, E-voting, Threshold Ring Signatures, Threshold Cryptography}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.1
Cache Timing Leakages in Zero-Knowledge Protocols

Authors: Shibam Mukherjee, Christian Rechberger, and Markus Schofnegger

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

Abstract
The area of modern zero-knowledge proof systems has seen a significant rise in popularity over the last couple of years, with new techniques and optimized constructions emerging on a regular basis. As the field matures, the aspect of implementation attacks becomes more relevant, however side-channel attacks on zero-knowledge proof systems have seen surprisingly little treatment so far. In this paper, we give an overview of potential attack vectors and show that some of the underlying finite field libraries, and implementations of heavily used components like hash functions using them, are vulnerable w.r.t. cache attacks on CPUs. On the positive side, we demonstrate that the computational overhead to protect against these attacks is relatively small.
Cite as

Shibam Mukherjee, Christian Rechberger, and Markus Schofnegger. Cache Timing Leakages in Zero-Knowledge Protocols. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 1:1-1:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mukherjee_et_al:LIPIcs.AFT.2025.1,
  author =	{Mukherjee, Shibam and Rechberger, Christian and Schofnegger, Markus},
  title =	{{Cache Timing Leakages in Zero-Knowledge Protocols}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{1:1--1:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.1},
  URN =		{urn:nbn:de:0030-drops-247201},
  doi =		{10.4230/LIPIcs.AFT.2025.1},
  annote =	{Keywords: zero-knowledge, protocol, cache timing, side-channel, leakage}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.2
Zero-Knowledge Authenticator for Blockchain: Policy-Private and Obliviously Updateable

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

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

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

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

Copy BibTex To Clipboard

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

Authors: Jing Chen, Jin Dong, Jichen Li, Xuanzhi Xia, and Wentao Zhou

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

Abstract
Byzantine agreement (BA) is a foundational building block in distributed systems that has been extensively studied for decades. With the growing demand for protocol composition in practice, the security analysis of BA protocols under multi-instance executions has attracted increasing attention. However, most existing adversary models focus solely on party corruption and neglect important threats posed by adversarial manipulations of communication channels in the network. Through channel attacks, messages can be reordered across multiple executions and lead to violations of the protocol’s security guarantees, without the participating parties being corrupted. In this work, we present the first adversary model that combines party corruption and channel attacks. Based on this model, we establish new security thresholds for Byzantine agreement under parallel and concurrent compositions, supported by complementary impossibility and possibility results that match each other to form a tight bound. For the impossibility result, we show that even authenticated Byzantine agreement protocols cannot be secure under parallel composition when n ≤ 3t or n ≤ 2c + 2t + 1, where t and c denote the number of corrupted parties and communication channels, respectively. For the possibility result, we prove the existence of secure protocols for unauthenticated Byzantine agreement under parallel and concurrent composition, when n > 3t and n > 2c+2t+1. More specifically, we provide a general black-box compiler that transforms any single-instance secure BA protocol into one that is secure under parallel executions, and we provide a non-black-box construction for concurrent compositions.
Cite as

Jing Chen, Jin Dong, Jichen Li, Xuanzhi Xia, and Wentao Zhou. Composable Byzantine Agreements with Reorder Attacks. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.AFT.2025.13,
  author =	{Chen, Jing and Dong, Jin and Li, Jichen and Xia, Xuanzhi and Zhou, Wentao},
  title =	{{Composable Byzantine Agreements with Reorder Attacks}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{13:1--13:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.13},
  URN =		{urn:nbn:de:0030-drops-247321},
  doi =		{10.4230/LIPIcs.AFT.2025.13},
  annote =	{Keywords: Byzantine agreement, protocol composition, channel reorder attack, security threshold}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.16
Nakamoto Consensus from Multiple Resources

Authors: Mirza Ahad Baig, Christoph U. Günther, and Krzysztof Pietrzak

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

Abstract
The blocks in the Bitcoin blockchain "record" the amount of work W that went into creating them through proofs of work. When honest parties control a majority of the work, consensus is achieved by picking the chain with the highest recorded weight. Resources other than work have been considered to secure such longest-chain blockchains. In Chia, blocks record the amount of disk-space S (via a proof of space) and sequential computational steps V (through a VDF). In this paper, we ask what weight functions Γ(S,V,W) (that assign a weight to a block as a function of the recorded space, speed, and work) are secure in the sense that whenever the weight of the resources controlled by honest parties is larger than the weight of adversarial parties, the blockchain is secure against private double-spending attacks. We completely classify such functions in an idealized "continuous" model: Γ(S,V,W) is secure against private double-spending attacks if and only if it is homogeneous of degree one in the "timed" resources V and W, i.e., αΓ(S,V,W) = Γ(S,α V, α W). This includes the Bitcoin rule Γ(S,V,W) = W and the Chia rule Γ(S,V,W) = S ⋅ V. In a more realistic model where blocks are created at discrete time-points, one additionally needs some mild assumptions on the dependency on S (basically, the weight should not grow too much if S is slightly increased, say linear as in Chia). Our classification is more general and allows various instantiations of the same resource. It provides a powerful tool for designing new longest-chain blockchains. E.g., consider combining different PoWs to counter centralization, say the Bitcoin PoW W₁ and a memory-hard PoW W₂. Previous work suggested to use W₁+W₂ as weight. Our results show that using e.g., √{W₁}⋅ √{W₂} or min{W₁,W₂} are also secure, and we argue that in practice these are much better choices.
Cite as

Mirza Ahad Baig, Christoph U. Günther, and Krzysztof Pietrzak. Nakamoto Consensus from Multiple Resources. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{baig_et_al:LIPIcs.AFT.2025.16,
  author =	{Baig, Mirza Ahad and G\"{u}nther, Christoph U. and Pietrzak, Krzysztof},
  title =	{{Nakamoto Consensus from Multiple Resources}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.16},
  URN =		{urn:nbn:de:0030-drops-247353},
  doi =		{10.4230/LIPIcs.AFT.2025.16},
  annote =	{Keywords: Nakamoto Consensus, Heaviest-chain Rule, Resource Theory}
}
  • Refine by Type
  • 69 Document/PDF
  • 38 Document/HTML

  • Refine by Publication Year
  • 9 2026
  • 30 2025
  • 3 2024
  • 5 2023
  • 9 2022
  • Show More...

  • Refine by Author
  • 16 Ishai, Yuval
  • 4 Boyle, Elette
  • 4 Filmus, Yuval
  • 4 Gilboa, Niv
  • 4 Wootters, Mary
  • Show More...

  • Refine by Series/Journal
  • 67 LIPIcs
  • 1 OASIcs
  • 1 LITES

  • Refine by Classification
  • 11 Security and privacy → Information-theoretic techniques
  • 11 Theory of computation → Cryptographic primitives
  • 10 Theory of computation → Computational complexity and cryptography
  • 6 Theory of computation → Cryptographic protocols
  • 5 Theory of computation → Circuit complexity
  • Show More...

  • Refine by Keyword
  • 4 communication complexity
  • 4 homomorphic secret sharing
  • 3 Cryptography
  • 3 Private information retrieval
  • 3 secret sharing
  • 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