Miyaji Laboratory

Based on highly developed internet technology, online services have become a trend. Security plays an important role in protecting individuals, companies, and governments from hackers' threats. Recent years, auctions in a government to select vendors are often done electronically rather than on paper. It is necessary to keep each vendor's bidding price confidential. In a sealed-bid auction, each bid is sealed by the bidder and sent to a manager. The manager is trusted to announce the winning bidder without revealing each bidder's bid. A second-price sealed-bid auction, where the bidding price is close to the bidder's true valuation of the goods, won the Nobel Prize. The winning bidder only needs to pay the second-highest bidding price to buy the goods. Google used a second-price auction to sell advertisements but changed to an English auction that the winner pays the highest price because it is difficult to provide public verifiability on the second-price when all bids are sealed. A second-price sealed-bid auction can be generalized to a M + 1st-price sealed-bid auction to sell M goods at the same time. The top M bidders pay the M + 1st-price to buy the goods. A secure M+1st-price auction needs to follow four necessary properties: correctness, public verifiability, bid secrecy, and M + 1st-bidder's anonymity. Correctness means given each bidder's bids, the auction protocol can output M winners and the M +1st-price. The correctness needs to be publicly verifiable. Bid secrecy means all bids are sealed and should not be learned by other bidders. M + 1st-bidder's anonymity means the bidder who bids the M + 1st-price should kept anonymous, cannot be learned by other bidders.

To build a M + 1st-price auction protocol that fulfills all necessary properties, there are many difficulties. First, it is difficult to find a trusted manager in the real world. To compare bids and find winners while keeping bid secrecy, a trusted manager is commonly used to compare bids secretly and keep bid secrecy from bidders. However, this allows the manager to learn all the secrets since the bids submitted by each bidder are encrypted by the manager's public key. The manager can decrypt the ciphertexts anytime when they want. In the real world, it is difficult to find a manager who can be trusted never leak any secrets. Therefore, removing the trusted manager in an auction protocol has a significant meaning. Therefore, designing an auction protocol that does not require a trusted manager has a significant meaning. Second, the computation cost is very high. In order to keep bid secrecy, many homomorphic computations need to be performed and many zero-knowledge proofs need to be verified. Even if the time complexity is at a linear level, the constant of the time complexity is still very high. In the auction protocol that has a manager, the manager needs to spend O(BPM) time to verify each bidder's encrypted bid, find M winners and the M +1st-price. In these protocols, O(B) amount of time is used to compare all bidders' bids. O(P) amount of time is used to verify each bidder's bidding vector V . O(M) amount of time is used by the Mix and Match protocol in order to keep the M + 1st-bidder's anonymity. These three variables are multiplied together since all computations need to be applied to all bidders and all elements in all bidding vectors. As for the bidder, O(P) amount of time is necessary to generate the bidding vector. If the trusted manager is removed from the protocol, the situation is even worse since the manager's work needs to be done by all bidders together. This means the time complexity for each bidder is the same as a manager, O(BPM) per bidder. The computation cost for a bidder is largely increased. Therefore, reducing or removing the time complexity to a sublinear or constant level has a significant meaning. Third, the Mix and Match protocols used to keep the M +1st-bidder's anonymity has high computation and communication costs. Bit-slice is a technique used to compare secret values without revealing any information. In an auction protocol, each bid b is encoded bit by bit as a bit-slice bidding vector V = [E(θ^0), · · · , E(θ^1), · · · , E(θ^0)]. Mix and Match protocols are widely applied to bit-slice bidding vectors to verify the bidding vector without leaking bid secrecy and find the M + 1st-price without leaking the M + 1st-bidder's anonymity. It is a useful but heavy protocol that consists of Mix net, Mix server, and verifiable secret shuffle. Some of them take multiple rounds to complete. Therefore, reducing the usage of Mix and Match can largely reduce computation costs and improve scalability. Last but not least, the bidding price bound is linear to the length of the bidding vector. In a linear bidding vector, the b-th element is E(θ^1) and other elements are E(θ^0). The bidding price bound of a linear bidding vector is the length of the bidding vector |V |−1. A binary format bidding vector was proposed by Mitsunaga et, al (MMO) to extend the bidding price bound to the exponential level (2^(|V |) − 1). The design of the protocol is much more difficult since homomorphic AND and homomorphic OR are necessary. To solve this problem, somewhat homomorphic encryption (SHE) or fully homomorphic encryption (FHE) is commonly used to mimic homomorphic AND and homomorphic OR operations. An auction protocol can be more efficient and easier to achieve public verifiability if it only requires a partially homomorphic encryption scheme such as ElGamal encryption.

This dissertation studies how to build a secure M +1st-price sealed-bid auction protocol
that fulfills all necessary properties and solves the difficulties at the same time. In this dissertation, we propose the following.
• An auction protocol that does not have a trusted manager.
• An auction protocol that reached optimal time complexity, O(|V |) per bidder.
• An auction protocol that the bidding price bound is extended to 2^(|V |) − 1.

In the first study, we propose an auction protocol without a trusted manager. To construct an auction protocol without a trusted manager, Smart Contract is a very plausible option. The underlying Blockchain executes the program written in the Smart Contract honestly to ensure correctness. Public verifiability can also achieve easily by using zero-knowledge proofs. The Smart Contract verifies the proofs to make sure each bidder follows the protocol. If a bidder cannot provide valid zero-knowledge proof, the bidder will be considered malicious. At the beginning of the auction, all bidders need to send some money as a stake to the auction contract. When malicious behavior is detected, the malicious bidder's stake will be used to compensate all other honest bidders. The only problem is the storage in a Smart Contract is public. A Smart Contract cannot hide any secrets. As a result, we propose multi-party ElGamal encryption to ensure bid secrecy and the M + 1st-bidder's anonymity. The multi-party ElGamal encryption allows each bidder to encrypt their bidding vector by all bidders' public keys. Unless all bidders collaborate, a malicious bidder cannot learn any information. Our multi-party encryption is asynchronous to ensure efficiency. After the aggregated public key is computed by the Smart Contract, the encryption and the decryption can be done by each bidder independently.

In the second study, we propose an auction protocol that reached optimal time complexity O(|V |) per bidder. In the first study, the time complexity of each bidder is O(BM|V |). The B factor is mainly caused by the design that each bidder needs to check all other bidders' bids. The M factor is mainly caused by the usage of Mix and Match to keep the M + 1st-bidder's anonymity. To remove the B factor, we try to replace all algorithms that need all bidders' collaboration with zero-knowledge proofs. For example, each bidder can prove their bidding vector follows the protocol. Each bidder also proves they are a winner by themself at the end of the auction. To remove the M factor, we found a greedy strategy that when there's no tie (the Mst-price is different from the M +1st-price) a Mix and Match is not necessary. We propose a zero-knowledge algorithm that can find the M + 1st-price in O(1) time while keeping the M + 1st-bidder's anonymity. By removing the B factor and the M factor, the computation cost for each bidder does not increase when the number of bidders and the number of goods increases. The auction protocol can reach the optimal time complexity O(|V |) per bidder. To further reduce the constants, we found the EIP-196 prebuild functions can be used to speed up the zero-knowledge proof verification in Smart Contracts. The computation cost is reduced by 95%. The findings in this proposal not only largely improve the scalability but also removes the Mix and Match protocol from the auction protocol for the first time.

In the third study, we propose an auction protocol that has an exponential level bidding price bound. To extend the bidding price bound to 2^(|V |)−1, a binary format bidding vector is commonly used and a somewhat homomorphic encryption (SHE) or a fully homomorphic encryption (FHE) is also necessary to mimic the homomorphic AND and homomorphic OR algorithms. The SHE and FHE encryption schemes are much more complicated and cannot reach public verifiability easily. A homomorphic operation is only necessary when the plaintext of the ciphertext is unknown. By deeply observing the protocol used for binary format bidding vector, we found that each bidder knows their own plaintext input of the homomorphic AND operation. By this observation, we propose a zero-knowledge proof that each bidder can prove the result of a homomorphic AND operation without using a homomorphic multiplication. Based on this proof, our protocol only needs a partially homomorphic encryption such as an ElGamal encryption to use homomorphic addition to mimic the homomorphic OR operation. A homomorphic multiplication is not necessary. The finding in this proposal extends the bidding price bound to an exponential level without a SHE or FHE for the first time.

From now on, we provide a summary of the proposal. We have made the above three proposals in order to realize a secure auction protocol in response to the social issues mentioned above. In the first study, we propose an auction protocol without a trusted manager. In the second study, we proposed an efficient auction protocol that reaches the optimal time complexity. In the third study, we proposed an auction protocol that extends the bidding price bound to an exponential level without a SHE or FHE. Our all proposals satisfy the necessary properties, correctness, public verifiability, bid secrecy, and M + 1st-bidder's anonymity. In this dissertation, we proposed many techniques such as greedy strategy and zero-knowledge AND proof for the bit-slice vectors for the first time. These techniques are also important for protocols that need to compare secret values such as a millionaire problem and multi-party computation. However, there are still many problems in the systems that surround us. We will continue to address this problem using cryptographic techniques.