International Association
for Cryptologic Research

End-to-end encrypted (E2EE) messaging platforms serving hundreds of millions of users face a fundamental vulnerability: users must trust service providers to distribute authentic public keys. This problem creates opportunities for sophisticated man-in-the-middle attacks and surveillance. While key transparency systems promise to eliminate this trust requirement, existing solutions have failed to achieve practical deployment due to prohibitive cost in computation and bandwidth, and inadequate infrastructure. Our main innovation is the integration of a zero-knowledge virtual machine to create a “rollup” architecture on a third-party data availability layer via which every user automatically checks the integrity of the whole key directory. Counterintuitively, this approach yields substantial performance improvements over custom-built zk proof circuits and enables verification of targeted policies within the cryptographic proof system. We introduce PRISM, the first practically deployable key transparency protocol that eliminates hidden backdoors in E2EE services through automatic, trust-minimized verification. Our system advances beyond previous approaches by proving not just structural validity of key directory updates, but their semantic correctness as well. Previous solutions require some form of manual interaction by the user. This burden prevented wide spread adoption. Our solution however eliminates user intervention entirely. This paper is intended as an overview rather than an exhaustive specification. Our implemented system already integrates additional components whose full complexity exceeds the scope of this short presentation.