Please use this identifier to cite or link to this item:
Title: Short redactable signatures using random trees
Authors: Chang, E.-C. 
Lim, C.L.
Xu, J.
Keywords: Privacy
Random tree
Redactable signature scheme
Issue Date: 2009
Citation: Chang, E.-C.,Lim, C.L.,Xu, J. (2009). Short redactable signatures using random trees. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5473 : 133-147. ScholarBank@NUS Repository.
Abstract: A redactable signature scheme for a string of objects supports verification even if multiple substrings are removed from the original string. It is important that the redacted string and its signature do not reveal anything about the content of the removed substrings. Existing schemes completely or partially leak a piece of information: the lengths of the removed substrings. Such length information could be crucial in many applications, especially when the removed substring has low entropy. We propose a scheme that can hide the length. Our scheme consists of two components. The first component H, which is a "collision resistant" hash, maps a string to an unordered set, whereby existing schemes on unordered sets can then be applied. However, a sequence of random numbers has to be explicitly stored and thus it produces a large signature of size at least (mk)-bits where m is the number of objects and k is the size of a key sufficiently large for cryptographic operations. The second component uses RGGM tree, a variant of GGM tree, to generate the pseudo random numbers from a short seed, expected to be of size O(k+tk logm) where t is the number of removed substrings. Unlike GGM tree, the structure of the proposed RGGM tree is random. By an intriguing statistical property of the random tree, the redacted tree does not reveal the lengths of the substrings removed. The hash function H and the RGGM tree can be of independent interests.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISBN: 9783642008610
ISSN: 03029743
DOI: 10.1007/978-3-642-00862-7_9
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Dec 10, 2018

Page view(s)

checked on Nov 17, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.