Zero Knowledge Proofs in Hybrid Environments

Abstract

The impending advent of quantum computing poses a significant threat to classical cryptographic primitives, necessitating a robust migration toward post-quantum cryptographic (PQC) systems. However, a complete transition remains impractical in the short term, giving rise to hybrid environments where classical and PQC schemes coexist. This thesis addresses a fundamental challenge in such settings: the need for efficient and secure zero-knowledge proofs (ZKPs) that establish plaintext consistency across cryptographic primitives defined over distinct algebraic domains. We present novel zero-knowledge protocols that bridge lattice-based schemes, specifically NTRU, with classical constructions like Pedersen vector commitments and ElGamal encryption. Our primary contributions include (1) a !-protocol for proving plaintext equality between an NTRU ciphertext and a Pedersen commitment, and (2) a ZKP of plaintext equality between NTRU and ElGamal ciphertexts. Both constructions ensure perfect honest-verifier zero-knowledge and computational soundness, while preserving efficiency and composability. A central innovation of our work lies in constructing a common linear language across domains— leveraging homomorphic properties and inner product arguments—allowing the prover to demonstrate equivalence of messages without revealing their content. Our protocols integrate rejection sampling techniques to preserve privacy in the lattice setting and achieve 2n-special soundness. We further extend our constructions to support batch proofs, enabling scalable and bandwidthefficient verification of multiple plaintext equalities. These protocols are, to the best of our knowledge, the first concrete and fully specified ZKPs achieving plaintext equality across NTRU and widely used classical primitives. Our work lays foundational tools for secure interoperability in hybrid systems and facilitates verifiable migration paths toward post-quantum secure infrastructures.