### More Efficient (Almost) Tightly Secure Structure-Preserving Signatures

Romain Gay, Dennis Hofheinz, 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)$$).

Available format(s)
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2018
Keywords
Structure-preserving signaturestight security
Contact author(s)
rgay @ di ens fr
History
2018-08-20: last of 2 revisions
See all versions
Short URL
https://ia.cr/2018/054

CC BY

BibTeX

@misc{cryptoeprint:2018/054,
author = {Romain Gay and Dennis Hofheinz and Lisa Kohl and Jiaxin Pan},
title = {More Efficient (Almost) Tightly Secure Structure-Preserving Signatures},
howpublished = {Cryptology ePrint Archive, Paper 2018/054},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/054}},
url = {https://eprint.iacr.org/2018/054}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.