Efficient proof of bid validity with untrusted verifier in homomorphic e-auction
- Author(s): Kun Peng 1
-
-
View affiliations
-
Affiliations:
1:
Institute for Infocomm Research, Agency for Science, Technology and Research
-
Affiliations:
1:
Institute for Infocomm Research, Agency for Science, Technology and Research
- Source:
Volume 7, Issue 1,
March 2013,
p.
11 – 21
DOI: 10.1049/iet-ifs.2012.0076 , Print ISSN 1751-8709, Online ISSN 1751-8717
Bid validity proof and verification is an efficiency bottleneck and privacy drawback in homomorphic e-auction. The existing bid validity proof technique is inefficient and only achieves honest-verifier zero knowledge (ZK). In this study, an efficient proof and verification technique is proposed to guarantee bid validity in homomorphic e-auction. The new proof technique is mainly based on hash function operations and only needs a very small number of costly public key cryptographic operations. Moreover, it can handle untrusted verifiers and achieve perfect ZK. As a result, efficiency and privacy of homomorphic e-auction applications are significantly improved. To the best of authors’ knowledge, it proof technique is the first to handle untrusted verifiers in e-auction applications.
Inspec keywords: formal verification; tendering; Internet; data privacy; public key cryptography; electronic commerce
Other keywords:
Subjects: Data security; Formal methods
References
-
-
1)
-
11. Peng, K., Boyd, C., Dawson, E.: ‘Optimization of electronic first-bid sealed-bid auction based on homomorphic secret sharing’. Mycrypt 2005, (LNCS, 3715), 2005, pp. 84–98.
-
-
2)
-
27. Shamir, A.: ‘How to share a secret’, Commun. ACM, 1979, 22, (11), pp. 612–613 (doi: 10.1145/359168.359176).
-
-
3)
-
41. Chida, K., Yamamoto, G.: ‘Batch processing for proofs of partial knowledge and its applications’. IEICE Trans. Fundamentals, vol. E91CA, no. 1January 2008, 2008, pp. 150–159 (doi: 10.1093/ietfec/e91-a.1.150).
-
-
4)
-
21. Peng, K., Bao, F.: ‘An efficient range proof scheme’. IEEE PASSAT'10, pp. 826–833.
-
-
5)
-
39. Damgård, I., Jurik, M.: ‘A generalisation, a simplification and some applications of Paillier's probabilistic public-key system’. PKC ’01, (LNCS, 1992), 2001, pp. 119–136.
-
-
6)
-
32. MacKenzie, P., Frankel, Y., Yung, M.: Robust efficient distributed RSA-key generation. 1998, p. 320.
-
-
7)
-
23. Suzuki, K., Kobayashi, K., Morita, H.: ‘Efficient sealed-bid auction using hash chain’. Int. Conf. on Information Security and Cryptology 2000, (LNCS, 2015), 2000, pp. 183–191.
-
-
8)
-
38. Baudron, O., Fouque, P.-A., Pointcheval, D., Poupard, G., Stern, J.: ‘Practical multi-candidate election system’. PODC'01, 2001, pp. 274–283 (doi: 10.1145/383962.384044).
-
-
9)
-
40. Lee, B., Kim, K.: ‘Receipt-free electronic voting through collaboration of voter and honest verifier’. JW-ISC 2000, 2000, pp. 101–108.
-
-
10)
-
30. Paillier, P.: ‘Public key cryptosystem based on composite degree residuosity classes’. EURO-CRYPT'99, (LNCS, 1592), 1999, pp. 223–238.
-
-
11)
-
25. Sako, K.: ‘An auction scheme which hides the bids of losers’. Public Key Cryptology 2000, (LNCS, 1880), 2000, pp. 422–432.
-
-
12)
-
33. Damgård, I., Koprowski, M.: ‘Practical threshold RSA signatures without a trusted dealer’. EUROCRYPT'01, (LNCS, 2000, 2045), pp. 152–165.
-
-
13)
-
14. Peng, K., Bao, F.: ‘Efficiency improvement of homomorphic e-auction’. TRUSTBUS'10, 2010 (LNCS, 6264), pp. 238–249.
-
-
14)
-
15. Peng, K.: ‘Secure e-auction for mobile users with low-capability devices in wireless network’. WISTP'11, (LNCS, 6633), pp. 351–360.
-
-
15)
-
42. Guillou, L.C., Quisquater, J.J.: ‘A ‘paradoxical’ identity-based signature scheme resulting from zero-knowledge’, in: Goldwasser, S. (Ed.), CRYPTO'88, (LNCS, 403), 1989, pp. 216–231.
-
-
16)
-
16. Peng, K., Bao, F.: ‘Efficient proof of validity of votes in homomorphic e-voting’. Int. Conf. on Network and System Security (NSS'10), 2010, pp. 17–23.
-
-
17)
-
29. Naccache, D., Stern, J.: ‘A new public key cryptosystem based on higher residues’. ACM Computer Science Conf. 1998, 1998, pp. 160–174.
-
-
18)
-
18. Chaum, D., Evertse, J., Graaf, J.: ‘An improved protocol for demonstrating possession of discrete logarithms and some generalizations’. EUROCRYPT'87, (LNCS, 293), 1987, pp. 127–141.
-
-
19)
-
6. Brandt, F.: Cryptographic protocols for secure second-price auctions. 2001. Available at http://www.brauer.in.tum.de/~brandtf/papers/cia2001.pdf.
-
-
20)
-
26. Peng, K., Boyd, C., Dawson, E., Viswanathan, K.: ‘Non-interactive auction scheme with strong privacy’. Fifth Int. Conf. on Information Security and Cryptology (ICISC 2002), (LNCS, 2587), 2002, pp. 407–420.
-
-
21)
-
28. Okamoto, T., Uchiyama, S.: ‘A new public-key encyptosystem as secure as factoring’. CRYPTO'98, (LNCS, 1403), 1998, pp. 308–318.
-
-
22)
-
13. Peng, K., Dawson, E.: ‘Efficient bid validity check in elgamal-based sealed-bid e-auction’. ISPEC 2007, (LNCS, 4464), 2007, pp. 209–224.
-
-
23)
-
2. Kikuchi, H., Hotta, S., Abe, K., Nakanishi, S.: ‘Distributed auction servers resolving winner and winning bid without revealing privacy of bids’. Proc. Int. Workshop on Next Generation Internet (NGITA2000), July 2000, pp. 307–312.
-
-
24)
-
1. Kikuchi, H., Harkavy, M., Tygar, J.D.: ‘Multi-round anonymous auction’. Proc. First IEEE Workshop on Dependable and Real-Time E-Commerce Systems, June 1998, pp. 62–69.
-
-
25)
-
3. Chida, K., Kobayashi, K., Morita, H.: ‘Efficient sealed-bid auctions for massive numbers of bidders with lump comparison’. Proc. Fourth Int. Information Security Conf., (ISC 2001), 2001(LNCS, 2200), pp. 408–419.
-
-
26)
-
7. Omote, K., Miyaji, A.: ‘A second-price sealed-bid auction with the discriminant of the pth root’. Financial Cryptography 2002, (LNCS, 2357), 2002, pp. 57–71.
-
-
27)
-
20. Abe, M., Suzuki, K.: ‘M + 1st price auction using homomorphic encryption’. Public Key Cryptology 2002, (LNCS, 2288), 2002, pp. 115–124.
-
-
28)
-
19. Damgård, I.: ‘Efficient concurrent zero-knowledge in the auxiliary string model’. EURO-CRYPT'00, 2000(LNCS, 1807), pp. 431–444.
-
-
29)
-
17. Boneh, D., Boyen, X.: ‘Short signatures without random oracles’. Eurocrypt'04, (LNCS, 3027), pp. 56–73.
-
-
30)
-
37. Fouque, P.-A., Poupard, G., Stern, J.: Sharing decryption in the context of voting or lotteries. Financial Cryptography 2000, (LNCS, 1962), 2000, pp. 90–104.
-
-
31)
-
31. Boneh, D., Franklin, M.: ‘Efficient generation of shared RSA keys’. Crypto'97, (LNCS, 1233), 2004, pp. 425–439.
-
-
32)
-
34. Feldman, P.: ‘A practical scheme for non-interactive verifiable secret sharing’. FOCS'87, pp. 427–437.
-
-
33)
-
10. Peng, K., Boyd, C., Dawson, E.: ‘A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption’. ISC 2005, (LNCS, 3650), 2005, pp. 374–388.
-
-
34)
-
35. Pedersen, T. ‘A threshold cryptosystem without a trusted party’. EUROCRYPT'91, pp. 522–526.
-
-
35)
-
5. Abe, M., Suzuki, K.: ‘Receipt-free sealed-bid auction’. ISC 2002, (LNCS, 2433), 2002, pp. 191–199.
-
-
36)
-
22. Sakurai, K., Miyazaki, S.: ‘A bulletin-board based digital auction scheme with bidding down strategy – towards anonymous electronic bidding without anonymous channels non trusted centers’. Proc. Int. Workshop on Cryptographic Techniques and e-Commerce, 1999, pp. 180–187.
-
-
37)
-
9. Cramer, R., Damgard, I., Schoenmakers, B.: ‘Proofs of partial knowledge and simplified design of witness hiding protocols’. CRYPTO'94, (LNCS, 839), 1994, pp. 174–187.
-
-
38)
-
24. Watanabe, Y., Imai, H.: ‘Reducing the round complexity of a sealed-bid auction protocol with an off-line ttp’. STOC 2000, ACM, 2000, pp. 80–86.
-
-
39)
-
8. Peng, K., Boyd, C., Dawson, E., Viswanathan, K.: ‘Robust, privacy protecting and publicly verifiable sealed-bid auction’. Fourth Int. Conf. on Information and Communications Security, (ICICS 2002), (LNCS, 2513), 2002, pp. 147–159.
-
-
40)
-
4. Kikuchi, H.: ‘(m + 1)st-price auction’. Fifth Int. Conf. on Financial Cryptography 2001, 2001(LNCS, 2339), pp. 291–298.
-
-
41)
-
12. Peng, K., Boyd, C., Dawson, E.: ‘Batch verification of validity of bids in homomorphic e-auction’, Comput. Commun., 2006, 29, (2006), pp. 2798–2805 (doi: 10.1016/j.comcom.2005.10.031).
-
-
42)
-
36. Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: ‘Secure distributed key generation for discrete-log based cryptosystems’. EUROCRYPT'99, pp. 123–139.
-
-
43)
- K. Peng . Secure e-auction for mobile users with low-capability devices in wireless network. WISTP'11 , 351 - 360
-
44)
- I. Damgård , M. Koprowski . Practical threshold RSA signatures without a trusted dealer. EUROCRYPT'01 , 152 - 165
-
45)
- K. Peng , F. Bao . An efficient range proof scheme. IEEE PASSAT'10 , 826 - 833
-
46)
- K. Peng , E. Dawson . Efficient bid validity check in elgamal-based sealed-bid e-auction. ISPEC 2007 , 209 - 224
-
47)
- T. Okamoto , S. Uchiyama . A new public-key encyptosystem as secure as factoring. CRYPTO'98 , 308 - 318
-
48)
- P. Paillier . Public key cryptosystem based on composite degree residuosity classes. EURO-CRYPT'99 , 223 - 238
-
49)
- D. Boneh , X. Boyen . Short signatures without random oracles. Eurocrypt'04 , 56 - 73
-
50)
- D. Chaum , J. Evertse , J. Graaf . An improved protocol for demonstrating possession of discrete logarithms and some generalizations. EUROCRYPT'87 , 127 - 141
-
51)
- Kikuchi, H., Harkavy, M., Tygar, J.D.: `Multi-round anonymous auction', Proc. First IEEE Workshop on Dependable and Real-Time E-Commerce Systems, June 1998, p. 62–69.
-
52)
- R. Gennaro , S. Jarecki , H. Krawczyk , T. Rabin . Secure distributed key generation for discrete-log based cryptosystems. EUROCRYPT'99 , 123 - 139
-
53)
- Chida, K., Kobayashi, K., Morita, H.: `Efficient sealed-bid auctions for massive numbers of bidders with lump comparison', Proc. Fourth Int. Information Security Conf., (ISC 2001), 2001, p. 408–419(LNCS, 2200), .
-
54)
- Naccache, D., Stern, J.: `A new public key cryptosystem based on higher residues', ACM Computer Science Conf. 1998, 1998, p. 160–174.
-
55)
- P. Feldman . A practical scheme for non-interactive verifiable secret sharing. FOCS'87 , 427 - 437
-
56)
- M. Abe , K. Suzuki . M + 1st price auction using homomorphic encryption. Public Key Cryptology 2002 , 115 - 124
-
57)
- Peng, K., Boyd, C., Dawson, E., Viswanathan, K.: `Robust, privacy protecting and publicly verifiable sealed-bid auction', Fourth Int. Conf. on Information and Communications Security, (ICICS 2002), 2002, p. 147–159(LNCS, 2513), .
-
58)
- K. Omote , A. Miyaji . A second-price sealed-bid auction with the discriminant of the pth LNCS. Financial Cryptography 2002 , 57 - 71
-
59)
- K. Sako . An auction scheme which hides the bids of losers. Public Key Cryptology 2000 , 422 - 432
-
60)
- Suzuki, K., Kobayashi, K., Morita, H.: `Efficient sealed-bid auction using hash chain', Int. Conf. on Information Security and Cryptology 2000, 2000, p. 183–191, (LNCS 2015).
-
61)
- P. MacKenzie , Y. Frankel , M. Yung . (1998) Robust efficient distributed RSA-key generation.
-
62)
- Brandt, F.: Cryptographic protocols for secure second-price auctions, 2001, Available at http://www.brauer.in.tum.de/~brandtf/papers/cia2001.pdf.
-
63)
- T. Pedersen . A threshold cryptosystem without a trusted party. EUROCRYPT'91 , 522 - 526
-
64)
- I. Damgård . Efficient concurrent zero-knowledge in the auxiliary string model. EURO-CRYPT'00 , 431 - 444
-
65)
- Peng, K., Boyd, C., Dawson, E., Viswanathan, K.: `Non-interactive auction scheme with strong privacy', Fifth Int. Conf. on Information Security and Cryptology (ICISC 2002), 2002, p. 407–420, LNCS 2587.
-
66)
- I. Damgård , M. Jurik . A generalisation, a simplification and some applications of Paillier's probabilistic public-key system. PKC ’01 , 119 - 136
-
67)
- K. Chida , G. Yamamoto . Batch processing for proofs of partial knowledge and its applications. IEICE Trans. Fundam. , 1 , 150 - 159
-
68)
- Sakurai, K., Miyazaki, S.: `A bulletin-board based digital auction scheme with bidding down strategy – towards anonymous electronic bidding without anonymous channels non trusted centers', Proc. Int. Workshop on Cryptographic Techniques and e-Commerce, 1999, p. 180–187.
-
69)
- Kikuchi, H., Hotta, S., Abe, K., Nakanishi, S.: `Distributed auction servers resolving winner and winning bid without revealing privacy of bids', Proc. Int. Workshop on Next Generation Internet (NGITA2000), July 2000, p. 307–312.
-
70)
- Kikuchi, H.: `(', Fifth Int. Conf. on Financial Cryptography 2001, 2001, p. 291–298(LNCS, 2339), .
-
71)
- Peng, K., Boyd, C., Dawson, E.: `A multiplicative homomorphic sealed-bid auction based on Goldwasser-Micali encryption', ISC 2005, 2005, p. 374–388(LNCS, 3650), .
-
72)
- D. Boneh , M. Franklin . Efficient generation of shared RSA keys. Crypto'97 , 425 - 439
-
73)
- K. Peng , C. Boyd , E. Dawson . Optimization of electronic first-bid sealed-bid auction based on homomorphic secret sharing. Mycrypt 2005 LNCS , 84 - 98
-
74)
- K. Peng , C. Boyd , E. Dawson . Batch verification of validity of bids in homomorphic e-auction. Comput. Commun. , 2006 , 2798 - 2805
-
75)
- O. Baudron , P.-A. Fouque , D. Pointcheval , G. Poupard , J. Stern . Practical multi-candidate election system. PODC'01 , 274 - 283
-
76)
- Peng, K., Bao, F.: `Efficient proof of validity of votes in homomorphic e-voting', Int. Conf. on Network and System Security (NSS'10), 2010, p. 17–23.
-
77)
- K. Peng , F. Bao . Efficiency improvement of homomorphic e-auction. TRUSTBUS'10 LNCS , 238 - 249
-
78)
- A. Shamir . How to share a secret. Commun. ACM , 11 , 612 - 613
-
79)
- B. Lee , K. Kim . Receipt-free electronic voting through collaboration of voter and honest verifier. JW-ISC 2000 , 101 - 108
-
80)
- R. Cramer , I. Damgard , B. Schoenmakers . Proofs of partial knowledge and simplified design of witness hiding protocols. CRYPTO'94 LNCS , 174 - 187
-
81)
- P.-A. Fouque , G. Poupard , J. Stern . (2000) Sharing decryption in the context of voting or lotteries. Financial Cryptography 2000.
-
82)
- M. Abe , K. Suzuki . Receipt-free sealed-bid auction. ISC 2002 , 191 - 199
-
83)
- Y. Watanabe , H. Imai . Reducing the round complexity of a sealed-bid auction protocol with an off-line ttp. STOC 2000, ACM , 80 - 86
-
84)
- L.C. Guillou , J.J. Quisquater , S. Goldwasser . (1989) A ‘paradoxical’ identity-based signature scheme resulting from zero-knowledge, CRYPTO'88.
-
1)