mswphd

the server doesn't do what you say. Roughly, the server has a fixed circuit C they run on the ciphertext. They run this same circuit on any ciphertext. They give you back the result. the fact that the result, when decrypted, gives the desired answer isn't something the server can verify though.

Think about a very simple setting, say a database lookup. I send an index `i` in a database I want to lookup. The server sends back DB[i] or whatever.

In the clear, the server can immediately fetch the correct row. Under FHE, the server does a full scan of the database, and (roughly) for each row will do something like DB[i] * (encrypted selector variable that is 0 or 1 depending on if it is the row you want).

This is actually a baby version of FHE known as "Private Information Retrieval". For it, you (roughly) can design an encryption scheme that supports linear function evaluation. For example, a ciphertext Enc(m) can be paired with a matrix A to produce Enc(Am). You can then encrypt the ith basis vector m := e_i, and view the database as a matrix DB, to get DB * Enc(e_i) = Enc(DB*e_i) = Enc(DB_i). This works, and can be implemented in ~1k LoC, e.g. it is not particularly complicated to practically instantiate (though this basic sketch has some performance issues).

note that this is even true for an honest server. Roughly, FHE computations often require certain bounds on the (encrypted) messages for things like tuning polynomial approximation domains etc. If your messages are out of distribution for the tuned polynomial approximations you'll get back garbage as as result.

addition is easy/essentially the same cost as standard (not really, because you have to compute mod p addition rather than mod 2^32, but ignoroing that it's roughly the same).

as a general rule multiplication is the difficult part.

it's hard to accurately quantify what "nontrivial" cost overheads are because they're very application dependent. for example, things that require encrypted control flow are very hard under FHE. so an encrypted hashmap sounds roughly unimplemnetable. but things that do not require encrypted control flow (e.g. many ML applications) are less bad. this can still be quite bad though. for example, relu is trivial in plaintext. it is hard homomorphically, because the trivial way to write it uses private control flow.

I've found having draconian phone blocking rules helps. I use Jomo

https://jomo.so

but I'm sure there are other competing products.

Roughly, you can classify apps in your phone to things that

1. are fundamentally fine (various bank/payment apps, messaging app, map apps), and

2. are known time wasters (social media)

you then just block the time wasters. you can configure it so that to edit the settings of the app, you have to enter some 150 character randomized code. it is very annoying to do.

this is the point though. there are other ways you can add friction to using your phone. setting its display to be black and white makes it much less enjoyable to use, for example. if you add in enough friction (and stick with it over an initial "hump"), you'll findi yourself reaching for other options.

OpenRouter is (roughly) a single proxy between you + many different models + providers. it works with opencode (+ many other products), and is relatively convenient for trying out a bunch of models.

for example, they already have qwen3.8-max

https://openrouter.ai/discover?model=qwen/qwen3.8-max

note that they add some fee ontop of things (maybe 10% of spend?). it isn't htat big of a deal for general experimentation, but if you end up wanting to use a single model in a higher-volume way, it likely makes sense to cut them out of your stack.

not really. The hardness of SVP is relevant, but this is a paper giving improved provable bounds for SVP algorithms. heuristically (which people use to choose parameter sizes etc) people assume SVP is much easier to solve, closer to 2^{.29n + o(n)}.

So it's tangentially related, but does not itself imply an improvement on the (heuristically assumed) SOTA for these problems.

it's worth mentioning the infinite number of decimal places isn't an issue. there is the formalism of computable numbers to get around this

https://en.wikipedia.org/wiki/Computable_number

roughly represent each number as a turing machine, which on input i outputs the ith digit. it works fine (it's slower than floats, but that's a different concern).

the issue is that the computable numbers are relatively small. in particular, there are countably many turing machines, so they're a countable subset (in fact subfield) of the reals. so in a precise sense they only make up a vanishingly small fraction of the real numbers. but they still capture many important mathematical constants, e.g. e and pi.

it doesn't overturn much. For example, here is a post from 2004

https://www.math.columbia.edu/~woit/wordpress/?p=105

it is about a purported (though incorrect) positive proof of the Jacobian conjecture in 2 dimemnsions. It is true in 1 dimension. The Fable proof is that it is false in >= 3 dimensions. 2 dimensions is still open.

Anyway, in that post it says

> It now seems that a proof has been found by Carolyn Dean of the University of Michigan, for the case of polynomials in two complex variables *(for more variables, many people believe it is not even true)*

so the resolution of this is a "surprise" in that it is a very long open with many failed proof attempts. But the direction it resolved was not surprising.

verification also requires computing the jacobian. an undergraduate-level exercise, but harder than verifying p(pt1) == p(pt2).

this is only true in the IND-CPA model for most "practical" FHE work. So a more precise way to describe things is "a server who faithfully performs the task given to them does not gain any sort of insight" (perhaps with an additional caveat about decryption failures).

https://paseo.sh/ supports self-hosting, though I've only used it a mild amount tbh.

I don't think quibbling over "equivalence" vs "equality" is useful personally. They're both "equality". Just what the sign "=" means differs depending on the type information.

E.g x: ZmodN == y: ZmodN is a different operation than x: Z == y: Z, but they're both the equality operation. We wouldn't makeup a new name for addition in this context.

It's also worth mentioning we can use the equality function (==): Z x Z -> bool to define the (==_N): ZmodN x ZmodN -> bool function in a semi-generic way. To do so, we "just" need a way to assign a unique representative (in Z) to any x: ZmodN. In other words, this is choosing a partial inverse to the reduction function modN: Z -> ZmodN. I think the partial inverse is a right inverse? so a function g : ZmodN -> Z such that (modN) o g x == x for all x in ZmodN. Anyway, given such a right inverse g, you can define (==_N): ZmodN x ZmodN -> bool via

(==_N) x y := (==) (g x) (g y)

This has the benefit that it doesn't treat ZmodN as special in any way. You can apply the same song and dance for more general quotient structures. This can be useful when doing e.g. matrix arithmetic, where you might want equivalence up to the choice of some rotation or something.

there's been some forward movement on doing this via an appropriate intrinsic in LLVM

https://github.com/llvm/llvm-project/pull/166702

note that this isn't the only "trick" needed for constant-time programming though. Indexing an array with a secret index needs its own trick, for example.

I agree that trying to trick the compiler is very ugly. A well-known applied cryptographer has a paper from last year saying that not only is it ugly, but it doesn't work particularly well, and if anything the trendline of the various "tricks" is that they get less effective over time.

https://eprint.iacr.org/2025/435

that has some technical limitations. For example, their impl can compile to wasm, which makes giving an online interpreter simpler/lighter weight than relying on running python in the browser.

note that similar concepts appear in mathematics. Generally the term for it is a "mollified" function.

applied to the step function, you would get a smooth cutoff function

https://en.wikipedia.org/wiki/Mollifier#Smooth_cutoff_functi...

this is also related somewhat to the notion of differentiable programming. RELU is (roughly) the same as x * step(x). In differentiable programming one can replace it with smooth approximations, cf "softplus"

https://arxiv.org/pdf/2403.14606

That book also has a chapter on control flow, which is very similar to what you're talking about.

Unrolling an if statement into x = b (result of one branch) + (1-b) (result of the other branch) is also incredibly common in cryptography. If `b` is a "secret" variable, an if statement may leak the value of it via the branch predictor/speculative execution. The way around this is to compute both branches, and then select them with the above arithmetic expression. This mostly works, though compilers are tediously smart, and so one often has to be careful how with how you precisely do it.

as a heads up, there is another attack paper against McEliece today

https://eprint.iacr.org/2026/1339

Note that this is by someone from the BSI. It's worth mentioning the BSI is very familiar with lattice-based schemes (they recommend using FrodoKEM rather than Kyber, but whatever). Despite this familiarity, the attacks they are able to publish aren't regarding lattice-based schemes, and instead a different scheme Bernstein was affiliated with.

NTRU-derivatives and McEliece derivatives are (objectively speaking) not a good track record to have, PQC-wise.

you'd probably call it "Product NTRU" then, and be a minimum a decade out of date. So you'd probably have to do all that weird shit with co-different ideals Peikert was trying to get us all to do (I know it was "right" but sometimes you need to put a muzzle on the math guys for all of our sakes).

huh. I really wouldn't want the Nobel Prize committee in medicine doing cryptographic work then. good thing your comment has nothing to do with cryptography then :)

it's worth clarifying that its entrants were all qualified, and 2 other essentially identical schemes, namely New Hope and Saber, made it very deep into the NIST competition.

All 3 (roughly) took the approach of

1. take the obvious best design, and

2. tweak various internal design knobs you have access to, and

3. that's pretty much it.

So they differ in the internal design knobs they chose. But the fact that 3 independent teams all created something substantially similar to ML-KEM should be an indication of how much harder it would be for the NSA to be behind it.

It really depends on what the precise details of the attack look like.

1. algebraic structure: sure use frodoKEM

2. error rates smaller than those required for worst-case to average-case reductions: idk bump error rates

3. some coding theorist ruins everyone's fun and has linear time decoding for p-ary construction A codes: probably drink a lot idk

fortunately there haven't been any "incremental" attacks in any of these directions, so it is really more an academic discussion.

Also note the primary issue with FrodoKEM isn't performance (though that is definitely worse), but size. My impression from the following

https://blog.cloudflare.com/sizing-up-post-quantum-signature...

https://blog.cloudflare.com/making-protocols-post-quantum/

was that TLS w/ FrodoKEM might have some undesirable performance characteristics, though that isn't directly stated in the articles. Iirc TLS w/ FrodoKEM

that's really not possible for ML-KEM. They took a well-known "boring" design, and tweaked certain internal sub-components of it. Their tweaks were good, and their analysis/exposition of it were good. So they deserve to win. But there were many essentially identical schemes (e.g. Saber and New Hope are essentially the same as ML-KEM).

To infiltrate/compromise ML-KEM, then NSA would need to do something like

1. corrupt some europeans for the literal submission, and

2. corrupt the competing submissions, which are substantially similar, and

3. corrupt the entirety of the cryptographic community so they miss a flaw in the (extremely simple tbh) 2011 paper htat kicked off hte design.

If a conspiracy requires corrupting a single person it's plausible. ML-KEM being intentionally weakend by the NSA would quite literally require corrupting like 100+ different people in different countries. it makes no sense.

the NSA also recommends elliptic curve cryptography, and designed SHA2 themselves. if you want we can talk through how to disable all of these ciphersuites, so you can be stuck with a bunch of shitty stuff from the 90s and feel warm and fuzzy about it.

as mentioned it's complicated, but the general trend of the NSA pushing cryptography they can break and others can't is well-known.

https://en.wikipedia.org/wiki/NOBUS

note that there is no even candidate way the NSA would have a NOBUS-type vulnerability for ML-KEM. DUAL_EC_DRBG was known to plausibly have a NOBUS-style backdoor prior to standardization, provided you used a certain "default" generator (vs freshly generating your own). It was later discovered that the NSA payed RSA (the company) to do this.

While this payment was private, the possibility of a back door was publicly known. There are no publicly known candidate backdoors for ML-KEM. The broad design of an ML-KEM-like scheme permits one ("static" matrix A), but ML-KEM was specifically designed to make this impossible ("ephemeral" matrix A).

1. Kyberslash is mostly marketing. Some implementations (including the Kyber reference implementation, but *not* including the Kyber AVX implementation) had a non-constant time component. This is a meaningful CVE. It is not some fundamental weakness that should cause a panic. Note that the non-constant time implementations were caught ~2 years ago, prior to any deployment. So it was a sign of everything going "as expected", not of some new fundamental issue.

2. combining the cryptosystems, in most settings, is rather low cost. I would personally recommend it as a sensible default. It is not low cost in every setting though, for example in hardware it necessitates both a SHA2 and SHA3 impl, which is fairly expensive. So while hybrids are a sensible default, I would not go as far as to attempt to "ban" use of pure ML-KEM.

3. pure ML-KEM is much more "proven" than people are discussing. The core hardness assumption dates back to 2005, and has been intensely studied (the paper introducing it got a cryptography version of a Nobel prize (Godel prize), as did several follow-up works only achievable using that hardness assumption. The essential components of ML-KEM were proposed in ~2011. An extremely similar scheme (New Hope) was deployed experimentally in a hybrid in Chrome in 2016. Very concretely, the best theoretical attacks on ML-KEM take time ~2^cn for a c that has not changed in the last ~decade. Everything is as boring as you might hope.

On essentially any reasonable measure you could ask for, things have been "stable" with ML-KEM for ~1 decade. In the intervening years, a number of academics/companies have devoted a great deal of money on things built from even more sketchy hardness assumptions (I'm discussing the things underlying Fully Homomorphic Encryption). Even these have been essentially fine (I have some personal quibbles with some assumptions used, though they are technically dense, and are not relevant to ML-KEM in the slightest). So this is to say that there are natural "easier instances" of the thing underlying ML-KEM, and there still haven't been successful attacks of those instances.

Anyway though, the question isn't "should you use pure ML-KEM rather than hybrid". I would personally suggest hybrid unless it is extremely limiting for some particular scenario (and there are scenarios, such as hardware, where it is). The question is "should we standardize how pure ML-KEM TLS works, so implementors can create interoperable implementations?".

The answer to this should (clearly) be yes. ML-KEM is boring, high-quality cryptography. If a quantum computer appeared tomorrow, and only ML-KEM protected me, I would not lose any sleep personally. Efforts to delay standardization rely on "arguments" that do not match reality in the slightest.

there is no indication there are similar papers. Curiously, the best lattice cryptanalysts in the world are chinese and european (here I'm thinking of people like Ducas, Albrecht, and Ding). It's actually a weird blindspot of american cryptography (this isn't true for all cryptanalysis, but in general European cryptography is "more concrete" vs "theoretical" american cryptography).

This isn't to say that it is impossible for the NSA to have their own private cryptanalysis. It is to say they're not some magical fairy that produces non-trivial attacks. They, like any other organization, need to develop talent. In the past they have been able to do this (they, through the CCR, hired Don Coppersmith in 2005. A VERY notable cryptanalyst at the time). I am unaware of any lattice cryptanalysts who have "gone dark" in a way similar to how Coppersmith did in ~2005.

Note that we also have theoretical reasons to be more confident in the hardness of ML-KEM. The reasons are technical (and worse than the practical reasons we have, namely people have iterated on attacks and the attacks stopped getting appreciably better). But it is (curiously) the hardness assumption we perhaps have the best (theoretical) justification for why it is hard.

Using RSA as a hedge would be incredibly stupid. Index calculus attacks were significantly improved in the 2010s, at least for small characteristic finite field DH. These improvements have only tangentially hit RSA. I've heard a integer factorization record holder directly say there's no real barrier to similar improvements hitting factoring. It hasn't been done, so it isn't "easy". But also people wouldn't be surprised if it was done. The record for binary characteristic finite field DH is ~30k bits (by an academic team. governments could throw more money at it of course).

this is not what I said before. As I mentioned in the post you replied to, there are certain scenarios (e.g. hardware) where pure ML-KEM has significant performance benefits. It instead should not be the default implementation suggestion.

if you blindly distrust the NSA, you should stop using x25519 immediately. It uses SHA2, which was solely developed by the NSA.

If DJB blindly distrusts the NSA, he would also recommend against SHA2. But he doesn't, and instead wants to mix a scheme developed by European academics with one built by the NSA. If you go by blind distrust, this should be extremely concerning.

Of course, I'm not suggesting you use blind distrust, and only pointing out that none of the blind distrust discourse makes any sense. We all trust SHA2, which was an explicit NSA product. Kyber had no NSA input. why is Kyber the NSA-suspect scheme?

you would make poor decisions then. McEliece recently (in the last month) had a large new attack against it

https://eprint.iacr.org/2026/1232

This doesn't hit classic McEliece yet, but is part of a line of work that Randriambololona has been doing, which are at a minimum very concerning for the security of McEliece.

this is entirely wrong. Lattice-based cryptography has been extremely well-studied theoretically and practically, even before standardization. For example, a (hybrid) lattice-based KEM was (experimentally) deployed in Chrome in 2016.

https://security.googleblog.com/2016/07/experimenting-with-p...

one or more decades were required to get good understanding of the relevant lattice problems. But they were introduced in

* the ~1990s, for NTRU, and * ~2005, for LWE, and * ~2012, for RWLE

ironically, of all of them LWE is probably understood the best (though our understanding of LWE, RLWE, and MLWE are all roughly similar now). This is because it is a problem more amenable to understanding than NTRU, which is (by comparison) a little more "ad hoc".

For lattice-based KEMs, we also have very strong understanding of things. Roughly, we were able to design the lattice-based KEMs based on our prior understanding of general KEMs. Concretely, we had a much better understanding of the precise details of the FO transform, which fed into teh design of lattice-based KEMs. So most lattice-based KEMs solely had to construct a lattice-based PKE. Doing so from LWE is fairly straightforward. Iirc since ~2005 there was a certain technique known, and then a more optimized technique was developed in ~2011. All lattice-based KEMs (that construct IND-CPA PKE -> FO Transform -> IND-CCA2 PKE) proceed with this ~2011 technique, with various internal knobs tweaked.

Post-standardization there has been some additional research into lattice-based KEMs, but they have (generally) been proceeding by tweaking the core ~2005 hardness assumption to try to get more efficiency. It's an interesting idea, but generally hardness assumptions take the longest time to gain confidence out of any part of a cryptographic algorithm (as they're the only unprovable part), so it might be a bit before we feel "safe" regarding them.

NTRU based schemes are not the most conservative. NTRU is an old design from the 90s, that had some shocking structural attacks against it appear ~2016. These attacks so far are only relevant for moduli q ~ (1/100) n^{2.3...}. This makes them worse than conventional attacks against NTRU-based PKE. But they completely killed roughly half of all NTRU-based fully homomorphic encryption schemes, and are a (major) structural issue with NTRU that RLWE/MLWE does not have.

In other words, Bernstein proposed a NTRU-based scheme under his theory it was the most conservative. The only major attacks on lattice-based schemes since his proposal have been on the hardness assumption his scheme uses. I would personally suggest this means that Bernstein is not an accurate predictor of the security of lattice-based schemes. So far his track record (with this notable example, but also many others) is remarkably bad.