Verifiably anonymous data collection on web

Abstract

In this paper, a new notion which we call verifiably anonymous data collection protocol is introduced and formalized in the client-server model where each respondent uses a web interface to communicate with a server operated by the data miner. A construction leveraging a combination of semantically secure double trap-door encryption and OR zero-knowledge proof system is proposed and analyzed, where data sent from a respondent Alice is first encrypted using her personal partial key; Alice then proves to the data miner that the resulted ciphertext is valid and is sent by one of respondents dynamically formed by the respondent without getting the consent or assistance of the other respondents. A rigorous proof of the soundness and the zero-knowledge property of our data collection protocol in the presence of malicious adversary is presented.