Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2510.02402

Probability distributions over CSS codes: two-universality, QKD hashing, collision bounds, security

Pete Rigas

Published Oct 1, 2025• 3 citations
arXivHTMLPDF

Abstract

We characterize novel probability distributions for CSS codes. Such classes of error correcting codes, originally introduced by Calderbank, Shor, and Steane, are of great significance in advancing the fidelity of Quantum computation, with implications for future near term applications. Within the context of Quantum key distribution, such codes, as examined by Ostrev in arXiv: 2109.06709 along with two-universal hashing protocols, have greatly simplified Quantum phases of computation for unconditional security. To further examine novel applications of two-universal hashing protocols, particularly through the structure of parity check matrices, we demonstrate how being able to efficiently compute functions of the parity check matrices relates to marginals of a suitably defined probability measure supported over random matrices. The security of the two-universal QKD hashing protocol will be shown to depend upon the computation of purified states of random matrices, which relates to probabilistic collision bounds between two hashing functions. Central to our approach are the introduction of novel real, simulator, and ideal, isometries, hence allowing for efficient computations of functions of the two parity check matrices. As a result of being able to perform such computations involving parity check matrices, the security of the two-universal hashing protocol is a factor of $2^{ \frac{5}{2} ( 5 - \frac{3}{2} ) + \mathrm{log}_2 \sqrt{C}}$ less secure, for some strictly positive constant $C$.

DOI
10.48550/arxiv.2510.02402

Related papers

Dual Universality of Hash Functions and Its Applications to Quantum Cryptography

Toyohiro Tsurumaru, M. Hayashi

In this paper, we introduce the concept of dual universality of hash functions and present its applications to quantum cryptography. We begin by establishing the one-to-one correspondence between a linear function familyFand a code familyC, and thereby defining ε-almost dual universal2hash functions, as a generalization of the conventional universal2hash functions. Then, we show that this generalized (and thus broader) class of hash functions is in fact sufficient for the security of quantum cryptography. This result can be explained in two different formalisms. First, by noting its relation to the δ-biased family introduced by Dodis and Smith, we demonstrate that Renner's two-universal hashing lemma is generalized to our class of hash functions. Next, we prove that the proof technique by Shor and Preskill can be applied to quantum key distribution (QKD) systems that use our generalized class of hash functions for privacy amplification. While Shor-Preskill formalism requires an implementer of a QKD system to explicitly construct a linear code of the Calderbank-Shor-Steane (CSS) type, this result removes the existing difficulty of the construction of a linear code of CSS code by replacing it by the combination of an ordinary classical error correcting code and our proposed hash function. We also show that a similar result applies to the quantum wire-tap channel. Finally, we compare our results in the two formalisms and show that, in typical QKD scenarios, the Shor-Preskill-type argument gives better security bounds in terms of the trace distance and Holevo information than the method based on the δ-biased family.

arXiv:1101.0064•IEEE Transactions on Information Theory•Apr 2, 2013•58 citations

General Entropic Constraints on Calderbank-Shor-Steane Codes within Magic Distillation Protocols

Rhea Alexander, Si Gvirtz-Chen, Nikolaos Koukoulekidis +1 more

Magic states are fundamental building blocks on the road to fault-tolerant quantum computing.Calderbank-Shor-Steane (CSS) codes play a crucial role in the construction of magic distillation protocols.Previous work has cast quantum computing with magic states for odd dimension d within a phase-space setting in which universal quantum computing is described by the statistical mechanics of quasiprobability distributions.Here we extend this framework to the important d = 2 qubit case and show that we can exploit common structures in CSS circuits to obtain distillation bounds capable of outperforming previous monotone bounds in regimes of practical interest.Moreover, in the case of CSS-code projections, we arrive at a novel cutoff result on the code length n of the CSS code in terms of parameters characterizing a desired distillation, which implies that for fixed target error rate and acceptance probability, one needs to consider only CSS codes below a threshold number of qubits.These entropic constraints are not due simply to the data-processing inequality but rely explicitly on the stochastic representation of such protocols.

arXiv:2211.07535•PRX Quantum•Jun 30, 2023•1 citation

Quantum error correcting codes based on privacy amplification

Zhicheng Luo

Calderbank-Shor-Steane (CSS) quantum error-correcting codes are based on pairs of classical codes which are mutually dual containing. Explicit constructions of such codes for large blocklengths and with good error correcting properties are not easy to find. In this paper we propose a construction of CSS codes which combines a classical code with a two-universal hash function. We show, using the results of Renner and Koenig, that the communication rates of such codes approach the hashing bound on tensor powers of Pauli channels in the limit of large block-length. While the bit-flip errors can be decoded as efficiently as the classical code used, the problem of efficiently decoding the phase-flip errors remains open.

arXiv:0808.1392•Aug 10, 2008•2 citations

Calderbank-Shor-Steane codes on group-valued qudits

Ben T. McDonough, Jian-Hao Zhang, Victor V. Albert +1 more

Calderbank-Shor-Steane (CSS) codes are a versatile quantum error-correcting family built out of commuting $X$- and $Z$-type checks. We introduce CSS-like codes on $G$-valued qudits for any finite group $G$ that reduce to qubit CSS codes for $G = \mathbb{Z}_2$ yet generalize the Kitaev quantum double model for general groups. The $X$-checks of our group-CSS codes correspond to left and/or right multiplication by group elements, while $Z$-checks project onto solutions to group word equations. We describe quantum-double models on oriented two-dimensional CW complexes (which need not cellulate a manifold) and prove that, when $G$ is non-Abelian and simple, every $G$-covariant group-CSS code with suitably upper-bounded $Z$-check weight and lower-bounded $Z$-distance reduces to a CW quantum double. We describe the codespace and logical operators of CW quantum doubles via the same intuition used to obtain logical structure of surface codes. We obtain distance bounds for codes on non-Abelian simple groups from the graph underlying the CW complex, and construct intrinsically non-Abelian code families with asymptotically optimal rate and distances. Adding "ghost vertices" to the CW complex generalizes quantum double models with defects and rough boundary conditions whose logical structure can be understood without reference to non-Abelian anyons or defects. Several non-invertible symmetry-protected topological states, both with ordinary and higher-form symmetries, are the unique codewords of simply-connected CW quantum doubles with a single ghost vertex.

quant-pharXiv:2602.19558•Feb 24, 2026•4 citations

Reliability of Calderbank–Shor–Steane codes and security of quantum key distribution

Mitsuru Hamada

After Mayers (1996, 2001) gave a proof of the security of the Bennett-Brassard 1984 (BB84) quantum key distribution protocol, Shor and Preskill (2000) made a remarkable observation that a Calderbank-Shor-Steane (CSS) code had been implicitly used in the BB84 protocol, and suggested its security could be proven by bounding the fidelity, say F(n), of the incorporated CSS code of length n in the form 1-F(n) <= exp[-n E+o(n)] for some positive number E. This work presents such a number E=E(R) as a function of the rate of a code R, and a threshold R' such that E(R)>0 whenever R < R', which is larger than the achievable rate based on the Gilbert-Varshamov bound that is essentially due to Shor and Preskill (2000). The codes in the present work are robust against fluctuations of channel parameters, which fact is needed to establish the security rigorously and was not proved for rates above the Gilbert-Varshamov rate before in the literature. As a byproduct, the security of a modified BB84 protocol against any joint (coherent) attacks is proved quantitatively.

arXiv:quant-ph/0308029•Journal of Physics A Mathematical and General•Aug 12, 2004•44 citations

The security analysis of the BB84 protocol in the case of Calderbank–Shor–Steane code leakage

Ming Fang, Yaping Li, Li Fei

Quantum key distribution (QKD) allows authenticated parties to share secure keys. Its security comes from quantum physics rather than computational complexity. The previous work has been able to demonstrate the security of the BB84 protocol based on the uncertainty principle, entanglement purification and information theory. In the security proof method based on entanglement purification, it is assumed that the information of Calderbank–Shor–Steane (CSS) error correction code cannot be leaked, otherwise, it is insecure. However, there is no quantitative analysis of the relationship between the parameter of CSS code and the amount of information leaked. In the attack and defense strategy of the actual quantum key distribution system, especially in the application of the device that is easy to lose or out of control, it is necessary to assess the impact of the parameter leakage. In this paper, we derive the relationship between the leaked parameter of CSS code and the amount of the final key leakage based on the BB84 protocol. Based on this formula, we simulated the impact of different CSS code parameter leaks on the final key amount. Through the analysis of simulation results, the security of the BB84 protocol is inversely proportional to the value of [Formula: see text] and [Formula: see text] in the case of the CSS code leak.

International Journal of Quantum Information•Jan 6, 2022•0 citations
We characterize novel probability distributions for CSS codes. Such classes of error correcting codes, originally introduced by Calderbank, Shor, and Steane, are of great significance in advancing the fidelity of Quantum computation, with implications for future near term applications. Within the context of Quantum key distribution, such codes, as examined by Ostrev in arXiv: 2109.06709 along with two-universal hashing protocols, have greatly simplified Quantum phases of computation for unconditional security. To further examine novel applications of two-universal hashing protocols, particularly through the structure of parity check matrices, we demonstrate how being able to efficiently compute functions of the parity check matrices relates to marginals of a suitably defined probability measure supported over random matrices. The security of the two-universal QKD hashing protocol will be shown to depend upon the computation of purified states of random matrices, which relates to probabilistic collision bounds between two hashing functions. Central to our approach are the introduction of novel real, simulator, and ideal, isometries, hence allowing for efficient computations of functions of the two parity check matrices. As a result of being able to perform such computations involving parity check matrices, the security of the two-universal hashing protocol is a factor of 252(5−32)+log2C2^{ \frac{5}{2} ( 5 - \frac{3}{2} ) + \mathrm{log}_2 \sqrt{C}}225​(5−23​)+log2​C​ less secure, for some strictly positive constant CCC.
In this paper, we introduce the concept of dual universality of hash functions and present its applications to quantum cryptography. We begin by establishing the one-to-one correspondence between a linear function familyFand a code familyC, and thereby defining ε-almost dual universal2hash functions, as a generalization of the conventional universal2hash functions. Then, we show that this generalized (and thus broader) class of hash functions is in fact sufficient for the security of quantum cryptography. This result can be explained in two different formalisms. First, by noting its relation to the δ-biased family introduced by Dodis and Smith, we demonstrate that Renner's two-universal hashing lemma is generalized to our class of hash functions. Next, we prove that the proof technique by Shor and Preskill can be applied to quantum key distribution (QKD) systems that use our generalized class of hash functions for privacy amplification. While Shor-Preskill formalism requires an implementer of a QKD system to explicitly construct a linear code of the Calderbank-Shor-Steane (CSS) type, this result removes the existing difficulty of the construction of a linear code of CSS code by replacing it by the combination of an ordinary classical error correcting code and our proposed hash function. We also show that a similar result applies to the quantum wire-tap channel. Finally, we compare our results in the two formalisms and show that, in typical QKD scenarios, the Shor-Preskill-type argument gives better security bounds in terms of the trace distance and Holevo information than the method based on the δ-biased family.
Magic states are fundamental building blocks on the road to fault-tolerant quantum computing.Calderbank-Shor-Steane (CSS) codes play a crucial role in the construction of magic distillation protocols.Previous work has cast quantum computing with magic states for odd dimension d within a phase-space setting in which universal quantum computing is described by the statistical mechanics of quasiprobability distributions.Here we extend this framework to the important d = 2 qubit case and show that we can exploit common structures in CSS circuits to obtain distillation bounds capable of outperforming previous monotone bounds in regimes of practical interest.Moreover, in the case of CSS-code projections, we arrive at a novel cutoff result on the code length n of the CSS code in terms of parameters characterizing a desired distillation, which implies that for fixed target error rate and acceptance probability, one needs to consider only CSS codes below a threshold number of qubits.These entropic constraints are not due simply to the data-processing inequality but rely explicitly on the stochastic representation of such protocols.
Calderbank-Shor-Steane (CSS) quantum error-correcting codes are based on pairs of classical codes which are mutually dual containing. Explicit constructions of such codes for large blocklengths and with good error correcting properties are not easy to find. In this paper we propose a construction of CSS codes which combines a classical code with a two-universal hash function. We show, using the results of Renner and Koenig, that the communication rates of such codes approach the hashing bound on tensor powers of Pauli channels in the limit of large block-length. While the bit-flip errors can be decoded as efficiently as the classical code used, the problem of efficiently decoding the phase-flip errors remains open.
Calderbank-Shor-Steane (CSS) codes are a versatile quantum error-correcting family built out of commuting XXX- and ZZZ-type checks. We introduce CSS-like codes on GGG-valued qudits for any finite group GGG that reduce to qubit CSS codes for G=Z2G = \mathbb{Z}_2G=Z2​ yet generalize the Kitaev quantum double model for general groups. The XXX-checks of our group-CSS codes correspond to left and/or right multiplication by group elements, while ZZZ-checks project onto solutions to group word equations. We describe quantum-double models on oriented two-dimensional CW complexes (which need not cellulate a manifold) and prove that, when GGG is non-Abelian and simple, every GGG-covariant group-CSS code with suitably upper-bounded ZZZ-check weight and lower-bounded ZZZ-distance reduces to a CW quantum double. We describe the codespace and logical operators of CW quantum doubles via the same intuition used to obtain logical structure of surface codes. We obtain distance bounds for codes on non-Abelian simple groups from the graph underlying the CW complex, and construct intrinsically non-Abelian code families with asymptotically optimal rate and distances. Adding "ghost vertices" to the CW complex generalizes quantum double models with defects and rough boundary conditions whose logical structure can be understood without reference to non-Abelian anyons or defects. Several non-invertible symmetry-protected topological states, both with ordinary and higher-form symmetries, are the unique codewords of simply-connected CW quantum doubles with a single ghost vertex.
After Mayers (1996, 2001) gave a proof of the security of the Bennett-Brassard 1984 (BB84) quantum key distribution protocol, Shor and Preskill (2000) made a remarkable observation that a Calderbank-Shor-Steane (CSS) code had been implicitly used in the BB84 protocol, and suggested its security could be proven by bounding the fidelity, say F(n), of the incorporated CSS code of length n in the form 1-F(n) <= exp[-n E+o(n)] for some positive number E. This work presents such a number E=E(R) as a function of the rate of a code R, and a threshold R' such that E(R)>0 whenever R < R', which is larger than the achievable rate based on the Gilbert-Varshamov bound that is essentially due to Shor and Preskill (2000). The codes in the present work are robust against fluctuations of channel parameters, which fact is needed to establish the security rigorously and was not proved for rates above the Gilbert-Varshamov rate before in the literature. As a byproduct, the security of a modified BB84 protocol against any joint (coherent) attacks is proved quantitatively.
Quantum key distribution (QKD) allows authenticated parties to share secure keys. Its security comes from quantum physics rather than computational complexity. The previous work has been able to demonstrate the security of the BB84 protocol based on the uncertainty principle, entanglement purification and information theory. In the security proof method based on entanglement purification, it is assumed that the information of Calderbank–Shor–Steane (CSS) error correction code cannot be leaked, otherwise, it is insecure. However, there is no quantitative analysis of the relationship between the parameter of CSS code and the amount of information leaked. In the attack and defense strategy of the actual quantum key distribution system, especially in the application of the device that is easy to lose or out of control, it is necessary to assess the impact of the parameter leakage. In this paper, we derive the relationship between the leaked parameter of CSS code and the amount of the final key leakage based on the BB84 protocol. Based on this formula, we simulated the impact of different CSS code parameter leaks on the final key amount. Through the analysis of simulation results, the security of the BB84 protocol is inversely proportional to the value of [Formula: see text] and [Formula: see text] in the case of the CSS code leak.