Tamper Detection against Unitary Operators

Tamper Detection against Unitary Operators

Time Stamp: November 8, 2023 10:24 AM
Source Node: 2979655

Naresh Goud Boddu1 and Upendra Kapshikar2

1NTT Research, Sunnyvale, USA
2Center for Quantum Technologies, National University of Singapore, Singapore

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Security of a storage device against a tampering adversary has been a well-studied topic in classical cryptography. Such models give black-box access to an adversary, and the aim is to protect the stored message or abort the protocol if there is any tampering.
In this work, we extend the scope of the theory of tamper detection codes against an adversary with quantum capabilities. We consider encoding and decoding schemes that are used to encode a $k$-qubit quantum message $vert mrangle$ to obtain an $n$-qubit quantum codeword $vert {psi_m} rangle$. A quantum codeword $vert {psi_m} rangle$ can be adversarially tampered via a unitary $U$ from some known tampering unitary family $mathcal{U}_{mathsf{Adv}}$ (acting on $mathbb{C}^{2^n}$).
Firstly, we initiate the general study of $textit{quantum tamper detection codes}$, which detect if there is any tampering caused by the action of a unitary operator. In case there was no tampering, we would like to output the original message. We show that quantum tamper detection codes exist for any family of unitary operators $mathcal{U}_{mathsf{Adv}}$, such that $vertmathcal{U}_{mathsf{Adv}} vert lt 2^{2^{alpha n}}$ for some constant $alpha in (0,1/6)$; provided that unitary operators are not too close to the identity operator. Quantum tamper detection codes that we construct can be considered to be quantum variants of $textit{classical tamper detection codes}$ studied by Jafargholi and Wichs ['15], which are also known to exist under similar restrictions.
Additionally, we show that when the message set $mathcal{M}$ is classical, such a construction can be realized as a $textit{non-malleable code}$ against any $mathcal{U}_{mathsf{Adv}}$ of size up to $2^{2^{alpha n}}$.

► BibTeX data

► References

[1] Zahra Jafargholi and Daniel Wichs. ``Tamper detection and continuous non-malleable codes''. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, Theory of Cryptography. Pages 451–480. Berlin, Heidelberg (2015). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​978-3-662-46494-6_19

[2] M. Cheraghchi and V. Guruswami. ``Capacity of non-malleable codes''. IEEE Transactions on Information Theory 62, 1097–1118 (2016).
https:/​/​doi.org/​10.1109/​TIT.2015.2511784

[3] Sebastian Faust, Pratyay Mukherjee, Daniele Venturi, and Daniel Wichs. ``Efficient non-malleable codes and key-derivation for poly-size tampering circuits''. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology – EUROCRYPT 2014. Pages 111–128. Berlin, Heidelberg (2014). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​978-3-642-55220-5_7

[4] Ronald Cramer, Yevgeniy Dodis, Serge Fehr, Carles Padró, and Daniel Wichs. ``Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors''. In Nigel Smart, editor, Advances in Cryptology – EUROCRYPT 2008. Pages 471–488. Berlin, Heidelberg (2008). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​978-3-540-78967-3_27

[5] Ronald Cramer, Carles Padró, and Chaoping Xing. ``Optimal algebraic manipulation detection codes in the constant-error model''. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, Theory of Cryptography. Pages 481–501. Berlin, Heidelberg (2015). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​978-3-662-46494-6_20

[6] Peter W Shor. ``Scheme for reducing decoherence in quantum computer memory''. Physical review A 52, R2493 (1995).
https:/​/​doi.org/​10.1103/​PhysRevA.52.R2493

[7] A Robert Calderbank and Peter W Shor. ``Good quantum error-correcting codes exist''. Physical Review A 54, 1098 (1996).
https:/​/​doi.org/​10.1103/​PhysRevA.54.1098

[8] Daniel Gottesman. ``Stabilizer codes and quantum error correction''. PhD thesis. Caltech. (1997). url: https:/​/​thesis.library.caltech.edu/​2900/​2/​THESIS.pdf.
https:/​/​thesis.library.caltech.edu/​2900/​2/​THESIS.pdf

[9] A.Yu. Kitaev. ``Fault-tolerant quantum computation by anyons''. Annals of Physics 303, 2–30 (2003).
https:/​/​doi.org/​10.1016/​s0003-4916(02)00018-0

[10] Andrew M Steane. ``Error correcting codes in quantum theory''. Physical Review Letters 77, 793 (1996).
https:/​/​doi.org/​10.1103/​PhysRevLett.77.793

[11] Gorjan Alagic and Christian Majenz. ``Quantum non-malleability and authentication''. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology – CRYPTO 2017. Pages 310–341. Cham (2017). Springer International Publishing.
https:/​/​doi.org/​10.1007/​978-3-319-63715-0_11

[12] Andris Ambainis, Jan Bouda, and Andreas Winter. ``Nonmalleable encryption of quantum information''. Journal of Mathematical Physics 50, 042106 (2009).
https:/​/​doi.org/​10.1063/​1.3094756

[13] A. Broadbent and Sébastien Lord. ``Uncloneable quantum encryption via random oracles''. IACR Cryptol. ePrint Arch. 2019, 257 (2019).
https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2020.4

[14] Daniel Gottesman. ``Uncloneable encryption''. Quantum Info. Comput. 3, 581–602 (2003).
https:/​/​doi.org/​10.26421/​qic3.6-2

[15] Stefan Dziembowski, Krzysztof Pietrzak, and Daniel Wichs. ``Non-malleable codes''. J. ACM 65 (2018).
https:/​/​doi.org/​10.1145/​3178432

[16] Mihir Bellare, David Cash, and Rachel Miller. ``Cryptography secure against related-key attacks and tampering''. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology – ASIACRYPT 2011. Pages 486–503. Berlin, Heidelberg (2011). Springer Berlin Heidelberg.

[17] Mihir Bellare and David Cash. ``Pseudorandom functions and permutations provably secure against related-key attacks''. In Tal Rabin, editor, Advances in Cryptology – CRYPTO 2010. Pages 666–684. Berlin, Heidelberg (2010). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​978-3-642-14623-7_36

[18] Mihir Bellare and Tadayoshi Kohno. ``A theoretical treatment of related-key attacks: Rka-prps, rka-prfs, and applications''. In Eli Biham, editor, Advances in Cryptology — EUROCRYPT 2003. Pages 491–506. Berlin, Heidelberg (2003). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​3-540-39200-9_31

[19] Mihir Bellare, Kenneth G. Paterson, and Susan Thomson. ``Rka security beyond the linear barrier: Ibe, encryption and signatures''. In Xiaoyun Wang and Kazue Sako, editors, Advances in Cryptology – ASIACRYPT 2012. Pages 331–348. Berlin, Heidelberg (2012). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​978-3-642-34961-4_21

[20] Sebastian Faust, Krzysztof Pietrzak, and Daniele Venturi. ``Tamper-proof circuits: How to trade leakage for tamper-resilience''. In Luca Aceto, Monika Henzinger, and Jiří Sgall, editors, Automata, Languages and Programming. Pages 391–402. Berlin, Heidelberg (2011). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​978-3-642-22006-7_33

[21] Rosario Gennaro, Anna Lysyanskaya, Tal Malkin, Silvio Micali, and Tal Rabin. ``Algorithmic tamper-proof (atp) security: Theoretical foundations for security against hardware tampering''. In Moni Naor, editor, Theory of Cryptography. Pages 258–277. Berlin, Heidelberg (2004). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​978-3-540-24638-1_15

[22] Vipul Goyal, Adam O'Neill, and Vanishree Rao. ``Correlated-input secure hash functions''. In Yuval Ishai, editor, Theory of Cryptography. Pages 182–200. Berlin, Heidelberg (2011). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​978-3-642-19571-6_12

[23] Yuval Ishai, Manoj Prabhakaran, Amit Sahai, and David Wagner. ``Private circuits ii: Keeping secrets in tamperable circuits''. In Serge Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006. Pages 308–327. Berlin, Heidelberg (2006). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​11761679_19

[24] Yael Tauman Kalai, Bhavana Kanukurthi, and Amit Sahai. ``Cryptography with tamperable and leaky memory''. In Phillip Rogaway, editor, Advances in Cryptology – CRYPTO 2011. Pages 373–390. Berlin, Heidelberg (2011). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​978-3-642-22792-9_21

[25] Krzysztof Pietrzak. ``Subspace lwe''. In Ronald Cramer, editor, Theory of Cryptography. Pages 548–563. Berlin, Heidelberg (2012). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​978-3-642-28914-9_31

[26] Thiago Bergamaschi. ``Pauli manipulation detection codes and applications to quantum communication over adversarial channels'' (2023). Available at https:/​/​arxiv.org/​abs/​2304.06269.
arXiv:2304.06269

[27] Divesh Aggarwal, Naresh Goud Boddu, and Rahul Jain. ``Quantum secure non-malleable codes in the split-state model''. IEEE Transactions on Information Theory (2023).
https:/​/​doi.org/​10.1109/​TIT.2023.3328839

[28] Roman Vershynin. ``Introduction to the non-asymptotic analysis of random matrices'' (2010). arXiv:1011.3027.
arXiv:1011.3027

[29] Yinzheng Gu. ``Moments of random matrices and weingarten function'' (2013).
https:/​/​qspace.library.queensu.ca/​server/​api/​core/​bitstreams/​cee37ba4-2035-48e0-ac08-2974e082a0a9/​content

[30] Don Weingarten. ``Asymptotic behavior of group integrals in the limit of infinite rank''. Journal of Mathematical Physics 19, 999–1001 (1978).
https:/​/​doi.org/​10.1063/​1.523807

[31] Benoît Collins. ``Moments and cumulants of polynomial random variables on unitarygroups, the Itzykson-Zuber integral, and free probability''. International Mathematics Research Notices 2003, 953–982 (2003).
https:/​/​doi.org/​10.1155/​S107379280320917X

[32] Benoı̂t Collins and Piotr Śniady. ``Integration with Respect to the Haar Measure on Unitary, Orthogonal and Symplectic Group''. Communications in Mathematical Physics 264, 773–795 (2006). arXiv:math-ph/​0402073.
https:/​/​doi.org/​10.1007/​s00220-006-1554-3
arXiv:math-ph/0402073

[33] Naresh Goud Boddu, Vipul Goyal, Rahul Jain, and João Ribeiro. ``Split-state non-malleable codes and secret sharing schemes for quantum messages'' (2023). arXiv:2308.06466.
arXiv:2308.06466

Cited by

[1] Thiago Bergamaschi, "Pauli Manipulation Detection codes and Applications to Quantum Communication over Adversarial Channels", arXiv:2304.06269, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2023-11-26 16:15:44). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2023-11-26 16:15:42).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

Time Stamp:

More from Quantum Journal