We present a quantum auction protocol using superpositions to represent bids and distributed search to identify the winner(s). Measuring the final quantum state gives the auction outcome while simultaneously destroying the superposition. Thus, non-winning bids are never revealed. Participants can use entanglement to arrange for correlations among their bids, with the assurance that this entanglement is not observable by others. This protocol is useful for information hiding applications, such as partnership bidding with allocative externality or concerns about revealing bidding preferences. The protocol applies to a variety of auction types, e.g. first or second price, and to auctions involving either a single item or arbitrary bundles of items (i.e. combinatorial auctions). We analyze the game-theoretical behavior of the quantum protocol for the simple case of a sealed-bid quantum, and show how a suitably designed adiabatic search reduces the possibilities for bidders to game the auction. This design illustrates how incentive rather that computational constraints affect quantum algorithm choices.
We present a quantum auction protocol using superpositions to represent bids and distributed search to identify the winner(s). Measuring the final quantum state gives the auction outcome while simultaneously destroying the superposition. Thus, non-winning bids are never revealed. Participants can use entanglement to arrange for correlations among their bids, with the assurance that this entanglement is not observable by others. This protocol is useful for information hiding applications, such as partnership bidding with allocative externality or concerns about revealing bidding preferences. The protocol applies to a variety of auction types, e.g. first or second price, and to auctions involving either a single item or arbitrary bundles of items (i.e. combinatorial auctions). We analyze the game-theoretical behavior of the quantum protocol for the simple case of a sealed-bid quantum, and show how a suitably designed adiabatic search reduces the possibilities for bidders to game the auction. This design illustrates how incentive rather that computational constraints affect quantum algorithm choices.
We examine a proposed auction algorithm using quantum states to represent bids and distributed adiabatic search to find the winner.1 When the auctioneer follows the protocol, the final measurement giving the outcome of the auction also destroys the bid states, thereby preserving the privacy of losing bidders. We describe how a dishonest auctioneer could alter the protocol to violate this privacy guarantee, and present methods by which bidders can counter such attacks. We also suggest possible quantum circuit implementations of the auction protocol, and quantum circuits to perpetrate and to counter attacks by a dishonest auctioneer.
Sealed-bid auction is an important tool in modern economic especially concerned with networks. However, the bidders still lack the privacy protection in previously proposed sealed-bid auction schemes. In this paper, we focus on how to further protect the privacy of the bidders, especially the non-winning bidders. We first give a new privacy-preserving model of sealed-bid auction and then present a quantum sealed-bid auction scheme with stronger privacy protection. Our proposed scheme takes a general state in N-dimensional Hilbert space as the message carrier, in which each bidder privately marks his bid in an anonymous way, and further utilizes Grover's search algorithm to find the current highest bid. By O(lnn) iterations, it can get the highest bid finally. Compared with any classical scheme in theory, our proposed quantum scheme gets the lower communication complexity.
In this article, we first define a primitive problem of secure multiparty computations, i.e., secure multiparty disjunction (SMD), and present a novel quantum protocol for SMD that can ensure information-theoretical security, i.e., unconditional security. Furthermore, based on the quantum SMD protocol, we design a quantum sealed-bid auction (QSA) scheme without an auctioneer. In the proposed QSA scheme, all bidders can jointly find the winning bidder without the help of an auctioneer while it can perfectly protect the privacy of nonwinning bidders. The proposed quantum SMD protocol and quantum QSA scheme take Bell states as quantum resources and only perform single-particle Pauli operators and two-particle Bell measurements. Finally, we simulate the related quantum protocols in Qiskit and verify the correctness and the feasibility of the proposed protocols.
A sealed-bid auction is an essential tool for trading commodities in modern society. However, the non-winning bidders in previously proposed sealed-bid auction schemes lack privacy protection. In this paper, we define a sealed-bid auction with strong privacy protection, which can protect the privacy of all non-winning bidders. In order to fulfil the task, we first present a quantum secret sharing protocol and a secure quantum summation protocol and then design their corresponding quantum circuits, where the security of the latter is guaranteed by the former, while the former is information-theoretically secure. We further present a quantum seal-bid auction (QSA) scheme with strong privacy protection based on the designed quantum protocols. In our QSA scheme, each bidder first encodes a private vector by his private bid and public agreement information, and then all bidders jointly compute the summations of their respective private vectors without a trusted third party. Finally, we verify the correctness and the feasibility of the proposed QSA scheme by circuit simulations in IBM Qiskit.
Secure multi-party computation (SMC) addresses the problem of jointly computing global functions of private inputs while revealing minimal information about individual data. Two prominent examples of SMC tasks are sealed-bid auction and secure multi-party summation. Existing schemes for quantum auction and quantum summation have largely been developed independently, motivated by distinct applications and employing different computational primitives. In this work, mutual reductions between the two tasks are established for single-item sealed-bid auctions with first-price payment. In one direction, an auction used as a black box computes a secure sum: each party bids a private random key drawn from its input, so the clearing price depends on the inputs only through their sum S. The reduction is perfectly private against colluding semi-honest parties and uses O(S2log(1/δ)) auction rounds, which is optimal, or O(Slog(1/δ)) under coherent access. It can be instantiated with an existing auctioneer-free quantum auction after a one-line change to its disjunction subroutine, which as published leaks occupancy counts. In the other direction, summation with randomized inputs yields threshold disjunctions, and a single search over composite keys locates the highest bid and a winner, revealing nothing else. Because each query consumes the bidders' encodings, a bidder can adapt its effective bid undetected, while a fixed query set restores sealed bidding. Combinatorial auctions and general payment rules lie outside this framework. On a superconducting processor, one instance of each direction is executed, recovering the winner for four-bidder instances with ties and the sum of private inputs from repeated auctions.
Quantum sealed-bid auction (QSA) is expected to provide an alternative to classical sealed-bid auction to defend against attacks from quantum adversaries. However, most previous QSA protocols required bidders to have quantum operation capabilities, resulting in excessive quantum resource requirements. To relieve the burden of protocol quantum resources, a measurement-based quantum sealed-bid auction protocol with the one-way transmission is proposed. Compared to previous protocols, our protocol only requires bidders to perform measurements, and no other operations, such as Pauli or Phase operations, are required. In order to verify the correctness and feasibility of the proposed QSA protocol, the corresponding quantum circuits are designed and simulated by IBM Qiskit. The proposed protocol satisfies security properties, including anonymity, fairness, verifiability, privacy, and non-repudiation. In addition, we further extend the protocol to scenarios that do not require an auctioneer and achieve bid privacy protection for unsuccessful bidders. Therefore, our protocol may have broad applications in auction scenarios.