Welcome to the resource topic for 2022/778
Title:
SPHINCS+C: Compressing SPHINCS+ With (Almost) No Cost
Authors: Eyal Ronen and Eylon Yogev
Abstract:The SPHINCS+~[CCS '19] proposal is one of the alternate candidates for digital signatures in NIST’s post-quantum standardization process. The scheme is a hash-based signature and is considered one of the most secure and robust proposals. The proposal includes a fast (but large) variant and a small (but costly) variant for each security level. The main problem that might hinder its adoption is its large signature size. Although SPHICS+ supports a tradeoff between signature size and the computational cost of the signature, further reducing the signature size (below the small variants) results in a prohibitively high computational cost for the signer (as well as the verification cost). This paper presents several novel methods for further compressing the signature size while requiring negligible added computational costs for the signer and faster verification time. Moreover, our approach enables a much more efficient tradeoff curve between signature size and the computational costs of the signer. In many parameter settings, we achieve small signatures and faster running times simultaneously. For example, for 128-bit security, the small signature variant of SPHINCS+ is 7856 bytes long, while our variant is only 6304 bytes long: a compression of approximately 20% while still reducing the signer’s running time. The main insight behind our scheme is that there are predefined specific subsets of messages for which the WOTS+ and FORS signatures (that SPHINCS+ uses) can be compressed and made faster (while maintaining the same security guarantees). Although most messages will not come from these subsets, we can search for suitable hashed values to sign. We sign a hash of the message concatenated with a counter that was chosen such that the hashed value is in the subset. The resulting signature is both smaller and faster to sign and verify. Our schemes are simple to describe and implement. We provide an implementation and benchmark results.
ePrint: https://eprint.iacr.org/2022/778
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .