Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Efficient proof of bid validity with untrusted verifier in homomorphic e-auction

© The Institution of Engineering and Technology
Received 15/02/2012, Accepted 26/09/2012, Revised 04/08/2012, Published

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: untrusted verifier; bid validity verification technique; bid validity proof technique; privacy drawback; public key cryptographic operations; efficiency bottleneck; homomorphic e-auction applications; hash function operations; honest-verifier zero knowledge

Subjects: Data security; Formal methods

References

    1. 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. 2)
      • 27. Shamir, A.: ‘How to share a secret’, Commun. ACM, 1979, 22, (11), pp. 612–613 (doi: 10.1145/359168.359176).
    3. 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. 4)
      • 21. Peng, K., Bao, F.: ‘An efficient range proof scheme’. IEEE PASSAT'10, pp. 826–833.
    5. 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. 6)
      • 32. MacKenzie, P., Frankel, Y., Yung, M.: Robust efficient distributed RSA-key generation. 1998, p. 320.
    7. 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. 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. 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. 10)
      • 30. Paillier, P.: ‘Public key cryptosystem based on composite degree residuosity classes’. EURO-CRYPT'99, (LNCS, 1592), 1999, pp. 223–238.
    11. 11)
      • 25. Sako, K.: ‘An auction scheme which hides the bids of losers’. Public Key Cryptology 2000, (LNCS, 1880), 2000, pp. 422–432.
    12. 12)
      • 33. Damgård, I., Koprowski, M.: ‘Practical threshold RSA signatures without a trusted dealer’. EUROCRYPT'01, (LNCS, 2000, 2045), pp. 152–165.
    13. 13)
      • 14. Peng, K., Bao, F.: ‘Efficiency improvement of homomorphic e-auction’. TRUSTBUS'10, 2010 (LNCS, 6264), pp. 238–249.
    14. 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. 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)
      • 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. 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)
      • 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. 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. 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. 21)
      • 28. Okamoto, T., Uchiyama, S.: ‘A new public-key encyptosystem as secure as factoring’. CRYPTO'98, (LNCS, 1403), 1998, pp. 308–318.
    22. 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. 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. 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. 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. 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. 27)
      • 20. Abe, M., Suzuki, K.: ‘M + 1st price auction using homomorphic encryption’. Public Key Cryptology 2002, (LNCS, 2288), 2002, pp. 115–124.
    28. 28)
      • 19. Damgård, I.: ‘Efficient concurrent zero-knowledge in the auxiliary string model’. EURO-CRYPT'00, 2000(LNCS, 1807), pp. 431–444.
    29. 29)
      • 17. Boneh, D., Boyen, X.: ‘Short signatures without random oracles’. Eurocrypt'04, (LNCS, 3027), pp. 56–73.
    30. 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)
      • 31. Boneh, D., Franklin, M.: ‘Efficient generation of shared RSA keys’. Crypto'97, (LNCS, 1233), 2004, pp. 425–439.
    32. 32)
      • 34. Feldman, P.: ‘A practical scheme for non-interactive verifiable secret sharing’. FOCS'87, pp. 427–437.
    33. 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. 34)
      • 35. Pedersen, T. ‘A threshold cryptosystem without a trusted party’. EUROCRYPT'91, pp. 522–526.
    35. 35)
      • 5. Abe, M., Suzuki, K.: ‘Receipt-free sealed-bid auction’. ISC 2002, (LNCS, 2433), 2002, pp. 191–199.
    36. 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. 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. 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. 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. 40)
      • 4. Kikuchi, H.: ‘(m + 1)st-price auction’. Fifth Int. Conf. on Financial Cryptography 2001, 2001(LNCS, 2339), pp. 291–298.
    41. 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. 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. 43)
      • K. Peng . Secure e-auction for mobile users with low-capability devices in wireless network. WISTP'11 , 351 - 360
    44. 44)
      • I. Damgård , M. Koprowski . Practical threshold RSA signatures without a trusted dealer. EUROCRYPT'01 , 152 - 165
    45. 45)
      • K. Peng , F. Bao . An efficient range proof scheme. IEEE PASSAT'10 , 826 - 833
    46. 46)
      • K. Peng , E. Dawson . Efficient bid validity check in elgamal-based sealed-bid e-auction. ISPEC 2007 , 209 - 224
    47. 47)
      • T. Okamoto , S. Uchiyama . A new public-key encyptosystem as secure as factoring. CRYPTO'98 , 308 - 318
    48. 48)
      • P. Paillier . Public key cryptosystem based on composite degree residuosity classes. EURO-CRYPT'99 , 223 - 238
    49. 49)
      • D. Boneh , X. Boyen . Short signatures without random oracles. Eurocrypt'04 , 56 - 73
    50. 50)
      • D. Chaum , J. Evertse , J. Graaf . An improved protocol for demonstrating possession of discrete logarithms and some generalizations. EUROCRYPT'87 , 127 - 141
    51. 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. 52)
      • R. Gennaro , S. Jarecki , H. Krawczyk , T. Rabin . Secure distributed key generation for discrete-log based cryptosystems. EUROCRYPT'99 , 123 - 139
    53. 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. 54)
      • Naccache, D., Stern, J.: `A new public key cryptosystem based on higher residues', ACM Computer Science Conf. 1998, 1998, p. 160–174.
    55. 55)
      • P. Feldman . A practical scheme for non-interactive verifiable secret sharing. FOCS'87 , 427 - 437
    56. 56)
    57. 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. 58)
    59. 59)
      • K. Sako . An auction scheme which hides the bids of losers. Public Key Cryptology 2000 , 422 - 432
    60. 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. 61)
      • P. MacKenzie , Y. Frankel , M. Yung . (1998) Robust efficient distributed RSA-key generation.
    62. 62)
      • Brandt, F.: Cryptographic protocols for secure second-price auctions, 2001, Available at http://www.brauer.in.tum.de/~brandtf/papers/cia2001.pdf.
    63. 63)
      • T. Pedersen . A threshold cryptosystem without a trusted party. EUROCRYPT'91 , 522 - 526
    64. 64)
      • I. Damgård . Efficient concurrent zero-knowledge in the auxiliary string model. EURO-CRYPT'00 , 431 - 444
    65. 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. 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. 67)
    68. 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. 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. 70)
      • Kikuchi, H.: `(', Fifth Int. Conf. on Financial Cryptography 2001, 2001, p. 291–298(LNCS, 2339), .
    71. 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. 72)
      • D. Boneh , M. Franklin . Efficient generation of shared RSA keys. Crypto'97 , 425 - 439
    73. 73)
    74. 74)
    75. 75)
    76. 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. 77)
      • K. Peng , F. Bao . Efficiency improvement of homomorphic e-auction. TRUSTBUS'10 LNCS , 238 - 249
    78. 78)
    79. 79)
      • B. Lee , K. Kim . Receipt-free electronic voting through collaboration of voter and honest verifier. JW-ISC 2000 , 101 - 108
    80. 80)
      • R. Cramer , I. Damgard , B. Schoenmakers . Proofs of partial knowledge and simplified design of witness hiding protocols. CRYPTO'94 LNCS , 174 - 187
    81. 81)
      • P.-A. Fouque , G. Poupard , J. Stern . (2000) Sharing decryption in the context of voting or lotteries. Financial Cryptography 2000.
    82. 82)
      • M. Abe , K. Suzuki . Receipt-free sealed-bid auction. ISC 2002 , 191 - 199
    83. 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. 84)
      • L.C. Guillou , J.J. Quisquater , S. Goldwasser . (1989) A ‘paradoxical’ identity-based signature scheme resulting from zero-knowledge, CRYPTO'88.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2012.0076
Loading

Related content

content/journals/10.1049/iet-ifs.2012.0076
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address