A Quantum Approach for Reducing Communications in Classical Cryptographic Primitives

• URL: http://arxiv.org/abs/2310.05213v2
• Date: Thu, 16 Nov 2023 01:58:04 GMT
• Title: A Quantum Approach for Reducing Communications in Classical Cryptographic Primitives
• Authors: Jiayu Zhang
• Abstract summary: We show that, perhaps surprisingly, it's possible to solve this problem with quantum techniques under much weaker assumptions. Our work conveys an interesting message that quantum cryptography could outperform classical cryptography in a new type of problems.
• Score: 2.3465488122819123
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: How could quantum cryptography help us achieve what are not achievable in classical cryptography? In this work we consider the following problem, which we call succinct RSPV for classical functions (SRC). Suppose $f$ is a function described by a polynomial time classical Turing machine, which is public; the client would like to sample a random $x$ as the function input and use a protocol to send $f(x)$ to the server. What's more, (1) when the server is malicious, what it knows in the passing space should be no more than $f(x)$; (2) the communication should be succinct (that is, independent to the running time of evaluating $f$). Solving this problem in classical cryptography seems to require strong cryptographic assumptions. We show that, perhaps surprisingly, it's possible to solve this problem with quantum techniques under much weaker assumptions. By allowing for quantum communication and computations, we give a protocol for this problem assuming only collapsing hash functions [Unr16]. Our work conveys an interesting message that quantum cryptography could outperform classical cryptography in a new type of problems, that is, to reduce communications in meaningful primitives without using heavy classical cryptographic assumptions.

Related papers

• Towards Unconditional Uncloneable Encryption [1.18749525824656]
  Uncloneable encryption is a cryptographic primitive which encrypts a classical message into a quantum ciphertext. We show that the adversary's success probability in the related security game converges quadratically as $1/2+1/ (2sqrtK)$, where $K$ represents the number of keys and $1/2$ is trivially achievable.
  arXiv  Detail & Related papers  (2024-10-30T14:40:06Z)
• Hybrid Quantum Cryptography from Communication Complexity [0.43695508295565777]
  We build a key distribution protocol called HM-QCT from the Hidden Matching problem. We show that the security of HM-QCT against arbitrary i.i.d. attacks can be reduced to the difficulty of solving the underlying Hidden Matching problem. Remarkably, the scheme remains secure with up to $mathcalObig( fracsqrtnlog(n)big)$ input photons for each channel use.
  arXiv  Detail & Related papers  (2023-11-15T18:03:15Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• Functional Encryption in the Bounded Storage Models [0.0]
  We investigate possibilities in the bounded quantum storage model (BQSM) and the bounded classical storage model (BCSM) In the BQSM, we construct non-interactive functional encryption satisfying information-theoretic simulation based security with $q=O(sqrts/r)$. In the BCSM, we construct non-interactive functional encryption satisfying information-theoretic subexponential simulation based security.
  arXiv  Detail & Related papers  (2023-09-13T03:55:36Z)
• 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)
• Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security [67.06003361150228]
  A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
  arXiv  Detail & Related papers  (2020-12-30T18:03:56Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• Security Limitations of Classical-Client Delegated Quantum Computing [54.28005879611532]
  A client remotely prepares a quantum state using a classical channel. Privacy loss incurred by employing $RSP_CC$ as a sub-module is unclear. We show that a specific $RSP_CC$ protocol can replace the quantum channel at least in some contexts.
  arXiv  Detail & Related papers  (2020-07-03T13:15:13Z)
• Succinct Blind Quantum Computation Using a Random Oracle [0.8702432681310399]
  We give a new universal blind quantum computation protocol. The protocol's first phase is succinct, that is, its complexity is independent of circuit size.
  arXiv  Detail & Related papers  (2020-04-27T07:47:11Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• Fault tolerant quantum data locking [0.0]
  We present a quantum data locking protocol that employs pseudo-random circuits consisting of Clifford gates only. We show that information can be encrypted into $n$-qubit code words using order $n. As an application, we discuss an efficient method for encrypting the output of a quantum computer.
  arXiv  Detail & Related papers  (2020-03-25T16:07:41Z)

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.