Internal Annoucement - NovaNet
October 31, 2024

Enhancing Apple's Homomorphic Encryption with On-Device ZKPs

NovaNet's zero knowledge proofs (ZKPs) enhance homomorphic encryption (HE).

In a recent blog post, Apple detailed how they use HE in conjunction with other privacy-preserving technologies such as Private Information Retrieval (PIR) and Private Nearest Neighbor Search (PNNS) to power features like Enhanced Visual Search for Photos.

But what if we could take this commitment to privacy even further?

Enter ZKPs, a cryptographic innovation that allows one party to prove to another that a statement is true without revealing any information beyond the validity of the statement itself.

By generating these proofs locally on the user's device, Apple can enhance privacy, security, and trust without relying on external computations. In this detailed exploration, we'll explain how integrating NovaNet on-device ZKPs can enhance Apple's existing technologies at each step, bolstering privacy and ensuring that sensitive computations remain within the user's control.

What Are Zero-Knowledge Proofs?

Zero-knowledge proofs are cryptographic protocols that enable one party (the prover) to convince another party (the verifier) that a certain statement is true, without revealing any information beyond the fact that the statement is indeed true. This concept was first introduced in the 1980s and has since become a cornerstone in the field of cryptography.

How Do They Work?

At a high level, ZKPs involve complex mathematical computations that allow the prover to demonstrate knowledge of a secret without disclosing the secret itself. This is achieved through iterative processes where the verifier poses challenges, and the prover responds in a way that confirms they possess the knowledge, all without revealing the knowledge itself.

On-Device Generation of Zero-Knowledge Proofs

Crucially, for maximum privacy, the generation of zero-knowledge proofs can and should occur locally on the user's device. By doing so, users maintain full control over their data and the cryptographic proofs derived from it. This eliminates the need to trust external entities with sensitive computations or proof generation.

Apple's Use of Homomorphic Encryption and Privacy-Preserving Techniques

Apple's current approach to privacy-preserving computations involves several advanced technologies:

· Homomorphic Encryption (HE): Allows computation on encrypted data without decryption.

· Private Information Retrieval (PIR): Enables private keyword-value database lookups.

· Private Nearest Neighbor Search (PNNS): Facilitates approximate matching on vector embeddings.

· Differential Privacy (DP): Adds statistical noise to protect individual data points.

· iCloud Private Relay: Acts as an anonymization network to obscure user IP addresses.

While these technologies are robust, integrating on-device ZKPs can address certain limitations and enhance the overall privacy and security framework.

Improving Private Information Retrieval (PIR) with On-Device Zero-Knowledge Proofs

In Apple's implementation of PIR:

1. The client encrypts a keyword and sends it to the server.

2. The server performs computations on the encrypted keyword without decrypting it.

3. The server returns an encrypted result, which the client decrypts to obtain the value.

Limitations

· Trust in Correct Computation: The client must trust that the server performed the computations correctly on the encrypted data.

· Potential for Malicious Servers: A compromised server could return incorrect results or attempt to glean information from the interaction pattern.

Integrating On-Device Zero-Knowledge Proofs

By incorporating ZKPs generated locally on the device:

1. Proof of Correct Query Formation: The device generates a zero-knowledge proof that the encrypted query is correctly formed from the user's input without revealing the input itself.

2. Server's Proof of Correct Computation: The server performs the computation and provides a zero-knowledge proof (which can be verified using public parameters) that it correctly operated on the encrypted data without learning anything about the keyword.

3. Client Verification: The client uses the locally generated proof to verify the integrity of its query and verifies the server's proof upon receiving the response.

Benefits

· Increased Trust: Clients can verify both the correctness of their own queries and the server's computations, enhancing overall trust.

· Resistance to Malicious Actors: Even if the server is compromised, it cannot deceive the client without failing the proof verification.

· Local Control: By generating proofs on-device, users maintain full control over their data and the associated cryptographic proofs.

Enhancing Private Nearest Neighbor Search (PNNS) with On-Device Zero-Knowledge Proofs

In PNNS, used for features like Enhanced Visual Search:

1. The client encrypts an embedding vector and sends it to the server.

2. The server performs HE computations to find nearest neighbors in its database.

3. The server returns encrypted scores and metadata, which the client decrypts.

Limitations

· Computation Integrity: Similar to PIR, the client must trust that the server performed the nearest neighbor search correctly.

· Privacy of Server Data: While the client's data is protected, the server's database could be at risk if not properly secured.

Integrating On-Device Zero-Knowledge Proofs

By applying ZKPs generated locally on the device:

1. Client's Proof of Correct Embedding: The device generates a zero-knowledge proof that the encrypted embedding vector is computed correctly from the input data (e.g., the photo's ROI), without revealing the data itself.

2. Server's Proof of Correct Computation: The server provides a zero-knowledge proof that it correctly computed the nearest neighbors using the encrypted embedding, without learning anything about the client's data.

3. Client Verification: The client verifies both its own proof and the server's proof locally on the device before accepting the results.

Benefits

· Mutual Privacy: Both client and server data remain private, with cryptographic guarantees.

· Auditability: Enables future auditing of server computations without exposing sensitive data.

· On-Device Assurance: Users gain confidence knowing that all proofs and verifications happen on their own devices.

Implementing On-Device Zero-Knowledge Proofs in Enhanced Visual Search for Photos

Let's examine how on-device ZKPs can be woven into the specific steps of Enhanced Visual Search.

Step 1: On-Device Processing

· Current Process: An on-device ML model detects regions of interest (ROIs) and computes an embedding vector.

· With On-Device ZKPs: The device generates a zero-knowledge proof locally that the embedding vector corresponds to a valid ROI derived from the user's photo, without revealing the photo itself.

Step 2: Query Preparation

· Current Process: The embedding vector is quantized and encrypted before being sent to the server.

· With On-Device ZKPs: Along with the encrypted embedding, the device includes the locally generated zero-knowledge proof that the embedding was computed correctly and honestly from the input data.

Step 3: Server Computation

· Current Process: The server performs HE computations to find the nearest neighbors.

· With On-Device ZKPs: The server, upon receiving the encrypted embedding and proof, verifies the proof (using public parameters) to ensure the embedding is valid. After computation, the server generates its own zero-knowledge proof that it performed the nearest neighbor search correctly, which can be verified by the client.

Step 4: Response Verification

· Current Process: The client decrypts the response and uses a local model to identify the best match.

· With On-Device ZKPs: Before decrypting, the client verifies the server's zero-knowledge proof locally on the device to ensure the computations were performed correctly.

Step 5: Updating Metadata

· Current Process: The photo's metadata is updated with the landmark label.

· With On-Device ZKPs: The device can generate a zero-knowledge proof locally that the metadata update corresponds to the received, verified data, maintaining integrity and allowing for future verification if needed.

Benefits in This Context

· End-to-End Integrity: Every step is verifiable, ensuring that both the client and server uphold their parts without exposing sensitive data.

· Enhanced Privacy: ZKPs prevent any leakage of information, even in the face of active adversaries.

· User Trust: Users gain increased confidence that their data is handled securely and correctly, knowing that all proofs are generated and verified on their own devices.

Benefits of Integrating On-Device Zero-Knowledge Proofs
Improved Privacy

· Data Minimization: ZKPs ensure that only necessary information is exchanged, with zero leakage of sensitive data.

· Protection Against Data Breaches: Even if intercepted, zero-knowledge proofs do not reveal any useful information.

Enhanced Security

· Verification of Computations: Clients can cryptographically verify that servers performed computations correctly.

· Resistance to Malicious Actors: Reduces the risk posed by compromised servers or intermediaries.

Increased Trust and Transparency

· Auditable Processes: ZKPs allow for the creation of audit trails without compromising privacy.

· Regulatory Compliance: Helps in meeting stringent data protection regulations by providing provable security guarantees.

Local Control and User Empowerment

· On-Device Generation and Verification: By generating and verifying proofs locally, users maintain full control over their data and the associated cryptographic processes.

· No Reliance on External Entities: Eliminates the need to trust external servers or third-party services for sensitive computations.

Potential for Efficiency Gains

· Optimized Protocols: Advances in ZKP protocols have led to more efficient computations, which could reduce latency.

· Scalability: Cryptographic assurances enable more scalable architectures by reducing the need for heavy-handed security measures.

Conclusion

Zero-knowledge proofs, when generated and verified locally on the user's device, offer a powerful enhancement to Apple's already robust privacy-preserving technologies.

By integrating on-device ZKPs at each step—whether in PIR for exact matches, PNNS for approximate matches, or the specific implementation in Enhanced Visual Search—Apple can provide even stronger guarantees of privacy, security, and trust.

Gradient Shape - NovaNet
Gradient Shape - NovaNet