Aumasson, Jean-PhilippeEndignoux, Guillaume2018-12-132018-12-132018-12-132018-01-0110.1007/978-3-319-76953-0_12https://infoscience.epfl.ch/handle/20.500.14299/152119WOS:000445246500012present several optimizations to SPHINCS, a stateless hash-based signature scheme proposed by Bernstein et al. in (2015): PORS, a more secure variant of the HORS few-time signature scheme used in SPHINCS; secret key caching, to speed-up signing and reduce signature size; batch signing, to amortize signature time and reduce signature size when signing multiple messages at once; mask-less constructions to reduce the key size and simplify the scheme; and Octopus, a technique to eliminate redundancies from authentication paths in Merkle trees. Based on a refined analysis of the subset resilience problem, we show that SPHINCS' parameters can be modified to reduce the signature size while retaining a similar security level and computation time. We then propose Gravity-SPHINCS, our variant of SPHINCS embodying the aforementioned tricks. Gravity-SPHINCS has shorter keys (32 and 64 bytes instead of approximate to 1 KB), shorter signatures (approximate to 30 KB instead of 41KB), and faster signing and verification for the same security level as SPHINCS.Computer Science, Software EngineeringComputer Science, Theory & MethodsComputer Sciencemerkle tree traversaldigital-signaturestimetext::conference output::conference proceedings::conference paper