Non-interactive editable signatures for assured data provenance

In order to make people truly benefit from data sharing, we need technical solutions to assuring the trustworthiness of data received from parties one may not have encountered in the past. Assured data provenance is an important means for this purpose because it (i) allows data providers to get credited for their contribution or sharing of data, (ii) is able to hold the data providers accountable for the data they contributed, and (iii) enables the data providers to supply high-quality data in a self-healing fashion. While the above (i) and (ii) have been investigated to some extent, the above (iii) is a new perspective that, to our knowledge, has not been investigated in the literature. In this paper, we introduce a novel cryptographic technique that can simultaneously offer these properties. Our technique is called editable signatures, which allow a user, Bob, to edit (e.g., replace, modify, and insert) some portions of the message that is contributed and signed by Alice such that the resulting edited message is jointly signed by Alice and Bob in some fashion. While it is easy to see that the above (i) and (ii) are achieved, the above (iii) is also achieved because Bob may have a better knowledge of the situation that allows him to provide more accurate/trustworthy information than Alice, who may intentionally or unintentionally enter inaccurate or even misleading data into an information network. This is useful because Alice's inaccurate or even misleading information will never be released into an information network if it can be "cleaned" or "healed" by Bob. Specifically, we propose two novel cryptographic constructions that can be used to realize the above functions in some practical settings.