Paper 2019/1144

Rerandomizable Signatures under Standard Assumption

Sanjit Chatterjee and R. Kabaleeshwaran


The Camenisch-Lysyanskaya rerandomizable signature (CL-RRS) scheme is an important tool in the construction of privacy preserving protocols. One of the limitations of CL-RRS is that the signature size is linear in the number of messages to be signed. In 2016, Pointcheval-Sanders introduced a variant of rerandomizable signature (PS-RRS) scheme which removes the above limitation. However, the security of PS-RRS scheme was proved under an interactive assumption. In 2018, Pointcheval-Sanders improved this to give a reduction under a parameterized assumption. In 2012, Gerbush et al.\ introduced the dual-form signature technique to remove the dependency on interactive/parameterized assumption. They applied this technique on the CL-RRS scheme (for single message) and proved its unforgeability under static assumptions instead of the interactive assumption used in the original work but in the symmetric composite-order pairing setting. In this work, we realize a fully rerandomizable signature scheme in the prime order setting without random oracle based on the SXDH assumption. The signature structure is derived from Ghadafi's structure-preserving signature. We first apply the dual-form signature technique to obtain a composite-order variant, called \texttt{RRSc}. A signature in \texttt{RRSc} consists of only two group elements and is thus independent of the message block length. The security of the proposed scheme is based on subgroup hiding assumptions. Then we use the dual pairing vector space framework to obtain a prime-order variant called \texttt{RRS} and prove its security under the SXDH assumption.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. INDOCRYPT 2019
Rerandomizable signatureStandard assumptionDual-form signature techniqueSubgroup Hiding assumption.
Contact author(s)
kabaleeshwar @ iisc ac in
2019-10-03: received
Short URL
Creative Commons Attribution


      author = {Sanjit Chatterjee and R.  Kabaleeshwaran},
      title = {Rerandomizable Signatures under Standard Assumption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1144},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.