New quantum computers have the potential to crack current cryptographic schemes. So, a wide variety of algorithms are being investigated as part of the US NIST competition for post-quantum cryptography. These are cryptographic schemes that are resistant to quantum attacks. One area that is actively being explored involves finding new ways to generate key pairs used in public key cryptography.
Hash-based signatures are quantum-resilient signature schemes that will play an essential role in the near future. Researchers at the Technology Innovation Institute, in collaboration with researchers from Universidade Federal de Santa Catarina (Brazil), Carleton University (Canada), and the University of Ottawa (Canada), have developed a more efficient implementation technique that can reduce signature sizes by 50% compared to some of the recent works.
Lucas Perin, Lead Cryptographer at the Cryptography Research Center of the Technology Innovation Institute (TII), said, “It is always interesting to find ways to compute these encodings faster. I think constant sum encoding could become a general replacement for the encodings used in state-of-the-art algorithms if we can do this well.”
The recent research explored how the encoding process in various hash-based signature schemes determines the costs for signing and verifying signatures. The investigations found that different parameters allow either for faster signing or faster verifying. Researchers also explored various strategies for using different parameters that affected the speed of generating signatures or verifying them.
Predicting the cost of these operations is essential in some applications. The new work could help develop more efficient schemes for signing or verifying documents and always at the same cost of compute.
Building on promising research
Public key signatures provide a way to authenticate a document or data set created by someone with a private key. The authenticity is vetted through a mathematical process involving a public key and a signature. This signature is generated by processing the document using the private key.
Digital signatures involve some overheads in both signing a document and vetting its authenticity. In some cases, a document may be signed once and then vetted by multiple parties, such as in determining that an individual made a specific web post. The data may be vetted only once in other cases, such as in a financial transaction.
One popular scheme used inside many prominent hash-based candidates is Winternitz signatures. A team of researchers recently developed a constant sum encoding technique based on this scheme to obtain signature verification at lower and predictable costs in exchange for increased key generation and signature verification costs. Perin refers to this new method as CKY after the researchers Jason Paul Cruz, Yoshio Yatani, and Y. Kaji, who were responsible for developing it.
The main advantage of the CKY technique is that it can pre-determine the number of hash iterations required for signature verification. This is important because signatures are usually computed once but verified many times later. The technique also eliminates the need for a checksum and allows greater customization.
“The solution proposed by CKY is very elegant, and we wanted to find ways to improve it,” Perin said.
More efficient signatures
The TII researchers along with their peers in Brazil and Canada developed a different algorithm for the encoding processing that can reduce the overall cost of the signature scheme compared to CKY. This algorithm helps lessen the total number of operations needed for signing and verifying data and the cost of key generation.
One additional benefit is that the new algorithm does not rely on a collision-resistant hash function – and therefore, promises to reduce the size of the signature while providing the same security level as the state-of-the-art WOTS+. “This means that our signatures are about half the size as they were when using the previous CKY technique for the same security level, allowing us to compare fairly with WOTS+,” Perin said.
Hash-based signature schemes commonly have a trade-off aspect of space vs. efficiency. One must choose between increasing compute resources for smaller signatures or increasing signature sizes to reduce CPU resources. The new algorithm allows one to choose larger sets of parameters for highly customizable schemes. One novelty of the proposal is the possibility of reducing the cost of the key generation, while the original proposal required a higher cost for doing so.
On the downside, the encoding process can become more expensive and may overshadow the expected gains of the proposal. “We found that our proposal is clearly not a general replacement for the original base-w encoding of the Winternitz scheme but can still perform better for some parameters,” Perin said.
Hash-based signature schemes will soon be essential tools to secure the internet and perform digital signatures worldwide. “Hopefully, this work may be a small step towards more efficient post-quantum digital signature designs,” Perin said.
