Redactable Signature Scheme for Tree-structured Data based on Merkle Tree

Shoichi Hirose, Hidenori Kuwakado

2013

Abstract

In 2008, Kundu and Bertino proposed a structural signature scheme for tree-structured data. A signature generated by the scheme is redactable: for given tree-structured data and its signature, it is possible to compute signatures of subtrees of the given tree without the secret signing key. Brzuska et al. formalized security requirements of such kind of redactable signature schemes. They also proposed a provably secure redactable signature scheme for tree-structured data using an ordinary signature scheme. This paper presents a new redactable signature scheme for tree-structured data using an ordinary signature scheme and a Merkle tree constructed by a keyed hash function such as HMAC. The proposed scheme assumes that the out-degree of each node in a tree is at most constant. It is also shown that the proposed scheme is provably secure under standard security assumptions of the underlying primitives. The proposed scheme first generates a digest of given tree-structured data based on the Merkle tree using the keyed hash function, and computes a single signature for the digest using the ordinary signature scheme. On the other hand, the total number of signatures required by previous provably secure schemes is at least as large as that of the nodes of the tree.

Paper Citation

in Harvard Style

Hirose S. and Kuwakado H. (2013). Redactable Signature Scheme for Tree-structured Data based on Merkle Tree . In Proceedings of the 10th International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2013) ISBN 978-989-8565-73-0, pages 313-320. DOI: 10.5220/0004507003130320

in Bibtex Style

@conference{secrypt13,
author={Shoichi Hirose and Hidenori Kuwakado},
title={Redactable Signature Scheme for Tree-structured Data based on Merkle Tree},
booktitle={Proceedings of the 10th International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2013)},
year={2013},
pages={313-320},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004507003130320},
isbn={978-989-8565-73-0},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 10th International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2013)
TI - Redactable Signature Scheme for Tree-structured Data based on Merkle Tree
SN - 978-989-8565-73-0
AU - Hirose S.
AU - Kuwakado H.
PY - 2013
SP - 313
EP - 320
DO - 10.5220/0004507003130320