There Is No Diffie-Hellman but Elliptic Curve Diffie-Hellman(keymaterial.net)
keymaterial.net
There Is No Diffie-Hellman but Elliptic Curve Diffie-Hellman
https://keymaterial.net/2025/05/23/there-is-no-diffie-hellman-but-elliptic-curve-diffie-hellman/
66 comments
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.
I've seen cryptopals and cryptohack.
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.
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.
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.
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.
How much does the lack of parallelization matter in practice though? Sure, AES-CTR can be parallelized, but the authentication function you're probably pairing it with likely can't. And in a lot of cases I'm aware of where encryption parallelism is important for performance (e.g. line-rate VPN encryption), you can achieve parallelism for the operation as a whole without achieving stream based parallelism. In the VPN example, even if you can't encrypt all the blocks in a single packet in parallel, you can probably achieve just as much parallelism speedup by encrypting multiple packets in parallel.
> Unfortunately, Keccak and sponge constructions in general are inherently sequential.
Couldn't you simply using BLAKE3 instead? To my knowledge BLAKE3 exactly was designed to solve this "parallelism problem" by combining the "cryptographic ideas" of BLAKE2 with the binary tree structure of Bao (the latter was designed to make the hash construction easy to parallelize).
Couldn't you simply using BLAKE3 instead? To my knowledge BLAKE3 exactly was designed to solve this "parallelism problem" by combining the "cryptographic ideas" of BLAKE2 with the binary tree structure of Bao (the latter was designed to make the hash construction easy to parallelize).
Fwiw I don't think there's anything inherently sequential about the Keccak permutation itself. KangarooTwelve is a fully parallelizable hash built on Keccak. (Though they did use the sponge construction on the XOF side, so that part is serial.)
I meant the absorb and squeeze part. The permutation itself (or more specifically its round) could be efficiently implemented in hardware, but you can't mask latency by parallel application of the permutation. Yes, KangarooTwelve is an improvement in this regard, but the grandparent was talking specifically about Keccak/SHA-3.
Sorry for lack of clarity, but i was saying “Keccak” and not “sha3” for that specific reason: it’s a permutation building block suitable for a whole range of constructions - cshake, kangaroo etc. sha3 specifically is an overkill and unnecessary imho.
CShake128 is much better replacement for hmac and sha512 in (zk)proofs, while Kangaroo for things like FDE and massive volumes of data.
CShake128 is much better replacement for hmac and sha512 in (zk)proofs, while Kangaroo for things like FDE and massive volumes of data.
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 tradeoff is not that simple (I wish it was :-).
Usually it goes like that: someone made something useful optimised for a specific use-case with certain time (or competence) constraints, within a total lack of decent alternatives. Then people adopt and use it, it becomes the standard. Then people want to do more things with it, and try to build around that thing, or on top of that thing and Frankenstein monsters get born and also become standard.
If you start from scratch you can do a crypto protocol that is both better designed (causes less UX pain and critical bugs) AND performs better on relevant hardware. Also do not forget that performance is easily solved by hardware: Moore's law and then custom hardware extensions are a thing.
Example: Keccak is so much better from the composition perspective, that when used ubiquitously you'd definitely have ubiquitous hardware support. But if everyone continues to use a mishmash of AES and SHA constructions on the pretext of "Keccak" is not as fast, then we'd never move forward. People would continue building over-complicated protocols, bearing subpar performance and keeping the reputation of dark wizardry inaccessible for mere mortals.
Usually it goes like that: someone made something useful optimised for a specific use-case with certain time (or competence) constraints, within a total lack of decent alternatives. Then people adopt and use it, it becomes the standard. Then people want to do more things with it, and try to build around that thing, or on top of that thing and Frankenstein monsters get born and also become standard.
If you start from scratch you can do a crypto protocol that is both better designed (causes less UX pain and critical bugs) AND performs better on relevant hardware. Also do not forget that performance is easily solved by hardware: Moore's law and then custom hardware extensions are a thing.
Example: Keccak is so much better from the composition perspective, that when used ubiquitously you'd definitely have ubiquitous hardware support. But if everyone continues to use a mishmash of AES and SHA constructions on the pretext of "Keccak" is not as fast, then we'd never move forward. People would continue building over-complicated protocols, bearing subpar performance and keeping the reputation of dark wizardry inaccessible for mere mortals.
> Also do not forget that performance is easily solved by hardware: Moore's law
"Just write slow algorithms, hardware will eventually get faster" doesn't really work when talking about performance implications now. If the hash algorithm used million of times doesn't perform on current user hardware, then the algorithm is simply not a good fit.
> and then custom hardware extensions are a thing.
That's the kind of trade-off I eluded to as well. As a developer of a tool (e.g. git), I'd pick hash algorithms that do have hardware extensions on the most common hardware and not use something, that may eventually get hardware extensions.
I guess developing such protocols right now for the future might still be advisable, but it seems odd to critic software that use well-optimized algorithms and fulfill the requirements.
"Just write slow algorithms, hardware will eventually get faster" doesn't really work when talking about performance implications now. If the hash algorithm used million of times doesn't perform on current user hardware, then the algorithm is simply not a good fit.
> and then custom hardware extensions are a thing.
That's the kind of trade-off I eluded to as well. As a developer of a tool (e.g. git), I'd pick hash algorithms that do have hardware extensions on the most common hardware and not use something, that may eventually get hardware extensions.
I guess developing such protocols right now for the future might still be advisable, but it seems odd to critic software that use well-optimized algorithms and fulfill the requirements.
[deleted]
sha-1 in git was just supposed to catch corruption, it was never intended to be used for security.
This is a justification that was made up after Git came under increasing criticism for its poor choise of a hash function after the shattered attack. It was already known that SHA-1 is weak before Git was invented.
The problem is... it doesn't line up with the facts.
Git has been using SHA-1 hashes for signatures since very early on. It also has claims in its documentation about "cryptographic security". It does not rigorously define what "cryptographic security" means, but plausibly, it should mean using a secure hash function without known weaknesses.
The problem is... it doesn't line up with the facts.
Git has been using SHA-1 hashes for signatures since very early on. It also has claims in its documentation about "cryptographic security". It does not rigorously define what "cryptographic security" means, but plausibly, it should mean using a secure hash function without known weaknesses.
Torvald claimed:
"So that was one of the issues. But one of the issues really was, I knew I needed it to be distributed, but it needed to be really, really stable. And people kind of think that using the SHA-1 hashes was a huge mistake. But to me, SHA-1 hashes were never about the security. It was about finding corruption.
Because we’d actually had some of that during the BitKeeper things, where BitKeeper used CRCs and MD5s, right, but didn’t use it for everything. So one of the early designs for me was absolutely everything was protected by a really good hash."
https://github.blog/open-source/git/git-turns-20-a-qa-with-l...
"So that was one of the issues. But one of the issues really was, I knew I needed it to be distributed, but it needed to be really, really stable. And people kind of think that using the SHA-1 hashes was a huge mistake. But to me, SHA-1 hashes were never about the security. It was about finding corruption.
Because we’d actually had some of that during the BitKeeper things, where BitKeeper used CRCs and MD5s, right, but didn’t use it for everything. So one of the early designs for me was absolutely everything was protected by a really good hash."
https://github.blog/open-source/git/git-turns-20-a-qa-with-l...
[deleted]
[deleted]
That's a valid point. However, modern hardware and crypto algorithms are fast enough that it pays off to have "do it all" protocols, with as little tradeoffs as possible.
Example: Git users do need both corruption protection AND secure authentication. If authentication is not built in, it will have to be built around. Building around is always going to be more costly in the end.
Unfortunately, 20-30 years ago considerations such as "sha1 is shorter + faster" were taken seriously, plus all the crypto that existed back then sucked big time. Remember Snowden scandal in 2013? That, plus Bitcoin and blockchains moving towards mainstream brought about review of TLS, started SHA-3 competition. Many more brains turned to crypto since then and the new era began.
Example: Git users do need both corruption protection AND secure authentication. If authentication is not built in, it will have to be built around. Building around is always going to be more costly in the end.
Unfortunately, 20-30 years ago considerations such as "sha1 is shorter + faster" were taken seriously, plus all the crypto that existed back then sucked big time. Remember Snowden scandal in 2013? That, plus Bitcoin and blockchains moving towards mainstream brought about review of TLS, started SHA-3 competition. Many more brains turned to crypto since then and the new era began.
If this were true, then wouldn't MD5 have been the better choice?
Also, SHA-1's preimage resistance (which still isn't broken) is necessary for the security of signed commits, regardless of the hash function used for the signature itself, since a commit object references its tree and predecessor commit by their SHA-1 hashes.
Also, SHA-1's preimage resistance (which still isn't broken) is necessary for the security of signed commits, regardless of the hash function used for the signature itself, since a commit object references its tree and predecessor commit by their SHA-1 hashes.
[deleted]
Really nice summary! Thank you.
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.
eg CryptHOL needs a ton of infrastructure, and in still very limited: https://eprint.iacr.org/2017/753.pdf
eg CryptHOL needs a ton of infrastructure, and in still very limited: https://eprint.iacr.org/2017/753.pdf
There is also SSProve which has similar goal to CryptHOL:
https://dl.acm.org/doi/full/10.1145/3594735
https://github.com/SSProve/ssprove
https://dl.acm.org/doi/full/10.1145/3594735
https://github.com/SSProve/ssprove
There are no proofs of the hardness of DDH or RSA etc. That’s why they’re called assumptions.
OTOH if you want to win a Turing Award…
OTOH if you want to win a Turing Award…
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).
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).
Shor's algorithm suggests that a lot of encryption doesn't actually work, but of course it requires a quantum computer that hasn't yet been built, and may not be practical to build, so fingers crossed. At least there are quantum-resistant encryption algorithms, and OTPs are still provably secure like you say.
On "finger's crossed" - I think it's important to say that the majority of web traffic has switched over to PQC algorithms for key exchange that are not susceptible (thanks Cloudflare). We're not close to building a machine suitable for running Shor's in a practical sense, so even potential "store now, break later" attacks are now kinda pointless. Things like SSH keys are trivially revokable and often have enforced expirations, so they're not really a viable attack vector anyway.
The symmetric encryption used for the vast majority of actual encryption has always been safe. Grover's algorithm does not scale appropriately (exponential on key length) unlike Shor's and cannot be parallelized. Worst case, AES-128 becomes as week as AES-64. So we bump it to AES-256 and we're back at the same difficulty as before (impossible). There's a degree of confidence this will always hold true.
The symmetric encryption used for the vast majority of actual encryption has always been safe. Grover's algorithm does not scale appropriately (exponential on key length) unlike Shor's and cannot be parallelized. Worst case, AES-128 becomes as week as AES-64. So we bump it to AES-256 and we're back at the same difficulty as before (impossible). There's a degree of confidence this will always hold true.
Can't someone learn this stuff with the assumption that certain functions are hard to invert?
Like assuming f(x) is hard, let us try to prove these other properties of security.
Like assuming f(x) is hard, let us try to prove these other properties of security.
What you described is pretty much exactly how modern provable cryptography field works today. Reduction to assumptions about certain primitives and constructing the boundaries of security given such assumptions.
E.g. "Assuming AES block cipher is a perfect pseudorandom function, prove AES-GCM construction is secure up to certain number of messages"
E.g. "Assuming AES block cipher is a perfect pseudorandom function, prove AES-GCM construction is secure up to certain number of messages"
That’d indeed be nice to do.
Not really, but I liked this one.
https://github.com/nakov/practical-cryptography-for-develope...
https://github.com/nakov/practical-cryptography-for-develope...
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.
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.
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.
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.
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.
isn’t that how the article ends? maybe I don’t understand what you mean
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.
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].
[1]: https://youtu.be/DUGGJpn2_zY?t=2142
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
> like not catastrophically breaking if you can't generate a unique random "k" for ECDSA
How does that work? I thought that this vulnerability was independent of the curve that is used. Ed25519 has a bunch of other nice properties related to resistance to programming errors, but I never heard of this one.
How does that work? I thought that this vulnerability was independent of the curve that is used. Ed25519 has a bunch of other nice properties related to resistance to programming errors, but I never heard of this one.
> How does that work? I thought that this vulnerability was independent of the curve that is used.
The trick is that this value in Ed25519 is a deterministic hash of the private key and the message, which means that for the same message, the same value will always be chosen, and since the private key is part of the hash, for different messages the value is basically random unless you already know the private key.
Yes, the same trick can be used with any curve, and it will avoid the vulnerability; but for Ed25519, it's always been part of the specification so everyone does it that way, while for ECDSA it's a later addition (RFC 6979) and many implementations still do it the old way.
The trick is that this value in Ed25519 is a deterministic hash of the private key and the message, which means that for the same message, the same value will always be chosen, and since the private key is part of the hash, for different messages the value is basically random unless you already know the private key.
Yes, the same trick can be used with any curve, and it will avoid the vulnerability; but for Ed25519, it's always been part of the specification so everyone does it that way, while for ECDSA it's a later addition (RFC 6979) and many implementations still do it the old way.
>> 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.
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.
I believe you are mixing up NIST ECC curves with Dual_EC_DRBG[1] which is a random number generator based on elliptic curves which is widely considered to be backdoored and they revoked its recommendation (there are much better ways to construct an RNG so it was stupid to use in practice for reasons other than backdoor too.)
The P-series curves are still a NIST recommendation and widely deployed in TLS. The B-series fell out of fashion due to practical reasons.
[1]: https://en.wikipedia.org/wiki/Dual_EC_DRBG
The P-series curves are still a NIST recommendation and widely deployed in TLS. The B-series fell out of fashion due to practical reasons.
[1]: https://en.wikipedia.org/wiki/Dual_EC_DRBG
lol same - but i needed this comment to take the bait
So, addition under a particular elliptic curve is isomorphic to multiplication under integer modulo groups...
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.
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.
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.
What would that help with?
I know KaTeX supposedly lets you copy-and-paste the text, but that won't get you text that is fit for any purpose.
I know KaTeX supposedly lets you copy-and-paste the text, but that won't get you text that is fit for any purpose.
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.
Well, having gone and looked at the website, I'd have to agree that KaTeX would be an improvement, but not for reasons that relate to whether the math is rendered as an image.
Rather:
- The background of the math images is white, which doesn't match the background of the website;
- The baseline of the text in the images is not aligned with the baseline of the surrounding text.
I was imagining a more-competently-put-together website.
Rather:
- The background of the math images is white, which doesn't match the background of the website;
- The baseline of the text in the images is not aligned with the baseline of the surrounding text.
I was imagining a more-competently-put-together website.
(hopefully modern screen reading software is clever enough to OCR and summarise images as it does text.
And if not, then that seems to be something that is now within reach of modern AI and just needs application.)
And if not, then that seems to be something that is now within reach of modern AI and just needs application.)
It wouldn't really matter; the image includes a lot of structure that isn't present in the text that KaTeX provides. A text-only screen reader will never produce anything but gibberish if you feed it KaTeX output.
KaTeX will also style the text so that it visually resembles the image, stopping this problem from occurring for non-blind readers. You could have a screen reader that parsed all of the layout, but it seems like you might just as well OCR the image at that point.
KaTeX will also style the text so that it visually resembles the image, stopping this problem from occurring for non-blind readers. You could have a screen reader that parsed all of the layout, but it seems like you might just as well OCR the image at that point.
The image does have LaTeX source as it's alt text, so should be at least somewhat understandable for screen readers.
[deleted]
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.
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]
What insanity led someone to use 0 for the terminal object?
It makes some sense in the category of rings, but basically only there.
It’s also the standard notation for zero objects, i.e., for terminal objects that are also initial. This entails all abelian/additive/preadditive categories, such as categories of modules, vector spaces, or abelian groups. (But there are also counterexamples, such as the categories of groups and of pointed sets.)
But I’d agree that it’s not standard notation to use 0 for a terminal object in an arbitrary category. I’d guess that most people use 1 instead, so that for example 1 × X ≅ X. (The post talks about group objects in the category of algebraic varieties (over some field), in which case 1 seems to be more appropriate than 0.)
But I’d agree that it’s not standard notation to use 0 for a terminal object in an arbitrary category. I’d guess that most people use 1 instead, so that for example 1 × X ≅ X. (The post talks about group objects in the category of algebraic varieties (over some field), in which case 1 seems to be more appropriate than 0.)
The relevant category is really abelian group schemes (because DH necessarily works in a cyclic group), so 0 is quite reasonable.
I don't get this article. They make a big fuss about looking for the right category, because apparently the category of groups cannot explain the difficulty of breaking Diffie-Hellman, since there is an isomorphism <g> -> Z/nZ. But the same isomorphism exists in the category of algebraic varieties! So was all in vain?
To me this sounds a bit like an a-posteriori justification of why people use elliptic curves to do cryptography. This feels weird to me, as elliptic curves are a well-studied subject in algebraic geometry, whose history reaches back over 150 years to Clebsch. So when Victor Miller and Neal Koblitz proposed to do cryptography with them, they already knew very well about elliptic curves (both have a background in algebraic geometry of finite fields).
To me this sounds a bit like an a-posteriori justification of why people use elliptic curves to do cryptography. This feels weird to me, as elliptic curves are a well-studied subject in algebraic geometry, whose history reaches back over 150 years to Clebsch. So when Victor Miller and Neal Koblitz proposed to do cryptography with them, they already knew very well about elliptic curves (both have a background in algebraic geometry of finite fields).
I think the author's point is that while you might a priori think there are lots of groups out there that might be good candidates for DH, it turns out that elliptic curves are a strictly better choice than every alternative, and the reasons for this were definitely no fully known at the time Miller and Koblitz proposed ECC.
There was a period during which there was lots of interest in using abelian varieties of higher dimension (arising as Jacobians of curves of higher genus), with dimensions g=3 and g=4 being particularly attractive because then you could work over a very computationally friendly base field like Fp with p = 2^61-1. But it turns out the discrete logarithm problem (and therefore DH) is strictly easier in these settings (one can exploit Weil restrictions to get an algorithm that is still exponential-time but strictly better than O(p^(g/2)). But this wasn't known until the 2000's.
That leaves g=1 and g=2 as the best choices, and the group law is faster and simpler for g=1, and as far as I know nobody is really working on the g=2 case anymore (but there was a lot of activity in this area 10-20 years ago).
There was a period during which there was lots of interest in using abelian varieties of higher dimension (arising as Jacobians of curves of higher genus), with dimensions g=3 and g=4 being particularly attractive because then you could work over a very computationally friendly base field like Fp with p = 2^61-1. But it turns out the discrete logarithm problem (and therefore DH) is strictly easier in these settings (one can exploit Weil restrictions to get an algorithm that is still exponential-time but strictly better than O(p^(g/2)). But this wasn't known until the 2000's.
That leaves g=1 and g=2 as the best choices, and the group law is faster and simpler for g=1, and as far as I know nobody is really working on the g=2 case anymore (but there was a lot of activity in this area 10-20 years ago).
The plot at the bottom is of Y^2 = X^3 + X^2, not Y^2 = X^3 - X^2 as stated.
Random fun fact. Whit Diffie is cousin to the late country music singer Joe Diffie. Their Wiki pages make no mention of this, though they do mention the other’s page in case users end up on the wrong one.
It's a nice article, just the title needs a small tweak to add the word practical, as in "There is no practical DH..."
wtf did i just read
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.