Abstract
Combinatorial auctions are employed into many applications such as spectrum auctions held by the Federal Communications Commission (FCC). A crucial problem in such auctions is the lack of secure and efficiency mechanism to protect the privacy of the bidding prices and to ensure data security. To solve the problem, we propose an approach to represent the price as a polynomial's degree based on verifiable secret sharing. So, we can obtain the two polynomials's degree maximum/sum by the degree of the two polynomial's degree sum/product. In the protocol, the bidders' information is hidden. The auctioneers can receive the shares without a secure channel, so our protocol is more applicable to more scenarios. The scheme can resist the collusion attack, passive attack and so on. Moreover, Compared to Kikuchi (IEICE Trans Fundam Electron Commun Comput Sci 85(3):676-683, 2002); Suzuki and Yokoo (Secure combinatorial auctions by dynamic programming with polynomial secret sharing, 2003), the proposed scheme has the authentication property without increasing the communications cost.