### Efficient Redactable Signature and Application to Anonymous Credentials

Olivier Sanders

##### Abstract

Let us assume that Alice has received a constant-size signature on a set of messages $\{m_i\}_{i=1}^n$ from some organization. Depending on the situation, Alice might need to disclose, prove relations about or hide some of these messages. Ideally, the complexity of the corresponding protocols should not depend on the hidden messages. In particular, if Alice wants to disclose only $k$ messages, then the authenticity of the latter should be verifiable in at most $O(k)$ operations. Many solutions were proposed over the past decades, but they only provide a partial answer to this problem. In particular, we note that they suffer either from the need to prove knowledge of the hidden elements or from the inability to prove that the latter satisfy some relations. In this paper, we propose a very efficient constant-size redactable signature scheme that addresses all the problems above. Signatures can indeed be redacted to remain valid only on a subset of $k$ messages included in $\{m_i\}_{i=1}^n$. The resulting redacted signature consists of 4 elements and can be verified with essentially $k$ exponentiations. Different shows of the same signature can moreover be made unlinkable leading to a very efficient anonymous credentials system.

Note: Following this publication, a new redactable signature scheme with a much shorter public key has been proposed in https://eprint.iacr.org/2020/856. As it has the same characteristics as the scheme presented here, it can be readily used to construct anonymous credentials with improved efficiency.

Available format(s)
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2020
Keywords
redactable signaturesanonymous credentials
Contact author(s)
olivier sanders @ orange com
History
2022-03-07: last of 5 revisions
See all versions
Short URL
https://ia.cr/2019/1201

CC BY

BibTeX

@misc{cryptoeprint:2019/1201,
author = {Olivier Sanders},
title = {Efficient Redactable Signature and Application to Anonymous Credentials},
howpublished = {Cryptology ePrint Archive, Paper 2019/1201},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/1201}},
url = {https://eprint.iacr.org/2019/1201}
}

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