Explaning with ElGamal

Are there ways to explain the cryptography behind Grin with simpler terms? I’m led to believe there is because, when I first began to read about ElGamal cryptography, the texts were dense and hard to figure out what was going on, but once I read the implementation of it in code, all of that strange mathematical language became surprisingly simple to grasp. I can write the encryption, decryption, signature and verification in less than fifty lines of JavaScript! Here are the two brief equations that explains the cryptography of it. Given a generator “g” (which is about any integer greater than 1 and less than a prime number P), a secret “x” private key for the receiver of a message, some nonce “y” chosen by the sender of a message, we can send a secret number “a” in the range [1, p - 1] because these equations hold true (proof deferred, but you can obviously see it):

image
image

Why we can be confident that ElGamal Cryptography, given a prime of enough size (2048-bits), is secure? It’s because the receiver only publishes “g to the power of x” (which is the public key) for potential senders, keeping the secret “x” to oneself. it’s not feasible to calculate the private key, which is the exponent “x”, because this is the discrete logarithm problem. Can you easily solve the following equation? Try it and you’ll get the point of “asymmetric cryptography”.
image

I also noticed that, although there is “Elliptic Curve Cryptography” (ECC) and “ElGamal Cryptography”, they’re different implementations of the same thing: “Group Theory”. They’re both thought to be safe because of the “discrete logarithm problem”. Apparently, ECC is preferred because the non-prime number structure of the group prevents optimizations that would enable cryptanalysis (all groups in ElGamal Cyptography have a prime order), which is why the amount of points in an elliptic curve are counted and checked to not be prime. If my assumptions regarding the math of the whole of it do not fail me, the only difference is the key length: 256-bits of ECC versus 2048-bits of ElGamal.

So, is it possible to implement an almost-equivalent of Grin using ElGamal? This would greatly simplify the documents, as it would be possible to write code that explains what is going on. Even people that have concluded high school are likely to grasp ElGamal given “clock arithmetic”.

1 Like

Grin is based on a digital signature scheme (Schnorr), while you’re talking about an encryption scheme. Schnorr is similarly simple though. You sign message m with your private key x (with corresponding public key P = x*G) by taking a random secret nonce k, computing public nonce R = k* G, and publishing signature (R,s) with s = k + e * x, and e = hash(P | R | m). Anyone can verify the signature by checking that s*G = R + e * P.

That’s quite wrong. A prime order is preferred and the most used curve secp256k1 does in fact have prime order [1].

[1] order of group of points of secp256k1 - Bitcoin Stack Exchange

1 Like

That’s quite wrong. A prime order is preferred and the most used curve secp256k1 does in fact have prime order

Thanks for the input. I was hopelessly paranoid about four years ago and only fully comprehended the simple ElGamal cryptography and signature scheme. I rejected ECC (even though it provides shorter keys) because the sources explaining it couldn’t make a coherent message out of the noise. The source of disagreement comes from this other paper[1] , where it is claimed that “q” (amount of points in the curve) is preferred to be a power of two (obviously not a prime) for computational efficiency.

This other excerpt in the same paper even suggests a class of curves solely because it is easier to count how many points are there.

When I was hopelessly paranoid, I couldn’t take the security of ECC at face value. “Is it secure? Prove it to me!” - But all sources explaning it were all noise and I couldn’t find brief source code to read at. I couldn’t find something with the same simplicity and elegance as ElGamal. See? The sources do not agree with each other and I was unwilling to blindly trust the software.

[1] https://www.math.brown.edu/johsilve/Presentations/WyomingEllipticCurve.pdf

No; q is not the number of curve points (a.k.a. the curve order, usually called n), but the size of the field over which the curve is defined. Those are quite different things. In EC arithmetic, you take private keys/nonces modulo n, but you take curve point coordinates (i.e. field elements) modulo q.