HN user
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.
I'm of the opinion that worked examples are often worse than no documentation.
That's completely baffling to me so I'd be really curious to hear your reasons (or those of someone who shares that opinion, as there are others in the thread apparently).
When learning about an abstract notion, it has been my experience that having good examples in mind (in the sense that they are not too complex, but non-trivial enough to illustrate the relevant aspect of the notion at hand) is very helpful, if not essential, for comprehension. All the more so for very abstract subjects (e.g. back in grad school I was studying algebraic geometry, and you can't go very far in that subject trying to prove things about functors on the category of rings without examples in mind that connect the abstract nonsense to some actual geometric meaning).
Speaking of abstract nonsense, by the way, under the Curry-Howard isomorphism, publishing a library with type signatures but no worked out example is equivalent to publishing a mathematical paper consisting entirely of lemmas with no example of how to combine them to prove something interesting (in fact, it's worse, because the expressiveness of the Haskell type system obviously pales in comparison to the language of mathematical papers). I would almost certainly reject a paper like that if I received one for review, and I expect most referees would too.
The claim was that they are independent, in the sense that they do not depend on monied interests for their financial survival, and have a real commitment to investigative journalism. I think even their opponents will acknowledge that they won't shy away from running a damaging story on anyone regardless of which "team" they belong to. (Disclaimer: also a subscriber here).
On the other hand, what they are not is "unbiased" or "neutral". They are quite vocal about their political views. On most issues their stance is usually around the leftmost end of the French MSM Overton window, if that means anything. I happen to disagree with quite a few of these views, but I have a lot of respect both for their journalistic integrity and for the role they play within the French media.
Regular humans have, for over half a century, possessed the ability to annihilate the entirety of civilization by basically pushing a button. So it always amazes me when people feel the need to make science fictional assumptions like AGI in their doomsday scenarios.
Elsevier's role isn't finding collaborators - it's finding reviewers
This is also not true. It's usually journal editors who find reviewers. This is mostly unpaid work as well (publishers tend to chip in a bit for editorial board meetings, but that's about it).
Scientific publishers provide very, very little value to the scientific community. The reason why researchers want to publish in Journal X is that it has a good reputation, which is mostly a function of the editorial board's quality standards, and even more so, of Journal X's past publications (often dating back to way before Elsevier or whoever else actually acquired it).
Wall Whitman
Is that what he will be known as from now on? :)
On a more serious note, it's interesting to reread his poem _America_, which was certainly written more as an aspiration than a description at the time. However, this election makes you wonder whether the aspiration is even there anymore (from either side, if we're being honest).
| Centre of equal daughters, equal sons, | All, all alike endear’d, grown, ungrown, young or old, | Strong, ample, fair, enduring, capable, rich, | Perennial with the Earth, with Freedom, Law and Love, | A grand, sane, towering, seated Mother, | Chair’d in the adamant of Time.
Here in Japan, the NURO Hikari service of Sony Network Communications offers FTTH with 10 Gbps downlink and 2.5 Gbps uplink speeds for around ¥6500 (~65 USD) per month. It's only available in the central wards of Tokyo and a part of Kanagawa prefecture, but you can get it right now.
Obfuscation is different from homomorphic encryption, and in some sense much more powerful.
With homomorphic encryption, Alice can send some secret data to Bob in encrypted form, and let Bob carry out computation on that encrypted data. However, the result of the computation remains encrypted, and only Alice's private key can decrypt the result.
By contrast, obfuscation allows Alice to give Bob a program that contains some secret information (such as cryptographic keys) in such a way that Bob can run it (without any further interaction with Alice) on any inputs of his choice, and get the result in the clear. However, he cannot learn anything about the hidden secret information other than what is revealed by the input-output pairs he has obtained.
It's not hard to see that obfuscation gives you homomorphic encryption for free (you can probably get a rough idea of how to do it based on the somewhat imprecise descriptions above), but we don't know how to go in the other direction. (Current obfuscation candidates do use fully homomorphic encryption under the hood, but they need to rely on much more than that).
Not completely clear to me what you mean by "calculated to be true", but you may want to look at the difference between computational and statistical zero knowledge. A computational ZK proof hides the witness from computationally bounded (i.e. probabilistic polynomial time) adversaries. Statistical ZK, on the other hand, hides the witness from any adversary, even if they can carry out an unbounded amount of computations (there are slight subtleties there depending on the precise security model but that's the basic idea).
Another reason why you won't see practical applications for a while is that we aren't really sure yet whether indistinguishability obfuscation exists at all. The first proposed construction has recently been broken [1], and while other candidates do exist, they are mostly based on similar principles, so most experts wouldn't bet a lot on their long-term security.
This is a rapidly evolving field, though, so I'm cautiously hopeful that some genuinely novel ideas will emerge soon to overcome the current stumbling blocks.
LWE and SIS-based cryptography absolutely is lattice-based crypto, and I can't really imagine what other kind of scheme you would deem more deserving of the name than those. Even the epitome of classical lattice-based crypto, Ajtai-Dwork, is proved secure under a problem (hidden hyperplane) which is "not actually a lattice problem itself", at least not anymore than LWE and SIS. But being based on a problem equivalent to worst-case lattice problems under polynomial-time reductions strikes me as the strongest possible sense in which you could claim a scheme to be lattice-based.
Why don't we just look for a curve and field which has prime order
We very often do. These days, though, cofactors of 2, 3, 4 or perhaps 8 are getting more common because people like to use curves with more efficient/easier to implement arithmetic (such as Montgomery curves or Edwards curves), and those curves always have nontrivial points of small order.
This doesn't really explain why older cryptographic standards mandating Weierstrass curves allow cofactors greater than 1, admittedly. The reason is probably that generating good elliptic curve parameters back then was very time-consuming, and so it may have made sense to allow people to stop when they hit a curve with almost-but-not-quite prime order.
Unrelatedly, a couple of errors in the OP:
* "in fact, these equations work in every field, finite or infinite (with the exception of \mathbb{F}_2 and \mathbb{F}_3, which are special cased)": all fields of characteristic 2 or 3 are special cases. There are many more than just those two, including infinite fields.
* "RSA’s discrete logarithm problem can be stated as follows: if we know a and b, what’s k such that b = a^k mod p?": RSA and discrete logs don't have much to do with each other. Perhaps you meant DSA? (not sure I would call the finite field DLP "DSA's DLP", though).
A few years ago, Charlie Hebdo fired cartoonist Siné over a relatively innocuous joke about Jean Sarkozy (the son of then president Nicolas Sarkozy) planning to convert to judaism in order to marry into the family of the founders of supermarket chain Darty. Siné's quip was basically a direct quote of a comment by Patrick Gaubert (a personal friend of Nicolas Sarkozy's and the president of LICRA at the time) but since he had added a sarcastic bit to the effect that the young boy would have a bright future, Charlie Hebdo's editor-in-chief decided that it was an unacceptable display of antisemitism and could put the newspaper at risk of lawsuits. Therefore Siné had to be let go.
That's only one example for sure, and things may have been a bit different after Philippe Val left, but I don't think it's fair to say that Charlie was even-handed in the way it targeted its gushes of vitriol, and even less so that they were principled champions of freedom of speech. Like most French people across the whole political spectrum, they were stauch supporters of speech-they-agree-with.
None of this detracts from the horror of what has happened of course. I just thought I would mention that the popular "uncompromising beacon of freedom" narrative might be a bit too simplistic.
It certainly depends on the precise arithmetic being used, but for the usual complete addition law, for example, I'm pretty sure I can recover k from the computation of [k]P where P is of the form (0,y) (or (0:Y:1) in the projective case) and not on the curve. That's a cute idea for a paper that I'll probably write up, by the way; thanks!
This kind of invalid curve attack exists against all elliptic curves, so it's a bit difficult to argue that they're a reason to prefer one curve type over another.
The situation is a bit different in the presence of point compression, in which case you're typically concerned with twist security, but the security of the NIST P-256 quadratic twist is pretty decent, so again this isn't a strong argument against it.
The two good reasons to choose something like Curve25519 over NIST P-256 are 1/ speed and 2/ the fact that it's somewhat simpler to obtain side-channel protected implementations. For SSH key exchange, it's pretty much a wash for most realistic settings (only a server that spends significant CPU time simply establishing SSH connections would care about the performance difference here).
It's not clear that (2) is true. Support for the idea that "the husband should work outside and the wife should care for the household" remains surprisingly strong in Japan (people are roughly evenly split between for and against), even among younger generations. Actually, according to the latest Cabinet Office survey, support is stronger among 20-39 year olds than 40-59 year olds (see [0]), and only a few percentage points lower among women vs. men.
Similarly, a majority of respondents of the Japanese General Social Survey think that "in case the husband's income is sufficient, it is better for the wife not to work". But economic realities make such lifestyle choices difficult. For example, when asked what level of household income would be sufficient for them to consider getting married, a plurality of Japanese women cite a figure of around ¥500k net per month [1], which is around the limit of the top quartile of household incomes, and way above what unmarried men typically make on their own.
As for (3), I'm not particularly interested in debating whether "Japan is a racist country", but getting Japanese citizenship is far from being impossible. In fact, the rejection rate of formally submitted naturalization applications is about 1% (consistent over at least the past decade, see e.g. [2]).
[0] http://www2.ttcn.ne.jp/honkawa/2410.html [1]: http://jgss.daishodai.ac.jp/english/research/monographs/jgss... [2]: http://www.turning-japanese.info/2012/05/10-years-of-natural...
When the base field is pseudo-Mersenne, taking mods is actually fine, since the statistical distance to uniform of the resulting distribution is O(2^{-λ}) at the λ-bit security level. In other words, an attack that exploits the bias is at least as costly as breaking the discrete log problem directly, and therefore not a security concern. So I wouldn't worry about implementations of secp256k1 that do it like that (although it would be simpler and less "leaky" to just use the non-reduced 256-bit MAC value as the nonce; of course, anything shorter than 256 bits would be a huge problem).
But careful approaches like RFC 6979 are very important for curves over random fields, like the Brainpool parameters.
[By the way, a more regular contributor of this site suggested that it would be appropriate for me to mention that I'm one of the authors of the OP.]
Deterministic nonces are a good idea, but they don't necessarily prevent biases. Generally speaking, for (EC)DSA/Schnorr in a group of cardinality n, using a nonce of the form k=F_x(m) (where m is the message and x the public key) is safe if F is chosen as a Z/nZ-valued PRF; but if you use a PRF with values in bitstrings of the same length as n, the attack in the paper does apply.
So RFC 6979 is fine, but k=HMAC-SHA-256(x,m) is not a secure choice for 256-bit elliptic curves over random base fields.
Even assuming D-Wave actually achieves quantum annealing (a highly uncertain proposition at this point), the implications for cryptography are inexistent. Quantum algorithms relevant to cryptography (mostly Shor's and Grover's) require a general purpose quantum computer, which the D-Wave machine is emphatically not.