RT Journal Article
T1 Geometry of Banach Spaces: A New Route Towards Position Based Cryptography
A1 Junge, Marius
A1 Kubicki, Alexander M.
A1 Palazuelos Cabezón, Carlos
A1 Pérez García, David
AB In this work we initiate the study of position based quantum cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. Known upper bounds for that quantity are exponential in the size of the quantum systems manipulated in the honest implementation of the protocol. However, known lower bounds are only linear. In order to deepen the understanding of this question, here we propose a position verification (PV) protocol and find lower bounds on the resources needed to break it. The main idea behind the proof of these bounds is the understanding of cheating strategies as vector valued assignments on the Boolean hypercube. Then, the bounds follow from the understanding of some geometric properties of particular Banach spaces, their type constants. Under some regularity assumptions on the former assignment, these bounds lead to exponential lower bounds on the quantum resources employed, clarifying the question in this restricted case. Known attacks indeed satisfy the assumption we make, although we do not know how universal this feature is. Furthermore, we show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol. Unfortunately, we were not able to estimate the relevant type constant. Despite that, we conjecture an upper bound for this quantity and show some evidence supporting it. A positive solution of the conjecture would lead to stronger security guarantees for the proposed PV protocol providing a better understanding of the question asked above.
PB Springer Nature
SN 0010-3616
YR 2022
FD 2022-06-02
LK https://hdl.handle.net/20.500.14352/71650
UL https://hdl.handle.net/20.500.14352/71650
LA eng
NO 1. Malaney, R.: The quantum car. IEEE Wirel. Commun. Lett. 5.6, 624–627 (2016). https://doi.org/10.1109/LWC.2016.26077402. Beigi, S., Köonig, R.: Simplified instantaneous non-local quantum computation with applications to position-based cryptography. New J. Phys. 13.9, 093036 (2011). https://doi.org/10.1088/1367-2630/13/9/0930363. Speelman, F.: Instantaneous non-local computation of low T-depth quantum circuits (2015). arXiv:1511.02839 [quant-ph]4. Buhrman, H., Fehr, S., Schaffner, C., Speelman, F.: The garden-hose model. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science—ITCS ’13 (2013). https://doi.org/10.1145/2422436.24224555. May, A.: Quantum tasks in holography (2019). arXiv:1902.06845 [hep-th]6. May, A., Penington, G., Sorce, J.: Holographic scattering requires a connected entanglement wedge. J. High Energy Phys. 2020, 8 (2020). https://doi.org/10.1007/JHEP08(2020)1327. Chandran, N., Goyal, V., Moriarty, R., Ostrovsky, R.: Position based cryptography. In: CRYPTO2009, pp. 391–407 (2009). https://doi.org/10.1007/978-3-642-03356-8_238. Kent, A., Munro, W.J., Spiller, T.P.: Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Phys. Rev. A 84(1) (2011). https://doi.org/10.1103/PhysRevA.84.012326. ISSN: 1094-16229. Buhrman, H., Chandran, N., Fehr, S., Gelles, R., Goyal, V., Ostrovsky, R., Schaffner, C.: Position-based quantum cryptography: impossibility and constructions. In: Rogaway, P. (ed.) Advances in Cryptology—CRYPTO 2011, pp. 429–446. Springer, Berlin (2011)10. Vaidman, L.: Instantaneous measurement of nonlocal variables. Phys. Rev. Lett. (2003). https://doi.org/10.1103/PhysRevLett.90.01040211. Tomamichel, M., Fehr, S., Kaniewski, J., Wehner, S.: A monogamy-of-entanglement game with applications to device-independent quantum cryptography. New J. Phys. 15(10), 103002 (2013). https://doi.org/10.1088/1367-2630/15/10/10300212. Unruh, D.: Quantum position verification in the random oracle model. In: Garay, J.A., Gennaro, R. (eds.) Advances in Cryptology—CRYPTO 2014, pp. 1–18. Springer, Berlin (2014)13. Bluhm, A., Christandl, M., Speelman, F.: Position-based cryptography: single-qubit protocol secure against multi-qubit attacks (2021). arXiv:2104.06301 [quant-ph]14. Kubicki, A.M., Palazuelos, C., Pérez-García, D.: Resource quantification for the no-programing theorem. Phys. Rev. Lett. 122(8) (2019). https://doi.org/10.1103/physrevlett.122.080505. ISSN: 1079-711415. Nielsen, M.A., Chuang, I.L.: Programmable quantum gate arrays. Phys. Rev. Lett. 79(2), 321–324 (1997). https://doi.org/10.1103/PhysRevLett.79.32116. Pisier, G.: Random series of trace class operators. In: Proceedings Cuarto CLAPEM Mexico 1990. Contribuciones en probabilidad y estadistica matematica, pp. 29–42 (1990). arXiv:1103.209017. Kubicki, A.M.: Local Banach space theory and resource quantification in Quantum Information Processing. PhD thesis. Faculty of Mathematical Sciences, Universitat de València, (2021). https://roderic.uv.es/bitstream/handle/10550/80380/Thesis_AMKubicki.pdf?sequence=1&isAllowed=y18. Pietsch, A.: Eigenvalues and S-numbers. Cambridge University Press, Cambridge (1986)19. Defant, A., Floret, K.: Tensor Norms and Operator Ideals. North-Holland, Amsterdam (1993)20. Effros, E.G., Ruan, Z.-J.: Operator Spaces. Oxford University Press, Oxford (2000)21. Pisier, G.: The Volume of Convex Bodies and Banach Space Geometry. Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge (1989). https://doi.org/10.1017/CBO978051166245422. Bergh, J., Löfström, J.: Interpolation Spaces. Springer, Berlin (1976). ISBN: 978-3-642-66451-923. Triebel, H.: Interpolation Theory, Function Spaces, Differential Operators. North-Holland Publishing Company, Amsterdam (1978)24. Pisier, G.: Non-commutative vector valued Lp-spaces and completely p-summing maps. In: Asterique 247 (1998). http://www.numdam.org/issue/AST_1998__247__R1_0.pdf25. Tomczak-Jaegermann, N.: Banach-Mazur Distances and Finite-Dimensional Operator Ideals, vol. 38. Pitman Monographs, Surveys in Pure, and Applied Mathematics, p. 395 (1989)26. Kahane, J.P.: Some Random Series of Functions. Cambridge University Press, Cambridge (1993)27. Maurey, B.: Type, cotype and K-convexity. In: Handbook of the Geometry of Banach Spaces, vol. 2, pp. 1299– 1332. North-Holland (2003)28. Pisier, G.: On the duality between type and cotype. In: Chao, J.-A., Woyczy ´nski, W.A. (eds.) Martingale Theory in Harmonic Analysis and Banach Spaces, pp. 131–144. Springer, Berlin (1982)29. Pisie, G.: Probabilistic methods in the geometry of Banach spaces. In: Letta, G., Pratelli, M. (eds.)Probability and Analysis, pp. 167–241. Springer, Berlin (1986)30. Pisier, G.: Factorization of operator valued analytic functions. In: Advances in Mathematics 93.1 (1992),pp 61–125. https://doi.org/10.1016/0001-8708(92)90025-G. ISSN: 0001-870831. Randrianantoanina, N.: Non-commutative martingale transforms. J Funct Anal 194(1), 181–212 (2002).https://doi.org/10.1006/jfan.2002.395232. Burkholder, D.L.: A geometrical characterization of banach spaces in which martingale difference sequences are unconditional. Ann. Probab. 9(6), 997–1011 (1981)33. Burkholder, D.L.: Martingales and Fourier analysis in Banach spaces. In: Letta, G., Pratelli, M. (eds.) Probability and Analysis, pp. 61–108. Springer, Berlin (1986)34. Busch, P., Lahti, P., Pellonpää, J.-P., Ylinen, K.: Quantum Measurement. Springer, Switzerland (2016).https://doi.org/10.1007/978-3-319-43389-935. Stinespring,W.F.: Positive Functions on C*-Algebras. In: Proceedings of the American Mathematical Society 6.2 (1955), 211–216. issn: 00029939, 10886826. http://www.jstor.org/stable/203234236. Grothendieck, A.:. Résumé de la théorie métrique des produits tensoriels topologiques. In: Boletim Da Sociedades de Matemática de Sao Paulo 8:1 (1953)37. Krivine, J. L.: Constantes de Grothendieck et fonctions de type positif sur les sphères. fr. In: Séminaire d’Analyse fonctionnelle (dit “Maurey-Schwartz”) (1977-1978). talk:1 et 2. http://www.numdam.org/item/SAF_1977-1978____A1_0/38. Regev, O., Vidick, T.: Quantum XOR games. ACM Trans. Comput. Theory 7.4, 1–43 (2015). https://doi.org/10.1145/279956039. Hoeffding,W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301),13–30 (1963)40. Le Merdy, C.: The Schatten space S4 is a Q-algebra. Proc. Am. Math. Soc. 126(3), 715–719 (1998)41. Michal, A.D., Wyman, M.: Characterization of complex couple spaces. Engl. Ann. Math. (2) 42, 247–250 (1941)42. Taylor, A.E.: Analysis in complex Banach spaces. Engl. Bull. Am. Math. Soc. 49, 652–669 (1943)43. Wenzel, J.: Real and complex operator ideals. Quaest. Math. 18(1–3), 271–285 (1995). https://doi.org/10.1080/16073606.1995.963180044. Muñoz, G., Sarantopoulos, Y., Tonge, A.: Complexifications of real Banach spaces, polynomials andmultilinear maps. Eng. Studia Math. 134(1), 1–33 (1999)45. Wenzel, J.: A supplement to my paper on real and complex operator ideals. Quaest. Math. 20.4, 663–665 (1997). https://doi.org/10.1080/16073606.1997.963223346. Szarek, S.: Kashins Almost Euclidean Orthogonal Decomposition of L1 fng. Bull. Acad. Polon. Sci. Ser. Sci. Math. Astron. Phys. 26(8), 691–694 (1978)47. Szarek, S., Tomczak-Jaegermann, N.: On nearly euclidean decomposition for some classes of Banach spaces. Compos. Math. 40(3), 367–385 (1980)48. Bourgain, J., Milman, V.D.: New volume ratio properties for convex symmetric bodies in Rn. Invent. Math. 88(2), 319–340 (1987)49. Giladi, O., Prochno, J., Schütt, C., Tomczak-Jaegermann, N., Werner, E.: On the geometry of projective tensor products. J. Funct. Anal. 273(2), 471–495 (2017). https://doi.org/10.1016/j.jfa.2017.03.01950. Defant, A., Mastyło, M., Michels, C.: Summing norms of identities between unitary ideals. Math. Z. 252, 863–882 (2006). https://doi.org/10.1007/s00209-005-0893-751. Chevet, S: Séries de variables aléatoires gaussiennes à valeurs dans E⊗ˆϵ F. Application aux produits d’espaces de Wiener abstraits. In: Séminaire Analyse fonctionnelle (“dit Maurey-Schwartz”), pp. 1–15 (1978). http://www.numdam.org/item/SAF_1977-1978____A14_0/52. Kliesch, A., König, R.: Continuum limits of homogeneous binary trees and the Thompson group. Phys. Rev. Lett. (2020). https://doi.org/10.1103/PhysRevLett.124.01060153. Jones, V.F.: A no-go theorem for the continuum limit of a periodic quantum spin chain. Commun. Math. Phys. 357(1), 295–317 (2018). https://doi.org/10.1007/s00220-017-2945-3
NO CRUE-CSIC (Acuerdos Transformativos 2022)
NO Unión Europea. Horizonte 2020
NO Ministerio de Ciencia e Innovación (MICINN)
NO Comunidad de Madrid
DS Docta Complutense
RD 1 may 2024