On the Equivalence between Classical Position Verification and Certified Randomness

• URL: http://arxiv.org/abs/2410.03982v3
• Date: Wed, 18 Jun 2025 14:38:30 GMT
• Title: On the Equivalence between Classical Position Verification and Certified Randomness
• Authors: Fatih Kaleoglu, Minzhao Liu, Kaushik Chakraborty, David Cui, Omar Amer, Marco Pistoia, Charles Lim,
• Abstract summary: Gate-based quantum computers hold enormous potential to accelerate classically intractable computational tasks.<n>For a long time, it remained challenging to demonstrate the quantum utility of Random circuit sampling on practical problems.<n>Recently, leveraging RCS, an interactive protocol generating certified randomness was demonstrated using a trapped ion quantum computer.
• Score: 1.5391321019692432
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Gate-based quantum computers hold enormous potential to accelerate classically intractable computational tasks. Random circuit sampling (RCS) is the only known task that has been able to be experimentally demonstrated using current-day NISQ devices. However, for a long time, it remained challenging to demonstrate the quantum utility of RCS on practical problems. Recently, leveraging RCS, an interactive protocol generating certified randomness was demonstrated using a trapped ion quantum computer, advancing the practical utility of near-term gate-based quantum computers. In this work, we establish a strong connection between certified randomness and another quantum computation classical communication primitive, classically verifiable position verification (CVPV), which circumvents the practical challenges that may arise from long-distance quantum communications. We provide a new generic compiler that can convert any single-round proof of quantumness based certified randomness protocol into a secure classical communication-based position verification scheme. Later, we extend our compiler to different types of multi-round protocols. Notably, our compiler can be applied to any multi-round certified randomness protocol that can be analyzed using the entropy accumulation theorem, making its applicability very general. Moreover, we show that CVPV is equivalent to a relaxed variant of certified randomness that we define. We instantiate each of our compilers using existing certified randomness protocols. In particular, building on the work of Aaronson and Hung (STOC '23), we give a NISQ-friendly instantiation based on RCS, which was experimentally demonstrated by Liu et al.. Hence, we show that CVPV is another application within reach of NISQ devices.

Related papers

• Enhanced Simultaneous Quantum-Classical Communications Under Composable Security [0.2982610402087727]
  Simultaneous quantum-classical communications (SQCC) protocols allow for quantum and classical symbols to be integrated concurrently on the same optical pulse and mode.<n>We address security concerns inherently associated with SQCC schemes and provide an updated model of the coupling between the classical and quantum channels.
  arXiv  Detail & Related papers  (2025-05-06T03:40:48Z)
• Certified randomness using a trapped-ion quantum processor [4.744766948199187]
  We demonstrate the generation of certifiably random bits using a trapped-ion quantum computer accessed over the internet.<n>We analyze the security of our protocol against a restricted class of realistic near-term adversaries.
  arXiv  Detail & Related papers  (2025-03-26T12:38:22Z)
• Quantum Rewinding for IOP-Based Succinct Arguments [45.5096562396529]
  We prove that an interactive variant of the BCS transformation is secure in the standard model against quantum adversaries when the vector commitment scheme is collapsing. As a consequence of our results, we obtain standard-model post-quantum secure succinct arguments with the best complexity known.
  arXiv  Detail & Related papers  (2024-11-08T06:33:08Z)
• Practical hybrid PQC-QKD protocols with enhanced security and performance [44.8840598334124]
  We develop hybrid protocols by which QKD and PQC inter-operate within a joint quantum-classical network. In particular, we consider different hybrid designs that may offer enhanced speed and/or security over the individual performance of either approach.
  arXiv  Detail & Related papers  (2024-11-02T00:02:01Z)
• Towards efficient and secure quantum-classical communication networks [47.27205216718476]
  There are two primary approaches to achieving quantum-resistant security: quantum key distribution (QKD) and post-quantum cryptography (PQC) We introduce the pros and cons of these protocols and explore how they can be combined to achieve a higher level of security and/or improved performance in key distribution. We hope our discussion inspires further research into the design of hybrid cryptographic protocols for quantum-classical communication networks.
  arXiv  Detail & Related papers  (2024-11-01T23:36:19Z)
• Single-Round Proofs of Quantumness from Knowledge Assumptions [41.94295877935867]
  A proof of quantumness is an efficiently verifiable interactive test that an efficient quantum computer can pass. Existing single-round protocols require large quantum circuits, whereas multi-round ones use smaller circuits but require experimentally challenging mid-circuit measurements. We construct efficient single-round proofs of quantumness based on existing knowledge assumptions.
  arXiv  Detail & Related papers  (2024-05-24T17:33:10Z)
• Increasing Interference Detection in Quantum Cryptography using the Quantum Fourier Transform [0.0]
  We present two quantum cryptographic protocols leveraging the quantum Fourier transform (QFT) The foremost of these protocols is a novel QKD method that leverages this effectiveness of the QFT. We additionally show how existing quantum encryption methods can be augmented with a QFT-based approach to improve eavesdropping detection.
  arXiv  Detail & Related papers  (2024-04-18T21:04:03Z)
• 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)
• The Evolution of Quantum Secure Direct Communication: On the Road to the Qinternet [49.8449750761258]
  Quantum secure direct communication (QSDC) is provably secure and overcomes the threat of quantum computing. We will detail the associated point-to-point communication protocols and show how information is protected and transmitted.
  arXiv  Detail & Related papers  (2023-11-23T12:40:47Z)
• 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)
• Practical quantum secure direct communication with squeezed states [55.41644538483948]
  We report the first table-top experimental demonstration of a CV-QSDC system and assess its security. This realization paves the way into future threat-less quantum metropolitan networks, compatible with coexisting advanced wavelength division multiplexing (WDM) systems.
  arXiv  Detail & Related papers  (2023-06-25T19:23:42Z)
• Multi-User Entanglement Distribution in Quantum Networks Using Multipath Routing [55.2480439325792]
  We propose three protocols that increase the entanglement rate of multi-user applications by leveraging multipath routing. The protocols are evaluated on quantum networks with NISQ constraints, including limited quantum memories and probabilistic entanglement generation.
  arXiv  Detail & Related papers  (2023-03-06T18:06:00Z)
• From Auditable Quantum Authentication to Best-of-Both-Worlds Multiparty Quantum Computation with Public Verifiable Identifiable Abort [0.5076419064097734]
  We construct the first secure multiparty quantum computation with public verifiable identifiable abort (MPQC-PVIA) protocol. MPQC is the first quantum setting to provide Best-of-Both-Worlds (BoBW) security, which attains full security with an honest majority.
  arXiv  Detail & Related papers  (2022-11-03T09:12:48Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  "Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation. We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
  arXiv  Detail & Related papers  (2021-12-09T19:00:00Z)
• On Certified Randomness from Fourier Sampling or Random Circuit Sampling [0.1631115063641726]
  Certified randomness has a long history in quantum information, with many potential applications. Aaronson proposed a novel public certified randomness protocol based on existing random circuit sampling (RCS) experiments. We study certified randomness in the quantum random oracle model (QROM)
  arXiv  Detail & Related papers  (2021-11-29T18:51:50Z)
• On the Connection Between Quantum Pseudorandomness and Quantum Hardware Assumptions [1.4174475093445233]
  This paper addresses the questions related to the connections between the quantum pseudorandomness and quantum hardware assumptions. We show that the efficient pseudorandom quantum states (PRS) are sufficient to construct the challenge set for the universally unforgeable qPUF. As an application of our results, we show that the efficiency of an existing qPUF-based client-server identification protocol can be improved without losing the security requirements.
  arXiv  Detail & Related papers  (2021-10-22T11:55:06Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• Quantum Secure Direct Communication with Mutual Authentication using a Single Basis [2.9542356825059715]
  We propose a new theoretical scheme for quantum secure direct communication (QSDC) with user authentication. The present protocol uses only one orthogonal basis of single-qubit states to encode the secret message. We discuss the security of the proposed protocol against some common attacks and show that no eaves-dropper can get any information from the quantum and classical channels.
  arXiv  Detail & Related papers  (2021-01-10T16:32:42Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Forging quantum data: classically defeating an IQP-based quantum test [0.0]
  We describe a classical algorithm that can convince the verifier that the (classical) prover is quantum. We show that the key extraction algorithm is efficient in practice for problem sizes of hundreds of qubits.
  arXiv  Detail & Related papers  (2019-12-11T19:00:00Z)

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.