Found a pretty interesting blog on some cryptographic voting scheme(s?) that I've never heard of, here's one of the posts, on a detail of El Gamal implementation:

the mathematics here will be familiar to followers of libsecp256k1 and the BIP340/Schnorr stuff specifically.

The blog has a bunch of other stuff, e.g. high level discussion of mixnets. Quite interesting.

I appreciate the author actually explaining in detail here, something that is ... (1/n)

... pretty unobvious. Apart from just reading it, here's a concrete toy example: Imagine p=11 (so the "ring of integers" here is basically integers mod 11 with addition and multiplication defined), so q=5.

Now some numbers mod 11 are "quadratic residues" (means: squares) and some are not.
It's pretty obvious that ~ 1/2 are squares, because mod p, (p-x)^2 = p^2 -2px +x^2 = x^2 mod p. But that doesn't tell you *which* half are squares.


Show thread

As the author observes, the ones that *are* squares form a multiplicative group of order 5 (i.e. p-1/2), and that is exactly the group he needs to satisfy the properties of El Gamal's encryption scheme. He knows he has q numbers to work with, but it is *not* 0 ... q-1 (so 0..4 in our toy example), it is the q numbers in that group, so he has to map from Zq to Gq, as he puts it.

It turns out the Legendre symbol gives him exactly what he needs to do that.

· · Web · 0 · 0 · 0
Sign in to participate in the conversation
unidentified instance

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!