You are looking at a specific version 20200128:152215 of this paper. See the latest version.

Paper 2019/1201

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.

Metadata
Available format(s)
PDF
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
2019-10-15: received
See all versions
Short URL
https://ia.cr/2019/1201
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.