### Shorter QA-NIZK and SPS with Tighter Security

Masayuki Abe, Charanjit S. Jutla, Miyako Ohkubo, Jiaxin Pan, Arnab Roy, and Yuyu Wang

##### Abstract

Quasi-adaptive non-interactive zero-knowledge proof (QA-NIZK) systems and structure-preserving signature (SPS) schemes are two powerful tools for constructing practical pairing-based cryptographic schemes. Their efficiency directly affects the efficiency of the derived ad- vanced protocols. We construct more efficient QA-NIZK and SPS schemes with tight security reductions. Our QA-NIZK scheme is the first one that achieves both tight simulation soundness and constant proof size (in terms of number of group elements) at the same time, while the recent scheme from Abe et al. (ASIACRYPT 2018) achieved tight security with proof size linearly depending on the size of the language and the witness. Assuming the hardness of the Symmetric eXternal Diffie-Hellman (SXDH) problem, our scheme contains only 14 elements in the proof and remains independent of the size of the language and the witness. Moreover, our scheme has tighter simulation soundness than the previous schemes. Technically, we refine and extend a partitioning technique from a recent SPS scheme (Gay et al., EUROCRYPT 2018). Furthermore, we improve the efficiency of the tightly secure SPS schemes by using a relaxation of NIZK proof system for OR languages, called designated-prover NIZK system. Under the SXDH assumption, our SPS scheme contains 11 group elements in the signature, which is shortest among the tight schemes and is the same as an early non-tight scheme (Abe et al., ASIACRYPT 2012). Compared to the shortest known non-tight scheme (Jutla and Roy, PKC 2017), our scheme achieves tight security at the cost of 5 additional elements. All the schemes in this paper are proven secure based on the Matrix Diffie-Hellman assumptions (Escala et al., CRYPTO 2013). These are a class of assumptions which include the well-known SXDH and DLIN assumptions and provide clean algebraic insights to our constructions. To the best of our knowledge, our schemes achieve the best efficiency among schemes with the same functionality and security properties. This naturally leads to improvement of the efficiency of cryptosystems based on simulation-sound QA-NIZK and SPS.

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2019
Keywords
Contact author(s)
abe masayuki @ lab ntt co jp
csjutla @ us ibm com
m ohkubo @ nict go jp
jiaxin pan @ ntnu no
aroy @ us fujitsu com
wangyuyu @ uestc edu cn
History
Short URL
https://ia.cr/2019/1284

CC BY

BibTeX

@misc{cryptoeprint:2019/1284,
author = {Masayuki Abe and Charanjit S.  Jutla and Miyako Ohkubo and Jiaxin Pan and Arnab Roy and Yuyu Wang},
title = {Shorter QA-NIZK and SPS with Tighter Security},
howpublished = {Cryptology ePrint Archive, Paper 2019/1284},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/1284}},
url = {https://eprint.iacr.org/2019/1284}
}

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