Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols

• URL: http://arxiv.org/abs/2308.09704v1
• Date: Fri, 18 Aug 2023 17:55:37 GMT
• Title: Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Authors: Salvatore Mandr\`a, Gianni Mossi, Eleanor G. Rieffel
• Abstract summary: We present a novel method to generate hard instances with planted solutions based on the public-private McEliece post-quantum cryptographic protocol. Our protocol is suitable to test and evaluate quantum devices without the risk of "backdoors" being exploited.
• Score: 0.3522950356329992
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we present a novel method to generate hard instances with planted solutions based on the public-private McEliece post-quantum cryptographic protocol. Unlike other planting methods rooted in the infinite-size statistical analysis, our cryptographic protocol generates instances which are all hard (in cryptographic terms), with the hardness tuned by the size of the private key, and with a guaranteed unique ground state. More importantly, because of the private-public key protocol, planted solutions cannot be easily recovered by a direct inspection of the planted instances without the knowledge of the private key used to generate them, therefore making our protocol suitable to test and evaluate quantum devices without the risk of "backdoors" being exploited.

Related papers

• Provably Secure Public-Key Steganography Based on Admissible Encoding [66.38591467056939]
  The technique of hiding secret messages within seemingly harmless covertext is known as provably secure steganography (PSS) PSS evolves from symmetric key steganography to public-key steganography, functioning without the requirement of a pre-shared key. This paper proposes a more general elliptic curve public key steganography method based on admissible encoding.
  arXiv  Detail & Related papers  (2025-04-28T03:42:25Z)
• Performance of Practical Quantum Oblivious Key Distribution [0.7528462379265576]
  We propose a practical realization of randomized quantum oblivious transfer. We show that the protocol is secure under an indistinguishability-based notion of security.
  arXiv  Detail & Related papers  (2025-01-07T18:24:06Z)
• Seedless Extractors for Device-Independent Quantum Cryptography [0.0]
  Device-independent (DI) quantum cryptography aims at providing secure cryptography with minimal trust in, or characterisation of, the underlying quantum devices. An essential step in DI protocols is randomness extraction (or privacy amplification) which requires the honest parties to have a seed of additional bits with sufficient entropy and statistical independence of any bits generated during the protocol. In this work we introduce a method for extraction in DI protocols which does not require a seed and is secure against computationally unbounded quantum adversary.
  arXiv  Detail & Related papers  (2024-03-07T18:07:52Z)
• Coding-Based Hybrid Post-Quantum Cryptosystem for Non-Uniform Information [53.85237314348328]
  We introduce for non-uniform messages a novel hybrid universal network coding cryptosystem (NU-HUNCC) We show that NU-HUNCC is information-theoretic individually secured against an eavesdropper with access to any subset of the links.
  arXiv  Detail & Related papers  (2024-02-13T12:12:39Z)
• A Privacy-preserving key transmission protocol to distribute QRNG keys using zk-SNARKs [2.254434034390528]
  Quantum Random Number Generators can provide high-quality keys for cryptographic algorithms. Existing Entropy-as-a-Service solutions require users to trust the central authority distributing the key material. We present a novel key transmission protocol that allows users to obtain cryptographic material generated by a QRNG in such a way that the server is unable to identify which user is receiving each key.
  arXiv  Detail & Related papers  (2024-01-29T14:00:37Z)
• Entropy Accumulation under Post-Quantum Cryptographic Assumptions [4.416484585765028]
  In device-independent (DI) quantum protocols, the security statements are oblivious to the characterization of the quantum apparatus. We present a flexible framework for proving the security of such protocols by utilizing a combination of tools from quantum information theory.
  arXiv  Detail & Related papers  (2023-07-02T12:52:54Z)
• 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)
• Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive Privacy Analysis and Beyond [57.10914865054868]
  We consider vertical logistic regression (VLR) trained with mini-batch descent gradient. We provide a comprehensive and rigorous privacy analysis of VLR in a class of open-source Federated Learning frameworks.
  arXiv  Detail & Related papers  (2022-07-19T05:47:30Z)
• Data post-processing for the one-way heterodyne protocol under composable finite-size security [62.997667081978825]
  We study the performance of a practical continuous-variable (CV) quantum key distribution protocol. We focus on the Gaussian-modulated coherent-state protocol with heterodyne detection in a high signal-to-noise ratio regime. This allows us to study the performance for practical implementations of the protocol and optimize the parameters connected to the steps above.
  arXiv  Detail & Related papers  (2022-05-20T12:37:09Z)
• Certified Random Number Generation from Quantum Steering [1.0820909926464386]
  Certified randomness protocols have been developed which remove the need for trust in devices by taking advantage of nonlocality. Here, we use a photonic platform to implement our protocol, which operates in the quantum steering scenario. We demonstrate an approach for a steering-based generator of public or private randomness, and the first generation of certified random bits, with the detection loophole closed.
  arXiv  Detail & Related papers  (2021-11-18T03:49:43Z)
• Composably secure data processing for Gaussian-modulated continuous variable quantum key distribution [58.720142291102135]
  Continuous-variable quantum key distribution (QKD) employs the quadratures of a bosonic mode to establish a secret key between two remote parties. We consider a protocol with homodyne detection in the general setting of composable finite-size security. In particular, we analyze the high signal-to-noise regime which requires the use of high-rate (non-binary) low-density parity check codes.
  arXiv  Detail & Related papers  (2021-03-30T18:02:55Z)
• Bell nonlocality is not sufficient for the security of standard device-independent quantum key distribution protocols [1.9573380763700712]
  Device-independent quantum key distribution is a secure quantum cryptographic paradigm that allows two honest users to establish a secret key. We show that no protocol of this form allows for establishing a secret key when implemented on any correlation obtained by measuring local projective measurements.
  arXiv  Detail & Related papers  (2021-03-03T19:10:06Z)
• Entanglement purification by counting and locating errors with entangling measurements [62.997667081978825]
  We consider entanglement purification protocols for multiple copies of qubit states. We use high-dimensional auxiliary entangled systems to learn about number and positions of errors in the noisy ensemble.
  arXiv  Detail & Related papers  (2020-11-13T19:02:33Z)

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.