Nonlocal Games Through Communication Complexity and Quantum Cryptography

• URL: http://arxiv.org/abs/2510.09457v1
• Date: Fri, 10 Oct 2025 15:07:24 GMT
• Title: Nonlocal Games Through Communication Complexity and Quantum Cryptography
• Authors: Pierre Botteron,
• Abstract summary: This thesis explores foundational aspects of quantum information theory and quantum cryptography.<n>We aim to distinguish quantum correlations from non-signaling correlations by leveraging the principle of communication complexity.<n>We aim to construct an encryption scheme that prevents two distant parties from simultaneously obtaining information about a shared message.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This thesis explores foundational aspects of quantum information theory and quantum cryptography. First, we investigate quantum correlations in interactive settings, including the CHSH and graph isomorphism games. We aim to distinguish quantum correlations from non-signaling correlations by leveraging the principle of communication complexity. To this end, we employ techniques such as distributed computation, majority-function-based distillation protocols, the algebraic and geometric properties of nonlocal box wirings, and variations of some graph properties such as isomorphism, transitivity, and equitable partitions. This inquiry advances our understanding of non-physical correlations. Second, we address a key open problem in cryptography: the feasibility of unclonable encryption. We aim to construct an encryption scheme that prevents two distant parties from simultaneously obtaining information about a shared encrypted message. We introduce a candidate for unclonable encryption in the plain model, i.e. without assumptions, in working towards an unconditional proof. Our protocol is based on Clifford algebra, utilizing complex Hermitian unitary matrices that anti-commute. For small key sizes, we rigorously prove security using sum-of-squares methods, while for larger key sizes, we provide strong numerical evidence via the NPA hierarchy.

Related papers

• Computational Quantum Anamorphic Encryption and Quantum Anamorphic Secret-Sharing [0.0]
  The concept of anamorphic encryption, first formally introduced by Persiano et al., enables embedding covert messages within ciphertexts.<n>We present a quantum analogue of the classical anamorphic encryption definition based on public-key encryption.<n>We extend the work of akan et al. on computational quantum secret-sharing to computational quantum anamorphic secret-sharing.
  arXiv  Detail & Related papers  (2025-11-22T05:39:54Z)
• Isogeny Graphs in Superposition and Quantum Onion Routing [1.6321617803073527]
  Onion routing provides anonymity by layering encryption so that no relay can link sender to destination.<n>We propose a symmetric-enion-based quantum onion routing scheme by instantiating each layer with the abelian ideal class group action from the Theory of Complex multiplication.
  arXiv  Detail & Related papers  (2025-10-01T21:15:22Z)
• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  Quantum computers will be able to break modern cryptographic systems using Shor's Algorithm.<n>We first examine the McEliece cryptosystem, a code-based scheme believed to be secure against quantum attacks.<n>We then explore NTRU, a lattice-based system grounded in the difficulty of solving the Shortest Vector Problem.
  arXiv  Detail & Related papers  (2025-05-06T03:42:38Z)
• Homomorphic Encryption Based on Lattice Post-Quantum Cryptography [0.0]
  Homomorphic encryption methods are vulnerable to quantum computing attacks.<n>This study proposes a lattice-based post-quantum homomorphic encryption scheme.<n>The findings are intended to serve as a reference for developers of homomorphic encryption applications.
  arXiv  Detail & Related papers  (2024-12-23T05:30:44Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• QPP and HPPK: Unifying Non-Commutativity for Quantum-Secure Cryptography with Galois Permutation Group [0.0]
  We leverage two novel primitives: the Quantum Permutation Pad (QPP) for symmetric key encryption and the Homomorphic Polynomial Public Key (HPPK) for Key Encapsulation Mechanism (KEM) and Digital Signatures (DS) QPP achieves quantum-secure symmetric key encryption, seamlessly extending Shannon's perfect secrecy to both classical and quantum-native systems. HPPK, free from NP-hard problems, fortifies symmetric encryption for the plain public key.
  arXiv  Detail & Related papers  (2024-02-02T19:10:43Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
  arXiv  Detail & Related papers  (2022-05-07T03:15:15Z)
• Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
  We construct the first fully homomorphic encryption scheme with certified deletion. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
  arXiv  Detail & Related papers  (2022-03-03T10:07:32Z)
• A quantum encryption design featuring confusion, diffusion, and mode of operation [0.0]
  We propose a non-OTP quantum encryption scheme utilizing a quantum state creation process to encrypt messages. As essentially a non-OTP quantum block cipher the method stands out against existing methods with the following features.
  arXiv  Detail & Related papers  (2020-10-06T22:23:30Z)
• Backflash Light as a Security Vulnerability in Quantum Key Distribution Systems [77.34726150561087]
  We review the security vulnerabilities of quantum key distribution (QKD) systems. We mainly focus on a particular effect known as backflash light, which can be a source of eavesdropping attacks.
  arXiv  Detail & Related papers  (2020-03-23T18:23:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.