Comprehensive survey on privacy-preserving protocols for sealed-bid auctions
---
paper_title: Limitations of the Vickrey Auction in Computational Multiagent Systems

paper_content:

Auctions provide an efficient distributed mechanism for solving problems such as task and resource allocation in muitiagent systems. In the Vickrey auction--which has been widely advocated for automated auctions [22; 1; 3; 5; 24; 2; 8; 9; 20; 13J--the best bid wins the auction, but at the second best price. In certain settings this promotes truthful bidding and avoids counterspeculation. This paper analyses the circumstances when this protocol is appropriate, and explicates the desirable properties and lack thereof in varied settings. The first part of the paper discusses known deficiencies of the Vickrey auction: bidder collusion, a lying auctioneer, promotion of lying in non-private-value auctions, lower revenue than alternative protocols, and the necessity to reveal sensitive information. The second part of the paper presents our results regarding new limitations of the protocol, which arise especially among computational agents. These include inefficient allocation and lying in sequential suctions of interrelated items, untruthful bidding when a risk averse agent has local uncertainty, and the need for counterspeculation to make deliberation control (or information gathering) decisions when an agent has local uncertainty.
---
paper_title: Vicious strategies for Vickrey auctions

paper_content:

We show that the Vickrey auction, despite its theoretical benefits, is inappropriate if “antisocial” agents participate in the auction process. More specifically, an antisocial attitude for economic agents that makes {\em reducing the profit of competitors}\/ their main goal besides maximizing their own profit is introduced. Under this novel condition, agents need to deviate from the dominant truth-telling strategy. This paper presents a strategy for bidders in repeated Vickrey auctions who are intending to inflict losses to fellow agents in order to be more successful, not in absolute measures, but relatively to the group of bidders.
---
paper_title: Formal Verification of e-Auction Protocols

paper_content:

Auctions have a long history, having been recorded as early as 500 B.C.. With the rise of Internet, electronic auctions have been a great success and are increasingly used. Many cryptographic protocols have been proposed to address the various security requirements of these electronic transactions. We propose a formal framework to analyze and verify security properties of e-Auction protocols. We model protocols in the Applied π-Calculus and define privacy notions, which include secrecy of bids, anonymity of the participants, receipt-freeness and coercion-resistance. We also discuss fairness, non-repudiation and non-cancellation. Additionally we show on two case studies how these properties can be verified automatically using ProVerif, and discover several attacks.
---
paper_title: A method for obtaining digital signatures and public-key cryptosystems

paper_content:

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intented recipient. Only he can decipher the message, since only he knows the corresponding decryption key. (2) A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n , of two large secret primer numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d ≡ 1(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n .
---
paper_title: Cryptography: Theory and Practice

paper_content:

From the Publisher: ::: The object of the book is to produce a general, comprehensive textbook that treats all the essential core areas of cryptography.
---
paper_title: New Directions in Cryptography

paper_content:

Two kinds of contemporary developments in cryptography are examined. Widening applications of teleprocessing have given rise to a need for new types of cryptographic systems, which minimize the need for secure key distribution channels and supply the equivalent of a written signature. This paper suggests ways to solve these currently open problems. It also discusses how the theories of communication and computation are beginning to provide the tools to solve cryptographic problems of long standing.
---
paper_title: Completeness theorems for non-cryptographic fault-tolerant distributed computation

paper_content:

Every function of n inputs can be efficiently computed by a complete network of n processors in such a way that: If no faults occur, no set of size t n /2 of players gets any additional information (other than the function value), Even if Byzantine faults are allowed, no set of size t n /3 can either disrupt the computation or get additional information. Furthermore, the above bounds on t are tight!
---
paper_title: Efficient Sealed-Bid Auction Using Hash Chain

paper_content:

This paper proposes the first sealed-bid auction method which uses only hash function. We use a hash chain to commit a bidding price. By using the hash chain, we can drastically reduce the time needed for bidding and opening bids. If we use a practical hash function e.g. SHA-1, our method is 200,000 times faster than former methods that use public key cryptosystems. Accordingly, our method is capable of wide application in terms of the number of bidders and the range of bidding prices.
---
paper_title: Distributed provers with applications to undeniable signatures

paper_content:

This paper introduces distributed prover protocols. Such a protocol is a proof system in which a polynomially bounded prover is replaced by many provers each having partial information about the witness owned by the original prover. As an application of this concept, it is shown how the signer of undeniable signatures can distribute part of his secret key to n agents such that any k of these can verify a signature. This facility is useful in most applications of undeniable signatures, and as the proposed protocols are practical, the results in this paper makes undeniable signatures more useful. The first part of the paper describes a method for verifiable secret sharing, which allows non-interactive verification of the shares and is as secure as the Shamir secret sharing scheme in the proposed applications.
---
paper_title: Verifiable secret sharing and multiparty protocols with honest majority

paper_content:

Under the assumption that each participant can broadcast a message to all other participants and that each pair of participants can communicate secretly, we present a verifiable secret sharing protocol, and show that any multiparty protocol, or game with incomplete information, can be achieved if a majority of the players are honest. The secrecy achieved is unconditional and does not rely on any assumption about computational intractability. Applications of these results to Byzantine Agreement are also presented. Underlying our results is a new tool of Information Checking which provides authentication without cryptographic assumptions and may have wide applications elsewhere.
---
paper_title: The design and implementation of a secure auction service

paper_content:

We present the design and implementation of a distributed service for performing sealed-bid auctions. This service provides an interface by which clients, or "bidders", can issue secret bids to the service for an advertised auction. Once the bidding period has ended, the auction service opens the bids, determines the winning bid, and provides the winning bidder with a ticket for claiming the item bid upon. Using novel cryptographic techniques, the service is constructed to provide strong protection for both the auction house and correct bidders, despite the malicious behavior of any number of bidders and even a constant fraction of the servers comprising the auction service. Specifically, it is guaranteed that (i) bids of correct bidders are not revealed until after the bidding period has ended, (ii) the auction house collects payment for the winning bid, (iii) losing bidders forfeit no money, and (iv) only the winning bidder can collect the item bid upon. We also discuss techniques to enable anonymous bidding. >
---
paper_title: Practical electronic auction scheme with strong anonymity and bidding privacy

paper_content:

In 2003, Chang and Chang proposed an efficient and anonymous auction protocol with freewheeling bids. They claimed that their scheme could ensure the bidders' anonymity and secure confidentiality. Later, Jiang et al. pointed out that their scheme could not withstand the man-in-the-middle attacks; during this time, Jiang et al. proposed an improved scheme based on the scheme by Chang and Chang. In 2006, Chang and Chang proposed an anonymous auction scheme that was much more efficient than the abovementioned schemes. However, all of these three schemes were unable to achieve strong anonymity, bidding privacy, and secret bidding prices for sealed-bids. This article proposes a new scheme to resolve the above problems in which two managers and zero knowledge proof are used. The proposed scheme can be widely applied in any sensitive auction (e.g., auctions of cosmetics, medical services, etc.). Moreover, the proposed scheme also satisfies the following requirements: (1) bidding privacy, (2) strong anonymity, (3) secret bidding prices, (4) unforgeability, (5) verifiability, (6) non-repudiation, (7) traceability, (8) one-time registration and (9) easy revocation.
---
paper_title: Cryptographic Protocols for Secure Second-Price Auctions

paper_content:

In recent years auctions have become more and more important in the field of multiagent systems as useful mechanisms for resource allocation, task assignment and last but not least electronic commerce. In many cases the Vickrey (second-price sealed-bid) auction is used as a protocol that prescribes how the individual agents have to interact in order to come to an agreement. The main reasons for choosing the Vickrey auction are the existence of a dominant strategy equilibrium, the low bandwidth and time consumption due to just one round of bidding and the (theoretical) privacy of bids. This paper specifies properties that are needed to ensure the accurate and secret execution of Vickrey auctions and provides a classification of different forms of collusion. We approach the two major security concerns of the Vickrey auction: the vulnerability to a lying auctioneer and the reluctance of bidders to reveal their private valuations. We then propose a novel technique that allows to securely perform second-price auctions. This is achieved using the announcement of encrypted binary bidding lists on a blackboard. Top-down, bottom-up and binary search techniques are used to interactively find the second highest bid step by step without revealing unnecessary information.
---
paper_title: Non-interactive Auction Scheme with Strong Privacy

paper_content:

Key chain, as an effective tool to achieve strong bid privacy non-interactively, was employed by Watanabe and Imai in an auction scheme. But in their scheme bid privacy cannot be achieved unconditionally and losing bidders must trust bidders with higher bids for privacy of their bids. Moreover, their scheme is not efficient. In this paper the key chain in the shceme by Watanabe and Imai is optimised to achieve unconditional bid privacy. In the new scheme, every losing bidder can control privacy of their own bids while no trust is needed. Computational cost of this scheme is optimised by avoiding the costly verifiable encryption technique in their scheme.
---
paper_title: Secure Vickrey auctions without threshold trust

paper_content:

We argue that threshold trust is not an option in most of the real-life electronic auctions. We then propose two new cryptographic Vickrey auction schemes that involve, apart from the bidders and the seller S, an auction authority A so that unless S and A collude the outcome of auctions will be correct, and moreover, S will not get any information about the bids, while A will learn bid statistics. Further extensions make it possible to decrease damage that colluding S and A can do, and to construct (m + 1)st price auction schemes. The communication complexity between the S and A in medium-size auctions is at least one order of magnitude less than in the Naor-Pinkas-Sumner scheme.
---
paper_title: Efficient Sealed-Bid Auction Protocols Using Verifiable Secret Sharing

paper_content:

This article proposes efficient solutions for the construction of sealed-bid second-price and combinatorial auction protocols in an active adversary setting. The main reason for constructing secure auction protocols is that the losing bids can be used in the future auctions as well as negotiations if they are not kept private. Our motivation is to apply verifiable secret sharing in order to construct various kinds of sealed-bid auctions. We initially propose two secure second-price auction protocols with different masking methods. Subsequently, we provide two secure combinatorial auction protocols based on our second masking approach. In the first scheme, we apply an existing dynamic programming method. In the second protocol, we use inter-agent negotiation as an approximate solution in the multiple traveling salesman problem to determine auction outcomes. It is worth mentioning that our protocols are independent of the secret sharing scheme that is being used.
---
paper_title: Multi-round Anonymous Auction Protocols

paper_content:

SUMMARY Auctions are a critical element of the electronic commerce infrastructure. But for real-time applications, auctions are a potential problem – they can cause significant time delays. Thus, for most real-time applications, sealed-bid auctions are recommended. But how do we handle tie-breaking in sealed-bid auctions? This paper analyzes the use of multi-round auctions where the winners from an auction round participate in a subsequent tie-breaking second auction round. We perform this analysis over the classical first-price sealed-bid auction that has been modified to provide full anonymity. We analyze the expected number of rounds and optimal values to minimize communication costs.
---
paper_title: Unconditionally Secure Proactive Secret Sharing Scheme with Combinatorial Structures

paper_content:

. Verifiable secret sharing schemes (VSS) are secret sharing schemes dealing with possible cheating by the participants. In this paper, we propose a new unconditionally secure VSS. Then we construct a new proactive secret sharing scheme based on that VSS. In a proactive scheme, the shares are periodically renewed so that an adversary cannot get any information about the secret unless he is able to access a specified number of shares in a short time period. Furthermore, we introduce some combinatorial structure into the proactive scheme to make the scheme more efficient. The combinatorial method might also be used to improve some of the previously constructed proactive schemes.
---
paper_title: A two-server, sealed-bid auction protocol

paper_content:

Naor, Pinkas, and Sumner introduced and implemented a sealed-bid, two-server auction system that is perhaps the most efficient and practical to date. Based on a cryptographic primitive known as oblivious transfer, their system aims to ensure privacy and correctness provided that at least one auction server behaves honestly. As observed in [19], however, the NPS system suffers from a security flaw in which one of the two servers can cheat so as to modify bids almost arbitrarily and without detection. We propose a means of repairing this flaw while preserving the attractive practical elements of the NPS protocol, including minimal round complexity for servers and minimal computation by players providing private inputs. Our proposal requires a slightly greater amount of computation and communication on the part of the two auction servers, but actually involves much less computation on the part of bidders. This latter feature makes our proposal particularly attractive for use with low-power devices. While the original proposal of NPS involved several dozen exponentiations for a typical auction, ours by contrast involves only several dozen modular multiplications. ::: ::: The key idea in our proposal is a form of oblivious transfer that we refer to as verifiable proxy oblimous transfer (VPOT).
---
paper_title: An Auction Protocol Which Hides Bids of Losers

paper_content:

Many auction protocols using practical cryptographic means have successfully achieved capability of hiding the bids of each entity, but not the values of bids themselves. In this paper we describe an auction protocol which hides the bids of non-winners even from the bid-opening centers, and still makes it possible to publicly verify the validity of the winning bid, i.e. that it was the highest bid submitted. The first approach to such a protocol was made by Kikuchi et al in [KHT98]. However, several deficiencies have been pointed out regarding their protocol; for example, it is not well suited for handling tie bids.
---
paper_title: Efficient bid validity check in ElGamal-based sealed-bid e-auction

paper_content:

Bid opening in sealed-bid e-auction is efficient when a homomorphic encryption algorithm is employed to seal the bids and homomorphic bid opening is employed to open the bids. Such e-auction schemes are called homomorphic auctions. However, high efficiency of homomorphic auctions is based on an assumption: the bids are valid (e.g. within a special range). An undetected invalid bid can compromise correctness and fairness of the auction. Unfortunately, in most existing homomorphic auction schemes, proof and verification of validity of the bids is either ignored or too inefficient. Recently, a technique called batched bid validity check [25] is proposed to improve efficiency of proof and verification of bid validity in a special kind of homomorphic auction schemes: secretsharing-based homomorphic auctions. However, secret-sharing-based homomorphic auction schemes [13, 15, 26, 24] are not a main stream in homomorphic auction schemes as they employ threshold secret sharing techniques to seal the bids. Main stream homomorphic auction schemes employ a homomorphic encryption algorithm with threshold distributed decryption to seal the bids as it is simpler and more efficient than secret sharing. In this paper, an ElGamal-encryption-based homomorphic encryption scheme is proposed. It employs a batched proof and verification of bid validity to achieve high efficiency in bid validity check. Its batch proof and verification technique is more advanced than that in [25], so it is simpler and more efficient than the homomorphic auction scheme in [25].
---
paper_title: First price sealed bid auction without auctioneers

paper_content:

We propose two protocol variants for a first price sealed-bid auction, without using intermediatory auctioneers. One version achieves full privacy for the bidders and their bids, the other provides a form of verifiability, at the cost of some privacy. Full privacy protects all bids. In particular the winner's identity and price are only known by the seller. Lesser privacy allows the winner to be known and verified publicly. Both versions provide non-repudiation. We demonstrate correctness and show how computational and communication costs vary with different privacy levels.
---
paper_title: Cryptographic protocols for Vickrey auctions

paper_content:

Although the sealed second-price or Vickrey auctions have some nice theoretical properties, they are fairly seldom utilized in practice. It has been suggested that they are vulnerable to bid-taker cheating and that the revelation of bids after the bidding makes the bidders reluctant to reveal their true valuations. We outline procedures based on modern mathematical cryptography that are instrumental in avoiding some of these difficulties and thereby will improve the properties of the Vickrey auctions.
---
paper_title: Robust, Privacy Protecting and Publicly Verifiable Sealed-Bid Auction

paper_content:

The sealed bid model of auctions is ideally suited for electronic auction systems, as they avoid the requirement for real-time communications between various entities. A sealed bid auction scheme designed by Kikuchi, Harkavy and Tygar is analysed. Several shortcomings are identified in this scheme including the lack of public verifiability and the possibility of collusion between bidders and/or auctioneers. A new scheme is designed to overcome these shortcomings.
---
paper_title: Optimization of electronic first-bid sealed-bid auction based on homomorphic secret sharing

paper_content:

Although secret sharing techniques have been applied to implement secure electronic sealed-bid auction for a long time, problems and attacks still exist in secret-sharing-based electronic sealed-bid auction schemes. In this paper, a new secret-sharing-based first-bid e-auction scheme is designed to achieve satisfactory properties and efficiency. Correctness and fairness of the new auction are based on hard computation problems and do not depend on any trust. Complete bid privacy based on a threshold trust is achieved in the new scheme. Attacks to existing secret-sharing-based sealed-bid e-auction schemes are prevented.
---
paper_title: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes

paper_content:

This paper investigates a novel computational problem, namely the Composite Residuosity Class Problem, and its applications to public-key cryptography. We propose a new trapdoor mechanism and derive from this technique three encryption schemes : a trapdoor permutation and two homomorphic probabilistic encryption schemes computationally comparable to RSA. Our cryptosystems, based on usual modular arithmetics, are provably secure under appropriate assumptions in the standard model.
---
paper_title: Unconditionally secure first-price auction protocols using a multicomponent commitment scheme

paper_content:

Due to the rapid growth of e-commerce technology, secure auction protocols have attracted much attention among researchers. The main reason for constructing sealed-bid auction protocols is the fact that losing bids can be used in future auctions and negotiations if they are not kept private. Our motivation is to develop a new commitment scheme to construct first-price auction protocols similar to proposed solutions in [18,17,19]. Our constructions are auctioneer-free and unconditionally secure whereas those protocols rely on computational assumptions and use auctioneers. As our contribution, we first propose a multicomponent commitment scheme, that is, a construction with multiple committers and verifiers. Consequently, three secure first-price auction protocols are proposed, each of which has its own properties. We also provide the security proof and the complexity analysis of proposed constructions.
---
paper_title: Novel Secret Sharing and Commitment Schemes for Cryptographic Applications

paper_content:

In the second chapter, the notion of a social secret sharing (SSS ) scheme is introduced in which shares are allocated based on a player’s reputation and the way she interacts with other parties. In other words, this scheme renews shares at each cycle without changing the secret, and it allows the trusted parties to gain more authority. Our motivation is that, in real-world applications, components of a secure scheme have different levels of importance (i.e., the number of shares a player has) and reputation (i.e., cooperation with other parties). Therefore, a good construction should balance these two factors accordingly. In the third chapter, a novel socio-rational secret sharing (SRS ) scheme is introduced in which rational foresighted players have long-term interactions in a social context, i.e., players run secret sharing while founding and sustaining a public trust network. To motivate this, consider a repeated secret sharing game such as sealed-bid auctions. If we assume each party has a reputation value, we can then penalize (or reward) the players who are selfish (or unselfish) from game to game. This social reinforcement stimulates the players to be cooperative in the secret recovery phase. Unlike the existing protocols in the literature, the proposed solution is stable and it only has a single reconstruction round. In the fourth chapter, a comprehensive analysis of the existing dynamic secret sharing (DSS ) schemes is first provided. In a threshold scheme, the sensitivity of the secret and the number of players may fluctuate due to various reasons. Moreover, a common problem with almost all secret sharing schemes is that they are “one-time”, meaning that the secret and shares are known to everyone after secret recovery. We therefore provide new techniques where the threshold and/or the secret can be changed multiple times to arbitrary values after the initialization. In addition, we introduce a new application of dynamic threshold schemes, named sequential secret sharing (SQS ), in which several secrets with increasing thresholds are shared among the players who have different levels of authority. In the fifth chapter, a cryptographic primitive, named multicomponent commitment scheme (MCS ) is proposed where we have multiple committers and verifiers. This new scheme is used to construct different sealed-bid auction protocols (SAP) where the auction outcomes are defined without revealing the losing bids. The main reason for constructing secure auctions is the fact that the values of the losing bids can be exploited in future auctions and negotiations if they are not kept private. In our auctioneer-free protocols, bidders first commit to their bids before the auction starts. They then apply a decreasing price mechanism to define the winner and selling price in an unconditionally secure setting.
---
paper_title: Distributed auction servers resolving winner and winning bid without revealing privacy of bids

paper_content:

We have developed an electronic auction system with a set of distributed servers that collaborate to resolve a winning bid without revealing the secrecy of bids. This paper describes the system architecture and shows the performance in terms of the round complexity and the bandwidth consumption for a message. Based on the actual measurements, the upper bound of number of bidding prices is identified. In addition, by adding some steps to the basic auction protocol in Kikuchi, Harkavy, and Tygar, 1998, we improve the security of protocol so that the second highest bid must not be known even by the winner.
---
paper_title: Verifiable signature sharing

paper_content:

We introduce Verifiable Signature Sharing (VΣS), a cryptographic primitive for protecting digital signatures. VΣS enables the holder of a digitally signed document, who may or may not be the original signer, to share the signature among a set of proxies so that the honest proxies can later reconstruct it. We present efficient VΣS schemes for exponentiation based signatures (e.g., RSA, Rabin) and discrete log based signatures (e.g., ElGamal, Schnorr, DSA) that can tolerate the malicious (Byzantine) failure of the sharer and a constant fraction of the proxies. We also describe our implementation of these schemes and evaluate their performance. Among the applications of VΣS is the incorporation of digital cash into multiparty protocols, e.g., to enable cash escrow and secure distributed auctions.
---
paper_title: Efficient private bidding and auctions with an oblivious third party

paper_content:

We describe a novel and efficient protocol for the following problem: A wants to buy some good from B if the price is less than a . B would like to sell, but only for more than b , and neither of them wants to reveal the secret bounds. Will the deal take place? Our solution uses an oblivious third party T who learns no information about a or b , not even whether a > b . The protocol needs only a single round of interaction, ensures fairness, and is not based on general circuit evaluation techniques. It uses a novel construction, which combines homomorphic encryption with the φ-hiding assumption and which may be of independent interest. Applications include bargaining between two parties and secure and efficient auctions in the absence of a fully trusted auction service.
---
paper_title: An Online Public Auction Protocol Protecting Bidder Privacy

paper_content:

On-line auctioning is one of the fundamental services for the new Internet economy. Most current auction services are public auction where all bids are made available to any party. User privacy is a primary concern in electronic world because electronic environment facilitates the gathering of personal data. This paper proposes a public auction protocol that achieves bidder privacy using binding group signatures. A concrete solution for preventing defaults in auctions is also presented.
---
paper_title: M+1-st Price Auction Using Homomorphic Encryption

paper_content:

This paper provides a M + 1-st price auction scheme using homomorphic encryption and the mix and match technique; it offers secrecy of bidding price and public verifiability. Our scheme has low round communication complexity: 1 round from each bidder to auctioneer in bidding and log p rounds from auctioneer to trusted authority in opening when prices are selected from p prefixed choices.
---
paper_title: A verifiable, bidder-resolved Auction Protocol

paper_content:

Security and privacy have become crucial factors in auction design. Various schemes to ensure the safe conduction of sealed-bid auctions have been proposed recently. We introduce a new standard of privacy for auctions (“full privacy”), that prevents extraction of bid information despite any collusion of participants. This requirement is stronger than other common assumptions that prohibit the collusion of certain third-parties (e.g., distinct auctioneers). Full privacy can be obtained by applying a secret sharing scheme in which the bidders jointly compute the selling price on their own without uncovering any additional information. No auctioneers or other trusted third parties are used to resolve the auction. The major contribution of this work is the fully private (M + 1)st-price auction protocol in which only the winning bidders and the seller learn the selling price. To the best of our knowledge there is no other cryptographic auction protocol that achieves a similar level of privacy. The auction outcome cannot be changed or nullified by dishonest bidders because the protocol is publicly verifiable. As full privacy is our main goal, the drawback of the presented protocol is efficiency. Without relaxing any security demands, it is only applicable for high-security auctions with relatively few bidders in reasonable time.
---
paper_title: Secure multi-attribute procurement auction

paper_content:

In this paper, we develop a secure multi-attribute procurement auction, in which a sales item is defined by several attributes called quality, the buyer is the auctioneer (e.g., a government), and the sellers are the bidders. Our goal is to develop a protocol in which acting honestly is a dominant strategy for sellers and that does not leak the true cost of the sellers, which is highly classified information that the sellers want to keep private. We first present a Vickrey-type protocol that can be used for multi-attribute procurement auctions. Next, we show how this protocol can be executed securely.
---
paper_title: Fully Private Auctions in a Constant Number of Rounds

paper_content:

We present a new cryptographic auction protocol that prevents extraction of bid information despite any collusion of participants. This requirement is stronger than common assumptions in existing protocols that prohibit the collusion of certain third-parties (e.g. distinct auctioneers). Full privacy is obtained by using homomorphic ElGamal encryption and a private key that is distributed among the set of bidders. Bidders jointly compute the auction outcome on their own without uncovering any additional information in a constant number of rounds (three in the random oracle model). No auctioneers or other trusted third parties are needed to resolve the auction. Yet, robustness is assured due to public verifiability of the entire protocol. The scheme can be applied to any uniform-price (or so-called (M + 1)st-price) auction. An additional, optional, feature of the protocol is that the selling price is only revealed to the seller and the winning bidders themselves. We furthermore provide an in-depth analysis of ties in our protocol and sketch a scheme that requires more rounds but is computationally much more efficient.
---
paper_title: Sealed-bid Auctions with Efficient Bids

paper_content:

Efficient general secure multiparty computation (MPC) protocols were previously proposed, and the combination with the efficient auction circuits achieves the efficient sealed-bid auctions with the full privacy and correctness. However, the combination requires that each bidder submits ciphertexts of bits representing his bid, and their zero-knowledge proofs. This cost amounts to about 80 multi-exponentiations in usual case that the bid size is 20 bits (i.e. about 1,000,000 bid prices). This paper proposes the sealed-bid auction protocols based on the efficient MPC protocols, where a bidder can submit only a single ciphertext. The bidder's cost is a few multi-exponentiations, and thus the proposed protocols are suitable for mobile bidders.
---
paper_title: Efficient Implementation of Relative Bid Privacy in Sealed-Bid Auction

paper_content:

The concept of relative bid privacy in auction is proposed, which does not conceal the bids, but conceals the link between them and the corresponding bidders. Relative bid privacy leads to three advantages: high efficiency, the bidding values can be very precise and any auction rule can be applied. A new mix network is designed and applied to implement relative bid privacy efficiently. Two rounds of shuffling are employed in the mix network, so that fairness can be achieved in the auction without any trust and relative bid privacy is achieved even in abnormal situations.
---
paper_title: An electronic online bidding auction protocol with both security and efficiency

paper_content:

In this paper, a new electronic auction scheme is proposed, which not only satisfies the requirement for the electronic auction properties of anonymity, security, privacy, atomicity and low overhead cost but also adds the properties of the non-repudiation, untraceability, auditability, one-time registration and unlinkability. Furthermore, we improve the operational scheme of the proposed electronic auction to meet its security and efficiency. Therefore, the proposed scheme is suitable for implementation.
---
paper_title: A sealed-bid multi-attribute auction protocol with strong bid privacy and bidder privacy

paper_content:

In this paper, a sealed-bid multi-attribute auction protocol that mainly focuses on security issues (i.e., bid privacy, bidder anonymity, and fairness problem) is presented. In recent years, existing literatures mainly focus on the multi-attribute winner determination problem and other issues, but research of multi-attribute e-auction just begin from the perspective of information security. The new proposal is motivated by the conflict between bidder anonymity and denial-of-service attack from an insider. It utilizes private set intersection method to solve the privacy problem of winner determination of sealed-bid multi-attribute auction. The proposed sealed-bid auction scheme preserves the strong privacy of the bids and provides verifiable correctness. According to the security analysis, it satisfies the security requirements of an e-auction. Copyright © 2013 John Wiley & Sons, Ltd.
---
paper_title: Electronic Auctions with Private Bids

paper_content:

Auctions are a fundamental electronic commerce technology. We describe a set of protocols for performing sealed-bid electronic auctions which preserve the privacy of the submitted bids using a form of secure distributed computation. Bids are never revealed to any party, even after the auction is completed. Both first-price and second-price (Vickrey) auctions are supported, and the computational costs of the methods are low enough to allow their use in many real-world auction situations.
---
paper_title: Completeness theorems for non-cryptographic fault-tolerant distributed computation

paper_content:

Every function of n inputs can be efficiently computed by a complete network of n processors in such a way that: If no faults occur, no set of size t n /2 of players gets any additional information (other than the function value), Even if Byzantine faults are allowed, no set of size t n /3 can either disrupt the computation or get additional information. Furthermore, the above bounds on t are tight!
---
paper_title: Efficient anonymous channel and all/nothing election scheme

paper_content:

The contribution of this paper are twofold. First, we present an efficient computationally secure anonymous channel which has no problem of ciphertext length expansion. The length is irrelevant to the number of MIXes (control centers). It improves the efficiency of Chaum's election scheme based on the MIX net automatically. Second, we show an election scheme which satisfies fairness. That is, if some vote is distrupted, no one obtains any information about all the other votes. Each voter sends O(nk) bits so that the probability of the fairness is 1 - 2-k, where n is the bit length of the ciphertext.
---
paper_title: Design and verification of a secure electronic auction protocol

paper_content:

Auctions are an important and common form of commerce today. A difficult aspect of auctions is that the bidder must be present at the site of the auction. This reduces the appeal of auction and restricts the number of people who would otherwise participate in it. An auction over an electronic network is therefore an attractive way of conducting business. The author proposes a protocol for electronic auctions. This protocol ensures: (a) anonymity of the customer, (b) security from passive attacks, active attacks, message corruption, and loss of messages, (c) customer privacy, and (d) atomicity (i.e., under all circumstances, the transaction is either completed or aborted). A logic is developed based on the semantics of BAN-style logic (M. Burrows et al., 1990). Using this logic, the properties of anonymity, security, privacy, and atomicity are proved for the proposed protocol.
---
paper_title: Adding timestamps to the secure electronic auction protocol

paper_content:

Recently, Subramanian proposed a secure electronic auction protocol. It was claimed that the auction protocol ensured anonymity, security, privacy, atomicity, and low overhead. However, the sensitive information of payment, such as credit card number, can be revealed by the auctioneer. The bid can be forged by a malicious auctioneer. Also, the situation of two or more bidders who offered the same price was not resolved efficiently. In this paper, we will improve the robustness of this electronic auction protocol.
---
paper_title: Untraceable electronic mail, return addresses, and digital pseudonyms

paper_content:

A technique based on public key cryptography is presented that allows an electronic mail system to hide who a participant communicates with as well as the content of the communication - in spite of an unsecured underlying telecommunication system. The technique does not require a universally trusted authority. One correspondent can remain anonymous to a second, while allowing the second to respond via an untraceable return address. The technique can also be used to form rosters of untraceable digital pseudonyms from selected applications. Applicants retain the exclusive ability to form digital signatures corresponding to their pseudonyms. Elections in which any interested party can verify that the ballots have been properly counted are possible if anonymously mailed ballots are signed with pseudonyms from a roster of registered voters. Another use allows an individual to correspond with a record-keeping organization under a unique pseudonym, which appears in a roster of acceptable clients.
---
paper_title: A multiplicative homomorphic sealed-bid auction based on goldwasser-micali encryption

paper_content:

Instead of the costly encryption algorithms traditionally employed in auction schemes, efficient Goldwasser-Micali encryption is used to design a new sealed-bid auction. Multiplicative homomorphism instead of the traditional additive homomorphism is exploited to achieve security and high efficiency in the auction. The new scheme is the currently known most efficient non-interactive sealed-bid auction with bid privacy.
---
paper_title: Mix and match: secure function evaluation via ciphertexts

paper_content:

We introduce a novel approach to general secure multiparty computation that avoids the intensive use of verifiable secret sharing characterizing nearly all previous protocols in the literature. Instead, our scheme involves manipulation of ciphertexts for which the underlying private key is shared by participants in the computation. The benefits of this protocol include a high degree of conceptual and structural simplicity, low message complexity, and substantial flexibility with respect to input and output value formats. We refer to this new approach as mix and match. ::: ::: While the atomic operations in mix and match are logical operations, rather than full field operations as in previous approaches, the techniques we introduce are nonetheless highly practical for computations involving intensive bitwise manipulation. One application for which mix and match is particularly well suited is that of sealed-bid auctions. Thus, as another contribution in this paper, we present a practical, mix-and-match-based auction protocol that is fully private and non-interactive and may be readily adapted to a wide range of auction strategies.
---
paper_title: Robust, Privacy Protecting and Publicly Verifiable Sealed-Bid Auction

paper_content:

The sealed bid model of auctions is ideally suited for electronic auction systems, as they avoid the requirement for real-time communications between various entities. A sealed bid auction scheme designed by Kikuchi, Harkavy and Tygar is analysed. Several shortcomings are identified in this scheme including the lack of public verifiability and the possibility of collusion between bidders and/or auctioneers. A new scheme is designed to overcome these shortcomings.
---
paper_title: New Sealed-Bid Electronic Auction with Fairness, Security and Efficiency

paper_content:

Electronic sealed-bid auction schemes usually have a common drawback, the third party (auction host) can conspire with a malicious bidder to leak all bidding prices before the opening stage. It results in the malicious bidder wining the auction with an optimal bidding price. Recently, Liaw et al. proposed an auction protocol for electronic online bidding in which they designed a deposit deduction certification for government procurement. However, it also has above mentioned flaw. Moreover, we further found that there were some extra security drawbacks in their protocol. First, the bidder can forge a bidding receipt to claim that he/she is a valid auction winner. Second, it may suffer from the third party forging attack. Third, their protocol leaked some bidders' private information to the third party, such as the bidder's bank account number and the authorization code. Thus, it cannot protect the bidder's privacy at all. In this paper, we not only point out the drawbacks from the previous scheme but also propose a new electronic auction scheme to overcome the above mentioned drawbacks. Furthermore, the computational complexity can be decreased in our online sealed-bid auction scheme.
---
paper_title: Privacy-respecting auctions and rewarding mechanisms in mobile crowd-sensing applications

paper_content:

Abstract Mobile Crowdsensing (MCS) has emerged as a new paradigm for data collection and knowledge representation, where people use their devices to interact with the environment and create a more accurate picture of their surroundings. In many MCS scenarios it is desirable to give micro-payments to contributors as an incentive for their participation. However, to further encourage participants to use the system, one important requirement is protection of user privacy. In this work we present a multi-attribute reverse auction mechanism as an efficient way to offer incentives to users by allowing them to determine their own price for the data they provide, but also as a way to motivate them to submit better quality data. Our auction protocol guarantees bidders' anonymity and suggests a new rewarding mechanism that enables winners to claim their reward without being linked to the data they contributed. We have analyzed our protocol and showed that it offers strong security and privacy guarantees in all phases of the auction process, from bidding to rewarding. Additionally, we have implemented the protocol using off-the-shelf cryptographic primitives; our experiments show that the protocol is scalable, it can be applied to a large class of auctions and remains efficient from both a computation and communication point of view so that it can be run to the users' mobile devices.
---
paper_title: A Paradoxical Indentity-Based Signature Scheme Resulting from Zero-Knowledge

paper_content:

At EUROCRYPT'88, we introduced an interactive zero-knowledge protocol (Guillou and Quisquater [13]) fitted to the authentication of tamper-resistant devices (e.g. smart cards, Guillou and Ugon [14]).Each security device stores its secret authentication number, an RSA-like signature computed by an authority from the device identity. Any transaction between a tamper-resistant security device and a verifier is limited to a unique interaction: the device sends its identity and a random test number, then the verifier tells a random large question; and finally the device answers by a witness number. The transaction is successful when the test number is reconstructed from the witness number, the question and the identity according to numbers published by the authority and rules of redundancy possibly standardized.This protocol allows a cooperation between users in such a way that a group of cooperative users looks like a new entity, having a shadowed identity the product of the individual shadowed identities, while each member reveals nothing about its secret.In another scenario, the secret is partitioned between distinct devices sharing the same identity. A group of cooperative users looks like a unique user having a larger public exponent which is the greater common multiple of each individual exponent.In this paper, additional features are introduced in order to provide: firstly, a mutual interactive authentication of both communicating entities and previously exchanged messages, and, secondly, a digital signature of messages, with a non-interactive zero-knowledge protocol. The problem of multiple signature is solved here in a very smart way due to the possibilities of cooperation between users.The only secret key is the factors of the composite number chosen by the authority delivering one authentication number to each smart card. This key is not known by the user. At the user level, such a scheme may be considered as a keyless identity-based integrity scheme. This integrity has anew and important property: it cannot be misused, i.e. derived into a confidentiality scheme.
---
paper_title: Multiparty Computation from Threshold Homomorphic Encryption

paper_content:

We introduce a new approach to multiparty computation (MPC) basing it on homomorphic threshold crypto-systems. We show that given keys for any sufficiently efficient system of this type, general MPC protocols for n players can be devised which are secure against an active adversary that corrupts any minority of the players. The total number of bits sent is O(nk|C|), where k is the security parameter and |C| is the size of a (Boolean) circuit computing the function to be securely evaluated. An earlier proposal by Franklin and Haber with the same complexity was only secure for passive adversaries, while all earlier protocols with active security had complexity at least quadratic in n. We give two examples of threshold cryptosystems that can support our construction and lead to the claimed complexities.
---
paper_title: Distributed auction servers resolving winner and winning bid without revealing privacy of bids

paper_content:

We have developed an electronic auction system with a set of distributed servers that collaborate to resolve a winning bid without revealing the secrecy of bids. This paper describes the system architecture and shows the performance in terms of the round complexity and the bandwidth consumption for a message. Based on the actual measurements, the upper bound of number of bidding prices is identified. In addition, by adding some steps to the basic auction protocol in Kikuchi, Harkavy, and Tygar, 1998, we improve the security of protocol so that the second highest bid must not be known even by the winner.
---
paper_title: Non-interactive Private Auctions

paper_content:

We describe a new auction protocol that enjoys the following properties: the biddings are submitted non-interactively and no information beyond the result is disclosed. The protocol is efficient for a logarithmic number of players. Our solution uses a semi-trusted third party T who learns no information provided that he does not collude with any participant. The robustness against active cheating players is achieved through an extra mechanism for fair encryption of a bit which is of independent interest. The scheme is based on homomorphic encryption but differs from general techniques of secure circuit evaluation by taking into account the level of each gate and allowing efficient computation of unbounded logical gates. In a scenario with a small numbers of players, we believe that our work may be of practical significance, especially for electronic transactions.
---
paper_title: Efficient Sealed-Bid Auction Protocols Using Verifiable Secret Sharing

paper_content:

This article proposes efficient solutions for the construction of sealed-bid second-price and combinatorial auction protocols in an active adversary setting. The main reason for constructing secure auction protocols is that the losing bids can be used in the future auctions as well as negotiations if they are not kept private. Our motivation is to apply verifiable secret sharing in order to construct various kinds of sealed-bid auctions. We initially propose two secure second-price auction protocols with different masking methods. Subsequently, we provide two secure combinatorial auction protocols based on our second masking approach. In the first scheme, we apply an existing dynamic programming method. In the second protocol, we use inter-agent negotiation as an approximate solution in the multiple traveling salesman problem to determine auction outcomes. It is worth mentioning that our protocols are independent of the secret sharing scheme that is being used.
---
paper_title: Computationally Manageable Combinational Auctions

paper_content:

There is interest in designing simultaneous auctions for situations such as the recent FCC radio spectrum auctions, in which the value of assets to a bidder depends on which other assets he or she wins. In such auctions, bidders may wish to submit bids for combinations of assets. When this is allowed, the problem of determining the revenue maximizing set of nonconflicting bids can be difficult. We analyze this problem, identifying several different structures of permitted combinational bids for which computational tractability is constructively demonstrated and some structures for which computational tractability cannot be guaranteed.
---
paper_title: Some tractable combinatorial auctions

paper_content:

Auctions are the most widely used strategic gametheoretic mechanism in the Internet. Auctions have been mostly studied from a game-theoretic and economic perspective, although recent work in AI and OR has been concerned with computational aspects of auctions as well. When faced from a computational perspective, combinatorial auctions are perhaps the most challenging type of auctions. Combinatorial auctions are auctions where agents may submit bids for bundles of goods. Given that nding an optimal allocation of the goods in a combinatorial auction is intractable, researchers have been concerned with exposing tractable instances of combinatorial auctions. In this work we introduce polynomial solutions for a variety of non-trivial combinatorial auctions, such as combinatorial network auctions, various sub-additive combinatorial auctions, and some restricted forms of multi-unit combinatorial auctions.
---
paper_title: An efficient approximate algorithm for winner determination in combinatorial auctions

paper_content:

Auctions on the Internet have become especially popular in Electronic Commerce. Amongthe various studies on the Internet auctions, those on combinatorial auctions have lately attracted considerable attention. Combinatorial auctions simultaneously sell multiple items with interdependent values and allow the bidders to bid on any combination of items. Therefore, they tend to increase the buyers’ utilities and the seller’s revenue.
---
paper_title: Selling Spectrum Rights

paper_content:

The design of the FCC spectrum-license auction is a case study in the application of economic theory. Auction theory helped address policy questions such as: Should an open auction or a sealed-bid auction be used? Should the licenses be auctioned sequentially or simultaneously? Should the government allow bids for combinations of licenses, or should it accept only single-license bids? How should the auction be structured to promote the interests of minority-owned and other designated firms? Should the government impose royalties or reserve prices? How much should the bidders be informed about their competition?
---
paper_title: Secure multi-agent dynamic programming based on homomorphic encryption and its application to combinatorial auctions

paper_content:

This paper presents a secure dynamic programming protocol that utilizes homomorphic encryption. By using this method, multiple agents can solve a combinatorial optimization problem among them without leaking their private information. More specifically, in this method, multiple servers cooperatively perform dynamic programming procedures for solving a combinatorial optimization problem by using the private information sent from agents as inputs. Although the severs can compute the optimal solution correctly, the inputs are kept secret even from the servers.Such a secure protocol is important when a fully trusted agent is not available, e.g., an auctioneer cannot be fully trusted in a combinatorial auction. By utilizing the proposed protocol, multiple auction servers can solve the winner determination problem, while the information of bids that are not part of the optimal solution is kept secret even from the auction servers. We discuss the application of this protocol to various types of combinatorial auctions, i.e., multi-unit auctions, linear-good auctions, and general combinatorial auctions.
---
paper_title: Time-Lapse Cryptography

paper_content:

The notion of “sending a secret message to the future” has been around for over a decade. Despite this, no solution to this problem is in common use, or even attained widespread acceptance as a fundamental cryptographic primitive. We name, construct and specify an implementation for this new cryptographic primitive, “Time-Lapse Cryptography”, with which a sender can encrypt a message so that it is guaranteed to be revealed at an exact moment in the future, even if this revelation turns out to be undesirable to the sender. Our solution combines new ideas with Pedersen distributed key generation, Feldman verifiable threshold secret sharing, and ElGamal encryption, all of which rest upon the single, broadly accepted Decisional Diffie-Hellman assumption. We develop a Time-Lapse Cryptography Service (“the Service”) based on a network of parties who jointly perform the service. The protocol is practical and secure: at a given time T the Service publishes a public key so that anyone can use it, even anonymously. Senders encrypt their messages with this public key whose private key is not known to anyone – not even a trusted third party – until a predefined and specific future time T + δ, at which point the private key is constructed and published. At or after that time, anyone can decrypt the ciphertext using this private key. The Service is envisioned as a public utility publishing a continuous stream of encryption keys and subsequent corresponding time-lapse decryption keys. We complement our theoretical foundation with descriptions of specific attacks and defenses, and describe important applications of our service in sealed bid auctions, insider stock sales, clinical trials, and electronic voting. ∗Supported in part by National Science Foundation grant CNS-0205423.
---
paper_title: Secure Combinatorial Auctions by Dynamic Programming with Polynomial Secret Sharing

paper_content:

Combinatorial auctions have recently attracted the interests of many researchers due to their promising applications such as the spectrum auctions recently held by the FCC. In a combinatorial auction, multiple items with interdependent values are sold simultaneously and bidders are allowed to bid on any combination of items. This paper presents a method for implementing several secure combinatorial auction protocols based on our newly developed secure dynamic programming protocol. Dynamic programming is a very effective, widely used technique for tackling various combinatorial optimization problems, including several types of combinatorial auctions. Our secure dynamic programming protocol utilizes secret sharing techniques and can obtain the optimal solution of a combinatorial optimization problem, i.e., result of a combinatorial auction, without revealing the inputs of the problem, i.e., bidding prices. We discuss the application of the method to several combinatorial auctions, i.e., multiple-unit single-item auctions, linear-goods auctions, and general combinatorial auctions.
---
paper_title: Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches

paper_content:

In combinatorial auctions, multiple goods are sold simultaneously and bidders may bid for arbitrary combinations of goods. Determining the outcome of such an auction is an optimization problem that is NP-complete in the general case. We propose two methods of overcoming this apparent intractability. The first method, which is guaranteed to be optimal, reduces running time by structuring the search space so that a modified depth-first search usually avoids even considering allocations that contain conflicting bids. Caching and pruning are also used to speed searching. Our second method is a heuristic, market-based approach. It sets up a virtual multi-round auction in which a virtual agent represents each original bid bundle and places bids, according to a fixed strategy, for each good in that bundle. We show through experiments on synthetic data that (a) our first method finds optimal allocations quickly and offers good anytime performance, and (b) in many cases our second method, despite lacking guarantees regarding optimality or running time, quickly reaches solutions that are nearly optimal.
---
paper_title: Algorithm for Optimal Winner Determination in Combinatorial Auctions

paper_content:

Combinatorial auctions, that is, auctions where bidders can bid on combinations of items, tend to lead to more efficient allocations than traditional auction mechanisms in multi-item auctions where the agents' valuations of the items are not additive. However, determining the winners so as to maximize revenue is NP-complete. First, we analyze existing approaches for tackling this problem: exhaustive enumeration, dynamic programming, and restricting the allowable combinations. Second, we study the possibility of approximate winner determination, proving inapproximability in the general case, and discussing approximation algorithms for special cases. We then present our search algorithm for optimal winner determination. Experiments are shown on several bid distributions which we introduce. The algorithm allows combinatorial auctions to scale up to significantly larger numbers of items and bids than prior approaches to optimal winner determination by capitalizing on the fact that the space of bids is sparsely populated in practice. The algorithm does this by provably sufficient selective generation of children in the search tree, by using a secondary search for fast child generation, by using heuristics that are admissible and optimized for speed, and by preprocessing the search space in four ways. Incremental winner determination and quote computation techniques are presented.
---
paper_title: Efficient Sealed-Bid Auction Using Hash Chain

paper_content:

This paper proposes the first sealed-bid auction method which uses only hash function. We use a hash chain to commit a bidding price. By using the hash chain, we can drastically reduce the time needed for bidding and opening bids. If we use a practical hash function e.g. SHA-1, our method is 200,000 times faster than former methods that use public key cryptosystems. Accordingly, our method is capable of wide application in terms of the number of bidders and the range of bidding prices.
---
paper_title: A verifiable, bidder-resolved Auction Protocol

paper_content:

Security and privacy have become crucial factors in auction design. Various schemes to ensure the safe conduction of sealed-bid auctions have been proposed recently. We introduce a new standard of privacy for auctions (“full privacy”), that prevents extraction of bid information despite any collusion of participants. This requirement is stronger than other common assumptions that prohibit the collusion of certain third-parties (e.g., distinct auctioneers). Full privacy can be obtained by applying a secret sharing scheme in which the bidders jointly compute the selling price on their own without uncovering any additional information. No auctioneers or other trusted third parties are used to resolve the auction. The major contribution of this work is the fully private (M + 1)st-price auction protocol in which only the winning bidders and the seller learn the selling price. To the best of our knowledge there is no other cryptographic auction protocol that achieves a similar level of privacy. The auction outcome cannot be changed or nullified by dishonest bidders because the protocol is publicly verifiable. As full privacy is our main goal, the drawback of the presented protocol is efficiency. Without relaxing any security demands, it is only applicable for high-security auctions with relatively few bidders in reasonable time.
---
paper_title: Multi-round Anonymous Auction Protocols

paper_content:

SUMMARY Auctions are a critical element of the electronic commerce infrastructure. But for real-time applications, auctions are a potential problem – they can cause significant time delays. Thus, for most real-time applications, sealed-bid auctions are recommended. But how do we handle tie-breaking in sealed-bid auctions? This paper analyzes the use of multi-round auctions where the winners from an auction round participate in a subsequent tie-breaking second auction round. We perform this analysis over the classical first-price sealed-bid auction that has been modified to provide full anonymity. We analyze the expected number of rounds and optimal values to minimize communication costs.
---
paper_title: An Anonymous Aution Protocol with a Single Non-trusted Center Using Binary Trees

paper_content:

Some works about an electronic auction protocol have been proposed. An electronic auction protocol should satisfy the following seven properties: (a)Fair of bidders; (b)Security of bids; (c)Anonymity; (d)Validity of winning bids; (e)Non-repudiation; (f)Robustness; and (g)Efficient bidding points. As for anonymity, previous protocols assume some entities like a dealer or plural centers to be trusted. In this paper, anonymity is realized without a trusted center, maintaining both computational and round complexity low. Furthermore, we represent a bid efficiently by using binary trees: for 2k bidding points, the size of the representation of bids is just k. Previous works investigating a sealed-bid auction aim at "efficiency" but not "entertainment" seen in English auction. We introduce a new idea of entertainment to the opening phase by decreasing winner candidates little by little. Our protocol has the following three main features in addition to the above seven properties: perfect anonymity(a single non-trusted center), efficient bidding points and entertainment.
---
paper_title: An Auction Protocol Which Hides Bids of Losers

paper_content:

Many auction protocols using practical cryptographic means have successfully achieved capability of hiding the bids of each entity, but not the values of bids themselves. In this paper we describe an auction protocol which hides the bids of non-winners even from the bid-opening centers, and still makes it possible to publicly verify the validity of the winning bid, i.e. that it was the highest bid submitted. The first approach to such a protocol was made by Kikuchi et al in [KHT98]. However, several deficiencies have been pointed out regarding their protocol; for example, it is not well suited for handling tie bids.
---
paper_title: Robust, Privacy Protecting and Publicly Verifiable Sealed-Bid Auction

paper_content:

The sealed bid model of auctions is ideally suited for electronic auction systems, as they avoid the requirement for real-time communications between various entities. A sealed bid auction scheme designed by Kikuchi, Harkavy and Tygar is analysed. Several shortcomings are identified in this scheme including the lack of public verifiability and the possibility of collusion between bidders and/or auctioneers. A new scheme is designed to overcome these shortcomings.
---
paper_title: Distributed auction servers resolving winner and winning bid without revealing privacy of bids

paper_content:

We have developed an electronic auction system with a set of distributed servers that collaborate to resolve a winning bid without revealing the secrecy of bids. This paper describes the system architecture and shows the performance in terms of the round complexity and the bandwidth consumption for a message. Based on the actual measurements, the upper bound of number of bidding prices is identified. In addition, by adding some steps to the basic auction protocol in Kikuchi, Harkavy, and Tygar, 1998, we improve the security of protocol so that the second highest bid must not be known even by the winner.
---
paper_title: Efficient private bidding and auctions with an oblivious third party

paper_content:

We describe a novel and efficient protocol for the following problem: A wants to buy some good from B if the price is less than a . B would like to sell, but only for more than b , and neither of them wants to reveal the secret bounds. Will the deal take place? Our solution uses an oblivious third party T who learns no information about a or b , not even whether a > b . The protocol needs only a single round of interaction, ensures fairness, and is not based on general circuit evaluation techniques. It uses a novel construction, which combines homomorphic encryption with the φ-hiding assumption and which may be of independent interest. Applications include bargaining between two parties and secure and efficient auctions in the absence of a fully trusted auction service.
---
paper_title: An Online Public Auction Protocol Protecting Bidder Privacy

paper_content:

On-line auctioning is one of the fundamental services for the new Internet economy. Most current auction services are public auction where all bids are made available to any party. User privacy is a primary concern in electronic world because electronic environment facilitates the gathering of personal data. This paper proposes a public auction protocol that achieves bidder privacy using binding group signatures. A concrete solution for preventing defaults in auctions is also presented.
---
paper_title: Implementation and analysis of Dutch-style sealed-bid auctions computational vs unconditional security

paper_content:

Designing a sealed-bid auction protocol is a challenging problem in the field of applied cryptography. In the last couple of decades, numerous protocols have been proposed in the literature where each one has its own property in terms of the security model, communication and computation complexities. To the best of our knowledge, there has been no study to implement and compare a similar class of sealed-bid auction protocols. This paper therefore implements and evaluates five different Dutch-style sealed-bid auction protocols, of which three protocols are computationally secure and two protocols are unconditionally secure. It mainly focuses on the computational cost of the initialization and verification phases of these privacy-preserving protocols.
---
paper_title: On the Existence of Unconditionally Privacy-Preserving Auction Protocols

paper_content:

We investigate whether it is possible to preserve privacy in sealed-bid auctions to a maximal extent. In particular, this paper focuses on unconditional full privacy , i.e., privacy that relies neither on trusted third parties (like auctioneers), nor on computational intractability assumptions (like the hardness of factoring). These constraints imply a scenario in which bidders exchange messages according to some predefined protocol in order to jointly determine the auction outcome without revealing any additional information. It turns out that the first-price sealed-bid auction can be emulated by an unconditionally fully private protocol. However, the protocol's round complexity is exponential in the bid size, and there is no more efficient protocol. On the other hand, we prove the impossibility of privately emulating the second-price sealed-bid auction for more than two bidders. This impossibility holds even when relaxing various privacy constraints such as allowing the revelation of all but one losing bid (while maintaining anonymity) or allowing the revelation of the second highest bidder's identity.
---

Title: Comprehensive Survey on Privacy-Preserving Protocols for Sealed-Bid Auctions

Section 1: Introduction
Description 1: Introduce the basics of auctions, different types of auctions, and the importance of privacy-preserving protocols in sealed-bid auctions.

Section 2: Desired Properties and Trust Models
Description 2: Discuss the essential properties required for electronic auction mechanisms and various trust models.

Section 3: Our Motivation and Contribution
Description 3: Explain the motivation behind the survey and outline the contributions made by this work.

Section 4: Organization of the Article
Description 4: Provide an overview of how the article is structured and what each section will cover.

Section 5: Preliminary Materials
Description 5: Cover the basic cryptographic techniques and concepts essential for understanding sealed-bid auctions.

Section 6: Survey on Sealed-Bid Auction Protocols
Description 6: Provide a comprehensive overview of the state-of-the-art related to sealed-bid auction protocols classified into different categories.

Section 7: First-Price Sealed-Bid Auctions
Description 7: Explore protocols specifically designed for first-price sealed-bid auctions.

Section 8: Second-Price Sealed-Bid/Vickrey Auctions
Description 8: Discuss protocols that focus on second-price sealed-bid or Vickrey auctions.

Section 9: (M+1)-Price Sealed-Bid Auctions
Description 9: Examine protocols for (M+1)-price sealed-bid auctions where multiple highest bidders win and the (M+1)-st price sets the selling price.

Section 10: Rule-Flexible Sealed-Bid Auctions
Description 10: Cover protocols that provide a flexible framework for sealed-bid auctions, adaptable to different auction rules.

Section 11: Combinatorial Sealed-Bid Auctions
Description 11: Discuss protocols for auctions where bidders can place bids on combinations of items, known as combinatorial auctions.

Section 12: Technical Discussion
Description 12: Highlight technical challenges, limitations, and efficiency considerations for the various protocols discussed.

Section 13: Concluding Remarks
Description 13: Summarize the findings, emphasize the importance of privacy-preserving auction protocols, and suggest areas for future research.

Section 14: Acknowledgment
Description 14: Acknowledge the contributions of reviewers and other individuals who provided feedback on the survey.