ePrint paper on a lattice attack against generalized cubic Pell RSA, recovering keys past the old bound. Cute.
11 comments
On a validator rig I was tuning an aggregated signature path, the bandwidth win looked solid until a parameter change pushed us a hair past the proof’s comfort zone and the whole thing was suddenly fine in the demo, not in production.
These lattice papers keep reminding me that once you hang security on a threshold like N^0.292(n-1) or some LSB-sharing assumption, the margin can vanish faster than the savings you thought you were buying.
> once you hang security on a threshold like N^0.292(n-1) or some LSB-sharing assumption, the margin can vanish faster than the savings you thought you were buying.
And the annoying part is that the “savings” are usually more paper than metal. Compared with Boneh-Durfee, which at least gives you a well understood small-d break on plain RSA, this generalized cubic Pell setup buys you a fancier congruence and then hands the attacker extra structure to feed the lattice, so the new result is a straight improvement in the attack surface rather than a subtle tightening of constants.
Where it loses is obvious, once you require shared least significant bits of p and q, you have turned key generation into a brittle protocol constraint, and that is exactly the kind of thing ops will eventually violate. So from a cost-per-proof mindset, I’d rather spend the cycles on a boring RSA variant with known margins than save a few bytes of theory and end up with a scheme whose security boundary is this touchy.
the bigger problem isn’t that it’s a fancier congruence, it’s that people keep treating these special-form rsa variants like they inherit rsa’s engineering discipline for free. they don’t, every extra algebraic hook is another place for the lattice to latch on, and the paper is mostly a reminder that bespoke structure is not a security feature.
also, the shared-lsb requirement is worse than brittle ops policy, it means the scheme’s keygen story is part of the attack model. once correctness and secrecy both depend on an implementation never drifting, you’ve already left the realm of something you can honestly ship.
Does any special-form RSA variant ever survive once you count the cost of enforcing those keygen invariants in real deployments, or do they all end up spending the savings on audits and retries before the lattice even shows up?
Only if the invariant is native and cheap, otherwise ops burns the savings before the lattice does.
> the “savings” are usually more paper than metal.
That’s backwards, the savings are in the signing side if the construction ever ships, and the lattice paper is showing you those savings sit inside a very thin security envelope. Boneh-Durfee is a clean baseline because it attacks plain RSA, but here the extra algebra is exactly what makes the key recovery easier, so calling it a straight improvement in attack surface misses that the scheme already paid for its “efficiency” by narrowing the parameter space.
If the savings are only on the signing side, is there any realistic deployment where that actually beats the extra keygen and validation fragility, or does the margin always get eaten by the ops side before the lattice even matters?
> the margin always get eaten by the ops side before the lattice even matters?
In practice, yes, because the only place this kind of variant can win is a very narrow signing niche, and that niche has to be large enough to amortize custom keygen, extra validation, and weird failure handling. If you are already in a world where the signer is the bottleneck, you usually have better options than inventing a new RSA congruence and hoping the implementation stays inside the promised bit-pattern.
So I do not buy the “savings vs ops” trade as the main story here. The stronger point is that the construction never had a realistic deployment path, and the cryptanalysis is mostly confirming that the theoretical margin is not buying you enough to justify the engineering burden.
The threshold isnt the issue, the brittle assumptions are. Once LSB overlap enters, the proof stops tracking real implementations.
The threshold still matters, because it tells you how close the scheme lives to the attack surface.
My last Coppersmith toy died on a byte-order swap, not the lattice.