Abu Dhabi, UAE: 29 April 2022: Pairing-based cryptography is commonly used for constructing and analysing cryptographic protocols in blockchain and other use cases. A pairing is calculated between two input groups and a third output group as part of common public-key cryptographic protocols.
In a multi-party protocol, communications are encrypted and decoded using a combination of public and private keys. These cryptographic systems are designed to leverage the trust between parties that may not know each other. However, that trust can be misplaced. One concern is that a hacker could trick someone by sending them an unexpected and invalid input. By continuing to process this input, the victim may then unwittingly simplify the hacker’s task of discovering their secrets.
Over the years, cryptographers have developed various approaches for checking such inputs to ensure their validity. However, such tests can be quite time-consuming. Michael Scott, technical director at the Technology Innovation Institute, has found a more elegant solution that dramatically reduces processing time. It has already been integrated into various cryptography and blockchain libraries.
Scott said, “The paper was quite impactful – from being an improvement that impressed fellow academics to one that found immediate use in pairing-based applications, particularly in the context of blockchains”.
Checking for good input
Cryptography is protected by ensuring the use of a wide range of very large numbers. However, if someone is tricked into working with a smaller range of numbers, it becomes a trivial matter for attackers to try all the permutations to find the specific key.
In addition, many numbers may look large on the surface, so it is not immediately obvious if it is part of a smaller or larger range. For example, a number might look big, but there may only be one of 12 possible numbers. The attacker could then guess that your secret is one of 12 numbers so that he can try them all.
“You have inadvertently made the attacker’s problem a lot easier”, Scott said. So, validity checks need to be performed across the three groups of numbers that arise in pairing-based cryptography, commonly referred to as G1, G2, and GT. But the standard calculations required to vet the numbers presented in pairing-based protocols have a reputation for being slow. These delays can accumulate across multiple parties, as each must check for everything they receive.
The new technique provides the same level of security more quickly. It is twice as fast for performing checks in G1 groups and four times faster for performing checks in the G2 and GT groups.
“As a result, you know with the same certainty as the older, slower methods that the input you have received is valid and can be trusted”, Scott said.
An itch to scratch
Scott has been working on pairing-based cryptography for over 20 years and pointed out: “The mathematics of pairing-based cryptography is incredibly elegant. But the older methods for validating group membership were kludgy”.
Something kept bringing him back to the problem like it was an itch to scratch. Then one day, it struck him to approach the problem from a different angle.
The technique has already been incorporated into his open-source security library for other researchers to tinker with. He expects these results to percolate across the field in the long run and eventually make their way into the textbooks.
Further refinements could extend the technique to other types of curves used in pairing-based cryptography in the future. Scott said, “I like to leave a few threads hanging. Partly because I am lazy, but also because it gives PhD or post-doc students something to work with”.
To read the full paper, please visit: https://eprint.iacr.org/2021/1130.pdf
In addition, here are papers elaborating on the technique from teams in France and China who were “inspired by the method given by Scott”.
