Eva: Efficient Privacy-Preserving Proof of Authenticity for Lossily Encoded Videos

Eva: Efficient Privacy-Preserving Proof of Authenticity for Lossily Encoded Videos

Speakers: Chengru Zhang; Xiao Yang; David Oswald; Mark Ryan; Philipp Jovanovic

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=tPYq1R9x_8o

Overview

In an era increasingly plagued by sophisticated digital manipulation and the rapid proliferation of generative AI, establishing the authenticity and provenance of digital media, particularly videos, has become paramount. The talk "Eva: Efficient Privacy-Preserving Proof of Authenticity for Lossily Encoded Videos" by Chengru Zhang and co-authors introduces a groundbreaking cryptographic protocol designed to address this critical challenge. Eva provides a robust mechanism for verifying that a video was indeed captured at a claimed time and location, and subsequently transformed by specific, declared edits, all while safeguarding the privacy of the original footage.

Eva represents a significant leap forward in media provenance, being the first cryptographic protocol to offer authenticity proofs for videos, critically supporting lossy codecs like H.264, which are ubiquitous in modern video streaming and storage. Furthermore, it allows for arbitrary edits on videos of unlimited size, a flexibility often lacking in prior authentication schemes. The protocol achieves this with remarkable performance, boasting linear prover time and constant RAM usage during proof generation, culminating in a highly succinct proof of only 448 bytes.

This work is particularly relevant for combating the spread of deepfakes and misinformation, offering a verifiable chain of custody for video content. By integrating zero-knowledge proofs (ZKPs) into the video lifecycle, Eva empowers viewers to trust the content they consume, while content creators can assert the integrity of their work without exposing sensitive raw footage. Its efficiency and comprehensive feature set position Eva as a vital tool for securing the digital media landscape against increasingly advanced adversarial manipulations.

Background

▶ Watch: Introduction, problem, and Eva's workflow (0:00)

The digital video lifecycle, from capture to sharing, is inherently vulnerable to manipulation. A video is typically captured by a device, edited by a creator (e.g., adding effects, removing sensitive parts), encoded to reduce size, and finally shared. At each stage, especially post-capture, the integrity of the content can be compromised, intentionally or unintentionally. With the advent of sophisticated generative AI technologies, fabricating realistic, yet entirely fake, video content has become alarmingly easy, leading to a crisis of trust in digital media and fueling the spread of misinformation and fake news.

The fundamental problem is that viewers currently lack reliable mechanisms to ascertain a video's authenticity. They cannot determine if the footage was genuinely captured at the claimed time and location, nor if the transformations (edits and encoding) applied to it are precisely as declared by the content creator. This gap in trust necessitates a solution that can cryptographically guarantee provenance.

Adding another layer of complexity is the requirement for privacy. Original footage often contains sensitive information, such as faces, locations, or private moments, which might be masked or blurred in the final shared video. Any authenticity protocol must ensure that proving the integrity of the video does not inadvertently expose this sensitive original content.

Prior efforts in media provenance, such as the C2PA (Coalition for Content Provenance and Authenticity) standard, focus on embedding metadata and signatures at the point of capture. Eva builds upon this by enhancing the workflow with cryptographic proofs, specifically zero-knowledge proofs, to link the original signed footage to the final, potentially edited and lossily encoded, video.

However, applying cryptographic proofs to video presents two formidable challenges:

1. Enormous Data Size: Uncompressed video data is exceptionally large. Proving the integrity of an entire video in a single cryptographic circuit would result in impractically giant circuits, consuming vast computational resources and time.
2. Complexity of Lossy Codecs: Modern video codecs, such as H.264, are highly complex, involving intricate algorithms for compression that intentionally discard some data to achieve smaller file sizes. The reference implementations (e.g., JM reference encoder, X264 encoder) can exceed 100,000 lines of code. Building a zero-knowledge proof circuit that accurately models and proves every step of such a complex, lossy process is an immense undertaking.

Eva's design directly confronts these challenges by leveraging key observations about video processing and codec behavior, paving the way for a practical and efficient solution.

Key Findings

▶ Watch: Addressing video challenges: microblocks and shared data (3:56)

Eva introduces several groundbreaking contributions that collectively establish a new paradigm for video authenticity:

• First Cryptographic Protocol for Video Authenticity: Eva pioneers the application of zero-knowledge proofs specifically for verifying the authenticity and provenance of video content, moving beyond image-based solutions.
• First to Support Lossy Codecs: A critical innovation is Eva's ability to provide authenticity guarantees for videos encoded with lossy codecs (e.g., H.264). This is a significant departure from prior work, which typically struggled with or explicitly avoided the complexities introduced by lossy compression, making Eva applicable to virtually all real-world video scenarios.
• Arbitrary Edits on Unlimited Size Videos: The protocol supports a wide range of editing operations—such as masking, cropping, and scaling—and is designed to handle videos of arbitrary, effectively unlimited, size. This flexibility is crucial for real-world content creation workflows.
• High Performance and Efficiency: Eva demonstrates remarkable performance characteristics:
• Linear Prover Time: Achieves a prover time of approximately 2.6 microseconds per pixel on a consumer PC. This translates to roughly 2.5 hours for a 2-minute HD video, making it significantly faster than previous methods.
• Constant RAM Usage: During the proof generation phase, Eva requires a constant 8.5 GB of RAM, a manageable amount for typical systems. Proof compression, a one-time cost, uses 45 GB of RAM.
• Fully Succinct Proof: The final proof generated by Eva is exceptionally compact, requiring only a constant 448 bytes. This succinctness is vital for efficient storage and transmission, especially across networks.
• Novel Technical Observations: Eva's feasibility hinges on two key insights:
• Microblock-wise Processing: While entire videos are large, they are processed in small, manageable units called microblocks (typically 16x16 pixels). This allows for incremental proving.
• Shared Encoder/Decoder Data: Despite their lossy nature, video encoders and decoders share common procedures and data during certain stages. Specifically, data like prediction macroblocks (P) and quantized coefficients (Z) are recovered identically by the decoder as they were during encoding. Eva leverages this by treating these shared data points as public inputs, simplifying the proving circuit.

These findings collectively demonstrate that Eva provides a practical, efficient, and cryptographically sound solution for ensuring video authenticity and provenance in a privacy-preserving manner, marking a substantial advancement in digital media security.

Technical Deep Dive

▶ Watch: Practical ZKP techniques: lookups and succinct proofs (4:50)

Eva's core innovation lies in its enhanced workflow, which integrates zero-knowledge proofs (ZKPs) into the standard video lifecycle. The process begins with a recorder embedding a signing key, in line with C2PA standards. When a video is captured, the recorder produces a signature for the original footage. Subsequently, when a content creator edits and encodes the video, they additionally generate a zero-knowledge proof of authenticity. This proof attests to two critical facts: first, that the original footage was indeed signed by the legitimate recorder, and second, that the final compressed video stream was generated from this original footage through specific, declared editing and encoding operations. Finally, viewers can verify this proof against the video stream and the claimed edits, without needing access to the original sensitive footage.

To make this feasible for the enormous and complex nature of video data, Eva addresses the inherent challenges with two primary solutions:

1. Incremental Proving for Large Videos: Instead of attempting to prove the entire video in a single, massive SNARK circuit, Eva breaks down the proof generation into smaller, manageable steps. It employs Incrementally Verifiable Computation (IVC), proving the processing of one microblock (typically 16x16 pixels) at each step. This approach transforms a problem of unbounded size into a series of bounded computations, making the overall process tractable. The IVC structure allows the proof to accumulate across many microblocks, eventually covering the entire video while maintaining a linear relationship between prover time and video size.

1. Simplified Proof for Lossy Codecs: Proving the entire, highly complex, and lossy encoding process (like H.264 with over 100,000 lines of code) within a ZKP circuit is computationally prohibitive. Eva circumvents this by exploiting the observation that despite being lossy, decoders can recover certain data from the video stream that is identical to what was present during encoding. Specifically, prediction macroblocks (P) and quantized coefficients (Z) are consistent between the encoder and decoder. Eva treats these shared data points as public inputs that can be recovered and verified by the verifier directly from the video stream. The prover's task is then significantly simplified: it only needs to prove the correct derivation of the quantized coefficients (Z) from the prediction macroblocks (P) and the original pixel data, rather than proving the entirety of the complex encoding logic. This drastically reduces the circuit size and complexity.

Beyond these foundational solutions, Eva incorporates advanced cryptographic techniques to further enhance practicality and efficiency:

• Efficient Bitwise Operations with Lookups: Many operations involved in video processing, especially encoding and editing, require intricate bitwise manipulations. Performing these bitwise operations directly within SNARK circuits is notoriously expensive. Eva introduces a general paradigm that combines any folding scheme with lookup arguments to create an IVC system that efficiently supports lookups. In essence, this involves constructing an augmented step circuit that additionally verifies the lookup relation. This allows expensive bit operations to be replaced with more efficient lookup table operations, significantly reducing constraint counts and improving prover performance.

• Constant Proof Size Decider: While IVC schemes inherently produce proofs that grow linearly with the circuit size (or the number of steps), Eva aims for a fully succinct proof. To achieve this, it proposes another novel paradigm: building a decider with constant proof size from a folding scheme and Commitment Proofs (CP). This is accomplished by cleverly connecting the commitments generated in the folding instances with the witnesses of the decider. This architectural choice ensures that regardless of the video's length or the complexity of the edits, the final proof remains a constant 448 bytes, which is crucial for practical deployment and transmission.

Eva's implementation leverages several optimizations:

• It applies its paradigms to the Nova folding scheme, implementing a variant called Novaera based on the Nova implementation in the Synapse library.
• LogUp is utilized for efficient lookup arguments, and Groth16 is employed for the final decider proof, balancing efficiency and security.
• The artworks library was improved to achieve faster constraint synthesis and witness extraction from the circuit, a common bottleneck in ZKP development.
• To accelerate proof generation, Eva utilizes GPUs, specifically for MSM (Multi-Scalar Multiplication) implementation and a custom GPU-based sparse matrix vector multiplication, which are critical components for speeding up cryptographic operations.

This combination of architectural insights, cryptographic paradigms, and implementation optimizations makes Eva a highly efficient and practical solution for privacy-preserving video authenticity.

Demo / Proof of Concept

▶ Watch: Implementation strategies and GPU optimizations (6:00)

While the talk did not feature a live, interactive demonstration, the authors presented a comprehensive evaluation of Eva's performance across various video edits and formats, effectively serving as a proof of concept for its practicality and efficiency. The evaluation highlighted key performance metrics:

The IVC prover time for processing 256 microblocks (a common processing unit) was measured to be between 1 and 200 milliseconds. This translates to an impressive processing speed of 2 to 3 microseconds per pixel, demonstrating the efficiency of Eva's incremental proving approach.

During the proof generation phase, Eva maintained constant RAM usage, ranging from 6 to 11 GB. This consistency is crucial for processing large videos without encountering memory exhaustion issues, a common pitfall for other ZKP systems.

The most computationally intensive part is proof compression, which is a one-time cost performed after all IVC steps are completed. The decider takes approximately 65 to 80 seconds to compress the proof, utilizing 40 to 50 GB of RAM. While this memory usage is higher, its one-time nature makes it manageable for offline processing or dedicated proof generation services. The resulting final proof is exceptionally compact, at a mere 448 bytes.

For concrete performance benchmarks, Eva was tested on two video formats: a small "Forman" video and a 2-minute HD "Bonnie" video. The prover took about 2 minutes to generate a proof for the small Forman video. For the more demanding 2-minute HD Bonnie video, the proof generation time was approximately 2.5 hours. These figures, while seemingly long for real-time applications, are groundbreaking for cryptographic proofs of such complex data and are well within acceptable limits for offline media processing and content provenance systems.

A comparative analysis against existing related work on image authentication further underscored Eva's advantages. For scenarios involving a small number of pixels, Eva's performance was noted to be less efficient due to the overhead of its one-time proof compression. However, for practical numbers of pixels found in realistic videos, this overhead becomes negligible, and Eva's benefits become overwhelmingly evident. Specifically, for the 2-minute HD video, Eva was found to be at least 20 times faster than existing works that support arbitrary edits, even without considering memory constraints. When compared to VIR, a dedicated protocol focusing specifically on masking operations, Eva still emerged as six times faster, demonstrating its superior efficiency even against specialized solutions.

These evaluation results strongly validate Eva's design principles and implementation, proving that it offers a practical and highly efficient solution for privacy-preserving video authenticity, capable of handling real-world video sizes and editing complexities.

Defensive Implications

▶ Watch: Performance evaluation and comparison with related work (6:55)

Eva presents a transformative tool for bolstering digital media security and combating the pervasive threat of misinformation and deepfakes. Its defensive implications span content creators, platforms, and viewers:

1. For Content Creators and Recording Devices: The most direct implication is the ability to establish an undeniable chain of custody for digital video content. Recorders, such as smartphones and cameras, should integrate the C2PA standard for embedding signing keys and potentially even the initial steps of Eva's proof generation. Content creators, when editing and encoding videos, can leverage Eva to generate zero-knowledge proofs of authenticity. This allows them to cryptographically attest to the origin of their footage and the integrity of their edits, providing verifiable assurance to their audience without revealing sensitive original content. Adopting Eva could become a new standard for journalistic integrity, artistic provenance, and legal evidence.

1. For Social Media Platforms and News Organizations: These entities are on the front lines of combating fake news. By integrating Eva's proof verification mechanisms, platforms can allow users to verify the authenticity of uploaded videos. This could involve displaying a "verified" badge for videos accompanied by a valid Eva proof, or even automatically flagging content lacking verifiable provenance. Implementing such systems would significantly enhance platform trustworthiness and provide a powerful tool against the spread of manipulated media. News organizations could use Eva to demonstrate the authenticity of their investigative journalism, rebuilding public trust.

1. For Viewers and Consumers: Eva empowers viewers with the tools to critically assess the media they consume. While direct verification might be complex for the average user, user-friendly interfaces (e.g., browser extensions, mobile app features) could be developed to check Eva proofs. This shifts the burden of trust from implicit acceptance to explicit, cryptographic verification, fostering a more informed and resilient digital citizenry.

1. Enhancing Digital Forensics: In investigations involving video evidence, Eva proofs could provide an invaluable layer of cryptographic integrity. Law enforcement and forensic experts could use these proofs to quickly ascertain whether a video has been tampered with since its original capture and declared edits, streamlining investigations and strengthening legal cases.

1. Standardization and Ecosystem Development: The success of Eva will depend on its adoption and integration into broader industry standards for media provenance. Developers and researchers should explore how Eva can be further optimized, integrated into existing video processing pipelines, and potentially combined with other privacy-enhancing technologies. Efforts should focus on reducing the proof compression time and RAM usage further, and on creating open-source tools and libraries to facilitate widespread adoption.

In essence, Eva provides a robust cryptographic framework to rebuild trust in digital video content. By enabling verifiable provenance and integrity checks, it offers a powerful defense against the malicious use of generative AI and the pervasive problem of misinformation, shifting the paradigm from reactive content moderation to proactive cryptographic assurance.

Key Takeaways

• First-of-its-kind Protocol: Eva is the inaugural cryptographic protocol for video authenticity, uniquely supporting lossy codecs and enabling verifiable arbitrary edits on videos of unlimited size.
• Highly Efficient Proof Generation: It achieves linear prover time (2.6 microseconds/pixel) and constant RAM usage (8.5 GB) during the incremental proving phase, making it practical for real-world video processing.
• Ultra-Succinct Proofs: Eva culminates in a remarkably compact, constant 448-byte proof, facilitating efficient storage and transmission, regardless of video length or edit complexity.
• Innovative ZKP Techniques: Key to its feasibility are incremental proving (IVC) using microblocks, leveraging shared encoder/decoder data as public inputs, and employing lookup arguments for efficient bitwise operations within SNARKs.
• Superior Performance: Eva significantly outperforms prior image authentication methods (e.g., 20x faster than existing arbitrary-edit solutions, 6x faster than specialized masking protocols) for realistic video sizes.
• Crucial for Trust and Privacy: It offers a robust solution to combat deepfakes and misinformation by providing cryptographically verifiable video provenance while preserving the confidentiality and privacy of original sensitive footage.

About the Speaker(s)

The talk "Eva: Efficient Privacy-Preserving Proof of Authenticity for Lossily Encoded Videos" was presented by Chengru Zhang. This work is a collaborative effort, with significant contributions from co-authors Xiao Yang, David Oswald, Mark Ryan, and Philipp Jovanovic. The presentation was given at the IEEE S&P conference.