A polynomial-query classical eavesdropper recovers the shared key with certainty in every perfectly complete many-round QCCC key agreement protocol relative to a quantum-accessible random oracle.
Rational degree is polynomially related to degree
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We prove that $\mathrm{deg}(f) \leq \widetilde{O}(\mathrm{rdeg}(f)^3)$ for every Boolean function $f$, where $\mathrm{deg}(f)$ is the degree of $f$ and $\mathrm{rdeg}(f)$ is the rational degree of $f$. This resolves the second of the three open problems stated by Nisan and Szegedy, and attributed to Fortnow, in 1994.
fields
quant-ph 1years
2026 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM
A polynomial-query classical eavesdropper recovers the shared key with certainty in every perfectly complete many-round QCCC key agreement protocol relative to a quantum-accessible random oracle.