This site has not updated for over 12 hours (it normally updates every 3 hours), so what follows may be out of date.
arXiv Cryptography and Security (cs.CR) and the IACR Cryptology ePrint Archive.
RSS feedNothing on this page matches (the filter only searches this page).
In briefA paper showing that quantum advantage has limited complexity implications
SummaryThe paper examines the complexity-theoretic consequences of proofs of quantumness and quantum-verifier oblivious state preparation. The authors give oracle evidence that both can exist even when P = NP or BQP = QCMA. Their oracle separations lead to conclusions about what relativizing proofs can and cannot establish for classical or quantum cryptography.
In briefInformation Loss Is All You Need: Post-Quantum TC⁰ Pseudorandomness from Worst-Case Lattices
SummaryThe paper introduces learning with algebraic rounding (LAR), which applies deterministic integer rounding to blocks of secret-dependent linear measurements and encodes the result in a lattice quotient. For a fixed family with polynomially bounded modulus and dimensions, the authors show these deterministic labels on uniform, secret-independent public matrices are computationally indistinguishable from uniform labels given any polynomial number of classical random examples. Security rests on quantum worst-case hardness of GapSVP and SIVP over general lattices at approximation factor Õ(q). The construction yields a post-quantum weak pseudorandom function with joint key-and-input evaluation in TC⁰, and the paper also proves hardness of learning polynomial-size two-hidden-layer ReLU networks from noiseless uniform random examples.
WhyThe authors propose learning with algebraic rounding, a deterministic-rounding construction giving a TC0 weak PRF from worst-case lattice hardness, plus ReLU network learning hardness.
In briefInteractive Privacy Boosts Accuracy in Edge-Private Subgraph Counting
SummaryThis paper studies counting subgraphs of a fixed pattern in any undirected graph under interactive local edge differential privacy. The authors propose a two-round algorithm, Linear Noise Cancellation, with error O(n^{k-3/2}/ε^ℓ) on every graph, showing that one extra interaction round can polynomially improve worst-case accuracy over noninteractive methods. They also give a Predict and Correct framework for graphs with bounded maximum degree and prove matching lower bounds in n and d.
WhyThe authors propose a two-round interactive method improving triangle counting error by √n, with matching lower bounds showing tight bounds.