Strengthening Authenticity and Mitigating Misinformation: Slightly Homomorphic Digital Signatures and Privacy Preserving Folding Schemes

In an era where misinformation proliferates rapidly, ensuring the authenticity of digital content can be paramount. This dissertation explores two cryptographic solutions, which can be used to strengthen authenticity and thereby mitigate misinformation: slightly homomorphic digital signatures and privacy preserving folding schemes.

The first part of this dissertation focuses on slightly homomorphic digital signatures. Specifically, we construct quotable signatures for text, and digital signatures for images allowing JPEG compression. Quotable signatures allow extraction of a signature for a quote from a text, from a signature for the text, ensuring that quotes can be authenticated, even when detached from their original context. The digital signature scheme for JPEG images supporting compression is similar. It allows extracting a signature for a compressed JPEG image, from a signature for the original image, despite the utilized JPEG compression being lossy. Our construction requires the used quantization tables to contain only powers of two. For both constructions, the extracted signature is signed with the same private key as the original signature and, crucially, extraction does not require knowledge of the key, nor interaction with the signer.

In the second part, we introduce privacy preserving folding schemes, a natural extension of folding schemes with selective verification. Folding schemes transform the task of creating multiple zero-knowledge proofs that statements are in a language into creating one zero-knowledge proof for a (new) statement from the same language, at the cost of verification also requiring one to check a (cheap) inclusion proof. With known constructions of folding schemes, the inclusion proofs for a statement leak other statements. Privacy preserving folding schemes ensures that verification of one statement does not leak information about other statements, at a minimal increase in inclusion proof size. This is achieved through the introduction of NP-statement hiders, which allow an instance of a relation to be hidden as a new instance in the same relation, in a verifiable way.

We define and prove the security and the efficiency of these cryptographic constructions through rigorous theoretical analysis and performance evaluation. The proposed constructions offer mechanisms for maintaining the integrity and authenticity of digital content, providing a step forward in the fight against misinformation.