## Cryptology ePrint Archive: Report 2018/054

More Efficient (Almost) Tightly Secure Structure-Preserving Signatures

Romain Gay and Dennis Hofheinz and Lisa Kohl and Jiaxin Pan

Abstract: 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)$).

Category / Keywords: public-key cryptography / Structure-preserving signatures, tight security

Original Publication (with minor differences): IACR-EUROCRYPT-2018

Date: received 11 Jan 2018, last revised 20 Aug 2018

Contact author: rgay at di ens fr

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2018/054

[ Cryptology ePrint archive ]