Oh no, you're thinking, yet another cookie pop-up. Well, sorry, it's the law. We measure how many people read us, and ensure you see relevant ads, by storing cookies on your device. If you're cool with that, hit “Accept all Cookies”. For more info and to customize your settings, hit “Customize Settings”.

Review and manage your consent

Here's an overview of our use of cookies, similar technologies and how to manage them. You can also change your choices at any time, by hitting the “Your Consent Options” link on the site's footer.

Manage Cookie Preferences
  • These cookies are strictly necessary so that you can navigate the site as normal and use all features. Without these cookies we cannot provide you with the service that you expect.

  • These cookies are used to make advertising messages more relevant to you. They perform functions like preventing the same ad from continuously reappearing, ensuring that ads are properly displayed for advertisers, and in some cases selecting advertisements that are based on your interests.

  • These cookies collect information in aggregate form to help us understand how our websites are being used. They allow us to count visits and traffic sources so that we can measure and improve the performance of our sites. If people say no to these cookies, we do not know how many people have visited and we cannot monitor performance.

See also our Cookie policy and Privacy policy.

This article is more than 1 year old

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,

Similar topics

TIP US OFF

Send us news


Other stories you might like