mti

In a serious discipline like mathematics, this isn't just an asshole move, but a career-ending level of academic misconduct.

Good point. Note however that PIR is a rather restricted form of search (e.g., with no privacy for the server), but even so, DEPIR has polylog(n) queries (not log n), and requires superlinear preprocessing and a polynomial blowup in the size of the database. I think recent concrete estimates are around a petabyte of storage for a database of 2^20 words. So as you say, pretty impractical.

There is an even more fundamental reason why FHE cannot realistically be used for arbitrary computation: it is that some computations have much larger asymptomatic complexity on encrypted data compared to plaintext.

A critical example is database search: searching through a database on n elements is normally done in O(log n), but it becomes O(n) when the search key is encrypted. This means that fully homomorphic Google search is fundamentally impractical, although the same cannot be said of fully homomorphic DNN inference.

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.

The relevant category is really abelian group schemes (because DH necessarily works in a cyclic group), so 0 is quite reasonable.

Elligator is only tangentially relevant to the hashing problem. If "doesn't have a problematic structure" is understood in a weak sense, then this was already solved by Shallue and van de Woestijne almost a decade prior to the Elligator paper. And if it is understood in the stronger sense of indifferentiability, then Elligator by itself doesn't actually fit the bill, and you need something like the Brier et al. approach or SwiftEC.

The steganography stuff is the only actually novel contribution of the Elligator paper.

In that spirit, my pet "a monad is a monoid in the category of endofunctors, duh"-style one-line explanation of the Fourier transform is that it's just the decomposition in the common (Hilbert) eigenbasis for all translation operators. It makes it surprisingly clear (to some) why it is a both natural and important construction.

A map of algebraic curves is not a special case of a map between two sets. There aren't really source and destination sets to speak of. The fact that it is given by polynomials really is a definition.

The moral "justification" of the definition is something like "algebraic geometry is precisely the study of such objects" or "we want definitions that are stable under ring base change, and this implies polynomials", etc., but we don't formally need to justify definitions.

[One could take a different route to defining those things, in which this becomes a theorem instead of a definition. For example one can define algebraic curves over a field k as contravariant functors from k-algebras to sets satisfying certain additional properties, and then maps of algebraic curves are natural transformations between those functors. The fact that they are given by polynomial equations is then a theorem. Just stating the "additional properties" for a curve is a rather daunting task, though, unfortunately.]

NTRU also relies on cyclotomic rings, so if distrust in cyclotomics was a good reason to reject Kyber, it would apply to NTRU too.

The hardness of discrete logs over fields doesn't have much to do with the hardness of elliptic curve discrete logs. At this stage, I don't think we have any evidence that curves over binary fields are less secure than over prime fields, especially for cryptographically relevant curve sizes.

(The situation is different for pairing-friendly elliptic curves, of course, but that's a different kettle of fish).

That's what we call a "fired if you do, fired if you don't" kind of situation.

I'm not sure what specific scheme you have in mind, but while FHE for Turing machines does exist, it is really, really hard to instantiate. A construction with some restrictions and requiring a massive amount of preprocessing is given in Goldwasser et al.'s famous paper on reusable garbled circuits, and it already uses succinct functional encryption as a building block; and for the stronger notion of FHE for TM you basically need obfuscation. So thinking about implementing any of this seems somewhat premature to me.

I don't think most of the issues with freedom of speech in France would be of much concern to a putative startup founder, but they are real.

For example, "expressing support for acts of terror" is an imprisonable offense, and it has been interpreted incredibly broadly by the courts, to the point that drunk people have been sent to prison for years over tasteless jokes. Similarly, simply browsing websites that are deemed in support of terrorism: a man from Chartres recently received a two-year sentence for the latter.

It's fair to say that the current climate is pretty Orwellian. But if you're not a brown person or a Muslim, you're not what prosecutors are after.