Paper 2017/909

Clarifying the subset-resilience problem

Jean-Philippe Aumasson and Guillaume Endignoux

Abstract

We investigate the subset-resilience problem, defined in 2002 by Reyzin and Reyzin to analyze their HORS signature scheme. We show that textbook HORS is insecure against adaptive attacks, and present a practical attack based on a greedy algorithm. We also describe weak messages for HORS, that map to smaller subsets than expected, and are thus easier to cover. This leads to an improved attack against HORS and to an improved classical attack against the signature scheme SPHINCS, of complexity $2^{270}$ instead of $2^{277}$. We propose the PRNG to obtain a random subset construction (PORS), which avoids weak messages, for a tiny computational overhead. We adapt PORS to SPHINCS to also deterministically select the HORST instance that is used to sign the input message. This new construction reduces the attack surface and increases the security level, improving the security of SPHINCS by 67 bits against classical attacks and 33 bits against quantum attacks. A version of SPHINCS using our PORS construction can work with smaller parameters that reduce the signature size by 4616 bytes and speed up signature and verification, for the same 128-bit post-quantum security as the original SPHINCS.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
post-quantumsignatureshash functions
Contact author(s)
jeanphilippe aumasson @ gmail com
History
2017-09-25: revised
2017-09-24: received
See all versions
Short URL
https://ia.cr/2017/909
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/909,
      author = {Jean-Philippe Aumasson and Guillaume Endignoux},
      title = {Clarifying the subset-resilience problem},
      howpublished = {Cryptology ePrint Archive, Paper 2017/909},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/909}},
      url = {https://eprint.iacr.org/2017/909}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.