[Resource Topic] 2018/054: More Efficient (Almost) Tightly Secure Structure-Preserving Signatures

Welcome to the resource topic for 2018/054

More Efficient (Almost) Tightly Secure Structure-Preserving Signatures

Authors: Romain Gay, Dennis Hofheinz, Lisa Kohl, Jiaxin Pan


We provide a structure-preserving signature (SPS) scheme with an (almost) tight security reduction to a standard assumption. Compared to the state-of-the-art tightly secure SPS scheme of Abe et al. (CRYPTO 2017), our scheme has smaller signatures and public keys (of about (56%), resp. (40%) of the size of signatures and public keys in Abe et al.'s scheme), and a lower security loss (of (O(\log Q)) instead of (O(\lambda)), where (\lambda) is the security parameter, and (Q=poly(\lambda)) is the number of adversarial signature queries). While our scheme is still less compact than structure-preserving signature schemes \emph{without} tight security reduction, it significantly lowers the price to pay for a tight security reduction. In fact, when accounting for a non-tight security reduction with larger key (i.e., group) sizes, the computational efficiency of our scheme becomes at least comparable to that of non-tightly secure SPS schemes. Technically, we combine and refine recent existing works on tightly secure encryption and SPS schemes. Our technical novelties include a modular treatment (that develops an SPS scheme out of a basic message authentication code), and a refined hybrid argument that enables a lower security loss of (O(\log Q)) (instead of (O(\lambda))).

ePrint: https://eprint.iacr.org/2018/054

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 .