Weak approximate unitary designs and applications to quantum encryption

Cécilia Lancien1 and Christian Majenz2

1Institut de Mathématiques de Toulouse & CNRS, Université Paul Sabatier, 118 route de Narbonne, F-31062 Toulouse Cedex 9, France.
2QuSoft and Centrum Wiskunde & Informatica, Science Park 123, 1098 XG Amsterdam, the Netherlands.

Abstract

Unitary $t$-designs are the bread and butter of quantum information theory and beyond. An important issue in practice is that of efficiently constructing good approximations of such unitary $t$-designs. Building on results by Aubrun (Comm. Math. Phys. 2009), we prove that sampling $d^t\mathrm{poly}(t,\log d, 1/\epsilon)$ unitaries from an exact $t$-design provides with positive probability an $\epsilon$-approximate $t$-design, if the error is measured in one-to-one norm. As an application, we give a randomized construction of a quantum encryption scheme that has roughly the same key size and security as the quantum one-time pad, but possesses the additional property of being non-malleable against adversaries without quantum side information.

Unitary designs play an important role in quantum information theory and
beyond. Applications include the ubiquitous decoupling technique in
quantum information theory, quantum encryption, randomized benchmarking
and more. In this article, we study a weaker form of approximate unitary
designs motivated by operations on isolated quantum systems. We show
that approximate unitary designs of much smaller size exist in this
restricted setting compared to the general setting. We exemplify the
usefulness of such objects by describing a construction of a quantum
encryption scheme that, in addition to ensuring confidentiality of a
message akin to the quantum one-time pad, protects the message against
tampering by attackers without (or with small) quantum memory.

► References

[1] 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

[2] Anura Abeyesinghe, Igor Devetak, Patrick Hayden, and Andreas Winter, The mother of all protocols: Restructuring quantum information's family tree'' Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 465, 2537–2563 (2009).
https:/​/​doi.org/​10.1098/​rspa.2009.0202

[3] Gorjan Alagic and Christian Majenz Quantum Non-malleability and Authentication'' Advances in Cryptology – CRYPTO 2017 310–341 (2017).
https:/​/​doi.org/​10.1007/​978-3-319-63715-0_11

[4] Gorjan Alagic, Christian Majenz, and Alexander Russell, Efficient simulation of random states and random unitaries'' Cryptology ePrint Archive, Report 2019/​1204 (2019).
https:/​/​eprint.iacr.org/​2019/​1204

[5] Andris Ambainis, Michele Mosca, Alain Tapp, and Ronald De Wolf, Private quantum channels'' Proceedings 41st Annual Symposium on Foundations of Computer Science 547–553 (2000).
https:/​/​doi.org/​10.1109/​SFCS.2000.892142

[6] Guillaume Aubrun On almost randomizing channels with a short Kraus decomposition'' Communications in Mathematical Physics 288, 1103–1116 (2009).
https:/​/​doi.org/​10.1007/​s00220-008-0695-y

[7] Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith, and Alain Tapp, Authentication of quantum messages'' The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. 449–458 (2002).
https:/​/​doi.org/​10.1109/​SFCS.2002.1181969

[8] Mario Berta, Matthias Christandl, and Renato Renner, The quantum reverse Shannon theorem based on one-shot information theory'' Communications in Mathematical Physics 306, 579–615 (2011).
https:/​/​doi.org/​10.1007/​s00220-011-1309-7

[9] Fernando G.S.L. Brandão, Aram W. Harrow, and Michał Horodecki, Local Random Quantum Circuits are Approximate Polynomial-Designs'' Communications in Mathematical Physics 346, 397–434 (2016).
https:/​/​doi.org/​10.1007/​s00220-016-2706-8

[10] Eiichi Bannai, Gabriel Navarro, Noelia Rizo, and Pham Huu Tiep, Unitary $t$-groups'' Journal of the Mathematical Society of Japan 72, 909–921 (2020).
https:/​/​doi.org/​10.2969/​jmsj/​82228222

[11] Matthias Christandl The structure of bipartite quantum states - Insights from group theory and cryptography'' thesis (2006).
http:/​/​arxiv.org/​abs/​quant-ph/​0604183

[12] Frédéric Dupuis, Mario Berta, Jürg Wullschleger, and Renato Renner, One-Shot Decoupling'' Communications in Mathematical Physics 328, 251–284 (2014).
https:/​/​doi.org/​10.1007/​s00220-014-1990-4

[13] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine, Exact and approximate unitary 2-designs and their application to fidelity estimation'' Physical Review A 80, 012304 (2009).
https:/​/​doi.org/​10.1103/​PhysRevA.80.012304

[14] William Fultonand Joe Harris Representation theory: a first course'' Springer (2013).

[15] Patrick Hayden, Michał Horodecki, Andreas Winter, and Jon Yard, A Decoupling Approach to the Quantum Capacity'' Open Systems & Information Dynamics 15, 7–19 (2008).
https:/​/​doi.org/​10.1142/​S1230161208000043

[16] Patrick Hayden, Debbie Leung, Peter W. Shor, and Andreas Winter, Randomizing Quantum States: Constructions and Applications'' Communications in Mathematical Physics 250, 371–391 (2004).
https:/​/​doi.org/​10.1007/​s00220-004-1087-6

[17] Michał Horodecki, Jonathan Oppenheim, and Andreas Winter, Quantum state merging and negative information'' Communications in Mathematical Physics 269, 107–136 (2007).

[18] Zhengfeng Ji, Yi-Kai Liu, and Fang Song, Pseudorandom Quantum States'' Advances in Cryptology – CRYPTO 2018 126–152 (2018).
https:/​/​doi.org/​10.1007/​978-3-319-96878-0_5

[19] Daniel Kane Small designs for path-connected spaces and path-connected homogeneous spaces'' Transactions of the American Mathematical Society 367, 6387–6414 (2015).
https:/​/​doi.org/​10.1090/​tran/​6250

[20] Cécilia Lancien and Andreas Winter Approximating quantum channels by completely positive maps with small Kraus rank'' Preprint (2017).
https:/​/​arxiv.org/​abs/​1711.00697

[21] Christian Majenz, Mario Berta, Frédéric Dupuis, Renato Renner, and Matthias Christandl, Catalytic Decoupling of Quantum Information'' Physical Review Letters 118, 080503 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.118.080503

[22] Christian Majenz, Christian Schaffner, and Jeroen van Wier, Non-malleability for quantum public-key encryption'' Cryptology ePrint Archive, Report 2019/​496 (2019).
https:/​/​eprint.iacr.org/​2019/​496

[23] Oleg Szehr, Frédéric Dupuis, Marco Tomamichel, and Renato Renner, Decoupling with unitary approximate two-designs'' New Journal of Physics 15, 053022 (2013).
https:/​/​doi.org/​10.1088/​1367-2630/​15/​5/​053022

[24] Paul D. Seymourand Thomas Zaslavsky Averaging sets: A generalization of mean values and spherical designs'' Advances in Mathematics 52, 213–240 (1984).
https:/​/​doi.org/​10.1016/​0001-8708(84)90022-7

[25] Zak Webb The Clifford group forms a unitary 3-design'' Quantum Information and Computation 16, 1379–1400 (2016).
https:/​/​doi.org/​10.26421/​QIC16.15-16

[26] Huangjun Zhu Multiqubit Clifford groups are unitary 3-designs'' Physical Review A 96, 062336 (2017).
https:/​/​doi.org/​10.1103/​PhysRevA.96.062336

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2021-08-01 06:01:23). On SAO/NASA ADS no data on citing works was found (last attempt 2021-08-01 06:01:23).