[Resource Topic] 2019/1201: Efficient Redactable Signature and Application to Anonymous Credentials

Welcome to the resource topic for 2019/1201

Efficient Redactable Signature and Application to Anonymous Credentials

Authors: Olivier Sanders


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.

ePrint: https://eprint.iacr.org/2019/1201

Talk: https://www.youtube.com/watch?v=1HDkpyV0PbY

Slides: https://iacr.org/submit/files/slides/2020/pkc/pkc2020/103/slides.pdf

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .