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. ®,