Elliptic Curve Cryptography Explained
It&#x27;s great that people enjoy this-- but I&#x27;ve never seen explanations that centered on the group law as actually being especially useful for building insight producing understandings complex cryptosystems.<p>I think it&#x27;s a lot more useful to start from a generic group: e.g. you have some group G generated by g, and a group operator ... plus a way to (de)serialize members, a method to identify the additive identity, maybe a hash function and not much else.<p>From that point you can build a pretty solid understanding of real cryptosystems.<p>Knowledge of how to implement a particular group law is necessary to build one from scratch-- which people should almost never be doing, esp as it requires a serious amount of number theory to do well-- but it doesn&#x27;t give any real insight into the cryptography, not even any intuition as to why the DL problem in some groups is believed to be hard.<p>I think that understanding ECC starting at group law is kind of like understanding quick sort by studying CMOS logic: you can&#x27;t implement quicksort in practice without (someone) building some digital logic, but if you&#x27;re down in the trees it&#x27;s not particularly easy to see the forest.<p>When I&#x27;ve trained people on the subject I&#x27;ve enjoyed using a sequence that goes like:<p>1. Generic group, how we can construct efficient &#x27;multiplication&#x27; from only addition  (I prefer to call the group operator addition, but I talk about both notations and how both are equally valid). General intuition about how algebra essentially JustWorks(tm) in finite fields.<p>2. CDH and Diffe-hellman, the fact that the hardness of the DL problem (in particular groups) is a strong assumption.<p>3. Constructing a pedersen commitment using the additive homomorphism &#x27;in the exponent&#x27;, establishing the security assumption in pedersen commitments that the two generators have an unknown DL between them.<p>4. Constructing a chameleon hash function-- a trap-door hash function where someone knowing a secret can freely construct collisions at will-- by violating the pedersen security assumption.<p>5. Constructing a schnorr digital signature by feeding the output of a chameleon hash back into itself, creating an impossible causal loop that can only be resolved using the trapdoor.<p>6. Extending the causal loop: creating an OR proof (A signature that shows I know at least one of two secrets).<p>[FWIW, we cover 4,5,6 in this paper <a href="https:&#x2F;&#x2F;pdfs.semanticscholar.org&#x2F;4160&#x2F;470c7f6cf05ffc81a98e8fd67fb0c84836ea.pdf" rel="nofollow">https:&#x2F;&#x2F;pdfs.semanticscholar.org&#x2F;4160&#x2F;470c7f6cf05ffc81a98e8f...</a> for the purpose of describing a more efficient than typical OR proof.]<p>7. From there extending into other more elaborate protocols like range proofs (built from OR proofs of related secrets), private set-intersection (built from polynomial evaluation in-the-exponent), etc.<p>8. And critically, interesting attacks on these systems, with a particular focus on how fragile they can be:<p>8a. Linearly related nonce attacks against signatures. (unfortunately, these attacks are easier taught if the signature algorithm is understood as a hidden linear system, then the attack is just a &#x27;as many knows as unknowns attack&#x27;, but I strongly prefer the causal loop understanding of signatures for the intuition it creates for more complex protocols).<p>8b. Random-modular-subset sum attacks on naive blind signatures and naive multi-signature.<p>8c. At least one attack that break the generic group abstraction. I&#x27;m fond of invalid key attacks on DH with twist-insecure curves. (This is probably the only example that I think is important to teach that requires some group law understanding).<p>If I do get into group law, I think it&#x27;s interesting to talk about optimizations.  Particularly, projective coordinates, precomputation, addition&#x2F;subtraction ladders and signed digit representations, doubling sharing for multi-exp.<p>Bos-coster for sum-of-many products is an especially fun and easy algorithm to implement (similar kind of fun as implementing the peeling algorithm for decoding sparse linear codes in F(2)).<p>I&#x27;d like to have a 9 on that list that goes into the building blocks of proof techniques for these systems e.g. programmable oracles&#x2F;forking lemma... but that is enough out of my area of expertise that I don&#x27;t know how to teach it effectively.