Technical Overview V2.0

This document describes the zkPass protocol from a technical perspective. It presents the underlying cryptographic components and specifies the building blocks used to construct the zkPass protocol.

The zkPass protocol is meticulously designed to serve as a private data oracle, leveraging Vector Oblivious Linear Evaluation (VOLE) to create efficient commitments, commonly referred to as VOLE-Based Zero-Knowledge Proofs (VOLE-ZK). Specifically, beyond the use of SoftSpokenOT for Oblivious Transfer(OT), the security integrity of the zkPass protocol is intimately tied to the robustness of the VOLE-in-the-Head (VOLEitH) technique.

Overview

While Transport Layer Security (TLS) provides secure access to private data, it doesn't allow users to prove to third parties that the data genuinely came from a specific website. Existing solutions either require unwanted trust assumptions or server modifications, effectively locking users' data at its source. The zkPass protocol addresses this issue by extending TLS into a three-party TLS(3P-TLS) to prevent cheating and protect privacy, enabling secure data sharing without needing assistance or permission from the data holder.

The zkPass protocol involves three entities: the Prover (P), the Verifier (V), and the DataSource (TLS Server as S). Departing from conventional methods, P utilizes their access token to directly pinpoint and extract their data from S. P then generates a Zero-Knowledge Proof (ZKP) for the V's inspection. This procedure ensures that V remains oblivious to the P's personal data.

To actualize this architecture, we integrate 3P-TLS, MPC, and Non-Interactive Zero Knowledge (NIZK) technologies.

We have designed and implemented the zkPass protocol in two modes:

1. Proxy mode: In this mode, P communicates with S through V as a proxy.

2. MPC mode: In this mode, both P and V act as a client to communicates with S.

Typically, the zkPass protocol operates efficiently in Proxy mode. However, a small number of TLS servers do not support this mode, meaning they block the same account's requests originating from different IP addresses. In such cases, our protocol switches to operate in MPC mode.

Proxy Mode

Under the proxy mode, we propose having V act as a proxy between P and S. In this setup, P communicates with S through V, which allows V to record the traffic for later verification. The modified protocol flow is designed to maintain security while improving efficiency.

Flow and Security Properties

The protocol flow is as follows:

1. Three-Party Handshake: P, V, and S engage in a 3P-TLS handshake. This handshake establishes cryptographic parameters and ensures mutual authentication among the parties.

2. Prover's Key Share Commitment: After the handshake, P commits to her key share $K_p$. This commitment prevents P from altering her key share later in the protocol. P must commit to her key share $K_p$​ before learning the complete session key $K$. This commitment binds P to her key share, ensuring she cannot manipulate the session to produce fraudulent proofs later on.
3. Verifier Reveals Key Share: V reveals his key share $K_v$ ​ to P. With both key shares, P computes the full session key $K=K_p+K_v$.
4. Session Continuation: P uses the session key $K$ to continue the TLS session with S. V, acting as a proxy, records all traffic between P and S.
5. Proof Generation: After the session concludes, P proves statements about the recorded session to V.

To verify server identity, during the three-party handshake, V can verify S's identity by checking the server's signature over a fresh nonce, as per standard TLS procedures. Verifier integrity and privacy are maintained because, under the assumption that TLS is secure, a malicious V cannot compromise the integrity and privacy of the TLS session between P and S. Ensuring Prover integrity requires certain network assumptions. V must maintain a reliable connection to S throughout the session and ensure that the P cannot tamper with the messages exchanged between V and S such as those executed through BGP hijacking. Since attacks like BGP are difficult to execute in practice and are already mitigated by ICP and CSP, these network assumptions are generally acceptable and can be considered negligible in practical scenarios.

The Proxy mode in the zkPass protocol enhances efficiency and performance by simplifying the communication flow and eliminating the need for intensive cryptographic computations after the handshake phase. Since no complex cryptographic operations are required during the rest of the session, the protocol becomes faster and more efficient due to the reduced cryptographic workload. While this approach is more universal, it introduces an additional trust assumption for the proxy and requires not only a ZK solution that’s affordable for the client, but also special magic tricks to bypass the data source’s WAF.

VOLEitH Protocol

VOLEitH is the most suitable and client affordable ZKP Protocol for authorizing TLS. We have implemented the protocol using SoftSpokenOT[ROY22], VOLE-ZK[YSWW21] and Fiat-Shamir transform[FS87].

VOLE

In order to construct the zkPass protocol, we introduce the VOLEitH to create an interactive argument system. This system is then made non-interactive using the Fiat-Shamir transform and its security is proven within the Random Oracle Model(ROM). zkPass uses VOLE correlations over a finite field $F_{2^k}$ , to use as a form of linearly homomorphic commitment scheme. A VOLE correlation of length is defined by a random global key $Δ ∈ F_{2^k}$ , a set of random bits $u_i ∈ F_{2^k}$, random VOLE tags $v_i ∈ F_{2^k}$ and VOLE keys $q_i ∈ F_{2^k}$ such that:

$$q_i = u_i * \Delta + v_i \quad for \space i = 0,...,\ell-1.$$

The values $u_i$ and $v_i$ should be known only to P, while $q_i$ and $∆$ should be given to V. A VOLE correlation can be seen as committing P to the random bits $u_i$ via a linearly homomorphic commitment scheme. The scheme is hiding, because the random $v_i$ mask $u_i$ in the V's values $q_i$, and the scheme is binding, because opening to a different value $u^′_i$ requires P to come up with a tag $q^′_i = u^′_i ∗ Δ + v^′_i$ but then P would have successfully guessed $∆ = (v^′_i − v_i)/(u^′_i − u_i)$, which can only happen with probability $2^{−k}$.

A VOLE correlation can be created with a secure two-party protocol, in zkPass protocol, however, since we want to obtain ZKP that are publicly verifiable, we instead use the VOLEitH technique [BBD+23]. Here, P first generates its values $u_i$ , $v_i$ and commits to them using a special type of VOLE commitment. The commitment is set up such that V can later send to P the random key $∆$, after which, P can send an opening that allows V to learn its $q_i$ values, such that equation holds for $∆$, and nothing more. It is important that $∆$ is only given to P after running the main steps of the ZKP, since as soon as $∆$ is known, the binding property of the homomorphic commitments is trivially broken.

VOLEitH Commitment

The main building block of our VOLEitH approach is the technique of committing to a vector of N pseudo-random seeds by deriving them from a tree of length-doubling PRGs. This is also known as the GGM construction, which builds a puncturable PRF from a PRG [GGM84, KPTZ13,BW13, BGI14]. We model this as an all-but-one vector commitment scheme, where P commits to N seeds by sending a single hash value, and can later open N − 1 of them with only $O(logN)$ communication. To open all-but-one of the seeds, say all except index $sd_j$ , P takes the siblings of all nodes on the path from the root to leaf $j$ (excluding the root node) and sends these to V, together with the commitment $com_j$ . V can then reconstruct every $sd_i$ for $i \ne j$ using the sibling nodes, and also has enough information to compute the hash value $h$ and check the original commitment.

Then we start converting vector commitments to VOLE, to obtain our desired VOLE commitments, P starts by committing to τ all-but-one vector commitments. After send the vector commitments, the next step is to convert each vector commitment into a length-$l$, small-field VOLE correlation in $F_{2^k}$ , This involves first expanding each of the seeds $sd_0, . . . , sd_{N−1}$ (committed in the vector commitment) using a PRG, to obtain $N$ strings $r_0, . . . , r_{N−1} ∈ \{0,1\}^l$, and then computing in $F_{2^k}$:

$$u=\sum_{i=0}^{N-1}r_i, v=\sum_{i=0}^{N-1}i*r_i$$

where $i$ is encoded as an element of $F_{2^k}$.

To see how this can be used to get a VOLE correlation, consider a V who later learns seeds $sd_i$ for all $i \ne j$, for some index $j∈ {0, . . . , N − 1}$ (viewed as an $F_{2^k}$ element). V can compute:

$$q=\sum_{i=0}^{N-1}(j-i)*r_i = j^**u-v$$

After doing this for each of the vector commitments, P has $l$ small and independent VOLE correlations. Denote these as $u_i$，$V_i$ for $i = 0, . . . , τ − 1$, where we now view $V_i$ as a matrix in $\{0, 1\}^{l∗k}$ , instead of a vector in $F_{2^k}$ . V will eventually learn ($Δ_i ,Q_i$) such that:

$$Q_i = V_i + (\delta_0*u_i...\delta_{k-1}*u_i)$$

where $δ_0, ..., δ_{k−1}$ is the bit decomposition of $∆$.

After this P must send correction values so that the VOLEs can be fixed to use the same $u$ value. Finally we make a VOLE Consistency Check to ensure that all $u$ values are corrected in right ways.

VOLEitH Proof System

The VOLE-ZK is an interactive ZKP in the VOLE-hybrid model. It is based on the Line-Point Zero-Knowledge Paradigm[DIO21]. For the zkPass protocol, we use the QuickSilver protocol to prove boolean circuits satisfaction. As QuickSilver is an interactive proof system, it is described here as a protocol executed between two parties: P and V. And we will convert it into the NIZK eventually.

We have VOLE Commitments at last step, P first get $χ_i$ from Fiat-Shamir transformation and then P calculates the $∑ u_i$ ∗ $χ_i$ and $∑ v_i$ ∗ $χ_i$ for all the inputs and gates in circuit, and later get $Δ$ from Fiat-Shamir then open all the vector commits and $∑ u_i$ ∗ $χ_i$ , $∑ v_i$ ∗ $χ_i$ , to V, V reconstructs the GGM Trees to obtain VOLE instances and calculate $∑ q_i$ ∗ $χ_i$ then check:

$$\sum q_i*\chi_i = \sum u_i*\chi_i * \Delta + \sum v_i*\chi_i$$

If the equation equal then circuit satisfied.

At this point, we have successfully completed all protocol implementations.

Why VOLEitH

ZK systems like SNARKs are less suitable for authorizing TLS data because they involve intensive cryptographic computations, such as large-scale exponentiations and complex pairing operations. These operations require substantial computational resources and memory, leading to time-consuming proof generation that is often unaffordable for clients. Additionally, SNARKs typically require a trusted setup phase, which introduces potential security risks. While they may be acceptable for very small data sizes, they are inefficient and impractical for the typical data sizes found in TLS communications.

In contrast, VOLE-ZKs are much more efficient. They naturally handle the linear computations, enabling fast and low-overhead, which makes them more suitable for authorizing TLS data. They avoid the need for a trusted setup and do not require large memory or extensive calculations for proof generation, making them affordable for clients. However, VOLE-ZK proofs are interactive, necessitating the verifier's continuous online presence and potentially introducing risks of collusion.

To overcome these challenges, the zkPass protocol employs the VOLEitH technique, transforming the VOLE-ZK protocol into a non-interactive form. This ensures swift and efficient proof generation directly in the browser and device, addressing the limitations of both traditional SNARKs and VOLE-ZKs. By doing so, zkPass combines the efficiency of VOLE-ZK proofs with the convenience of non-interactivity, making it a practical and secure solution for authorizing TLS data.

MPC Mode

Under the MPC mode, we have implemented the protocol using a hybrid approach that combines ZKP and MPC technologies for 3P-TLS.

P and V work together as a single client to establish secure communication with S. They achieve this through a series of stages based on the elliptic curve Diffie-Hellman (ECDH) protocol, enhanced with MPC and OT techniques.

Three-Party Handshake

The first stage of the protocol is a three-party handshake between P, V, and S, where they work together to generate the pre-master key. P and V each receive a share of this key using Oblivious Linear Evaluation (OLE) based Multiplicative-to-Additive (MtA) or Additive-to-Multiplicative (AtM) schemes, which support additive homomorphism. The pre-master key is divided, with P and V each getting one half, while S retains the full key.

To ensure authenticity and prevent the client from impersonating fake websites, after the client and server exchange greetings, the server provides its certificate. During the key exchange phase, the server also signs the public key with its private key from the certificate. This allows V, within the client, to verify the certificate and signature, confirming the server's identity and establishing trust in the data source.

The second stage of the protocol is key derivation, where P and V work together using Garbled Circuit (GC) to generate two session keys from the pre-master key: the encryption key (enc_key) for data protection and the message authentication code key (mac_key) for data integrity. Notably, V only holds a share of the mac_key and has no access to the enc_key, ensuring that V cannot view P’s private information. P also holds a share of the mac_key, giving access to identity-related data but without the ability to tamper with it. Any tampering can be detected by verifying the authenticity of messages using the mac_key.

The MPC algorithm in zkPass has been significantly optimized in several areas, including communication time, hash functions for the Garbler and Evaluator, OT operations, and memory copying. These improvements have increased efficiency by more than threefold. A new AES128 proof method has also been introduced, reducing the number of blocks by 300 times and speeding up Garbler/Evaluator execution by tenfold. zkPass uses Silent OT, minimizing offline network communication during OT generation. For GC, zkPass implements Three Halves Make a Whole and Stacked GC, which reduces the size of the Garbled Tables, leading to less communication and faster execution. Overall, these optimizations have greatly reduced the runtime of the entire MPC process, making zkPass much more efficient.

ZKP

In the final stage of the zkPass protocol, the client creates a ZKP for public verification. After the 3P-TLS phase, the prover obtains the complete data and uses the VOLEitH process to generate a proof. Since this step is similar to the process used in proxy mode, we won’t go into the details here.

Why Not Prioritize MPC Mode

The performance overhead of MPC mode is significant, mainly due to the truth table(TT) in GC. Every block of application data must be encrypted using a TT, which greatly increases both computational and bandwidth requirements. For a single TLS session, there's a fixed cost of 20MB, plus 8MB per 1KB of outgoing data and 32KB per 1KB of incoming data. For a typical 1KB request and 100KB response, the prover would need to upload around 32MB, making this approach impractical for regular use.

Additionally, MPC mode isn't necessarily more secure than proxy mode because it still relies on a "trusted notary", similar to a proxy. A malicious notary could cache session data and collude with a compromised client. Since the server's decrypted key is hidden for privacy, external verification is impossible, meaning collusion or manipulation could go unnoticed. While MPC mode reduces some trust assumptions, it doesn't fully eliminate them, so it isn't inherently more secure.

Given these issues, while MPC mode provides some cryptographic advantages and may be useful for small requests, its high performance overhead and limited security benefits make it no better than a well-designed and decentralized proxy. Its resource demands and impracticality for everyday use restrict its real-world application. Therefore, we only reserve this mode as a backup for TLS servers that block requests from the same account when coming from different IP addresses.

Summary

The zkPass protocol stands out for its technical prowess in combining advanced cryptographic techniques to achieve secure, efficient, and privacy-preserving data sharing. By innovatively extending TLS into a three-party protocol and integrating VOLEitH for NIZK proofs, zkPass addresses both security and performance challenges.

Its ability to operate in two modes—Proxy and MPC—provides flexibility to adapt to various network conditions and server policies without compromising efficiency or security. The protocol's optimizations in cryptographic computations and communication flow result in a faster, more efficient system that is practical for real-world applications.