TL;DR
This paper introduces a novel "short redactable signature" scheme called SRSS that allows for the verification of a document even after parts of it have been removed, crucially hiding the lengths of these removed sections. This is achieved by combining a new "collision-resistant" hash function with a randomized tree structure that possesses a unique "hiding property," overcoming limitations of previous methods that leaked information about removed data.
What Problem Does This Paper Address?
Imagine you have a digitally signed document, like a contract or a report. You want to share it with someone, but they shouldn't see certain parts. A "redactable signature" scheme allows you to remove those parts and still provide a valid signature for the remaining document. The challenge is that previous schemes often leaked information about what was removed, specifically the lengths of the removed sections. This leakage can be a privacy concern, especially if the removed content has predictable patterns (e.g., "Approved" vs. "Not Approved"). This paper tackles the problem of creating a redactable signature scheme that not only allows for redaction but also completely hides the lengths of the removed substrings.
Methods
The paper proposes a two-pronged approach:
- A "Collision-Resistant" Hash Function (H): This function maps a string and an auxiliary input to an unordered set. The key innovation here is that this hash function is designed to be "redactable" itself, meaning it can be efficiently updated when parts of the input string are removed. Crucially, it's also designed to be "privacy-preserving," ensuring that the redacted hash doesn't reveal information about the removed parts.
- RGGM: A Randomized Tree with a Hiding Property: To reduce the signature size, the paper introduces RGGM, a variant of the GGM tree. Unlike standard GGM trees, RGGM uses a randomized tree structure. This randomization is key: when parts of the tree (corresponding to removed substrings) are deleted, the structure of the remaining subtrees doesn't reveal the number of leaves that were removed. This "hiding property" is central to achieving privacy.
These two components are combined to form the RSS (Redactable Signature Scheme for Strings) and then further optimized into SRSS (Short Redactable Signature Scheme for Strings) by using RGGM to generate pseudo-random numbers, significantly reducing the signature size.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Hiding Substring Lengths is Tricky: The paper highlights that even simple requirements like hiding the length of removed data are difficult to achieve with existing cryptographic primitives.
- Randomized Trees for Privacy: The core insight is that by randomizing the structure of a tree used for generating pseudo-random numbers, one can achieve a surprising level of privacy. Deleting parts of a random tree doesn't reveal information about the deleted portions.
- Hash Functions as Building Blocks: The paper demonstrates how a carefully designed hash function can serve as a fundamental building block for constructing complex cryptographic schemes like redactable signatures.
- Trade-offs in Signature Schemes: The paper implicitly discusses the trade-off between signature size, computational efficiency, and the level of privacy achieved. RSS offers privacy but has a large signature; SRSS improves the signature size by leveraging RGGM.
Key Results
- RSS Scheme: A redactable signature scheme that hides the lengths of removed substrings, proven secure against chosen-message attacks and privacy-preserving under reasonable assumptions. However, it has a large signature size.
- SRSS Scheme: An optimized version of RSS that significantly reduces signature size by using the RGGM generator. The expected signature size is O(k + tk log m), where k is the security parameter, t is the number of removed substrings, and m is the number of objects. SRSS is also proven unforgeable and privacy-preserving.
- RGGM Generator: A novel pseudo-random number generator based on randomized trees, which has the property that the remaining structure after removing parts does not reveal information about the removed parts.
Limitations and Future Work
- Signature Size: While SRSS improves upon RSS, the signature size still depends on the number of removed substrings and the length of the original string. The paper notes that for unordered sets, constant-size signatures are achievable, and the larger size for strings is a price paid for ordering information.
- Computational Cost: Verification can be computationally intensive for long strings with many removed substrings.
- Future Work: The authors suggest exploring practical ways to organize strings hierarchically to improve speedup. They also note that the hash function H and the RGGM tree could be of independent interest for other cryptographic applications, such as transitive signatures or secure outsourced database systems.
Summary updated