Zero-knowledge authentication to commercial VPN

Question

For VPNs which only connect to the greater internet (as opposed to a VPN for accessing a private network), it is only necessary for the server to know that the client is a paying customer. It doesn't need to know which customer.

How could such a system be made? One method is to use Chaum's digital cash method, but have the "cash" instead be a claim ticket for data transfer.

However, if you know of any other methods, please post them.

Answer 1

A modern approach might be to use blinded tokens like PrivacyPass based on a VOPRF. There are two parts to the protocol: an OPRF to negotiate blinded tokens with a payment that can later be redeemed for service, and DLEQ proof to verify that the tokens are unlinkable.

---

VOPRF, verifiable oblivious pseudorandom function family. This is a combination of a series of related concepts:

1. A PRF or pseudorandom function family is a family of functions $F_k$ that is hard to distinguish, if $k$ is chosen uniformly at random, from a uniform random function. In other words, for distinct $x$, $F_k(x)$ appears to be independent uniform random to anyone who doesn't know $k$.

   (PRFs are ubiquitous in cryptography. Typical examples: ChaCha, AES, HMAC-SHA256.)

2. An OPRF or oblivious PRF is a protocol by which a client and a server jointly compute a PRF using a key known only to the server and an input known only to the client, so that the client learns $F_k(x)$ but not $k$, and the server learns nothing.

   (OPRFs are used in protocols like the password-authenticated key agreement OPAQUE (paywall-free preprint).)

3. A VRF or verifiable PRF is a public-key cryptosystem for computing a PRF $F_k(x)$ giving a value $v$ together with a proof $\pi$ so that (a) without knowledge of the public key, $v$ is indistinguishable from uniform random (i.e., $F_k$ is a PRF to anyone who doesn't have the public key and $\pi$), but (b) with knowledge of the public key, a verifier can use $\pi$ to confirm that $v$ is the unique output of $F_k$ on $x$.

   (More on VRFs, and an application in DNSSEC.)

4. Finally, a VOPRF or verifiable OPRF is a protocol by which a client and a server jointly compute $v = F_k(x)$ and give the client a proof $\pi$. Then even the server—with knowledge of the public key, $k$, and $\pi$, but not $x$—can't distinguish $v$ from a uniform random string, but the client can verify with $\pi$ and the server's public key that $v$ is in fact the unique value of $F_k$ at $x$.

How does it work? Here's the OPRF used by PrivacyPass—ignoring the ‘verifiable’ part for the first approximation. Fix a group $G$ of prime order (written additively) with standard base point $X$, and fix hash functions $H_1\colon \{0,1\}^* \to G$ and $H_2\colon G \to \{0,1\}^n$. A public key is a group element $Y \in G$ and a private key is the secret scalar $k$ such that $Y = [k]X$. The PRF is $$t \mapsto H_2(t, [k]H_1(t)).$$ The client and server jointly compute it as follows:

PrivacyPass OPRF.

1. Client picks a secret bit string $t$.
2. Client picks a secret blinding scalar $r$ uniformly at random, and sends $P := [r]H_1(t)$ to the server (along with, say, a payment for purchase).
3. Server, given $P$, sends $Q := [k]P$ back to the client.
4. Client, given $Q$, reverses the blinding scalar $r$ to compute the group element $$[r^{-1}]Q = [r^{-1} k]P = [r^{-1} k r]H_1(t) = [k]H_1(t).$$
5. Client finally computes the bit string $z := H_2(t, [r^{-1}]Q) = H_2(t, [k]H_1(t))$.

(The client could alternatively do additive blinding: send $P := H_1(t) + [r]X$ to the server, and use $z := H_2(t, Q - [r]Y)$, like OPAQUE does. The two provide essentially equivalent security. Multiplicative blinding requires computing scalar inverses, which may be a little expensive. Additive blinding requires, well, computing addition, so it can't be used with, e.g., $x$-restricted scalar multiplication only like X25519—although X25519 can't be used directly anyway because it's not a prime-order group, and we'll want addition later on for the DLEQ proof of anonymity.)

---

How do we use an OPRF in a purchase and redemption protocol?

Purchase. The user picks a secret $t$ and sends a blinded token request $P$ for it together with a payment in order to purchase service, and the server—on confirmation of payment—returns a blinded token $Q$, computed with its private key $k$. The user then unblinds $Q$ and combines it with $t$ to obtain a token $(t, z)$.

Redemption. The user then redeems a token $(t, z)$ to authenticate a request for service $m$ by sending $(t, \operatorname{MAC}_z(m))$ as an authenticator for $m$. The server recomputes $z = H_2(t, [k]H_1(t))$ using the private key $k$ to verify the authenticator, and keeps a database of spent tokens $t$ to prevent replays; the server can also periodically—say, weekly, or monthly—rotate the public key so that the spent token database doesn't accumulate indefinitely. If the token is unspent and the authenticator matches, the server provides the service.

This protocol guarantees that the client is unable to forge tokens, no matter how many tokens they've already acquired from the server, and guarantees—if the server follows the protocol and uses a single key for every client—that the tokens submitted by each client are indistinguishable from one another to the server.

But wait! How do we know that the server doesn't use a different key for every client, enabling the server to track clients from purchase to redemption? We need a way for the server to prove to the client that the tokens are made with the same private key $k$ each time. This is where the verifiable part of the VOPRF comes in, using a zero-knowledge proof of discrete log equality.

---

DLEQ proof, a receipt for a non-interactive zero-knowledge proof of discrete log equality. A DLEQ proof is a proof that two group elements $Y, Q \in G$ have the same discrete log with respect to two bases $X, P \in G$: $\log_X Y = \log_P Q$. In other words, that $Y = [k]X$ and $Q = [k]P$ for the same $k$.

We start with an interactive zero-knowledge proof by a $\Sigma$-protocol due to Chaum and Pedersen between a prover and a verifier who share $(X, Y, P, Q)$ a priori:

Chaum–Pedersen interactive zero-knowledge proof of discrete log equality.

1. Prover picks a uniform random per-session secret $u$, and commits to it by announcing $A := [u]X$ and $B := [u]P$.
2. Verifier picks a uniform random scalar $c$ to challenge the prover.
3. Prover answers the challenge by returning $s := (u - c k) \bmod \ell$, where $\ell$ is the order of the group $G$.

Verifier accepts if $A \stackrel?= [s]X + [c]Y$ and $B \stackrel?= [s]P + [c]Q$.

Using a hash function $H_3$, with the Fiat–Shamir heuristic we can turn this into a non-interactive zero-knowledge proof system that gives a verifiable receipt, much like the Schnorr signature scheme is derived from the Schnorr identification protocol:

Chaum–Pedersen non-interactive zero-knowledge proof of discrete log equality.

1. Prover picks a uniform random $u$ and computes $A := [u]X$ and $B := [u]P$.
2. Prover computes challenge $c := H_3(X, Y, P, Q, A, B).$
3. Prover computes $s := (u - c k) \bmod \ell$ and returns $(c, s)$ as receipt.

Verifier accepts if $c \stackrel?= H_3(X, Y, P, Q, A', B')$ where $A' := [s]X + [c]Y$ and $B' := [s]P + [c]Q)$.

We can even efficiently extend a short receipt $(c, s)$ to work on a batch of discrete log pairs $\{(P_i, Q_i)\}_i$ by hashing $(X, Y, \{(P_i, Q_i)\}_i)$ into a sequence of challenges $\{c_i\}_i$, deriving $P' := \sum_i [c_i]P_i$ and $Q' := \sum_i [c_i]Q_i$, and then doing the one-point DLEQ proof on $(X, Y, P', Q')$.

Batch DLEQ proofs are important if you want to allow a single payment to purchase many unlinkable instances of service at once—like exchanging one robot overlord training session for the high privilege of just reading the f‍ucking newspaper without having to do another robot overlord training session for every newspaper you want to read, as is the dominant application of PrivacyPass with the global active adversary Cloudflare: to reduce $n$ captchas down to one captcha.

---

Armed with a DLEQ proof technique by which to turn an OPRF into a VOPRF, the server can now commit to a public key $Y$ relative to the standard base point $X$ in some very public verifiable space (e.g., a well-known URL like https://www.example.com/tokenkey that the user fetches through Tor), and prove to the user that the tokens are unlinkable with a minor variant of the purchase protocol:

Purchase with proof of anonymity. The user picks a secret $t$ and sends a blinded token request $P$ for it together with a payment in order to purchase service, and the server—on confirmation of payment—returns a blinded token $Q$, computed with its private key $k$, together with a DLEQ proof that $\log_X Y = \log_P = Q$. The user then unblinds $Q$ and combines it with $t$ to obtain a token $(t, z)$.

Before redeeming the token, the user verifies the DLEQ proof; if it fails, the user tells all their friends that the server is a lying sack of gastrointestinal distress and loudly demands to speak to the manager of the cryptocurrency scam by which they bought their tokens.

---

_{By the way, you could also just use Tor.}