This paper presents an efficient secure auction protocol for M+1st price auction. In our proposed protocol, a bidding price of a player is represented as a binary expression, while in the previous protocol it is represented as an integer. Thus, when the number of players is m and the bidding price is an integer up to p, compared to the complexity of the previous protocol which is a polynomial of m and p, the complexity of our protocol is a polynomial of m and log p. We apply the Boneh-Goh-Nissim encryption to the mix-and-match protocol to reduce the computation costs.

This paper presents efficient secure auction protocols for first price auction and second price auction. Previous auction protocols are based on a generally secure multi-party protocol called mix-and-match protocol based on plaintext equality tests. However, the time complexity of the plaintext equality tests is large, although the mix-and-match protocol can securely calculate any logical circuits. The proposed protocols reduce the number of times the plaintext equality tests is used by replacing them with the Boneh-Goh-Nissim encryption, which enables calculation of 2-DNF of encrypted data.