Pass the hash for peace, love and security in the quantum computing age

Boffins smokin' idea to share parts of keys to cook quantum-proof crypto


Digital signatures, one of the fundamental parts of cryptography, may one day be threatened by quantum computers – so crypto-boffins are busy devising schemes that can survive a post-quantum world.

In a paper that's just landed at the International Association for Cryptologic Research, a group of UK and Belgian researchers are offering up a dig-sig scheme they reckon is a feasible offering for a post-quantum world.

As the paper notes, there are currently two research streams examining what to do if Shor's algorithm* ever arrives to render today's signatures crackable. On one hand, there's research into “quantum-safe” systems, which extend the historical “hard problems” approach to the future. Today's hard problem, factoring very large numbers*, is exactly what a quantum computer might achieve, so the quantum-safe system propose new, harder problems.

The second, which this paper explores, is a universal approach: an “unconditionally secure signature” (USS) scheme, uncrackable according to mathematical proofs.

There's a downside, however: USS systems are symmetrical, depending on secret key distribution; that means key distribution becomes a problem and a vulnerability, and most proposals to handle it depend on a trusted third party.

The need to pre-distribute keys disqualifies USS from everyday applications, but the authors argue its high security means it's worth the effort for high-value applications (for example, inter-bank channels).

The proposal from Ryan Amiri and Erika Andersson of Heriot-Watt University in Edinburgh, Aysajan Abidin of Belgium's KU Leuven and iMinds, and Petros Wallden of the University of Edinburgh, is to create a USS that does away with third party for key distribution – and doesn't need anonymous communication channels.

The neat idea in the impenetrable academic maths of the typical crypto-paper seems to be this one: to make the scheme work, Amiri et al propose that in a group of participants, the sender starts by sharing a set of hashes with everybody else.

Recipients then pass around “a random portion of the keys that they received from the sender”. The recipients can, therefore, share enough of the keys to assure each other the message is authentic, without revealing enough information to compromise the signature.

“A signature for a message is a vector of tags generated by applying the hash functions to the message”, the paper continues.

For questions of forging, transferability, and non-repudiation, we'll have to defer to those with sufficient mathematics to decipher the rest of the paper.

The authors claim that with respect to other USS schemes:

  • ”We require fewer trust assumptions – the protocol does not require a trusted authority.
  • ”Security in our scheme can be tuned independently of message size, resulting in shorter signature lengths.
  • Our scheme scales more efficiently (with respect to message size) in terms of the number of secret shared bits required.”

Nice to know the post-quantum world could still be protected, at least. ®

*Bootnote: Shor's algorithm is one of the seminal ideas of quantum computing. Published in 1994, it proposed how to use a quantum computer to find the prime factors of any number, faster than a classical computer. ®

**Correction: This sentence originally read "factoring very large prime numbers, and has been corrected. &reg,


Other stories you might like

  • Prisons transcribe private phone calls with inmates using speech-to-text AI

    Plus: A drug designed by machine learning algorithms to treat liver disease reaches human clinical trials and more

    In brief Prisons around the US are installing AI speech-to-text models to automatically transcribe conversations with inmates during their phone calls.

    A series of contracts and emails from eight different states revealed how Verus, an AI application developed by LEO Technologies and based on a speech-to-text system offered by Amazon, was used to eavesdrop on prisoners’ phone calls.

    In a sales pitch, LEO’s CEO James Sexton told officials working for a jail in Cook County, Illinois, that one of its customers in Calhoun County, Alabama, uses the software to protect prisons from getting sued, according to an investigation by the Thomson Reuters Foundation.

    Continue reading
  • Battlefield 2042: Please don't be the death knell of the franchise, please don't be the death knell of the franchise

    Another terrible launch, but DICE is already working on improvements

    The RPG Greetings, traveller, and welcome back to The Register Plays Games, our monthly gaming column. Since the last edition on New World, we hit level cap and the "endgame". Around this time, item duping exploits became rife and every attempt Amazon Games made to fix it just broke something else. The post-level 60 "watermark" system for gear drops is also infuriating and tedious, but not something we were able to address in the column. So bear these things in mind if you were ever tempted. On that note, it's time to look at another newly released shit show – Battlefield 2042.

    I wanted to love Battlefield 2042, I really did. After the bum note of the first-person shooter (FPS) franchise's return to Second World War theatres with Battlefield V (2018), I stupidly assumed the next entry from EA-owned Swedish developer DICE would be a return to form. I was wrong.

    The multiplayer military FPS market is dominated by two forces: Activision's Call of Duty (COD) series and EA's Battlefield. Fans of each franchise are loyal to the point of zealotry with little crossover between player bases. Here's where I stand: COD jumped the shark with Modern Warfare 2 in 2009. It's flip-flopped from WW2 to present-day combat and back again, tried sci-fi, and even the Battle Royale trend with the free-to-play Call of Duty: Warzone (2020), which has been thoroughly ruined by hackers and developer inaction.

    Continue reading
  • American diplomats' iPhones reportedly compromised by NSO Group intrusion software

    Reuters claims nine State Department employees outside the US had their devices hacked

    The Apple iPhones of at least nine US State Department officials were compromised by an unidentified entity using NSO Group's Pegasus spyware, according to a report published Friday by Reuters.

    NSO Group in an email to The Register said it has blocked an unnamed customers' access to its system upon receiving an inquiry about the incident but has yet to confirm whether its software was involved.

    "Once the inquiry was received, and before any investigation under our compliance policy, we have decided to immediately terminate relevant customers’ access to the system, due to the severity of the allegations," an NSO spokesperson told The Register in an email. "To this point, we haven’t received any information nor the phone numbers, nor any indication that NSO’s tools were used in this case."

    Continue reading

Biting the hand that feeds IT © 1998–2021