Sealed-bid auctions with efficient bids

Toru Nakanishi; Daisuke Yamamoto; Yuji Sugiyama

doi:10.1007/978-3-540-24691-6_18

Sealed-bid auctions with efficient bids

Toru Nakanishi, Daisuke Yamamoto, Yuji Sugiyama

Research output: Chapter in Book/Report/Conference proceeding › Chapter

6 Citations (Scopus)

Abstract

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 zeroknowledge 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.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Jong In Lim, Dong Hoon Lee
Publisher	Springer Verlag
Pages	230-244
Number of pages	15
ISBN (Print)	3540213767, 9783540213765
DOIs	https://doi.org/10.1007/978-3-540-24691-6_18
Publication status	Published - 2004

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2971
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

Additive homomorphic cryptosystems
Mix-and-match
Multiparty computation (MPC)
Sealed-bid auction

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-24691-6_18

Cite this

Nakanishi, T., Yamamoto, D., & Sugiyama, Y. (2004). Sealed-bid auctions with efficient bids. In J. I. Lim, & D. H. Lee (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 230-244). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2971). Springer Verlag. https://doi.org/10.1007/978-3-540-24691-6_18

Sealed-bid auctions with efficient bids. / Nakanishi, Toru; Yamamoto, Daisuke; Sugiyama, Yuji.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Jong In Lim; Dong Hoon Lee. Springer Verlag, 2004. p. 230-244 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2971).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Nakanishi, T, Yamamoto, D & Sugiyama, Y 2004, Sealed-bid auctions with efficient bids. in JI Lim & DH Lee (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2971, Springer Verlag, pp. 230-244. https://doi.org/10.1007/978-3-540-24691-6_18

Nakanishi T, Yamamoto D, Sugiyama Y. Sealed-bid auctions with efficient bids. In Lim JI, Lee DH, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 230-244. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-24691-6_18

Nakanishi, Toru ; Yamamoto, Daisuke ; Sugiyama, Yuji. / Sealed-bid auctions with efficient bids. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Jong In Lim ; Dong Hoon Lee. Springer Verlag, 2004. pp. 230-244 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{b1d44ea96e794ba38082b7bb52d3251c,

title = "Sealed-bid auctions with efficient bids",

abstract = "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 zeroknowledge 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.",

keywords = "Additive homomorphic cryptosystems, Mix-and-match, Multiparty computation (MPC), Sealed-bid auction",

author = "Toru Nakanishi and Daisuke Yamamoto and Yuji Sugiyama",

year = "2004",

doi = "10.1007/978-3-540-24691-6_18",

language = "English",

isbn = "3540213767",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "230--244",

editor = "Lim, {Jong In} and Lee, {Dong Hoon}",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - CHAP

T1 - Sealed-bid auctions with efficient bids

AU - Nakanishi, Toru

AU - Yamamoto, Daisuke

AU - Sugiyama, Yuji

PY - 2004

Y1 - 2004

N2 - 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 zeroknowledge 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.

AB - 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 zeroknowledge 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.

KW - Additive homomorphic cryptosystems

KW - Mix-and-match

KW - Multiparty computation (MPC)

KW - Sealed-bid auction

UR - http://www.scopus.com/inward/record.url?scp=35048827459&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35048827459&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-24691-6_18

DO - 10.1007/978-3-540-24691-6_18

M3 - Chapter

AN - SCOPUS:35048827459

SN - 3540213767

SN - 9783540213765

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 230

EP - 244

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Lim, Jong In

A2 - Lee, Dong Hoon

PB - Springer Verlag

ER -

Sealed-bid auctions with efficient bids

Abstract

Publication series

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this