Fakultät für Informatik und Mathematik


MIP 1201

Paper Description

BibTeX entry

author="H. Poehls, K. Samelin, J. Posegga, H. de Meer"
title="Length-Hiding Redactable Signatures from One-Way Accumulators in O(n)"
institution="Fakult{\"a}t f{\"u}r Informatik und Mathematik, Universit{\"a}t Passau",


In this paper, we propose two provably secure and length-hiding redactable signature schemes. Both have a runtime complexity of O(n). This is lower than existing schemes, which have at best O(n · log(n)). Our first scheme protects the integrity of the elements in unordered (multi-)sets, with a storage complexity of O(1). Our second construction protects the structural relation of ordering of elements in lists, with a storage complexity of O(n). We build on a family of quasi-commutative accumulators and a family of hash-functions based on non-abelian but associative operations.

Paper itself