HyperLogLog Over RSA

A test/demo implementation of the HyperLogLog Over RSA protocol — a scheme for estimating the number of unique clients of a service without anyone, even someone with full access to the server logs, being able to identify or track individual clients.

📖 Documentation & writeup: https://karpinski.org/HyperLogLogOverRSA.jl/

That site is both the API documentation for this package and a full writeup of the protocol's motivation, design, and security arguments.

Here's a simple usage example:

julia> using HyperLogLogOverRSA

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

julia> cert = RingCert(ring) # generate certificate for ring
RingCert(B=4095, m=63, N=177070914387586352571192492189228052973580086445179045350132910675786234155925872091577641648330330437861987397104402807681707495004594872268782117890446979140863743782136343951674320625741536775879752775267456050832167730716939814749665659197987858339060047822080997153811827719554780573453247826807357487367)

julia> client = Client(cert) # check certificate, choose random x₀ value
Client(B=4095, m=63, N=177070914387586352571192492189228052973580086445179045350132910675786234155925872091577641648330330437861987397104402807681707495004594872268782117890446979140863743782136343951674320625741536775879752775267456050832167730716939814749665659197987858339060047822080997153811827719554780573453247826807357487367, x₀=102926587575858634076955879762046593209733369344464341180977773617051201246441559960571372040732398110059881222935051623679630290429991506134455683625144840388086206444582775975412246895968572021630376902999939715044968508757462247083994561511554584485402199422253346842287014113650454237624791501100299972344)

julia> y = hll_generate(client) # default resource class
93188929929029172725318787400658996454684486841201122742244990138031312913531410188686086811139706724713055874033272227426401246988942082156100613926814811959051821444017570245994985309003024055580922447669995871417317202566829833032510778692035285836562972123701757345960386355007306320221224618614625144844

julia> hll_decode(ring, y) # client's HLL value for default resource class
(1342, 0)

julia> y = hll_generate(client) # different y value
30240258907265037788952047993225243753399482430815828306735550180653798133538348895013770613072465108525565950099518369452206453233420179950950107402015169276981312409920743675311220558890175085818398547019020129029708751838788155024937670248358341822998175790911079551141253862538044524323992839440704746947

julia> hll_decode(ring, y) # same HLL value
(1342, 0)

julia> y = hll_generate(client, "/package/123")
33234168361140526337734366522299202298867531956824551370756828587895115417296589986934861529271723592575453097395156270529921746022028705237540380880453222419914754175802212541022059026215155170258220430822369137428147080229545531363497522192862685452027976689531960052598258254251331298977825506052268341159

julia> hll_decode(ring, y) # different y value
(1902, 3)

julia> y = hll_generate(client, "/package/123") # client's HLL value for "/package/123" resource class
47010257057219370350504153912890835284105119037443631495351515836742704852489315171049356787059080373271601807804216858797273395439592695521182254222286352387550690649374526351467950722533962876657376639938733809584757397485231962399805212104257057124432944841515402201947126902237337648347992632122442388639

julia> hll_decode(ring, y) # same HLL value
(1902, 3)

Documentation

The site under docs/ is built with Documenter.jl and deployed to GitHub Pages. To build it locally:

julia --project=docs -e 'using Pkg; Pkg.develop(PackageSpec(path=pwd())); Pkg.instantiate()'
julia --project=docs docs/make.jl

The output lands in docs/build/; open docs/build/index.html (or serve the directory) to preview it.

Checking the math

Documenter renders math with KaTeX, which is stricter than the MathJax used by Obsidian/HackMD. docs/check-math.js renders every math block in the built docs through KaTeX and reports anything that fails to parse (unbraced multi-letter subscripts, wrong alignat column counts, stray non-breaking spaces, unsupported macros, …) before it ships as raw, unrendered LaTeX:

julia --project=docs docs/make.jl   # build first
node docs/check-math.js             # then validate

It needs KaTeX, found automatically from either npm install katex or the Debian/Ubuntu katex package (sudo apt install katex). Exits non-zero if any block fails, so it can also gate CI.