Nearly Practical and Privacy-Preserving Proofs on Authenticated Data

Abstract. We study the problem of privacy-preserving proofs on authenticated data in which a party receives data from a trusted source and is requested to prove statements over the data to third parties in a correct and private way, i.e., the third party learns no information on the data but is still assured that the claimed proof is valid. Our work particularly focuses on the challenging requirement that the third party should be able to verify the validity with respect to the specific data authenticated by the source — even without having access to that source. This problem is motivated by various scenarios emerging from several application areas such as wearable computing, smart metering, or general business-tobusiness interactions. Furthermore, these applications also demand any meaningful solution to satisfy additional properties related to usability and scalability. First, third parties should be able to check proofs very efficiently. Second, the trusted source should be independent of the data processor: it simply (and possibly continuously) provides data, e.g., without knowing which statements will be proven. This paper formalizes the above three-party model, discusses concrete application scenarios, and introduces a new cryptographic primitive for proving NP relations where statements are authenticated by trusted sources. After discussing a generic approach to construct this primitive, we present a more direct and efficient realization that supports general-purpose NP relations. Our realization significantl