Expanding Blockchain Horizons through Privacy-Preserving Computation

In this thesis, we explore the area lying between privacy-preserving computation and blockchain applications. In particular, we consider the following applications: auctions, i.e., how to efficiently run auctions without an auctioneer while keeping the bids private; decentralized finance (DeFi), i.e., what are the current solutions and the open problems related to front-running; anonymous credentials, i.e., how to find a trade-off between privacy and accountability of the users.
In the context of auctions, we consider specifically the case of sealed-bid auctions, i.e., no bidder is supposed to know how much the other auction participants have bid. Sealed-bid auctions are a common way of allocating an asset among a set of parties but require trusting an auctioneer who analyses the bids and determines the winner. Many privacy-preserving computation protocols for auctions have been proposed to eliminate the need for a trusted third party. However, they lack fairness, meaning that the adversary learns the outcome of the auction before honest parties and may choose to make the protocol fail without suffering any consequences. In this thesis, we propose efficient protocols for both first and second-price sealed-bid auctions with fairness against rational adversaries, leveraging secret cryptocurrency transactions and public smart contracts. In our approach, the bidders jointly compute the winner of the auction while preserving the privacy of losing bids and ensuring that cheaters are financially punished by losing a secret collateral deposit. We guarantee that it is never profitable for rational adversaries to cheat by making the deposit equal to the bid plus the cost of running the protocol, i.e., once a party commits to a bid, it is guaranteed that it has the funds and it cannot walk away from the protocol without forfeiting the bid. Moreover, our protocols ensure that the winner is determined and the auction payments are completed even if the adversary misbehaves so that it cannot force the protocol to fail and then rejoin the auction with an adjusted bid. In comparison to the state-of-the-art, our constructions are both more efficient and furthermore achieve stronger security properties, i.e., fairness. Interestingly, we show how the second-price can be computed with a minimal increase of the complexity of the simpler first-price case. Moreover, in case there is no cheating, only collateral deposit and refund transactions must be sent to the smart contract, significantly saving on-chain storage.
In the context of decentralized finance, we take into consideration the problem of front-running. Front-running is the malicious, and often illegal, act of both manipulating the order of pending trades and injecting additional trades to make a profit at the cost of other users. In decentralized finance, front-running strategies exploit both public knowledge of user trades from transactions pend-ing on the network and the miner’s ability to determine the final transaction order. Given the financial loss and increased transaction load resulting from ad-versarial front-running in decentralized finance, novel cryptographic protocols have been proposed to mitigate such attacks in the permission-less blockchain setting. In this thesis, we systematize and discuss the state-of-the-art of front-running mitigation in decentralized finance, and illustrate remaining attacks and open challenges.
Finally, in the context of anonymous credentials, we study the notion of anonymous credentials with Publicly Auditable Privacy Revocation (PAPR). PAPR credentials simultaneously provide conditional user privacy and auditable privacy revocation. The first property implies that users keep their identity private when authenticating unless and until an appointed authority requests to revoke this privacy, retroactively. The second property enforces that the auditors can verify whether or not this authority has revoked privacy from an issued credential (i.e., learned the identity of the user who owns that credential), holding the authority accountable. In other words, the second property enriches anonymous credential systems with transparency by design, effectively discouraging such systems from being used for mass surveillance. In this thesis, we introduce the notion of a PAPR anonymous credential scheme, formalize it as an ideal functionality, and present constructions that are provably secure under standard assumptions in the Universal Composability framework. The core tool in our PAPR construction is a mechanism for randomly selecting an anonymous committee towards which users secret share their identity information, while hiding the identities of the committee members from the authority. As a consequence, in order to initiate the revocation process for a given credential, the authority is forced to post a request on a public bulletin board used as a broadcast channel to contact the anonymous committee that holds shares of the identity connected to the credential. This mechanism makes the user de-anonymization publicly auditable. Finally, we show how to modify our construction to obtain proactive security.
Overall, the goal of this thesis is to contribute to the extension and enhancement of blockchain applications through the usage of privacy-preserving computation.