⚡ electrical engineering

Deterministic Johnson--Lindenstrauss Projections from Pisot $\beta$ -Transformations for Zero-Knowledge Private Routing

This paper introduces a deterministic, zero-knowledge-friendly Johnson–Lindenstrauss projection derived from Pisot $\beta$ -transformations that eliminates the need for costly in-circuit randomness by using a single public seed to achieve dimension-free variance and exact finite-field reproducibility while preserving pairwise distances.

Original authors: I. Dey, I. Cherkaoui

Published 2026-08-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: I. Dey, I. Cherkaoui

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where your digital life is a series of secret handshakes. You want to prove to a bouncer that you belong to a VIP club without showing your ID, or prove to a bank that you have enough money without revealing your balance. This is the magic of "Zero-Knowledge Proofs" (ZK): a way to say "I know the secret" without ever whispering the secret itself. But here's the catch: to prove you belong to the right group, your digital identity is often a massive, complex cloud of numbers (a high-dimensional vector). Checking if this cloud matches the VIP list is like trying to find a specific grain of sand in a mountain; it takes so much computer power and time that it slows everything down.

To fix this, scientists use a trick called the "Johnson-Lindenstrauss" (JL) projection. Think of it as a magical photocopier that squashes a giant, 3D sculpture down into a flat, 2D shadow. Amazingly, if you squish it just right, the distances between the points in the shadow stay exactly the same as they were in the original sculpture. This makes the "bouncer's" job easy and fast. However, there's a snag: the standard way to make this squishing machine involves rolling a digital die. The machine is random, so to prove you didn't deviate from the protocol, you have to prove you rolled the die correctly. This proof is so heavy it cancels out all the speed you gained by squishing the data. We need a squishing machine that is fixed, public, and doesn't need a die roll to prove it's fair.

This paper introduces a new way to build that machine using a special kind of math called "Pisot β-transformations." The authors, I. Dey and I. Cherkaoui, have constructed a deterministic (non-random) projection that works just as well as the random ones but is perfectly reproducible by anyone, anywhere, without needing to prove a random seed.

The Problem: The "Random" Bottleneck

In the world of private routing—where an AI agent decides which expert model should handle a private message—the message is turned into a long list of numbers. To keep things private, the agent proves the message belongs to a "safe" category by comparing it to a list of known "centroids" (average examples of safe messages). This comparison is expensive.

The usual fix is to shrink the list of numbers using a random matrix (the JL projection). But because the matrix is random, the computer has to commit to it and prove it was generated fairly. This proof is so costly that it defeats the purpose of shrinking the data in the first place. The authors argue that we need a matrix that is public, fixed, and identical for everyone, so no proof of randomness is needed.

The Solution: The "Stretch-and-Fold" Machine

The authors propose building this fixed matrix using a chaotic map called a Pisot β-transformation.

The Analogy: Imagine a piece of dough. You stretch it out (multiply by a number $\beta$ ) and then fold it back onto itself (take the remainder). This is a "chaotic" process; if you start with two almost identical dots of dough, they will quickly end up in completely different places. This chaos is usually great for scrambling data, but it's terrible for computers that need to agree on the result.
The Problem with Normal Chaos: If two computers try to simulate this stretching and folding, tiny differences in their math (like rounding errors) will cause them to diverge quickly. One computer might think the dough is at position A, while the other thinks it's at position B. They can't agree on the matrix.
The Pisot Magic: The authors use a special type of number called a Pisot number (like the Golden Ratio, 1.618, or the Plastic Number, 1.325). These numbers have a special algebraic property: even though the process is chaotic, the "orbit" (the path the dough takes) can be calculated exactly using a finite set of rules.
- The Result: Two computers can run the exact same "stretch-and-fold" simulation and get the exact same result, bit-for-bit, without any rounding errors. It's like having a recipe that works perfectly whether you use a wooden spoon or a metal one, as long as you follow the steps.

What They Found

The team proved that this deterministic matrix works just as well as the random ones, but with a few key advantages:

It Preserves Distances: They mathematically proved that the "squished" data keeps the distances between points almost exactly the same as the original. The error (bias) is tiny and doesn't get worse even if the data gets huge.
It's Fast and Cheap: Because the matrix is fixed and public, the computer doesn't need to spend time proving it was generated fairly. It just uses the pre-agreed recipe.
It's Reproducible: They showed that while a generic chaotic map (like the famous "logistic map") would require an impossible amount of memory to calculate exactly (growing exponentially), the Pisot map only requires a tiny, fixed amount of memory (growing linearly).
- The Test: In their simulations, they compared their Pisot method against six other standard methods, including random Gaussian matrices and other chaotic maps.
- The Outcome: The Pisot method matched the statistical quality of the random matrices perfectly. The "noise" in the measurement was the same, and the ability to route messages correctly was identical. In fact, they found that a single public "seed" (the starting point of the dough) could preserve the distances for all pairs of centroids in a large list.

The Catch (and the Future)

The authors are very clear about what they have and haven't done.

What is Proven: They have mathematically proven that the bias is small and that the variance (noise) behaves well. They have proven that a good seed exists and can be found by searching.
What is Measured: They ran simulations showing that the method works as well as the random ones in practice, with no loss in accuracy.
What is Still Open: They admit that while they believe the method is even better than their current proof suggests (requiring less memory for large lists), they haven't fully proven the "concentration inequality" that would guarantee this for any possible input, only for the specific set of centroids they are protecting.

Why This Matters

This isn't just a math puzzle; it's a key to making private AI practical. Currently, if you want to route a private medical case to a specialist or verify a payment without revealing the details, the "proof" takes minutes and gigabytes of data. With this new deterministic projection, the authors suggest we could cut that time down to seconds and the data size to kilobytes, all while keeping the privacy guarantees rock-solid.

They didn't just find a new number; they found a way to make the "magic" of zero-knowledge proofs run on a fixed, public track that anyone can verify, removing the need for expensive, random "dice rolls" that slow everything down. It's a step toward a future where your digital privacy doesn't come at the cost of your patience.

Technical Summary: Deterministic Johnson–Lindenstrauss Projections from Pisot $\beta$ -Transformations for Zero-Knowledge Private Routing

1. Problem Statement

In Zero-Knowledge (ZK) proof systems for private routing, a prover must certify that a message embedding $v \in \mathbb{R}^d$ belongs to an allowed semantic class defined by a set of public centroids $C = \{c_1, \dots, c_N\}$ . This is typically done via a nearest-centroid test, which requires $O(Nd)$ arithmetic constraints. Given modern embedding dimensions ( $d \in [768, 4096]$ ), this constraint count dominates the proof size and prover time.

The standard remedy is a Johnson–Lindenstrauss (JL) projection to reduce dimension to $m \ll d$ . However, classical JL matrices are random. In a ZK context, using a random matrix forces the circuit to commit to the matrix and prove its correct sampling, reintroducing the very computational cost the projection was meant to eliminate. Furthermore, random matrices require proving the sampling process, creating a leakage risk. The challenge is to construct a public, deterministic, and fixed projection matrix that:

Preserves pairwise distances provably.
Is native to the circuit's finite field.
Requires no in-circuit randomness or sampling proofs.

2. Methodology

The authors propose constructing the projection matrix $A$ from the standardized orbit of a Pisot $\beta$ -transformation.

The Map: A $\beta$ -transformation $T_\beta x = \beta x - \lfloor \beta x \rfloor$ on the unit interval, where $\beta > 1$ is a Pisot number (an algebraic integer whose Galois conjugates lie strictly inside the unit disk, e.g., the golden ratio).
Dynamics: The map is a deterministic "stretch-and-fold" chaotic system with a unique invariant Parry measure $\mu$ . Crucially, because $\beta$ is Pisot, the transfer operator of the map possesses a spectral gap, causing correlations between observables to decay geometrically ( $|r_k| \le C\theta^k$ ).
Matrix Construction:
- A public seed $x_0$ is selected.
- A sampling gap $g$ is fixed to ensure samples are taken beyond the correlation time.
- The matrix entries $A_{ij}$ are filled sequentially with the normalized orbit values $z_p = \psi(T_\beta^{pg} x_0)$ .
- The projection is $\Phi(v) = Av/\sqrt{m}$ .
Finite Field Reproducibility: Unlike generic chaotic maps, the Pisot property ensures that the orbit is exactly reproducible in a fixed finite field. The cost of generating $k$ steps is linear in $k$ (specifically $O(k \log_2 \beta)$ bits), whereas generic chaotic maps (like the logistic map) require exponential bit growth ( $O(2^k)$ ) to maintain exact arithmetic.

3. Key Contributions

The paper presents four main theoretical and practical contributions:

Dimension-Free Bias and Variance Bounds:
- Bias: The authors prove that the bias of the squared-norm estimator is bounded by a term decaying geometrically with the sampling gap $g$ , independent of the ambient dimension $d$ (Lemma 1). This is derived from the spectral gap of the $\beta$ -map, offering a stronger guarantee than standard equidistribution arguments.
- Variance: They show the variance of the estimator scales as $V_0/m$ . Crucially, under a stated concentration hypothesis, the constant $V_0$ is dimension-free (does not grow with $d^2$ ), unlike crude bounds that suggest $O(d^2)$ . This implies a fixed projection dimension $m$ suffices regardless of how large $d$ becomes.
Existence of a Single Public Seed:
- Theorem 1 proves that a single public seed $x_0$ exists which preserves all $\binom{N}{2}$ pairwise centroid distances within $(1 \pm \varepsilon)$ .
- This seed can be found via an efficient offline search. Once found, the matrix is fixed, public, and requires no randomness commitment during the ZK proof.
Exact Reproducibility via Pisot Property:
- The paper identifies that the Pisot property (not just generic chaos) is essential for ZK deployment. It guarantees that the orbit can be reproduced exactly in a fixed finite field with linear computational cost per step. Generic chaotic maps fail here due to the exponential growth of required precision (denominators) to avoid floating-point divergence.
Robustness and Search:
- A closed-form certifiable robustness radius is provided (Proposition 1), defining the maximum perturbation a query can sustain without changing its nearest projected centroid.
- The search for the seed is unconditional (guaranteed by variance bounds) but can be improved to a logarithmic dependence on $N$ if a specific concentration inequality for the spectral-gap map holds.

4. Experimental Results

The construction was evaluated against six standard projections: Gaussian, Rademacher, Achlioptas sparse, Subsampled Randomized Hadamard Transform (SRHT), and a chaotic-sequence matrix (Yu et al.).

Statistical Quality: The Pisot projection matches the statistical quality of random projections.
- Variance Rate: The estimator variance follows the $1/m$ law and overlaps with the $2/m$ reference of Gaussian JL.
- Dimension Independence: The variance constant $V_0$ remains flat near 2 as $d$ increases from 64 to 1024, confirming the dimension-free theoretical prediction.
- Distortion: The worst-case relative distortion over all centroid pairs tracks the Gaussian JL baseline.
Task Performance: In a 24-class nearest-centroid routing task with $d=256$ , the Pisot projection recovered 100% accuracy at $m=32$ (an 8x compression), identical to other methods.
Reproducibility: Simulations confirmed that floating-point implementations diverge from exact orbits after $\approx 50-70$ steps (matching Lyapunov predictions), whereas the Pisot $\beta$ -adic representation remains exact and compact (139 bits for 200 steps vs. $1.66 \times 10^6$ bits for a logistic map).

5. Significance and Claims

The paper claims that this construction is the only method that simultaneously satisfies three critical requirements for ZK private routing:

Free of in-circuit randomness: No need to commit to or prove the sampling of a random matrix.
Exactly reproducible in a fixed finite field: Achieved via the Pisot property at a per-step cost of $\log_2 \beta$ , avoiding the $O(2^k)$ cost of generic chaotic maps.
Statistically equivalent to random projections: Matches the variance rate and distortion properties of standard JL matrices.

The authors note that while the statistical quality is proven, the theoretical step of upgrading the unconditional $O(N^2)$ seed search bound to a conditional $O(\log N)$ bound relies on a specific concentration inequality for the transfer operator, which remains an open theoretical step. Practically, the method enables a shift from minutes/gigabytes of proof generation to seconds, making verifiable private routing feasible for high-dimensional embeddings.