Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / redactable signatures, anonymous credentials

Original Publication (with minor differences): IACR-PKC-2020

Date: received 14 Oct 2019, last revised 28 Jan 2020

Contact author: olivier sanders at orange com

Available format(s): PDF | BibTeX Citation

Version: 20200128:152215 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]