Improving the Cryptanalysis of Lattice-Based Public-Key Algorithms

The winner of the Best Paper Award at Crypto this year was a significant improvement to lattice-based cryptanalysis.

This is important, because a bunch of NIST’s post-quantum options base their security on lattice problems.

I worry about standardizing on post-quantum algorithms too quickly. We are still learning a lot about the security of these systems, and this paper is an example of that learning.

News story.

Posted on February 14, 2024 at 7:08 AM10 Comments

Comments

Winter February 14, 2024 7:55 AM

I applaud giving interns a spot in the lime-lights (see author of news story).

But letting unpaid interns write a “major” article for a for-profit publication “raises my eye-brow”.

Clive Robinson February 14, 2024 9:36 AM

@ Bruce,

Re : Worries abound in those who have a little history in their rear view mirror.

“I worry about standardizing on post-quantum algorithms too quickly.”

It’s not just the unseemly haste that concerns me, it’s the fact that the NSA want to push a very non conservative algorithm without any fall back. No hybrid algorithms so “all in on betting the farm”.

It’s time to be cautious and have reasonable fall back and no time for rhinestone hat behaviours.

Mavek February 14, 2024 9:52 AM

The NSA types must be viewing this as the opportunity of a lifetime. While I think the threat to existing encryption techniques by quantum computers are real, I still think we are way off a point in time where they are a threat.

So we are in a time where the threat is being enhanced and the push to replace with other algorithms that don’t have the cryptanalysis eye run over them is the same. If I was trying to introduce a compromise to a system, I would be targeting the new one, rather than the old one.

A bold prediction, at least one quantum secure encryption technique will be picked that it will be found out to have a threat vector from at least the quantum space as more people learn and understand quantum algorithm, and maybe the classical space which will likely be a backdoor that was inserted.

MrC February 14, 2024 7:42 PM

@Mavek,

My understanding is that we have a couple options whose security is fairly well understood — McElice for encryption and Sphinx for signing — but people are so turned off by their bandwidth costs that they keep turning to less well understood options.

ResearcherZero February 14, 2024 9:52 PM

A legitimate concern too as some of the large vendors do some odd stuff with their implementations, until someone finds it, and then they might fix it.

‘https://media.ccc.de/v/hackerhotel-2024-82-crytocalypse-now-and-why-the-dutch-government-is-investing-so-much-in-post-quantum-crypto-already-

echo February 16, 2024 4:05 PM

I don’t know how this applies but found it a useful model whenever I think about standards bodies and standards. It’s not unique to government but I do find government documentation and standards and overall governance is a real pain. The UK has traditionally been very poor with governance and documentation. UKGOV and GCHQ pretty much freeload off the NSA when it comes to adopting industry standards. So much for engines of change and post Brexit sovereignty. (Eyeroll.)

I always liked how the old OpenGL Architectural review Board (OpenGL ARB) was set up and how OpenGL was specified and documented and taught. Good governance, documentation, and learning were baked in from the start. (Yes, I know the world has moved on and today it’s all about Khronos and Vulkan.) SGI retained a veto but the board was comprised of anyone who was anyone in manufacturing and development with smaller organisations and end users represented via board members.

This was during a different time when the market, and media and media organisation, and even politics was different to today and social media didn’t exist…

One element of specifications was the core functionality plus various levels of optional additional functions. And no you couldn’t call your implementation OpenGL unless it passed conformance tests and various criteria. That’s all fine and good but what gave OpenGL it’s real power (and something Microsoft utterly hated) was the extension mechanism. This allowed introducing vendor specific functionality which might be copied by other vendors and the best might find their way into a later iteration of the specification.

I strongly suspect most people will miss this but the makeup industry isn’t too dissimilar in operation. Some brands have a permanent collection. Whatever makes it to the permanent collection is going to stick around. That will be different from a one off seasonal range or attempts to expand the range in general. Like gets more complicated if you factor in formulas and colour palettes (which interact) and margins and market segmentation but generally nobody treads on anyone else toes or goes out of their way to wreck this model. Certification and market testing is not cheap and anyone thinking they know better then their clients can experience a very rude career defining moment.

I know people think graphics and makeup are frivolous but the underpinnings involves governance and standards which if they break can end in people dying, or billions being wiped off a companies value or it collapsing entirely. The shift from classic pipeline to shaders, and from animal testing to no animal testing were pretty major changes no different in concept from classical to quantum. There’s similar ragged ends and fallbacks and R&D spend ongoing in there. I guess the thing is how well they handle it.

cyntia Bell February 19, 2024 2:12 AM

Delve into the complexities of lattice-based cryptography! Share insights with your friend sporting a mountain tattoo. Consider discussing the implications of improved cryptanalysis on cybersecurity. Have you explored this field before?

Anonymous February 20, 2024 2:50 AM

In contrast to current conventional methods, lattice-based cryptography (LBC) is one of the best-analyzed areas of post-quantum crypto. The name derives from the fact that this crypto scheme is built on mathematical problems around lattices.

Z.Lozinski February 21, 2024 5:45 PM

Apple has just announced a new version of iMessage that uses Post-Quantum Cryptography (specifically Kyber, now ML-KEM) for key exchange. This looks like a significant piece of work over the last couple of years, and includes two academic reviews of the new PQ3 protocol.

https://security.apple.com/blog/imessage-pq3/

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.