# BA2P : Bidirectional and Anonymous Auction Protocol with Dispute-Freeness

Authors: Ke Huang; Yi Mu; Fatemeh Rezaeibagha; Zheyuan He; Xiaosong Zhang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Electronic auction is a popular platform to sell goods, task assignment, and resources’ allocation due to reductions of transaction costs and has attracted a huge number of potential buyers. However, it is challenging to address the disputes between the buyer and the auctioneer. The main reason is, on the one hand, solving such problem leverages to the broad domain of research aspects, such as economic theory, engineering, and cryptography, and, on the other hand, it is difficult to arbitrate in a decentralized and anonymous setting. In this work, we consider a more general framework to solve the potential disputes by enforcing bidirectional confirmation and public verification. Hence, the bidding procedure is clear to inspect and potential disputes can be erased. To achieve this goal, we propose policy-driven chameleon hash and revised linkable-and-redactable ring signature as building blocks. We used these two tools to build a bidirectional and anonymous auction protocol calledBA2P. In our BA2P protocol, the bidders can competitively and anonymously place their bids to outbid others. At the end of the auction protocol, everyone can verify the validity of the bidding proof and decide the winner. Thus, dispute-freeness feature is achieved. The analysis suggests that our proposal is provably secure and practically efficient, and it trades some efficiencies with dispute-freeness feature.


---

## Body

## 1. Introduction

Auction is a process to buy or sell commodities and services [1]. Specifically, the auction is a market institution in which traders or parties submit bids that can be an offer to buy or sell at a given price. Typically, an auction includes the following entities: bidder, seller, auctioneer, commodity, valuation, and price. Electronic auction (E-auction) is a fundamental part of the electronic commerce technology [2]. The Internet-turned e-auction is the most successful stories of web-based services. It removes physical limitations by enabling convenient and fast auction services remotely for audiences at any time and any space [2]. Due to the reductions in transaction costs, huge potential buyers, and independence of time and space, e-auctions are popular mechanisms to sell goods, task assignment, resources’ allocation, etc. [1]. English auction and sealed-bid auctions are two most commonly known auction types. In an English auction, buyers call out their prices increasingly. In a sealed-bid auction, prices are privately submitted to the auctioneer. In addition, the auction can be categorized by the seller-side and the buyer side auction. According to different types of auctions, there could be n buyers to 1 seller, 1 buyer to n sellers, or even n buyers to m sellers [1].Ensuring the e-auction protocol working properly is essential, especially considering the increasingly valuable assets traded in e-auction and people’s increasing preference to purchase items online. Due to the heterogeneity, freely accessible, and full anonymity of the Internet, e-auction protocols suffer from frequent and unprecedented threats from insiders (malicious buyer or auctioneer) and outsiders (e.g., hackers). For example, Abe and Suzuki [3] identified the bid-rigging problem in the sealed auction where the buyer seeks to manipulate the auction by ordering other bidders to bid very low price. This problem could be considered as an insider attack. One of the most challenging problems is dispute settlement and arbitration. During the execution of the e-auction protocol, doubts of the fairness during auction procedure and potential disputes between the buyer and the auctioneer may arise. However, solutions offer us a broad research domain: economy [4], engineering, and cryptography [5, 6]. For instance, how to reach [1] the nash equilibrium in game theory or how to achieve fair arbitration from the legal aspect. This is challenging in a totally decentralized and anonymous setting where the buyer’s identity and the bids are concealed. Ring signature is generally adopted to achieve the buyer anonymity in e-auction protocols [7–9]. Unlike group signature, which requires a group manager for setup, ring signature greatly simplifies the design by removing the need for a centralized entity. However, this also brings difficulties to arbitrate disputes since every buyer is hidden in pseudonyms and no justifiable evidence and mechanism are provided to support the dispute settlement.In this work, by using chameleon hash and ring signature, we give a solution to the aforementioned problems. Simply, Chameleon Hash or Trapdoor Commitment (TC) (also known as a trapdoor one-way hash function) [10] can be viewed as a box with a secret lock. It allows the holder of the key to change the secret (i.e., a committed value) in the box even after the box is locked. Such property allows both the buyer and the auction manager to confirm the bids securely while evidences can be revealed to the public for verification. As long as the buyer or the auction manager finds the bid suspicious or wrong, he will not confirm it. As a result, dispute-freeness is achieved since all successfully placed bids are guaranteed by dual confirmation and cryptographic proof.In this work, we propose a bidirectional and anonymous auction protocol with dispute-freeness, calledBA2P. The framework of our proposal is shown in Figure 1. Similar to the English auction, but with slight adaptations, our proposal allows the buyer to place his bid competitively. The bid is placed anonymously based on ring signature and the use of anonymous cryptocurrency and pseudonym for privacy concerns. An auction manager is delegated to confirm and verify the bids. All bids are bidirectionally verified and confirmed and then revealed during the Open Phase to the public to achieve the dispute-freeness. We propose Policy-driven Chameleon Hash (PCH) and Revised Linkable-and-Redactable Ring signature (R-LRRS) as building blocks to construct our BA2P scheme. Our contributions can be highlighted as below:(1)
We propose the PCH and R-LRRS as building blocks. PCH is a trapdoor one-way hash function with both deterministic and probabilistic hashing algorithms. R-LRRS is a revised version of our previously proposed ring signature [11].(2)
Our proposedBA2P is divided into five phases: initiation, prebidding, bidding, confirmation, and open. Our BA2P leverages PCH and R-LRRS to achieve bidirectional and anonymous bidding with dispute-freeness. Cryptocurrency and pseudonyms are used to achieve transaction and identity privacies for buyers. The buyer can competitively place his bids in order to win the auction. An auction manager is delegated to verify and confirm the bidder’s proof. As each proof is dually confirmed and is publicly verifiable, dispute-freeness feature is provided.(3)
We give the system model and several security requirements of our proposedBA2P. Followed by detailed construction as well as the predefined model, we give security and complexity analysis of our scheme. The evidence suggests that our proposal is provably secure based on intractable assumptions. Meanwhile, our proposal is practically efficient.Figure 1
The framework ofBA2P protocol.


## 2. Related Works

Zhang et al. [1] conducted a comprehensive survey of recent auction approaches. They systematically reviewed the auction-based applications and mechanisms in wireless and mobile systems. Their work is helpful for the reader to study this topic. We summarize the related works on auction protocols as follows.Cryptography offers a broad range of tools for the diverse designs of early auction systems and protocols. From 1999 to 2010, a number of works have been proposed, which applied cryptographic algorithms to achieve various desired properties for auction. Naor et al. [12] proposed an efficient sealed-bid, two-server auction system. This was an early design of private auction. Later, Viswanathan and Dawson [13] proposed a simple, efficient, and secure design to achieve sealed bidding with anonymity. They utilized modular approach in the analysis and design methodology. Later, Nguyen and Traore [7] proposed a public auction protocol that utilized blind group signatures to achieve bidder privacy. Differently, they considered public auction. The design of the public auction scheme was generally diverse to private auction. Omote and Miyaji [14] proposed to achieve English auction with efficient bidding and verification by using bulletin board. Their scheme enables easy revocation and one-time registration. Their scheme is desirable for users with limited computing capabilities. Abe and Suzuki [3] identified the bid-rigging problem in the sealed auction where the buyer seeks to manipulate the auction by ordering other bidders to bid very low price. Peng et al. [15] proposed a new concept, called relative bid privacy.They proposed a new mix network to implement an auction with relative bid privacy. Specifically, they employed ElGamal encryption and re-encryption to hide bidding information. Juels and Szydlo [23] introduced verifiable proxy oblivious transfer to address the security vulnerability in Naor et al.’s work [12]. Xiong et al. [8] proposed an efficient sealed-bidding protocol based on ring signature and variable technique of encryption key chain where the auctioneer is allowed to determine the winning bid while the losing bids are not revealed. Later, Xiong et al. [9] proposed an efficient and spontaneous privacy-preserving English auction protocol based on revocable ring signature. In comparison with their previous work [8], the new scheme in [9] offers conditional privacy-preservation and one-time registration. Most importantly, it is more efficient than the previous work in both communication and computation complexities. Following this, Nojoumian and Stinson [24] built a first-price auction protocol based on a new commitment. A multicomponent commitment is proposed as a building block, in which three schemes with diverse properties are proposed. In another work, Dong and Pang [25] formally studied the notion of receipt-freeness and bidding-price-secrecy by the formalization of observational equivalences and analysis.From 2010 to 2021, the design of auction protocol is mainly affected by the development of cryptography as well as diverse applications. Galal and Youssef [26] proposed several cryptographic primitives as building blocks to achieve a smart contract protocol for a succinctly verifiable sealed-bid auction on the Ethereum blockchain. Here, Ethereum is a decentralized platform based on blockchain technology. Smart contract is a Turing-complete protocol to achieve arbitrary computer program in Ethereum. Galal and Youssef [22] proposed another smart contract-based verifiable sealed-bid auction on the Ethereum blockchain. Similarly, multiple cryptographic primitives are used as building blocks to achieve the design. However, these constructions are generally complex and inefficient. Galal and Youssef [27] proposed Trustee as a trusted and efficient Vickrey auction on top of Ethereum for full privacy-preservation with much lower fees for the online auction. A prototype of Trustee for the inspection and security analysis and gas costs are provided. Jiao et al. [28] proposed an auction-based market model based on proof-of-work based blockchain network for computing resource allocation. Nguyen and Thai [29] exploited smart contract and state channel technologies to achieve decentralized and trustless framework for iterative double auction. An et al. [30] exploited smart contract and greedy strategy to achieve trustless crowdsensed data trading in reverse auction. As observed, Ethereum is a promising and popular platform to develop auction protocol since it supports fast payment and provides smart contract to enable application-rich services.We compare our scheme with relevant works in Table1 with a focus on privacy-preservation. Similarly, we employed a standard cryptographic algorithm called chameleon hash to achieve bidder’s anonymity and hidden bids. Noticeably, we do not rely on a trusted auctioneer since we can run an arbitration protocol to settle the disputes and it is publicly verifiable. To generalize, the early works have mainly focused on utilizing specific methodology or tool as solution, while current works have adopted multiple technologies. Current designs have heavily relied on multiple cryptographic building blocks [22, 26], which imposed high complexities to both design and performance. However, a work focusing on the dispute settlement or with arbitration does not exist in the literature. Therefore, once users have doubts over the process and outcomes, there is no easy way and clear evidence to justify.Table 1
Comparison of bidding schemes.
SchemeTechniqueAuctioneerHidden bidsOpener of bidsOur workChameleon hashDistrustedYesBidderFranklin and Reiter [16]Verifiable signature sharingDistrustedNoAuctioneerKikuchi et al. [17]Secret sharingTrustedYesAuctioneerSako. [18]Standard cryptographic algorithmsTrustedYesAuctioneerSuzuki and Kobayashi [19]Verifiable encryptionDistrustedYesAuctioneerSuzuki and Yokoo [20]Homomorphic encryptionDistrustedYesBidderPeng et al. [21]Secret sharingDistrustedYesAuctioneerXiong et al. [8]Ring signatureTrustedYesBidderGalal and Youssef et al. [22]Commitment and zero-knowledge proofDistrustedYesAuctioneer


## 3. Preliminary

We give some preliminary knowledge used in our work.


### 3.1. Complexity Assumptions

LetG be a cyclic multiplicative group generated by g with prime order q. We informally state the following assumptions:Discrete logarithm problem (DLP) : givenga∈G, where a←RZq, computing a is hard.Decisional Diffie–Hellman problem (DDHP) : giveng,ga,gb,gc∈G, where a,b,c←RZq, deciding whether c=ab is hard.Computational Diffie–Hellman problem (CDHP) : giveng,ga,gb∈G, where a,b←RZq, computing gab is hard.q-Strong Diffie–Hellman problem (q-SDHP) [31]: choose x←RZq. Given a q+1-tuple g,gx,…,gxq∈Gq+1 and a generator g of q-order cyclic group G, computing c,g1/x+c for some c∈Zq∗ is hard.


### 3.2. Bilinear Pairing

Given two multiplicative groupsG and GT with the same group order q and generator g, denote e^:G×G⟶GT as symmetric bilinear map, where e^xa,yb=e^x,yab, for all x,y∈G and a,b←RZq. Additionally, compute e^g,g≠1 is efficient.


### 3.3. Unpredictable File Source

We give the notion of “unpredictable file source” [32] as follows. This notion is used to capture the lower bound of our security given in Section 7.Specifically, denote file sourceℳ as a polynomial algorithm which on input λ, it outputs M0,…,Mn−1,Z. Denote M0,…,Mn−1∈0,1∗ as random vectors and Z∈0,1∗ as auxiliary information. Fix n by 1,2. The guessing probability of ℳ is defined by gpℳ=MaxgpMj|Z. We state that ℳ is an unpredictable file source if gpℳ is negligible.


## 3.1. Complexity Assumptions

LetG be a cyclic multiplicative group generated by g with prime order q. We informally state the following assumptions:Discrete logarithm problem (DLP) : givenga∈G, where a←RZq, computing a is hard.Decisional Diffie–Hellman problem (DDHP) : giveng,ga,gb,gc∈G, where a,b,c←RZq, deciding whether c=ab is hard.Computational Diffie–Hellman problem (CDHP) : giveng,ga,gb∈G, where a,b←RZq, computing gab is hard.q-Strong Diffie–Hellman problem (q-SDHP) [31]: choose x←RZq. Given a q+1-tuple g,gx,…,gxq∈Gq+1 and a generator g of q-order cyclic group G, computing c,g1/x+c for some c∈Zq∗ is hard.


## 3.2. Bilinear Pairing

Given two multiplicative groupsG and GT with the same group order q and generator g, denote e^:G×G⟶GT as symmetric bilinear map, where e^xa,yb=e^x,yab, for all x,y∈G and a,b←RZq. Additionally, compute e^g,g≠1 is efficient.


## 3.3. Unpredictable File Source

We give the notion of “unpredictable file source” [32] as follows. This notion is used to capture the lower bound of our security given in Section 7.Specifically, denote file sourceℳ as a polynomial algorithm which on input λ, it outputs M0,…,Mn−1,Z. Denote M0,…,Mn−1∈0,1∗ as random vectors and Z∈0,1∗ as auxiliary information. Fix n by 1,2. The guessing probability of ℳ is defined by gpℳ=MaxgpMj|Z. We state that ℳ is an unpredictable file source if gpℳ is negligible.


## 4. Building Blocks

We introduce the building blocks of our work in this section.


### 4.1. Policy-Driven Chameleon Hash

We propose the Policy-driven Chameleon Hash (PCH) as follows: PCH is a variant of chameleon hash (Trapdoor Commitment (TC) [10]) featured by two different hashing algorithms: Probabilistic Hashing ℋPCH and Deterministic Hashing ℋ^PCH. To explain, ℋPCH generates each hash with a freshly chosen randomness, while ℋ^PCH computes each hash deterministically from the message itself (similar as hash-as-a-key method [32]). A PCH scheme consists of the following five algorithms GPCH,ℋPCH,ℋ^PCH,VPCH,ℛPCH.GPCHλ⟶param,x,y: on inputting a security parameter λ, choose two groups G and GT with prime order q and generator g. Set bilinear map as e^:G×G⟶GT. Set hash functions as H2:0,1∗⟶Zq. Denote param=g,q,G,GT,H2,e^. Select a random number x←RZq∗ as the trapdoor key, and compute y=gx as the hash key. Output param,x,y.ℋPCHCID,y,m⟶ℏ,r: pick a customized identity CID∈0,1∗. Given the hash key y, compute coefficients e=H2CID and h1=ge. Choose a random α←RZq∗ and compute probabilistic chameleon randomness r=r1,r2=gα,yα. Then, compute chameleon hash ℏ=e^g,gH2m⋅e^h1⋅y,r1. Output ℏ,r.ℋ^PCHCID,y,m⟶ℏ^,r^: pick a customized identity CID∈0,1∗. Given a hash key y, compute coefficients e=H2CID, h1=ge, and k0=H2m. Compute deterministic chameleon randomness r^=r^1,r^2=gk0,yk0. Then, compute a deterministic chameleon hash ℏ^=e^r^1,g⋅e^h1⋅y,r^1. Output ℏ^,r^.VPCHCID,y,ℏ,r,m⟶0,1ordeter: on inputting a customized identity CID, a public key y, and a tuple ℏ,r,m, where m∈0,1∗, compute coefficients e=H2CID and h1=ge. Then, check whether equation 1 holds:(1)ℏ=?e^g,gH2m⋅e^h1⋅y,r1.and check whethere^r1,y=?e^r2,g holds. If no, output 0; else, compute k0=H2m and check whether r=?gk0,yk0. If yes, output deter which signifies ℏ is an output of ℋ^PCH; else, output 1 to indicate ℏ is an output of ℋPCH. ℛPCHℏ,r,m,x,m′⟶⊥orr′: on inputting a tuple ℏ,r,m, a customized identity CID, a trapdoor key x, and a new message m′, compute coefficients e=h0=H2CID and h1=ge. Then, compute new chameleon randomness r′=r1′,r2′=r1⋅gx+e−1H2m−H2m′,r2⋅yx+e−1H2m−H2m′.


### 4.2. Revised Linkable-and-Redactable Ring Signature

Liu et al. [33] proposed 1-out-of-n Linkable Spontaneous Anonymous Group (LSAG) Signature as an extension of Spontaneous Anonymous Group (SAG) [34]. In our previous work [11], we extended Liu et al.’s LSAG [33] to a Linkable-and-Redactable Ring Signature (LRRS) [11]. In this work, we revised our previous LRRS scheme slightly to derive a Revised LRRS (R-LRRS). To note, if we use a different L for each signing, linkability will not be achieved in our R-LRRS. An R-LRRS signature consists of the following four algorithms GR0LRRS,SR0LRRS,VR0LRRS,ℛR0LRRS.GR0LRRSλ⟶paramR0LRRS,x,y: on inputting a security parameter λ, choose a group G generated by g of order q. Then, set cryptographic hash function: H1:0,1∗⟶G and H2:0,1∗⟶Zq. Derive param. Finally, pick a random number x←RZq∗ as the private key, and compute y=gx as the public key. Output paramR0LRRS,x,y.SR0LRRSx,m,L,ℏ,r⟶σLmor⊥: input a private key x, a message m∈0,1∗, a list of n public keys L=yi1≤i≤n, and a set of tuples ℏ,r=ℏi,ri1≤i≤n. User π generates coefficients as follows:(1)
SetCID=L as a customized identity, compute h0=H1CID and y˜π=h0xπ for xπ←RZq. Then, pick two random numbers u,v←RZq and compute sπ+1=H2L,y˜π,gu,h0v.(2)
For each1≤i≤n, run VPCHCID,ℏi,ri,m. If all outputs are 1 or deter, proceed; otherwise, return ⊥ and terminate.(3)
For eachi=π+1,…,n,1,…,π−1, user π picks a random number βi←RZq∗, and compute si+1=H2L,y˜,ℏi⋅yisi,h0βi⋅y˜si.(4)
Then, computeαπ=u−xπsπmodq, and βπ=v−xπsπmodq.(5)
OutputσLm=s1,r1,…,rn,β1,…,βn,y˜π.VR0LRRSL,m,σLm,ℏ,r⟶0or1: on inputting a list L of n public keys, a message m, the ℛR0LRRS signature σLm, and a set of tuples ℏ,r=ℏi,ri1≤i≤n, the signature verification algorithm proceeds as follows:(1)
SetCID=L as a customized identity. Compute coefficients L=CID, h0=H1CID, and y˜π=h0xπ.(2)
Fori=π+1,…,n,1,…π−1, run VPCHL,y,ℏi,ri,m. If all outputs are 1 or deter, proceed; otherwise, abort and terminate.(3)
For eachi=π+1,…,n,1,…,π−1, compute zi′=ℏi⋅yisi and zi″=h0βi⋅y˜si. Then, compute si+1=H2L,y˜π,zi′,zi″, for i≠n.(4)
Check whethers1=?H2L,y˜π,zn′,zn″. If it holds, output 1; else, output 0.ℛR0LRRSx,L,m′,σLm⟶σLm′or⊥: on inputting a private signing key x, a list L of n public keys, a new message m′, and an old signature σLm, perform redaction as follows:(1)
SetCID=L as a customized identity. Compute coefficients h0=H1CID and h1=ge.(2)
For each1≤i≤n, run ℛPCHℏi,ri,m,x,m′ to derive ri′. If no ⊥ is returned, proceed; else, return ⊥ and terminate.(3)
For each1≤i≤n, run VPCHCID,y,ℏi,ri,m. If no 0 is returned, proceed; else, return ⊥ and terminate.(4)
OutputσLm′=s1,r1′,…,rn′,β1,…,βn,y˜π.


## 4.1. Policy-Driven Chameleon Hash

We propose the Policy-driven Chameleon Hash (PCH) as follows: PCH is a variant of chameleon hash (Trapdoor Commitment (TC) [10]) featured by two different hashing algorithms: Probabilistic Hashing ℋPCH and Deterministic Hashing ℋ^PCH. To explain, ℋPCH generates each hash with a freshly chosen randomness, while ℋ^PCH computes each hash deterministically from the message itself (similar as hash-as-a-key method [32]). A PCH scheme consists of the following five algorithms GPCH,ℋPCH,ℋ^PCH,VPCH,ℛPCH.GPCHλ⟶param,x,y: on inputting a security parameter λ, choose two groups G and GT with prime order q and generator g. Set bilinear map as e^:G×G⟶GT. Set hash functions as H2:0,1∗⟶Zq. Denote param=g,q,G,GT,H2,e^. Select a random number x←RZq∗ as the trapdoor key, and compute y=gx as the hash key. Output param,x,y.ℋPCHCID,y,m⟶ℏ,r: pick a customized identity CID∈0,1∗. Given the hash key y, compute coefficients e=H2CID and h1=ge. Choose a random α←RZq∗ and compute probabilistic chameleon randomness r=r1,r2=gα,yα. Then, compute chameleon hash ℏ=e^g,gH2m⋅e^h1⋅y,r1. Output ℏ,r.ℋ^PCHCID,y,m⟶ℏ^,r^: pick a customized identity CID∈0,1∗. Given a hash key y, compute coefficients e=H2CID, h1=ge, and k0=H2m. Compute deterministic chameleon randomness r^=r^1,r^2=gk0,yk0. Then, compute a deterministic chameleon hash ℏ^=e^r^1,g⋅e^h1⋅y,r^1. Output ℏ^,r^.VPCHCID,y,ℏ,r,m⟶0,1ordeter: on inputting a customized identity CID, a public key y, and a tuple ℏ,r,m, where m∈0,1∗, compute coefficients e=H2CID and h1=ge. Then, check whether equation 1 holds:(1)ℏ=?e^g,gH2m⋅e^h1⋅y,r1.and check whethere^r1,y=?e^r2,g holds. If no, output 0; else, compute k0=H2m and check whether r=?gk0,yk0. If yes, output deter which signifies ℏ is an output of ℋ^PCH; else, output 1 to indicate ℏ is an output of ℋPCH. ℛPCHℏ,r,m,x,m′⟶⊥orr′: on inputting a tuple ℏ,r,m, a customized identity CID, a trapdoor key x, and a new message m′, compute coefficients e=h0=H2CID and h1=ge. Then, compute new chameleon randomness r′=r1′,r2′=r1⋅gx+e−1H2m−H2m′,r2⋅yx+e−1H2m−H2m′.


## 4.2. Revised Linkable-and-Redactable Ring Signature

Liu et al. [33] proposed 1-out-of-n Linkable Spontaneous Anonymous Group (LSAG) Signature as an extension of Spontaneous Anonymous Group (SAG) [34]. In our previous work [11], we extended Liu et al.’s LSAG [33] to a Linkable-and-Redactable Ring Signature (LRRS) [11]. In this work, we revised our previous LRRS scheme slightly to derive a Revised LRRS (R-LRRS). To note, if we use a different L for each signing, linkability will not be achieved in our R-LRRS. An R-LRRS signature consists of the following four algorithms GR0LRRS,SR0LRRS,VR0LRRS,ℛR0LRRS.GR0LRRSλ⟶paramR0LRRS,x,y: on inputting a security parameter λ, choose a group G generated by g of order q. Then, set cryptographic hash function: H1:0,1∗⟶G and H2:0,1∗⟶Zq. Derive param. Finally, pick a random number x←RZq∗ as the private key, and compute y=gx as the public key. Output paramR0LRRS,x,y.SR0LRRSx,m,L,ℏ,r⟶σLmor⊥: input a private key x, a message m∈0,1∗, a list of n public keys L=yi1≤i≤n, and a set of tuples ℏ,r=ℏi,ri1≤i≤n. User π generates coefficients as follows:(1)
SetCID=L as a customized identity, compute h0=H1CID and y˜π=h0xπ for xπ←RZq. Then, pick two random numbers u,v←RZq and compute sπ+1=H2L,y˜π,gu,h0v.(2)
For each1≤i≤n, run VPCHCID,ℏi,ri,m. If all outputs are 1 or deter, proceed; otherwise, return ⊥ and terminate.(3)
For eachi=π+1,…,n,1,…,π−1, user π picks a random number βi←RZq∗, and compute si+1=H2L,y˜,ℏi⋅yisi,h0βi⋅y˜si.(4)
Then, computeαπ=u−xπsπmodq, and βπ=v−xπsπmodq.(5)
OutputσLm=s1,r1,…,rn,β1,…,βn,y˜π.VR0LRRSL,m,σLm,ℏ,r⟶0or1: on inputting a list L of n public keys, a message m, the ℛR0LRRS signature σLm, and a set of tuples ℏ,r=ℏi,ri1≤i≤n, the signature verification algorithm proceeds as follows:(1)
SetCID=L as a customized identity. Compute coefficients L=CID, h0=H1CID, and y˜π=h0xπ.(2)
Fori=π+1,…,n,1,…π−1, run VPCHL,y,ℏi,ri,m. If all outputs are 1 or deter, proceed; otherwise, abort and terminate.(3)
For eachi=π+1,…,n,1,…,π−1, compute zi′=ℏi⋅yisi and zi″=h0βi⋅y˜si. Then, compute si+1=H2L,y˜π,zi′,zi″, for i≠n.(4)
Check whethers1=?H2L,y˜π,zn′,zn″. If it holds, output 1; else, output 0.ℛR0LRRSx,L,m′,σLm⟶σLm′or⊥: on inputting a private signing key x, a list L of n public keys, a new message m′, and an old signature σLm, perform redaction as follows:(1)
SetCID=L as a customized identity. Compute coefficients h0=H1CID and h1=ge.(2)
For each1≤i≤n, run ℛPCHℏi,ri,m,x,m′ to derive ri′. If no ⊥ is returned, proceed; else, return ⊥ and terminate.(3)
For each1≤i≤n, run VPCHCID,y,ℏi,ri,m. If no 0 is returned, proceed; else, return ⊥ and terminate.(4)
OutputσLm′=s1,r1′,…,rn′,β1,…,βn,y˜π.


## 5. Definitions

In this section, we present our system model and security requirements.


### 5.1. System Model

The framework of ourBA2P is shown in Figure 1. It consists of four parties: auction manager (AM), seller, buyer, and certificate authority (CA). We briefly introduce each entity as follows:Auction Manager (AM). Auction manager is the one who initiates the system and holds the auction on behalf of the seller. The AM also holds the buyer’s deposit and publishes misbehaviors by deducting the deposit. After he verifies and confirms a winner’s bid, he relays the winner’s money from the buyer to the seller via anonymous cryptocurrency.Seller. Seller is the one who wishes to sell his merchandise online. He delegates the AM to hold an auction and transacts with AM with anonymous cryptocurrency. He communicates with AM via the anonymous channel.Buyer. Buyer is the one who involves in an auction protocol anonymously to make an offer. He places his bid competitively in order to outbid others. If he wins, he will send money to AM via cryptocurrency, as previously negotiated and confirmed. He communicates with AM via the anonymous channel.Certificate Authority (CA). Certificate authority is a trusted third party which is responsible for assigning private and public key pairs to each buyer, seller, and AM.


### 5.2. Security Requirements

A secureBA2P scheme satisfies the following properties:Ours is secure if the underlying R-LRRS scheme satisfies existential unforgeability against adaptive chosen-plaintext under chosen-public-key attack (EU-ACP-CPK) [33]. The EU-ACP-CPK security is an extension of the notion of existential unforgeability under adaptive chosen-message-attacks (EUF-CMA) [35]. Unlike EUF-CMA, EU-ACP-CPK additionally allows the adversary to select an arbitrary subset of initially generated public keys during each round of signing oracle access. Given the public keys of all group members in the aforementioned way, the adversary still cannot forge a valid signature for any message m. A formal definition for EU-ACP-CPK security is given in [33, 36].Definition 1.
LetSO be the signing oracle which takes inputs of any public key list L′=y,…,yn′ and any message m′ as queried and outputs a signature σ′ as a response such that VR0LRRSL′,m′,σL′m′=1. An R-LRRS scheme satisfies EU-ACP-CPK if, for any Probabilistic Polynomial Time (PPT) adversary A with signing oracle SO such that L,m,σLm←ASOL, A’s probability in successfully forging a valid signature σ∗ such that VL∗,m∗,σL∗m∗=1 is negligible. Here, L∗,m∗,σ∗ is not queried to the signing oracle SO previously.
Like all ring signature-based auction protocols proposed in [7–9], our BA2Pis secure if the underlying R-LRRS scheme satisfies anonymity. This means no adversary can efficiently determine the private key used to produce the given R-LRRS signature.Definition 2.
An R-LRRS scheme satisfies anonymity if, for any PPT algorithmA, on inputs of any message m, any list L of n public keys, any set of t private keys Xt=x1,…,xt⊂L, and any valid R-LRRS signature σLm generated by the signer π, A’s probability in successfully linking the signature σLm to the signer π is negligible.
OurBA2P is secure if the underlying chameleon hash scheme satisfies collision-resistance (COL-RES) and indistinguishability (IND). Following Camenisch et al.’s security model [37], we formalize the security requirements of COL-RES and IND as follows. To note, since one of our PCH’s subalgorithm ℋ^PCH cannot satisfy any semantic security, we prove by assuming the existence of unpredictable file source (as given in Section 3.3) to set up a lower bound [32].Definition 3.
A PCH scheme satisfies COL-RES security if, for any PPT algorithmA, it is hard to derive a fresh hash collision under unpredictable file source [32], i.e., collision-resistance under unpredictable file source [32], COL-UNP.Definition 4.
A PCH scheme satisfies IND security if, for any PPTA, following the model sketched in Figure 1 of [37], it is hard to distinguish between outputs of deterministic hash (generated by ℋ^PCH) and probabilistic hash ((generated by ℋPCH)). Denote this security as IND-D&P.


## 5.1. System Model

The framework of ourBA2P is shown in Figure 1. It consists of four parties: auction manager (AM), seller, buyer, and certificate authority (CA). We briefly introduce each entity as follows:Auction Manager (AM). Auction manager is the one who initiates the system and holds the auction on behalf of the seller. The AM also holds the buyer’s deposit and publishes misbehaviors by deducting the deposit. After he verifies and confirms a winner’s bid, he relays the winner’s money from the buyer to the seller via anonymous cryptocurrency.Seller. Seller is the one who wishes to sell his merchandise online. He delegates the AM to hold an auction and transacts with AM with anonymous cryptocurrency. He communicates with AM via the anonymous channel.Buyer. Buyer is the one who involves in an auction protocol anonymously to make an offer. He places his bid competitively in order to outbid others. If he wins, he will send money to AM via cryptocurrency, as previously negotiated and confirmed. He communicates with AM via the anonymous channel.Certificate Authority (CA). Certificate authority is a trusted third party which is responsible for assigning private and public key pairs to each buyer, seller, and AM.


## 5.2. Security Requirements

A secureBA2P scheme satisfies the following properties:Ours is secure if the underlying R-LRRS scheme satisfies existential unforgeability against adaptive chosen-plaintext under chosen-public-key attack (EU-ACP-CPK) [33]. The EU-ACP-CPK security is an extension of the notion of existential unforgeability under adaptive chosen-message-attacks (EUF-CMA) [35]. Unlike EUF-CMA, EU-ACP-CPK additionally allows the adversary to select an arbitrary subset of initially generated public keys during each round of signing oracle access. Given the public keys of all group members in the aforementioned way, the adversary still cannot forge a valid signature for any message m. A formal definition for EU-ACP-CPK security is given in [33, 36].Definition 1.
LetSO be the signing oracle which takes inputs of any public key list L′=y,…,yn′ and any message m′ as queried and outputs a signature σ′ as a response such that VR0LRRSL′,m′,σL′m′=1. An R-LRRS scheme satisfies EU-ACP-CPK if, for any Probabilistic Polynomial Time (PPT) adversary A with signing oracle SO such that L,m,σLm←ASOL, A’s probability in successfully forging a valid signature σ∗ such that VL∗,m∗,σL∗m∗=1 is negligible. Here, L∗,m∗,σ∗ is not queried to the signing oracle SO previously.
Like all ring signature-based auction protocols proposed in [7–9], our BA2Pis secure if the underlying R-LRRS scheme satisfies anonymity. This means no adversary can efficiently determine the private key used to produce the given R-LRRS signature.Definition 2.
An R-LRRS scheme satisfies anonymity if, for any PPT algorithmA, on inputs of any message m, any list L of n public keys, any set of t private keys Xt=x1,…,xt⊂L, and any valid R-LRRS signature σLm generated by the signer π, A’s probability in successfully linking the signature σLm to the signer π is negligible.
OurBA2P is secure if the underlying chameleon hash scheme satisfies collision-resistance (COL-RES) and indistinguishability (IND). Following Camenisch et al.’s security model [37], we formalize the security requirements of COL-RES and IND as follows. To note, since one of our PCH’s subalgorithm ℋ^PCH cannot satisfy any semantic security, we prove by assuming the existence of unpredictable file source (as given in Section 3.3) to set up a lower bound [32].Definition 3.
A PCH scheme satisfies COL-RES security if, for any PPT algorithmA, it is hard to derive a fresh hash collision under unpredictable file source [32], i.e., collision-resistance under unpredictable file source [32], COL-UNP.Definition 4.
A PCH scheme satisfies IND security if, for any PPTA, following the model sketched in Figure 1 of [37], it is hard to distinguish between outputs of deterministic hash (generated by ℋ^PCH) and probabilistic hash ((generated by ℋPCH)). Denote this security as IND-D&P.


## 6. The Construction ofBA2P

The detailed construction of ourBA2P is given in this section. A workflow of our BA2P is given in Figure 2.Figure 2
The workflow ofBA2P protocol.


### 6.1. Initiation

To joinBA2P, each user (buyer, seller, and AM) needs to acquire a set of private and public key pairs from the CA. We assume each user is assigned with one key pair x,y for simplicity. The AM selects a security parameter λ and runs GPCHλ and GR0LRRSλ to initiate the system.


### 6.2. Prebidding Phase

During this stage, each buyer is required to place his first bid. When this stage is finished, the first bid proof is generated. In addition, a deposit is sent to the AM. The AM can fix the first bid by setting up a base price. The first bid is paid as a ticket to the auction and a deposit to ensure penalization of future misbehavior. The deposit will be refunded if it is not a winner’s bid. When this phase is over, each buyer is supposed to output the first bid proof.(1)
Suppose the buyerπ places his first bid bidbase at time point tπ, where tπ is only known to the buyer π. He sends money to the AM via an anonymous cryptocurrency. Denote tπ as the time of the buyer π’s payment generation, xπ as the private key of the buyer π and yπ=gxπ as the corresponding public key, and xAM as the private key of AM and yAM=gxAM as the corresponding public key.(2)
Buyerπ randomly collects n public keys to form a sequence of ring L=y1,…,yL1≤i≤n, where y1 is the head and yn is the tail of the ring. Here, π∈1,L is hidden in the L and unknown to the public.(3)
For each1≤i≤n, the buyer π runs ℏi,ri←ℋPCHCID,yπ,tπ and ℏ^i,r^i←ℋ^PCHCID,yπ,tπ. Denote ℏ,r=ℏi,ri1≤i≤n as the first set of commitments and ℏ^i,r^i=ℏ^i,r^i1≤i≤n as the second set of commitments, and both are committed to tπ.(4)
Buyerπ runs σLtπ←SR0LRRSCID,xπ,L,ℏ,r and σ^Ltπ←SR0LRRSCID,xAM,L,ℏ^,r^. Output prffbp=σLtπ,σ^Ltπ as the first bid proof. Buyer π sends the first bid proof prffbp to the AM.To note, we use a different set of public keysLi for each different signing to generate R-LRRS signature. Thus, linkability will not hold in our BA2P. In other words, it is hard to detect two signatures generated by the same signer. This is vital since linkability will break the anonymity in our scheme (but is useful to detect double-spending in cryptocurrencies [33]).


### 6.3. Bidding Phase

During this stage, each buyer competitively places his new bids in order to outbid others. A bulletin board system (BBS) can be utilized to record the bidding history. At the end of this phase, the buyer is supposed to output the last bid proof.(1)
SetσL=σLtπ and σL^=σL^tπ. Set prflbp=σL,σL^ as the last bid proof.(2)
For a new bidbidπ,curr placed at time tπ,curr, suppose tπ,last is the time of last bid (for simplicity, assume tπ,last=tπ), and the buyer π runs ℛR0LRRSxπ,L,tπ,curr,σLtπ,last to generate a new signature σLtπ,curr. Then, set σL=σLtπ,curr.(3)
Repeat step 2 if the buyerπ places another bid. When this phase is over, output prflbp. Buyer π sends the last bid proof prflbp to the AM.To note,σLbidπ,curr is not necessarily required to be calculated immediately when the buyer π places a new bid. Ideally, it is just for the last bid. However, due to the unpredictability of the bidding process, it is undetermined which one is the last bid until this phase ends.


### 6.4. Confirmation Phase

In this stage, the AM is supposed to check the BBS and all last bid proofsprflbpi1≤i≤j0 (suppose there are j0 buyers who have placed their bids). At the end of this phase, the AM generates a confirmation proof prfconi for user i as follows:(1)
Parse the buyeri’s last bidding proof as prflbpi=σLti,σ^Lti, where ti is the time of buyer i’s first bid. Denote tπ,end as the time of buyer i’s last bid in the bidding phase. Set buyer i’s confirmation proof initially as prfconi=prflbpi.(2)
For each buyer1≤i≤j0, the AM runs ℛR0LRRSxAM,Li,tπ,end,σ^Lti to generate σ^L′bidπ,end. Set σ^Lti=σ^L′bidπ,end.(3)
AM relays the confirmation proofprfconi to each buyer i.


### 6.5. Open Phase

At this stage, each buyer is supposed to open his commitments to the first bid proof (i.e., inputs used to compute the first commitment). Meanwhile, AM will open his commitments to the confirmation proof (i.e., inputs used to compute the second commitment). Failure to comply leads to invalid bid. Based on the above, the public can verify the validity of the auction procedure and determine a winner. We assume each buyer has placed bids more than once and the buyerπ is the winner for the ease of analysis. We show how to verify as follows.(1)
Buyerπ reveals the first bid proof prffbp, the last bid proof prflbp, and corresponding commitments ℏ,r,ℏ^,r^=ℏi,ri1≤i≤n,ℏ^i,r^i1≤i≤n to the public. Accordingly, the AM reveals the confirmation proof prfcon and corresponding commitments to the public. The public can run VPCH and VR0LRRS to verify the validity of these proofs and commitments.(2)
Based on the information recorded in BBS, the public can determine a winner. Since each bid is confirmed bidirectionally by the buyer and the AM, it is undeniable for either the buyer or the AM to dispute the validity of the bid. This idea is brought from undeniable signature [38].Once the winner is determined and confirmed, the winner can transmit the money via anonymous cryptocurrency to the AM. In return, the AM will relay the money to the seller (maybe charge some transaction fees). In addition, it arranges the shipment of the purchased physical assets to the buyer or grant him access to the purchased digital assets. Accordingly, the shipment and the access are all conducted in the anonymous channel.


## 6.1. Initiation

To joinBA2P, each user (buyer, seller, and AM) needs to acquire a set of private and public key pairs from the CA. We assume each user is assigned with one key pair x,y for simplicity. The AM selects a security parameter λ and runs GPCHλ and GR0LRRSλ to initiate the system.


## 6.2. Prebidding Phase

During this stage, each buyer is required to place his first bid. When this stage is finished, the first bid proof is generated. In addition, a deposit is sent to the AM. The AM can fix the first bid by setting up a base price. The first bid is paid as a ticket to the auction and a deposit to ensure penalization of future misbehavior. The deposit will be refunded if it is not a winner’s bid. When this phase is over, each buyer is supposed to output the first bid proof.(1)
Suppose the buyerπ places his first bid bidbase at time point tπ, where tπ is only known to the buyer π. He sends money to the AM via an anonymous cryptocurrency. Denote tπ as the time of the buyer π’s payment generation, xπ as the private key of the buyer π and yπ=gxπ as the corresponding public key, and xAM as the private key of AM and yAM=gxAM as the corresponding public key.(2)
Buyerπ randomly collects n public keys to form a sequence of ring L=y1,…,yL1≤i≤n, where y1 is the head and yn is the tail of the ring. Here, π∈1,L is hidden in the L and unknown to the public.(3)
For each1≤i≤n, the buyer π runs ℏi,ri←ℋPCHCID,yπ,tπ and ℏ^i,r^i←ℋ^PCHCID,yπ,tπ. Denote ℏ,r=ℏi,ri1≤i≤n as the first set of commitments and ℏ^i,r^i=ℏ^i,r^i1≤i≤n as the second set of commitments, and both are committed to tπ.(4)
Buyerπ runs σLtπ←SR0LRRSCID,xπ,L,ℏ,r and σ^Ltπ←SR0LRRSCID,xAM,L,ℏ^,r^. Output prffbp=σLtπ,σ^Ltπ as the first bid proof. Buyer π sends the first bid proof prffbp to the AM.To note, we use a different set of public keysLi for each different signing to generate R-LRRS signature. Thus, linkability will not hold in our BA2P. In other words, it is hard to detect two signatures generated by the same signer. This is vital since linkability will break the anonymity in our scheme (but is useful to detect double-spending in cryptocurrencies [33]).


## 6.3. Bidding Phase

During this stage, each buyer competitively places his new bids in order to outbid others. A bulletin board system (BBS) can be utilized to record the bidding history. At the end of this phase, the buyer is supposed to output the last bid proof.(1)
SetσL=σLtπ and σL^=σL^tπ. Set prflbp=σL,σL^ as the last bid proof.(2)
For a new bidbidπ,curr placed at time tπ,curr, suppose tπ,last is the time of last bid (for simplicity, assume tπ,last=tπ), and the buyer π runs ℛR0LRRSxπ,L,tπ,curr,σLtπ,last to generate a new signature σLtπ,curr. Then, set σL=σLtπ,curr.(3)
Repeat step 2 if the buyerπ places another bid. When this phase is over, output prflbp. Buyer π sends the last bid proof prflbp to the AM.To note,σLbidπ,curr is not necessarily required to be calculated immediately when the buyer π places a new bid. Ideally, it is just for the last bid. However, due to the unpredictability of the bidding process, it is undetermined which one is the last bid until this phase ends.


## 6.4. Confirmation Phase

In this stage, the AM is supposed to check the BBS and all last bid proofsprflbpi1≤i≤j0 (suppose there are j0 buyers who have placed their bids). At the end of this phase, the AM generates a confirmation proof prfconi for user i as follows:(1)
Parse the buyeri’s last bidding proof as prflbpi=σLti,σ^Lti, where ti is the time of buyer i’s first bid. Denote tπ,end as the time of buyer i’s last bid in the bidding phase. Set buyer i’s confirmation proof initially as prfconi=prflbpi.(2)
For each buyer1≤i≤j0, the AM runs ℛR0LRRSxAM,Li,tπ,end,σ^Lti to generate σ^L′bidπ,end. Set σ^Lti=σ^L′bidπ,end.(3)
AM relays the confirmation proofprfconi to each buyer i.


## 6.5. Open Phase

At this stage, each buyer is supposed to open his commitments to the first bid proof (i.e., inputs used to compute the first commitment). Meanwhile, AM will open his commitments to the confirmation proof (i.e., inputs used to compute the second commitment). Failure to comply leads to invalid bid. Based on the above, the public can verify the validity of the auction procedure and determine a winner. We assume each buyer has placed bids more than once and the buyerπ is the winner for the ease of analysis. We show how to verify as follows.(1)
Buyerπ reveals the first bid proof prffbp, the last bid proof prflbp, and corresponding commitments ℏ,r,ℏ^,r^=ℏi,ri1≤i≤n,ℏ^i,r^i1≤i≤n to the public. Accordingly, the AM reveals the confirmation proof prfcon and corresponding commitments to the public. The public can run VPCH and VR0LRRS to verify the validity of these proofs and commitments.(2)
Based on the information recorded in BBS, the public can determine a winner. Since each bid is confirmed bidirectionally by the buyer and the AM, it is undeniable for either the buyer or the AM to dispute the validity of the bid. This idea is brought from undeniable signature [38].Once the winner is determined and confirmed, the winner can transmit the money via anonymous cryptocurrency to the AM. In return, the AM will relay the money to the seller (maybe charge some transaction fees). In addition, it arranges the shipment of the purchased physical assets to the buyer or grant him access to the purchased digital assets. Accordingly, the shipment and the access are all conducted in the anonymous channel.


## 7. The Security Analysis ofBA2P

Here, we give the security analysis of our proposed scheme based on security requirements defined in Section5.2.Theorem 1.
If there exists a PPT adversaryA who can break the EU-ACP-CPK property of our R-LRRS scheme, we can construct a PPT simulator S to solve the DLP with nonnegligible probability.Proof.
SupposeA can forge an R-LRRS signature with nonnegligible probability, i.e.,(2)PrAL⟶m,σ:VL,m,σ=1>1Q1k,for some polynomial Q1. Let qH be the maximum number of queries to H1 and H2 in total. Let qS be the maximum number of queries to SO. Then, we can construct a PPT simulator S which invokes A to solve the DLP with nonnegligible probability. Given a DLP instance g,gx, S sets y=gx where x∈L, and it aims to output x. S simulates inputs for A and processes outputs from A adaptively. We give a proof sketch as follows:
Letparam be the system parameter generated in the initiation phase. Let H1 and H2 be random oracles controlled by S, which return the same response to the same query by maintaining query histories. Let ℒ be a list of public keys where each key is generated properly according to the prebidding phase. S invokes A adaptively based on the constructed inputs and A’s responses. A simulation transcript tape T is used to record the invocation of A. S can simulate SO by back patching [33]. Some outputs of A are valid forgeries of R-LRRS signatures and are used to solve DLP with nonnegligible probability. A proof of unforgeability based on rewind simulation is given in [33]. Specifically, the signature returned by SO is the same as the one signed by the signer π in the adversary A’s view. To derive this conclusion, we can discuss the conditional probability of A in successfully forging a valid signature σ∗ in each A’s transcript and the queries made to the signing oracle SO. Furthermore, S can do a rewind-simulation accordingly. By considering the equations based on two l,π-forgery signatures from the tape T and a rewind-simulation tape S′, we can derive the answer to the DLP instance and bound the S’s probability in solving the DLP. Due to the intractability of the DLP, our R-LRRS satisfies EU-ACP-CPK security. Refer to [33], for more details.Theorem 2.
If there exists a PPT adversaryA who can break the anonymity of our R-LRRS scheme, we can construct a PPT simulator S to solve the DDHP with a nonnegligible advantage.Proof. On given g,ga,gb,gc∈G, the simulator S is supposed to call A and determine c=?ab. Suppose there exists a PPT adversary A, on inputs of any message m, a list L of n public keys, a set of t private keys Xt=x1,…,xt⊂L,0≤t<n−1, and a valid R-LRRS signature σLm generated by the buyer π; the A’s probability in successfully linking the signature σLm to the buyer (signer) π for polynomial Qk is(3)PrAm,L,SK,σLm⟶π>1n−t+1Qk.Then, we can construct a PPT simulatorS to solve the DDHP with probability:(4)Prℳg,ga,gb,gc⟶c=?ab=12+1Q2k.Refer to [33], for details.Theorem 3.
If there exists a PPT adversaryA who can break the COL-UNP of our PCH scheme, we can construct an algorithm ℬ to solve the q-SDHP with nonnegligible probability.Proof. We give a proof sketch as follows. On a given q-SDHP instance (g,gx,…,gxq) (parse it by (A0,A1,…,Aq), where x∈Zp∗), here, x∈Zp∗ is unknown. We can construct an algorithm ℬ which interacts with A to derive an answer: (c,g1/x+c), for some c∈Zq∗ as follows:(i)
Setup: the algorithmℬ runs GPCH to initiate the system and derives G,GT,g,q,H2,e^,x,y, where y=gx, and x is privately kept by ℬ. ℬ sends G,GT,g,q,H2,e^,y to A.(ii)
Query: adversaryA issues qs distinct queries CIDi,mi′,mi,ℏi,rii∈1,qs to ℬ (assume qs=q−1).(iii)
Response: for eachmi, where 1≤i≤qs, ℬ generates responses as follows. Set polynomial fz=∏i=1qsz+ei=∑i=1qsaizi, where a0,…,aqs are randomness of polynomial fz and ei=H2CIDi. Define coefficient g′ and c^ as follows:(5)g′=∏i=0qsAiai=gfz,c^∏i=1qsAiai−1=gzfz=g′z.Next, define polynomialfiz=fz/z+ei=∏j=1,j≠iqsz+ei and fiz=∑j=0qs−1bjzj. Compute si for each i as follows:(6)si=∏j=0qs−1Ajbj=g′1/x+ei,ei=H2CIDi.Then,ℬ can compute each ri′, for each i∈1,qs:(7)ri′=gαi⋅siH2mi−H2mi′,yαi⋅sixH2mi−H2mi′.Since the equation holds fore^g,gH2mi⋅e^hi⋅y,r1,i=e^g,gH2mi′⋅e^hi⋅y,r1,i′, where hi=gei=gH2CIDi and ri′=r1,i′,r2,i′ is the correct response to hold each collision. ℬ replies A with r1′,…,rqs′ as a response.Output: adversaryA wins the game by outputting CID,M,r,M∗,r∗,ℏ such that(8)e^g,gH2M⋅e^r1e+x,g=e^g,gH2M∗⋅e^r1∗e+x,g,where h=ge=gH2CID, r=r1,r2, and r∗=r1∗,r2∗.Next, we can parser∗ by(9)r∗=gα∗,yα∗=r1⋅sH2M−H2M∗,r2⋅sxH2M−H2M∗,where(10)s=r1∗r11/H2M−H2M∗=g′1/x+e=gfx/x+e.Next, we can parsef by fz=γzz+e+γ−1, for some γy=∑i=0qs−1γizi and γ−1∈Zq. Then, we can deduce by(11)fxz+e=γ−1z+e+∑i=0qs−1γizi.Sinceγ−1≠0 and CID has never been queried before (i.e., CID∉CID1,…,CIDqs), z+e cannot divide fz. So, the algorithm ℬ derives a q-SDHP answer as follows:(12)e=H2CID,g1/x+e=s⋅∑i=1qsAi−γi1/γ−1.Theorem 4.
If there exists a PPT adversaryAwho can break the IND-D&P of our PCH scheme, we can construct an algorithmℬto solve the DDHP with a nonnegligible advantage.Proof. Our IND-D&P is reducible to the DDHP. Suppose A is a PPT adversary against our IND-D&P; we prove by game hopping as follows:Game 0: this is the originalIND0D&P game.(1)
Setup: the algorithmℬ runs GPCH to initiate the system and derives G,GT,g,q,H2,e^,x,y, where y=gx, and x is privately kept by ℬ. Then, ℬ sends G,GT,g,q,H2,e^,y to A.(2)
Challenge:S flips a coin b∈0,1 and proceeds differently.Forb=0, compute coefficient r0 and chameleon hash ℏ0 as follows:(13)r0=gH2M,yH2M,ℏ0=e^g,gH2M⋅e^h1⋅yH2M,g.Forb=1, compute coefficient r1 and chameleon hash ℏ1 as follows:(14)α∈RZq,r1=gα,yα,ℏ^1=e^g,gH2M⋅e^h1⋅yα,g.S relays ℏb,rb to the adversary A. Suppose A issues at most qs distinct queries to oracle H2 (controlled by S) on ei and mi; then, S returns answer to each distinct query accordingly.(3)
Output: the adversary outputsa∈0,1 and wins if b=a.(ii)
Game 1: it is the same as Game 0, except that we randomly sampleR1∈G and use it to compute ℏ0. Thus, ℏ0,r0 is computed as follows:(15)R1∈RZq,r0=gH2M,yH2M,ℏ0=e^g,gH2M⋅e^h1H2M⋅R1,g,whereℏ1,r1 is computed as follows:(16)α∈RZq,r1=gα,yα,ℏ1=e^g,gH2M⋅e^h1⋅yα,g.(iii)
Game 2: it is the same as Game 1, except that we randomly sampleR2∈G and use it to compute ℏ1. Hence, ℏ0,r0 is computed as follows:(17)r0=gH2M,yH2M,R1∈RZq,ℏ0=e^g,gH2M⋅e^h1H2M⋅R1,g,whereℏ1,r1 is computed as follows:(18)α∈RZq,R2∈RZq,r1=gα,yα,ℏ1=e^g,gH2M⋅e^h1α⋅R2,g.IfQ=gab, this implies Game 0; else, Q←RG, this implies Game 1. Thus, we can bound ℬ’s advantage in solving the DDHP by AdvℬDDHP=PrE0−PrE1 via distinguishing among Game 0 and Game 1. Here, we denote Ei as the event for A winning the Game i. Analogically, we have AdvℬDDHP=PrE1−PrE2 via distinguishing among Game 1 and Game 2. Due to the unpredictability of file source ℳ, Game 2 generates ℏb,rb as the one-time pad, and therefore, we have AdvAGame2=1/2.Based on the above, we can boundℬ’s advantage in solving the DDHP by AdvAIND0D&P≤2⋅AdvℬDDHP. Details are omitted due to space limitations. Since each hop only made negligible changes, the modification is beyond the adversary A’s view; otherwise, we can construct an algorithm ℬ to solve the DDHP assuming the adversary A can distinguish among Game 0 and Game 1, or Game 1 and Game 2, subsequently. Refer to [39], for more details.


## 8. Performance Evaluation

In this section, we evaluate the computational complexity and experimental performance of ourBA2P scheme. We have given the complexity of each stage in Table 2. As shown in Table 2, during the prebidding and the bidding Phases, the buyer’s computational complexity is linear with n and b0. However, since b0 can be fixed to 1, if we let the buyer only compute the last bidding proof (instead of for each bid), this turns our auction protocol into a sealed bidding case. In addition, suppose there are j0 buyers who participated in the bidding. To verify the validity of all the last bidding proofs and determine the highest bidder from them, AM needs to perform j0 times verification for each set of commitments and the last bid proof, i.e., 3n+3Tm+2n+4Te+Tp⋅2j0 in total. The complexity of the open phase at the public side is bound by n and j0. However, the public can choose to verify or delegate a third party to do it.Denoten as the number of public keys in L, j0 as the number of buyers, b0 as the number of bids placed per bidder during the bidding Stage, Tm as the group multiplication, Te as the group exponentiation, Ti as the group inversion, and Tp as bilinear pairing operation.Parameter is defined as Table2.Table 2
The complexities in each stage.
StagesComputational complexityBuyer sideAuction manager sidePrebidding phase4n+4Tm+5n+9Te+4Tp0Bidding phase7n+1Tm+4n+2Te⋅b00Confirmation phase07n+1Tm+4n+2Te⋅j0Open phase3n+3Tm+2n+4Te+Tp⋅2j0We also compare the complexity of our scheme with other works in Table3. As observed in Table 3, Xiong et al.’s [9] scheme is most efficient one. The reason is Xiong et al.‘s [9] scheme did not involve trapdoor commitment to achieve bidirectional confirmation between the buyer and the AM. So, undeniability (dispute-freeness) is not achieved. Therefore, when a dispute occurs, it is hard to perform fair arbitration. Alternatively, our scheme provides bidirectional confirmation to achieve dispute-freeness since both the buyer and AM confirm every bid. These proofs are released together with the commitments during open stage and are publicly verifiable. Basically, our scheme trades efficiency with the dispute-freeness property.Table 3
The comparison of complexities in related works.
StagesComputational complexityOur schemeXiong et al. [9] (2012)Xiong et al. [8] (2009)Prebidding phase4n+4Tm+5n+9Te+4Tp02n+1Tm+3n−2TeBidding phase7n+1Tm+4n+2Te⋅b02n+2Tm+3Te+Tp2n+1Tm+3n−2TeConfirmation phase7n+1Tm+4n+2Te⋅b000Open phase3n+3Tm+2n+4Te+Tp⋅2j002n+1Tm+3n−2TeNext, we conduct experiments to evaluate the running costs of our protocol at the buyer side. To simulate, we implemented our scheme using C language on a laptop with 3.5 GHz 4-cores CPU, 8 GB RAM, and 256 SSD for storage. The operating system is 32 bits Windows 7 SP1. All algorithms are implemented using PBC (version-0.5.13) for all cryptographic operations. We choose a super supersingular curvey2=x3+x with embedding degree of 2. Denote |G|≈160 and |GT|≈1024 as the binary sizes of groups G and G, respectively. We range the number of pubic keys in L (i.e., n) from 0 to 5. We compare the running costs at the buyer side for different coefficients b0 and j0. We give experimental results in Figure 3. As it is shown in Figure 3, the costs at the buyer side are factored by several coefficients: n, b0, and j0. When these coefficients are not surprisingly large, the running costs are generally acceptable.Figure 3
The running costs at the buyer side.


## 9. Conclusion

We proposed a bidirectional and anonymous auction protocol with the dispute-freeness property. Our proposal is based on two cryptographic schemes as building blocks: policy-driven chameleon hash and revised linkable-and-redactable ring signature. In our proposal, bidders can competitively place their bids in order to outbid others.An auction manager is employed to verify and confirm the bidding proof generated by the buyer. Due to the bidirectional confirmation and public verifiability, our auction protocol is dispute-free. The evidence suggests that our proposal is provably secure based on intractable assumptions. Meanwhile, our proposal is practically efficient, and it trades efficiency with the dispute-freeness feature.There is a number of additional functionalities to enrich our current design, for example, employing more standard and sophisticated cryptographic algorithms (e.g., zero-knowledge proof) to achieve practical and stronger privacy preservation. In addition, more formal security model which captures practical security threat is needed. Though some current works focus on utilizing several sophisticated cryptographic algorithms in one scheme, they suffered from inefficiency issue. Therefore, to design a practical bidding protocol for mass deployment, the complexity of the underlying cryptographic algorithms should not be the bottleneck of the whole scheme. We consider the solutions to the above problems as challenging and interesting future works.



---

*Source: 6690766-2021-10-15.xml*