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.

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.