Thesis Proposal


"Privacy-Preserving Tools in the Age of Blockchain"

Apoorvaa Deshpande

Monday, November 19, 2018 at 10:30 A.M.

Lubrano Conference Room (CIT 4th Floor)

In recent years, the blockchain has emerged as a primitive with diverse applications. The blockchain gives us the ability to create a repository of public knowledge with global consensus through an immutable append-only decentralized data structure. However, data published in the public eye in an immutable fashion can have adverse privacy implications. Thus, we need privacy-preserving tools for harnessing the power of blockchain. The blockchain in turn also helps in achieving privacy-preserving solutions for various applications.

In this thesis, we propose and develop the following privacy-preserving tools:

Fully Homomorphic Proofs: Given zero-knowledge proofs for different statements, we give a framework to form proofs for new inferred statements. The security guarantee along with soundness and zero-knowledge is that of unlinkability; an inferred proof should be indistinguishable from a fresh proof for a combined statement. Fully homomorphic proofs enable more expressive and more private proofs for data published on the blockchain.

Round Optimal Witness Hiding Proofs: Witness hiding proofs are weaker versions of zero knowledge proofs that are often sufficient for proving statements about data published on the blockchain. For the first time, we give 2-round witness-hiding protocols for NP with respect to certain distributions. As a building block, we introduce Proofs of Ignorance; we formalize what it means to provably not know and explore the settings in which one could give a convincing proof of ignorance.

Adaptive Homomorphic Secret Sharing: Homomorphic Secret Sharing (HSS) is a form of secret sharing that supports evaluation of programs on shares of a secret w to get shares of P(w) for any program P. This primitive lends itself to design of applications for private data access with accountability; for example, the private data can be secret shared with independent servers and evaluations can be published on the blockchain for accountability. We define and construct the primitive of Adaptive HSS where one share can be generated and evaluated without knowing the input to be shared.

Privacy-Preserving Verifiable Key Directories: The current implementations of online chat services place a lot of trust in the central server that stores all the usernames and their public keys. We initiate the study of the primitive of Verifiable Key Directories (VKD) to formalize the security and privacy of a key verification service. We analyze its building blocks and using the blockchain give more efficient constructions for the building blocks and in turn, for VKD.

Host: Professor Anna Lysyanskaya