I think the article's point is that the notion of "groups" per se is too coarse for DH, because it abstracts away the data structure you use to represent the elements of the group. However, the notion of Algebraic Groups doesn't have this weakness, because it comes with an implied data structure: The data structure is tuples over finite fields, and the group operations are expressible as polynomials, which importantly are also algorithms. Done.
It then turns out that if you search for the algebraic groups that you can use for DH, you end up looking for candidates within the 2 possible kinds of algebraic groups: linear algebraic groups and abelian varieties. Within the abelian varieties, it turns out that elliptic curves are both the simplest kind, while also being perfect for DH. Within the linear algebraic groups, the possible cyclic groups are just the additive and multiplicative ones: The additive ones are hopelessly insecure, while the multiplicative ones are just the unit groups of a field, which are special cases of elliptic curves anyway. So elliptic curves really are all you need for DH.
Just wondering — has anyone come across a course or resource that explores how cryptographic systems are built up from smaller building blocks?
Like, using something like SageMath for algebraic structures, a prover like Lean to verify properties — to get a feel for how things actually fit together.
There's something cool about trying to reimplement known standards just to understand them better (with the usual "don’t roll your own crypto" warning, of course). By the way, it would be nice to have a kind of sandbox for the more formal path to explore how to build my own SP-network, prove that the Decisional Diffie-Hellman assumption holds or something.
When I learned crypto 5-10 years ago, it turned out that a lot of "building blocks" are mostly hacks. Looking back from 2020s we see that some of the standards that we use for the last 20-30 years can in principle be thrown out of the window (they can't for compatibility reasons, though) and replaced with much cleaner and more universal replacements.
If we do not talk about modern exotic stuff (post-quantum crypto, zkSNARKS, homomorphic encryption), the 99% of everyday cryptography is based on two building blocks:
1. Symmetric crypto for ciphers and hash functions.
2. Algebraic group with "hard discrete log problem" for key exchange, signatures, asymmetric encryption and simple zero-knowledge proofs.
Historically, these two categories are filled with a zoo of protocols. E.g. AES is a block cipher, but SHA(1,2) is a hash function.
Today, you can roughly achieve everything of the above with two universal building blocks:
- Keccak for all of symmetric crypto: it is suited both for encryption, hashing, duplex transcripts for ZK protocols etc.
- Ristretto255 group based on Curve 25519: for diffie-hellman, signatures, key derivation, threshold schemes, encryption and more.
The problem is that none of the described features is implemented in a turnkey standard, and we are still stuck using older crypto. Heck, even Git is using SHA-1 still.
Then, after you have your building blocks, there are more hairy stuff such as application-specific protocols: TLS, Signal, PAKE/OPAQUE, proprietary hardware security schemes for full disk encryption and access controls etc.
>Keccak for all of symmetric crypto: it is suited both for encryption, hashing, duplex transcripts for ZK protocols etc.
Unfortunately, Keccak and sponge constructions in general are inherently sequential. Even with hardware acceleration it heavily restricts possible performance. For example, AES-CBC encryption is 4-8 times slower than AES-CTR on high-end CPUs with AES-NI available. VAES makes the difference even bigger. Algorithms like AES-GCM, ChaCha20, and BLAKE3 are designed specifically to allow parallelization.
I'm absolutely clueless about crypto, isn't there also a trade-off between being mathematically superior and well optimized in software/hardware implementation?
the types of arguments and proofs used in cryptography are notoriously difficult to mechanize, a little bit of lean isn’t going to go get anywhere close to stating a security property.
Just to add to the above for clarity a proof that key based encryption isn't reversible requires a proof of P!=NP which hasn't been done.
That may surprise people but we have no proof of the robustness of the encryption we use. In fact it might not work! Consider a one time pad for really extreme security needs. One time pads do have a proof (see the work of Shannon).
Not a cryptographer, but my expectation of the admitted-to-be-clickbait title would be to see a proof or some claim of that sort that characterizes traditional finite-field integer DH as a special case of ECDH. However, --and please correct me if I am wrong as I am not a cryptographer or a math wiz anymore-- my understanding is you could characterize both as instantiations of an abstract protocol on a cyclic group with some properties, so in that sense, they are siblings derived from a more general idea, not derivable from each other.
While not completely explained in the article, the author correctly notes that the non-singular points on a singular cubic curve over a finite field form a group (under the same elliptic curve group law) that is isomorphic (in an easily computable way) to either the multiplicative or additive group of a finite field.
One could nitpick by pointing out that singular cubics are not elliptic curves (which are, by definition, smooth projective curves). One could also nitpick that the real reason you don't want to use DH in the multiplicative group of a finite field is that there is a known subexponential time algorithm that breaks DH in that setting (forcing > 3000-bit key sizes) whereas for elliptic curves the only known attacks take exponential time (and 256-bit keys are fine). But I don't think either of these nitpicks contradicts the author's thesis.
While not mentioned by the author, there is an alternate reason why finite field DH can be seen as a special case of ECDH, kind of: namely, there exists special elliptic curves (actual, smooth projective curves) that do have an efficiently computable endomorphism to a suitable form of the multiplicative group, via pairings. This is in essence the MOV attack against the XTR cryptosystem. That doesn't fit neatly in OP's framework, though, because the map isn't a morphism of algebraic groups (it is efficient for other reasons), and it is cheating a little bit, because the inverse map isn't efficiently computable.
Another point that the author glosses over a bit is that higher dimensional abelian varieties offer other instances of DH that are genuinely different from ECDH, and that are occasionally useful (mostly the case of Jacobians of hyperelliptic curves of genus 2). There isn't really a trick to make an arbitrary hyperelliptic curve DH/abelian variety DH instance a special case of ECDH: if anything, the relationship would be in the reverse direction.
As I see it, the article describes something in that vein, but then immediately flips and reasserts the title, which suggests integer DH is a special case of ECDH, which does not seem a convincing characterization to me (it could be my misunderstanding; maybe someone could further clarify if it is conclusive).
The logical click bait on this one. I could not resist thinking it’s like saying there is no circle other than a round circle, but I had no idea if it’s equivalent and fair comment given my limited cryptography knowledge (as in non existent). So I had to read it, and while I got little, by osmosis, I feel falling for the bait was worth it.
For historical context, TLS only really started to use the eliptic curve version of diffie-helman in the mid 2010s. Prior to that, plain diffie helman was more popular. (E.g. here is a thread from a decade ago complaining about lack of support https://security.stackexchange.com/questions/59459/how-widel... ).
ECC also used to have patents which restricted adoption back in the day.
There also used to be a lot of conspiracy theories that NSA backdoored nist curved ( e.g. https://m.slashdot.org/story/191445 ). Probably fud, but it slowed down adoption of eliptic curves.
I believe the patent issue was by far the dominant friction for adoption in 2000s. On the NIST curve problem, well, maybe FUD, but evidently, they indeed backdoored the elliptic curve-based random number generator, so I would say some distrust is warranted.
Irrespective of the curve issue, ed25519/x25519 is superior and has other nice properties like not catastrophically breaking if you can't generate a unique random "k" for ECDSA as PlayStation discovered the hard way[1].
>> Probably fud, but it slowed down adoption of eliptic curves.
Not FUD at all. NIST revoked their recommendation to use those curves because of it. The facts are that a "backdoor" exists whether anyone knows what it is or not, and NSA could not explain how those particular numbers were chosen so out of caution we must assume they know the backdoor and not use those curves.
The author seems to be a busy person, but I would appreciate it if they would consider modifying their blog publishing software so that the math and definitions could be rendered in text and KaTeX instead of raster images.
Better typography helps with reading. The same reason someone would complain if this was typed in Comic Sans. Also the images don't scale well, so if you look at this with a high resolution display, either the images are too small or not sharp.
I find it very hard to follow the overall reasoning, in particular due to the inconsistency around whether one should only consider algebraic structures up to isomorphism or not.
For any n, there is only one finite cylic group of size n, up to isomorphism (namely Z/nZ). As the author mentions, there are concrete choices of finite cyclic groups (like Z/nZ) that make Diffie-Hellman insecure. Consequently, the security comes entirely from the choice of the _representation_ of the group elements (since the algebraic structure is the same, i.e., it is just a relabeled Z/nZ).
In a similar spirit, people sometimes argue that Diffie-Hellman in some group G must be equally secure as in another group H, because the groups are isomorphic. This is unsound. In order to make such an argument sound, one needs to prove (or at least mention in case it is trivial) that one can _efficiently_ compute the isomorphism and its inverse.
Readit News
It then turns out that if you search for the algebraic groups that you can use for DH, you end up looking for candidates within the 2 possible kinds of algebraic groups: linear algebraic groups and abelian varieties. Within the abelian varieties, it turns out that elliptic curves are both the simplest kind, while also being perfect for DH. Within the linear algebraic groups, the possible cyclic groups are just the additive and multiplicative ones: The additive ones are hopelessly insecure, while the multiplicative ones are just the unit groups of a field, which are special cases of elliptic curves anyway. So elliptic curves really are all you need for DH.
Like, using something like SageMath for algebraic structures, a prover like Lean to verify properties — to get a feel for how things actually fit together.
There's something cool about trying to reimplement known standards just to understand them better (with the usual "don’t roll your own crypto" warning, of course). By the way, it would be nice to have a kind of sandbox for the more formal path to explore how to build my own SP-network, prove that the Decisional Diffie-Hellman assumption holds or something.
I've seen cryptopals and cryptohack.
If we do not talk about modern exotic stuff (post-quantum crypto, zkSNARKS, homomorphic encryption), the 99% of everyday cryptography is based on two building blocks:
1. Symmetric crypto for ciphers and hash functions.
2. Algebraic group with "hard discrete log problem" for key exchange, signatures, asymmetric encryption and simple zero-knowledge proofs.
Historically, these two categories are filled with a zoo of protocols. E.g. AES is a block cipher, but SHA(1,2) is a hash function.
Today, you can roughly achieve everything of the above with two universal building blocks:
- Keccak for all of symmetric crypto: it is suited both for encryption, hashing, duplex transcripts for ZK protocols etc.
- Ristretto255 group based on Curve 25519: for diffie-hellman, signatures, key derivation, threshold schemes, encryption and more.
The problem is that none of the described features is implemented in a turnkey standard, and we are still stuck using older crypto. Heck, even Git is using SHA-1 still.
Then, after you have your building blocks, there are more hairy stuff such as application-specific protocols: TLS, Signal, PAKE/OPAQUE, proprietary hardware security schemes for full disk encryption and access controls etc.
Unfortunately, Keccak and sponge constructions in general are inherently sequential. Even with hardware acceleration it heavily restricts possible performance. For example, AES-CBC encryption is 4-8 times slower than AES-CTR on high-end CPUs with AES-NI available. VAES makes the difference even bigger. Algorithms like AES-GCM, ChaCha20, and BLAKE3 are designed specifically to allow parallelization.
eg CryptHOL needs a ton of infrastructure, and in still very limited: https://eprint.iacr.org/2017/753.pdf
https://dl.acm.org/doi/full/10.1145/3594735
https://github.com/SSProve/ssprove
OTOH if you want to win a Turing Award…
That may surprise people but we have no proof of the robustness of the encryption we use. In fact it might not work! Consider a one time pad for really extreme security needs. One time pads do have a proof (see the work of Shannon).
Like assuming f(x) is hard, let us try to prove these other properties of security.
https://github.com/nakov/practical-cryptography-for-develope...
You can find more details in Silverman's book on elliptic curves, or if you don't have access to that, see Section 24.7 in Lecture 24 of https://ocw.mit.edu/courses/18-783-elliptic-curves-spring-20....
One could nitpick by pointing out that singular cubics are not elliptic curves (which are, by definition, smooth projective curves). One could also nitpick that the real reason you don't want to use DH in the multiplicative group of a finite field is that there is a known subexponential time algorithm that breaks DH in that setting (forcing > 3000-bit key sizes) whereas for elliptic curves the only known attacks take exponential time (and 256-bit keys are fine). But I don't think either of these nitpicks contradicts the author's thesis.
Another point that the author glosses over a bit is that higher dimensional abelian varieties offer other instances of DH that are genuinely different from ECDH, and that are occasionally useful (mostly the case of Jacobians of hyperelliptic curves of genus 2). There isn't really a trick to make an arbitrary hyperelliptic curve DH/abelian variety DH instance a special case of ECDH: if anything, the relationship would be in the reverse direction.
ECC also used to have patents which restricted adoption back in the day.
There also used to be a lot of conspiracy theories that NSA backdoored nist curved ( e.g. https://m.slashdot.org/story/191445 ). Probably fud, but it slowed down adoption of eliptic curves.
Irrespective of the curve issue, ed25519/x25519 is superior and has other nice properties like not catastrophically breaking if you can't generate a unique random "k" for ECDSA as PlayStation discovered the hard way[1].
[1]: https://youtu.be/DUGGJpn2_zY?t=2142
Not FUD at all. NIST revoked their recommendation to use those curves because of it. The facts are that a "backdoor" exists whether anyone knows what it is or not, and NSA could not explain how those particular numbers were chosen so out of caution we must assume they know the backdoor and not use those curves.
But for some reason the author keeps referring to the underlying group as "Diffie-Hellman" instead of the process operating on some group.
The result is interesting, the journey to get there was very confusing.
I know KaTeX supposedly lets you copy-and-paste the text, but that won't get you text that is fit for any purpose.
And if not, then that seems to be something that is now within reach of modern AI and just needs application.)
Deleted Comment
For any n, there is only one finite cylic group of size n, up to isomorphism (namely Z/nZ). As the author mentions, there are concrete choices of finite cyclic groups (like Z/nZ) that make Diffie-Hellman insecure. Consequently, the security comes entirely from the choice of the _representation_ of the group elements (since the algebraic structure is the same, i.e., it is just a relabeled Z/nZ).
In a similar spirit, people sometimes argue that Diffie-Hellman in some group G must be equally secure as in another group H, because the groups are isomorphic. This is unsound. In order to make such an argument sound, one needs to prove (or at least mention in case it is trivial) that one can _efficiently_ compute the isomorphism and its inverse.
Deleted Comment