GitHub

Reference Implementation

The HyperLogLogOverRSA.jl package is a test/demo implementation of the full protocol described in the writeup. It exists to make the design concrete and checkable — not to be a hardened production library.

Installation

pkg> add https://github.com/StefanKarpinski/HyperLogLogOverRSA.jl

Usage

julia> using HyperLogLogOverRSA

julia> ring = Ring(2^12-1, 63, 1024)   # generate a HyperLogLog RSA ring
Ring(B=4095, m=63, N=…)

julia> cert = RingCert(ring)           # certificate that the ring is fingerprint-free
RingCert(B=4095, m=63, N=…)

julia> client = Client(cert)           # check the certificate, pick a random secret x₀
Client(B=4095, m=63, N=…, x₀=…)

julia> y = hll_generate(client)        # encrypted HLL token, default resource class
…

julia> hll_decode(ring, y)             # ring holder decodes the (bucket, geometric) value
(1342, 0)

julia> y = hll_generate(client)        # a fresh, unlinkable token for the same client/class
…

julia> hll_decode(ring, y)             # …decodes to the same HLL value
(1342, 0)

julia> y = hll_generate(client, "/package/123")   # an independent value per resource class
…

julia> hll_decode(ring, y)
(1902, 3)

The server should log the y values and only decode them later, offline — the factorization of N never needs to live on the public-facing servers. See the Protocol Summary for the end-to-end flow.

hll_estimate decodes a batch of logged tokens for one resource class and estimates the number of unique clients behind them (Ertl’s improved HyperLogLog estimator). Repeated tokens from the same client collapse, since they all decode to that client’s single value for the class:

julia> ys = [hll_generate(client, "/registries") for _ in 1:1000];  # 1 client, many requests

julia> hll_estimate(ring, ys)                                       # ≈ 1 unique client
1.0...

(One client estimates to ≈ 1 no matter how many requests it sends; a real estimate aggregates tokens from many distinct clients.)

API

HyperLogLogOverRSA.Ring — Type
Ring(B, m, L; rng=…) -> Ring

A HyperLogLog RSA ring: a modulus N together with the secret structure that lets its holder decode HyperLogLog values while no one else can.

The ring has the form

N = P Q = (2 B p + 1)(2^m q + 1)

so that, multiplicatively,

ℤ_N^* ≅ C_2 × C_B × C_(2^m) × C_(p q)

where B (which must be odd) is the number of HyperLogLog buckets and m is the maximum geometric sample value; L is the target bit-length of N.

The primes P, Q, p, q are secret — and are deliberately omitted when a Ring is shown — so only a holder of the Ring can decode HLL values via hll_decode. Publish a RingCert so that clients can use the ring without learning its factorization.

rng (any AbstractRNG, default a RandomDevice) is the source of randomness for choosing the primes; pass a seeded RNG for a reproducible ring.

source
HyperLogLogOverRSA.RingCert — Type
RingCert(ring::Ring; rng=…) -> RingCert

A publishable certificate for a Ring: the public parameters B, m, N, a semigenerator g, and a list of square roots that together let anyone verify N is "fingerprint-free" — that it has the intended two-prime structure and so cannot be used to fingerprint clients — without revealing its factorization. A Client checks this certificate before trusting a ring.

rng (default a RandomDevice) is the source of randomness for picking the semigenerator g; the square roots are derived deterministically by hashing.

source
HyperLogLogOverRSA.Client — Type
Client(cert::RingCert; rng=…) -> Client

Verify a published RingCert and, if every check passes, construct a client holding the public ring parameters together with a freshly chosen random secret x₀ (a Jacobi "twist" element). Throws an ArgumentError if the certificate fails any check. rng (default a RandomDevice) is the source of randomness for x₀; pass a seeded RNG to get a reproducible client.

Call hll_generate to produce the encrypted HyperLogLog token to send with a request.

In this reference implementation the Client object is the client's persisted identity: each instance holds its own random x₀, so two instances are two distinct clients. Persisting a client across sessions would just mean serializing the object, which is out of scope here.

source
HyperLogLogOverRSA.hll_generate — Function
hll_generate(client::Client, class="/registries"; rng=…) -> Integer

Produce a fresh, randomized encrypted HyperLogLog token y = w xᵗ for the given resource class, to send along with a request. Every call re-randomizes the token, so two tokens from the same client are unlinkable; yet they all decode (by the ring holder) to that client's single, stable HLL value for the class. The client cannot itself decode or bias the value it samples.

rng (default a RandomDevice) supplies the per-token randomness. It does not affect the decoded value — only the token's unlinkable encoding — so seeding it makes token output reproducible without changing what the token decodes to.

source
HyperLogLogOverRSA.hll_decode — Function
hll_decode(ring::Ring, y; bmap=bucket_map(ring)) -> (bucket, geometric)

Decode an encrypted HyperLogLog token y to its (bucket, geometric) value, using the secret factorization carried by ring. Pass a precomputed bmap (from bucket_map) to amortize bucket decoding across many tokens.

source
HyperLogLogOverRSA.hll_estimate — Function
hll_estimate(ring::Ring, tokens) -> Float64

Estimate the number of unique clients behind a collection of encrypted HLL tokens — the y values logged for a single resource class. Each token is decoded with ring (sharing one bucket_map across the batch) and aggregated into a HyperLogLog sketch; repeated tokens from the same client collapse automatically, since they all decode to that client's single (bucket, geometric) value for the class.

Uses the improved estimator of Ertl (2017): unbiased across the whole cardinality range, with relative standard error ≈ 1.04/√B.

source