Tootfinder

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
Kartik Anand, Kabgyun Jeong, Junseo Lee
https://arxiv.org/abs/2506.19792

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
We investigate structural properties of quantum proof systems by establishing collapse results that uncover simplifications in their complexity landscape. We extend classical results such as the Karp-Lipton theorem to quantum polynomial hierarchy with quantum proofs and establish uniqueness preservation for quantum-classical probabilistically checkable proof systems. Our main contributions are threefold. First, we prove that restricting quantum-classical PCP systems to uniqueness does not red…

Fair Data Exchange with Constant-Time Proofs
Majid Khabbazian
https://arxiv.org/abs/2506.14944 https://arxiv.org/pdf/2506.14944

Fair Data Exchange with Constant-Time Proofs
The Fair Data Exchange (FDE) protocol introduced at CCS 2024 offers atomic pay-per-file transfers with constant-size proofs, but its prover and verifier runtimes still scale linearly with the file length n. We collapse these costs to essentially constant by viewing the file as a rate-1 Reed-Solomon (RS) codeword, extending it to a lower-rate RS code with constant redundancy, encrypting this extended vector, and then proving correctness for only a small random subset of the resulting ciphertexts…