Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                



Dates are inconsistent

Dates are inconsistent

26 results sorted by ID

2024/1822 (PDF) Last updated: 2024-11-07
Anonymous Public-Key Quantum Money and Quantum Voting
Alper Çakan, Vipul Goyal, Takashi Yamakawa
Foundations

Quantum information allows us to build quantum money schemes, where a bank can issue banknotes in the form of authenticatable quantum states that cannot be cloned or counterfeited: a user in possession of k banknotes cannot produce k +1 banknotes. Similar to paper banknotes, in existing quantum money schemes, a banknote consists of an unclonable quantum state and a classical serial number, signed by bank. Thus, they lack one of the most fundamental properties cryptographers look for in a...

2024/1820 (PDF) Last updated: 2024-11-06
On the Power of Oblivious State Preparation
James Bartusek, Dakshita Khurana
Cryptographic protocols

We put forth Oblivious State Preparation (OSP) as a cryptographic primitive that unifies techniques developed in the context of a quantum server interacting with a classical client. OSP allows a classical polynomial-time sender to input a choice of one out of two public observables, and a quantum polynomial-time receiver to recover an eigenstate of the corresponding observable -- while keeping the sender's choice hidden from any malicious receiver. We obtain the following results: - The...

2024/1785 (PDF) Last updated: 2024-11-01
A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire
John Bostanci, Barak Nehoran, Mark Zhandry
Public-key cryptography

Aaronson, Atia, and Susskind [Aaronson et al., 2020] established that efficiently mapping between quantum states $\ket{\psi}$ and $\ket{\phi}$ is computationally equivalent to distinguishing their superpositions $\frac{1}{\sqrt{2}}(|\psi\rangle + |\phi\rangle)$ and $\frac{1}{\sqrt{2}}(|\psi\rangle - |\phi\rangle)$. We generalize this insight into a broader duality principle in quantum computation, wherein manipulating quantum states in one basis is equivalent to extracting their value in a...

2024/1500 (PDF) Last updated: 2024-10-07
Hard Quantum Extrapolations in Quantum Cryptography
Luowen Qian, Justin Raizes, Mark Zhandry
Foundations

Although one-way functions are well-established as the minimal primitive for classical cryptography, a minimal primitive for quantum cryptography is still unclear. Universal extrapolation, first considered by Impagliazzo and Levin (1990), is hard if and only if one-way functions exist. Towards better understanding minimal assumptions for quantum cryptography, we study the quantum analogues of the universal extrapolation task. Specifically, we put forth the classical$\rightarrow$quantum...

2023/1797 (PDF) Last updated: 2024-03-04
A Modular Approach to Unclonable Cryptography
Prabhanjan Ananth, Amit Behera
Foundations

We explore a new pathway to designing unclonable cryptographic primitives. We propose a new notion called unclonable puncturable obfuscation (UPO) and study its implications for unclonable cryptography. Using UPO, we present modular (and in some cases, arguably, simple) constructions of many primitives in unclonable cryptography, including, public-key quantum money, quantum copy-protection for many classes of functionalities, unclonable encryption, and single-decryption encryption....

2023/1783 (PDF) Last updated: 2024-04-16
An efficient quantum parallel repetition theorem and applications
John Bostanci, Luowen Qian, Nicholas Spooner, Henry Yuen
Foundations

We prove a tight parallel repetition theorem for $3$-message computationally-secure quantum interactive protocols between an efficient challenger and an efficient adversary. We also prove under plausible assumptions that the security of $4$-message computationally secure protocols does not generally decrease under parallel repetition. These mirror the classical results of Bellare, Impagliazzo, and Naor [BIN97]. Finally, we prove that all quantum argument systems can be generically compiled...

2023/1772 (PDF) Last updated: 2023-12-05
Robust Combiners and Universal Constructions for Quantum Cryptography
Taiga Hiroka, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
Foundations

A robust combiner combines many candidates for a cryptographic primitive and generates a new candidate for the same primitive. Its correctness and security hold as long as one of the original candidates satisfies correctness and security. A universal construction is a closely related notion to a robust combiner. A universal construction for a primitive is an explicit construction of the primitive that is correct and secure as long as the primitive exists. It is known that a universal...

2023/1538 (PDF) Last updated: 2024-09-25
Unclonable Commitments and Proofs
Vipul Goyal, Giulio Malavolta, Justin Raizes
Foundations

Non-malleable cryptography, proposed by Dolev, Dwork, and Naor (SICOMP '00), has numerous applications in protocol composition. In the context of proofs, it guarantees that an adversary who receives a proof cannot maul it into another valid proof. However, non-malleable cryptography (particularly in the non-interactive setting) suffers from an important limitation: An attacker can always copy the proof and resubmit it to another verifier (or even multiple verifiers). In this work, we...

2023/1097 (PDF) Last updated: 2023-11-28
Quantum Money from Abelian Group Actions
Mark Zhandry
Cryptographic protocols

We give a construction of public key quantum money, and even a strengthened version called quantum lightning, from abelian group actions, which can in turn be constructed from suitable isogenies over elliptic curves. We prove security in the generic group model for group actions under a plausible computational assumption, and develop a general toolkit for proving quantum security in this model. Along the way, we explore knowledge assumptions and algebraic group actions in the quantum...

2023/069 (PDF) Last updated: 2023-01-21
On the (Im)plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions
Prabhanjan Ananth, Zihan Hu, Henry Yuen
Foundations

Public-key quantum money is a cryptographic proposal for using highly entangled quantum states as currency that is publicly verifiable yet resistant to counterfeiting due to the laws of physics. Despite significant interest, constructing provably-secure public-key quantum money schemes based on standard cryptographic assumptions has remained an elusive goal. Even proposing plausibly-secure candidate schemes has been a challenge. These difficulties call for a deeper and systematic study...

2022/1620 (PDF) Last updated: 2022-12-26
Another Round of Breaking and Making Quantum Money: How to Not Build It from Lattices, and More
Jiahui Liu, Hart Montgomery, Mark Zhandry
Foundations

Public verification of quantum money has been one of the central objects in quantum cryptography ever since Wiesner's pioneering idea of using quantum mechanics to construct banknotes against counterfeiting. So far, we do not know any publicly-verifiable quantum money scheme that is provably secure from standard assumptions. In this work, we provide both negative and positive results for publicly verifiable quantum money. **In the first part, we give a general theorem, showing that a...

2022/1336 (PDF) Last updated: 2024-05-08
One-Wayness in Quantum Cryptography
Tomoyuki Morimae, Takashi Yamakawa
Foundations

The existence of one-way functions is one of the most fundamental assumptions in classical cryptography. In the quantum world, on the other hand, there are evidences that some cryptographic primitives can exist even if one-way functions do not exist [Morimae and Yamakawa, CRYPTO 2022; Ananth, Qian, and Yuen, CRYPTO 2022]. We therefore have the following important open problem in quantum cryptography: What is the most fundamental element in quantum cryptography? In this direction, Brakerski,...

2022/624 (PDF) Last updated: 2022-05-23
Cryptanalysis of Three Quantum Money Schemes
Andriyan Bilyk, Javad Doliskani, Zhiyong Gong
Public-key cryptography

We investigate the security assumptions behind three public-key quantum money schemes. Aaronson and Christiano proposed a scheme based on hidden subspaces of the vector space $\mathbb{F}_2^n$ in 2012. It was conjectured by Pena et al in 2015 that the hard problem underlying the scheme can be solved in quasi-polynomial time. We confirm this conjecture by giving a polynomial time quantum algorithm for the underlying problem. Our algorithm is based on computing the Zariski tangent space of a...

2022/228 (PDF) Last updated: 2025-01-11
Semi-Quantum Tokenized Signatures
Omri Shmueli
Cryptographic protocols

Quantum tokenized signature schemes (Ben-David and Sattath, QCrypt 2017) allow a sender to generate and distribute quantum unclonable states which grant their holder a one-time permission to sign in the name of the sender. Such schemes are a strengthening of public-key quantum money schemes, as they imply public-key quantum money where some channels of communication in the system can be made classical. An even stronger primitive is semi-quantum tokenized signatures, where the sender is...

2021/1427 (PDF) Last updated: 2022-04-30
Public-Key Quantum Money with a Classical Bank
Omri Shmueli
Cryptographic protocols

Quantum money is a main primitive in quantum cryptography, that enables a bank to distribute to parties in the network, called wallets, unclonable quantum banknotes that serve as a medium of exchange between wallets. While quantum money suggests a theoretical solution to some of the fundamental problems in currency systems, it still requires a strong model to be implemented; quantum computation and a quantum communication infrastructure. A central open question in this context is whether we...

2021/1410 (PDF) Last updated: 2021-10-24
Franchised Quantum Money
Bhaskar Roberts, Mark Zhandry

The construction of public key quantum money based on standard cryptographic assumptions is a longstanding open question. Here we introduce franchised quantum money, an alternative form of quantum money that is easier to construct. Franchised quantum money retains the features of a useful quantum money scheme, namely unforgeability and local verification: anyone can verify banknotes without communicating with the bank. In franchised quantum money, every user gets a unique secret verification...

2021/1294 (PDF) Last updated: 2022-10-11
Quantum Money from Quaternion Algebras
Daniel M. Kane, Shahed Sharif, Alice Silverberg
Cryptographic protocols

We propose a new idea for public key quantum money. In the abstract sense, our bills are encoded as a joint eigenstate of a fixed system of commuting unitary operators. We perform some basic analysis of this black box system and show that it is resistant to black box attacks. In order to instantiate this protocol, one needs to find a cryptographically complicated system of computable, commuting, unitary operators. To fill this need, we propose using Brandt operators acting on the Brandt...

2021/946 (PDF) Last updated: 2022-01-09
Hidden Cosets and Applications to Unclonable Cryptography
Andrea Coladangelo, Jiahui Liu, Qipeng Liu, Mark Zhandry
Cryptographic protocols

In 2012, Aaronson and Christiano introduced the idea of hidden subspace states to build public-key quantum money [STOC '12]. Since then, this idea has been applied to realize several other cryptographic primitives which enjoy some form of unclonability. In this work, we study a generalization of hidden subspace states to hidden coset states. This notion was considered independently by Vidick and Zhang [Eurocrypt '21], in the context of proofs of quantum knowledge from quantum money schemes....

2020/1339 (PDF) Last updated: 2020-10-27
New Approaches for Quantum Copy-Protection
Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, Ruizhe Zhang
Foundations

Quantum copy protection uses the unclonability of quantum states to construct quantum software that provably cannot be pirated. Copy protection would be immensely useful, but unfortunately little is known about how to achieve it in general. In this work, we make progress on this goal, by giving the following results: –We show how to copy protect any program that cannot be learned from its input/output behavior, relative to a classical oracle. This improves on Aaronson [CCC’09], which ...

2020/1314 (PDF) Last updated: 2022-02-21
Secure Software Leasing from Standard Assumptions
Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
Foundations

Secure software leasing (SSL) is a quantum cryptographic primitive that enables an authority to lease software to a user by encoding it into a quantum state. SSL prevents users from generating authenticated pirated copies of leased software, where authenticated copies indicate those run on legitimate platforms. Although SSL is a relaxed variant of quantum copy protection that prevents users from generating any copy of leased softwares, it is still meaningful and attractive. Recently, Ananth...

2020/452 (PDF) Last updated: 2020-06-13
Almost Public Quantum Coins
Amit Behera, Or Sattath
Cryptographic protocols

In a quantum money scheme, a bank can issue money that users cannot counterfeit. Similar to bills of paper money, most quantum money schemes assign a unique serial number to each money state, thus potentially compromising the privacy of the users of quantum money. However in a quantum coins scheme, just like the traditional currency coin scheme, all the money states are exact copies of each other, providing a better level of privacy for the users. A quantum money scheme can be private, i.e.,...

2020/414 (PDF) Last updated: 2020-10-20
Semi-Quantum Money
Roy Radian, Or Sattath
Cryptographic protocols

Quantum money allows a bank to mint quantum money states that can later be verified and cannot be forged. Usually, this requires a quantum communication infrastructure to transfer quantum states between the user and the bank. Gavinsky (CCC 2012) introduced the notion of classically verifiable quantum money, which allows verification through classical communication. In this work we introduce the notion of classical minting, and combine it with classical verification to introduce semi-quantum...

2017/1080 (PDF) Last updated: 2018-08-14
Quantum Lightning Never Strikes the Same State Twice
Mark Zhandry
Foundations

Public key quantum money can be seen as a version of the quantum no-cloning theorem that holds even when the quantum states can be verified by the adversary. In this work, investigate quantum lightning, a formalization of ``collision-free quantum money'' defined by Lutomirski et al. [ICS'10], where no-cloning holds even when the adversary herself generates the quantum state to be cloned. We then study quantum money and quantum lightning, showing the following results: - We demonstrate...

2017/094 (PDF) Last updated: 2017-02-13
Quantum Tokens for Digital Signatures
Shalev Ben-David, Or Sattath

The fisherman caught a quantum fish. "Fisherman, please let me go", begged the fish, "and I will grant you three wishes". The fisherman agreed. The fish gave the fisherman a quantum computer, three quantum signing tokens and his classical public key. The fish explained: "to sign your three wishes, use the tokenized signature scheme on this quantum computer, then show your valid signature to the king, who owes me a favor". The fisherman used one of the signing tokens to sign the document...

2012/171 (PDF) (PS) Last updated: 2012-04-11
Quantum Money from Hidden Subspaces
Scott Aaronson, Paul Christiano
Cryptographic protocols

Forty years ago, Wiesner pointed out that quantum mechanics raises the striking possibility of money that cannot be counterfeited according to the laws of physics. We propose the first quantum money scheme that is (1) public-key, meaning that anyone can verify a banknote as genuine, not only the bank that printed it, and (2) cryptographically secure, under a "classical" hardness assumption that has nothing to do with quantum money. Our scheme is based on hidden subspaces, encoded as the...

1998/022 (PS) Last updated: 1998-08-12
Insecurity of Quantum Computations
Hoi-Kwong Lo

It had been widely claimed that quantum mechanics can protect private information during public decision in for example the so-called two-party secure computation. If this were the case, quantum smart-cards could prevent fake teller machines from learning the PIN (Personal Identification Number) from the customers' input. Although such optimism has been challenged by the recent surprising discovery of the insecurity of the so-called quantum bit commitment, the security of quantum two-party...

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.