Protean Signature Schemes


Protean Signature Schemes


Stephan Krenn (AIT), Henrich C. Pöhls (UNI PASSAU), Kai Samelin (IBM Research Zurich), Daniel Slamanig (AIT)


We introduce the notion of Protean Signature schemes. This novel type of signature scheme allows to remove and edit signer-chosen parts of signed messages by a semi-trusted third party simultaneously. In existing work, one is either allowed to remove or edit parts of signed messages, but not both at the same time. Which and how parts of the signed messages can be modified is chosen by the signer. Thus, our new primitive generalizes both redactable (Steinfeld et al., ICISC ’01 & Brzuska et al., ACNS ’10) and sanitizable signatures schemes (Ateniese et al., ESORICS ’05 & Brzuska et al., PKC ’09). We showcase a scenario where either primitive alone is not sufficient. Our provably secure construction (offering both strong notions of transparency and invisibility) makes only black-box access to sanitizable and redactable signature schemes, which can be considered standard tools nowadays. Finally, we implemented our scheme and our evaluation shows that the performance is reasonable. If one is willing to drop the invisibility property, the run-time can be considered entirely practical.


Cryptology and Network Security - CANS 2018  (

Place and Date

Naples, Italy, Sep 30 - Oct 3, 2018