Modification tolerant signature schemes: location and correction

Classical digital signature schemes (CDSS) are used to guarantee that a document was created by the sender (authenticity) and has not been modified along the way (integrity); they also help to prevent the signer from claiming s/he did not sign a message (non-repudiation). The verification algorithm has a boolean output: a successful outcome is achieved if and only if both the signature is valid and the document has not been modified. In this paper, we consider more general digital signature schemes which we call modification-tolerant signature schemes (MTSS), which go beyond the ability of detecting modifications provided by CDSS, and have the ability of locating modifications or locating and correcting modifications. We discuss two types of modification-tolerant signature schemes: a general MTSS that allows the location of modified blocks of the data, and an MTSS with correction capability, that allows the correction of the modified blocks, recovering the original message. We give three instantiations of the scheme for the purpose of location, correction, and redaction.

In which situations can modifications be allowed or even desired in the context of digital signatures? One situation where modifications are desirable is the so-called redactable signatures [13], also called content extraction signatures [21]. In redactable signature schemes [13, 18, 21], some blocks of a document are redacted (blacked out) for privacy purposes, without interacting with the original signer and without compromising the validity of the signature. Related to these are the “sanitizable” signatures introduced by Ateniese et al. [1] which are also used for the purpose of privacy of (parts of) the original message, but the modifications are done by a semi-trusted third party (the sanitizer) who can modify blocks of the document and sign the modified version, without the need of intervention by the original signer. Thus, in both redactable and sanitizable signature schemes, the privacy of the (redacted or modified parts of the) original message must be preserved. For MTSS, privacy of the original data that has been modified is not required. An MTSS with only location capability that guarantees privacy can be used for implementing redactable signatures, but that is not an intrinsic requirement for MTSS. Indeed, as pointed out in [18] the scheme provided in [12] does not meet standard privacy requirements. In the case of MTSS with correction capability, privacy cannot be guaranteed by definition, since the method permits the recovery of the original document.

A different scenario where a moderate amount of modification is desirable involves collaborative work. The authors of a document can use MTSS to allow further modifications as long as the original parts can be identified as their own. Other collaborators may apply modifications to the original document and append the original document’s signature, which provides information about which blocks were modified, as well as a guarantee of integrity of the original blocks. MTSS can separate the original blocks from the modified ones, while correction capability further provides retrieval of the original version of the document.

Locating modifications has also been considered in situations where modifications are not desired, but their localization is used as a mechanism to mitigate damage. Indeed, in the context of message authentication codes for data structures, Goodrich et al. [11] propose a message authentication code (MAC) with modification locating capabilities. They propose their use in data forensics applications since the identification of which information was modified can be used to identify the perpetrator of the crime (for example: the salary of a person or the grade of a student was modified on a database). In [12], in the context of MTSS with only location capability, the authors mention the advantage of being able to guarantee the integrity of part of the data instead of the all-or-nothing situation given by a CDSS boolean outcome. For example, the integrity of 95% of a document or database may contain enough information needed for a specific application, whereas it would have been considered completely corrupted and unusable in the case of CDSS. In the case of MTSS with correction capability, we can go beyond mitigating the damage, and actually recover the originally signed document.

The mechanism behind the MTSS schemes instantiated here, like in [11, 12], is the use of cover-free families (CFF) in the same way as it is traditionally employed in combinatorial group testing. Combinatorial group testing has been used in cryptography in the context of digital signatures [23], broadcast communication [8, 20], and many others. The main idea is to test $t$ groups, which are subsets of the $n$ blocks, together (with enough redundancy and intersections between groups), and each group is used to produce a distinct hash. The tuple of $t$ hashes is then signed and provided that no more than $d$ blocks were modified, it is possible to identify precisely which blocks have been modified. The main efficiency concern is the compression ratio: the order of growth of $n/t$ as $n$ grows, for a fixed modification tolerance $d$. Using cover-free families, it is possible to achieve a compression ratio of $O(n/(d^{2}\log n))$, which is not much worse than the $O(n)$ compression ratio given by modification intolerant schemes such as CDSS.

First, we extend methods that use cover-free families for modification location [11, 12] to further provide modification correction (Scheme 2 in Section 4.2), provided that the size of the blocks are small enough, say bounded by a constant $s$ where an algorithm with $2^{s}$ steps can run in an acceptable amount of time. In short, the localization of the modified blocks is done using CFF similarly to [11, 12] with an extra constraint on blocks of size at most $s$, and an exhaustive search is used to correct the block to a value that makes the concatenation of a specific group of blocks match its original hash. The assumption that a collision resistant hash function does not cause collisions for messages of small size up to $s$ is not only reasonable, but can be tested before employing it in the method.

Second, we propose a variation of the scheme for modification location to ensure total privacy of the modified blocks in order to extend it for the purpose of redactable signatures (Scheme 3 in Section 6). In this case, a block modification can be a redaction to hide private information. Unlike the modification correction scheme, this scheme does not need a restriction on block size.

The idea of error detection and correction of corrupted data is well established in coding theory. Combinatorial group testing can help locating where errors (modification of data) occurred, which can be considered an intermediate goal, which is stronger than error detection and more efficient than error correction. In the context of cryptography, localization of modified portions of data has been studied in the context of hash functions [4, 5], digital signatures [3, 12], and message authentication codes [7, 11]. Correction of modifications is proposed by some schemes, but they have severe limitations on the correction capability [3, 7]. Schemes such as the ones in [4, 5, 11, 12] use techniques related to cover-free families to generate redundant information, which is used later to locate the modified portions of the data. The benefit of cover-free families is that they require a small amount of redundant data for a fixed threshold $d$ in location capability.

The methods that provide location at the hash level [4, 5] are based on superimposed codes, which are binary codes equivalent to $d$-cover-free families ($d$-CFF). These codes are used in two steps of the process: to generate a small set of hash tags from an input message, and to verify the integrity of the message using these tags. Because of the $d$-CFF property, the scheme allows the identification of up to $d$ corrupted data segments [4, 5]. A digital signature scheme with location of modifications is presented in [12]. Their scheme uses $d$-CFF matrices to generate a digital signature scheme that carries extra information for location of modifications. In this case, data is divided into $n$ blocks which are concatenated and hashed according to the rows of the $d$-CFF. This set of hash values is signed using any classical digital signature algorithm, and both the signature and the set of hashes form the new signature of the message. The verification algorithm uses this information to precisely locate up to $d$ blocks that contain modified content [12]. This is presented in detail in Section 4.2 as Scheme 1. In [11], the authors propose a solution for locating the items that were modified inside a data structure. They compute a small set of message authentication tags based on the rows of a $d$-disjunct matrix, which is equivalent to $d$-CFFs. These tags are stored within the topology of the data structure, and an auditor can later use these tags to determine exactly which pieces of data were modified and perform forensics investigation.

The methods described above have a common approach: they all compute extra integrity information based on combinatorial group testing techniques and use this information to locate up to $d$ modified pieces of data. In our work, we show that if these pieces are small enough, it is possible to actually correct them to the originally-signed values. In the literature, we find signature and message authentication schemes that provide the correction of modifications, such as in [3, 7]. These schemes use different approaches than the ones previously discussed, and the capacity of location and correction is very limited. In [3] only a single error can be corrected, while in [7] the data is divided into blocks, and only one bit per block can be corrected.

Error correcting codes ($d$-ECC) are related to this work, as we could use them to provide authentication and correction of $d$ modifications as we explain next. For a message $m$ formed by blocks of up to $\log_{2}q$ bits each, sign it using a CDSS and compute the corresponding codeword $c_{m}$ using a $d$-ECC over alphabet $q$. Send the codeword $c_{m}$ and the signature $\sigma$. The receiver obtains $c^{\prime}$, which may differ from $c_{m}$ in at most $d$ blocks, and by decoding $c^{\prime}$, obtains $c_{m}$ and thus the original message $m$. Then, the verifier can check its authenticity and integrity by verifying $(m,\sigma$). We call this scheme Scheme E. In Section 4.3, we compare Scheme E and Scheme 2 using $d$-CFF, and find that they have very similar compression ratios. Scheme 2 has the advantage of giving more information in the failing case, of being more efficient when we do not need correction, and of being a simple variation of Schemes 1 and 3, facilitating comparison among the different approaches.

There is also a solution proposed in [2] for location of modifications in images with digital signatures, using a different approach than $d$-CFFs. Their scheme consists of partitioning the image into $n$ blocks, and generating one digital signature per block (with dependency on neighbours to avoid attacks). Although we can use signature schemes with very small signature sizes, the total number of signatures in this scheme is linear with the number of blocks $n$, while in [12], for example, the amount of extra information produced is logarithmic in $n$ because of the $d$-CFF.

Redactable or content extraction digital signatures [6, 13, 21] are used when the owner of a document signed by another party, needs to show parts of that document to a third party, but wants to keep parts of the document private. In Section 6, we give a variation of an MTSS scheme that implements redactable signatures. More on related work involving redactable signatures is discussed in that section.

Here we propose an MTSS that allows the modification of any set of up to $d$ blocks in the message, for a constant $d$ which we call a tolerance level. In other words, the authorized modification structure is $\mathcal{S}=\{T\subseteq\{1,\ldots,n\}:|T|\leq d\}$. To obtain a compact signature size, we rely on combinatorial group testing, which we summarize in Section 4.1 before we describe the scheme in Section 4.2. Similar modification location methods based on combinatorial group testing have been proposed in [11, 12], and the instantiation we propose for the first three algorithms of MTSS (Section 4.2) are based on [12]. Our new contributions in this section include proof of security for the MTSS scheme based on cover-free families and the addition of error correction capability by proposing algorithm MTSS-Verify&Correct that corrects modifications in this context.

In this section, we present the security proof of $d$-MTSS for Schemes 1 and 2. In order to do this, we need to check that the security of the hash function $h$ and the unforgeability of the underlying CDSS can together ensure unforgeability of $d$-MTSS. Note that although Scheme 1 appeared in [12], no security proof has been given in that paper. For the next proof we assume a collision-resistant hash function, i.e. a hash function in which a collision cannot be efficiently found [22].

When we consider $d$-MTSS using $d$-CFFs, a valid $(m,\sigma)$ as in Definition 5 implies that there exists $m^{\prime}$ such that $\sigma$ is an output of MTSS-Sign($m^{\prime},SK$) and $|\text{diff}(m,m^{\prime})|\leq d$. In the next theorem we suppose there is a valid $(m,\sigma)$ as a forgery to our scheme. We consider two types of forgery: a strong forgery consists of $(m,\sigma)$ such that MTSS-Verify($m,\sigma,PK$) = $(1,I),|I|\leq d$; a weak forgery consists of $(m,\sigma)$ such that MTSS-Verify($m,\sigma,PK$) = $(1,\emptyset)$.

Now we turn our attention to using MTSS in general and using similar algorithms to our proposed $d$-MTSS for redactable signature schemes. Redactable and sanitizable signature schemes allow for parts of a message to be removed or modified while still having a valid signature without the intervention of the signer. Sanitizable signatures usually requires the existence of a semi-trusted party called the sanitizer who is entrusted to do the modifications and recomputation of the signature, in some schemes done in a transparent way (see [18]). Our proposed scheme does not deal with sanitizable, but rather with redactable signatures.

Redactable signatures have been proposed in several variants also under the names of content extraction signatures [21] and homomorphic signatures [13]. Redactable signature schemes (RSS) “allow removing parts of a signed message by any party without invalidating the respective signature” [6] and without interaction with the signer. In [21], the authors mention content extraction for privacy protection or bandwidth savings. Suppose Bob is the owner of a document signed by Alice and does not want to send the whole document to a third verifying party Cathy but only some extracted parts of the document; however, Cathy still needs to verify that Alice is the signer of the original document. Alice is agreeable with future redactions when she signed the document. An example given in [21] is that Bob has his university transcripts signed by the issuing university (Alice) and wants to submit the transcripts to a prospect employer (Cathy) without revealing some of his private information such as his date of birth. Cathy must be able to verify that the signature came from the university in spite of the redaction. In addition to the privacy application, content extraction can be used in a similar way when only part of a large document needs to be passed by Bob to Cathy for the purpose of reducing the communication bandwidth [21].

The notion of redactable signatures we consider next is in line with our general definition of MTSS, but differs in that we add another algorithm called MTSS-Redact and we require total privacy of the redacted parts. We give next a $d$-MTSS version that is redactable based on ideas similar to Scheme 1 but modifying it to guarantee total privacy of redacted blocks. As mentioned in [18], the scheme proposed in [12] which was presented as Scheme 1 does not meet standard privacy requirements and in particular leaks the original message’s hash value. The scheme we propose below addresses this issue by individually signing each of the hashes of the groups of blocks, and at the time of redaction of blocks, also redacting from the signature tuple any hashes involving concatenations of the modified blocks. To avoid more complex forms of forgery, that could take advantage of combining individual signatures of concatenations coming from different signed messages, we add the same random string to the various hashes of concatenations to link the individual parts that are signed at the same time; in addition, to avoid reordering of blocks within the same message via reordering the groups, we add a group counter to these hashes before signing.

In the description below, a redaction is represented by the symbol $\blacksquare$.

The scheme requires an underlying CDSS $\Sigma$, a public hash function $h$, a $d$-CFF($t,n$) matrix $\mathcal{M}$ and a random number generator rand. The algorithms are given next:

• •

  MTSS-KeyGeneration$(\ell)$: generates a key pair ($SK,PK$) using algorithm
  $\Sigma$.KeyGeneration$(\ell)$.

• •

  MTSS-sign($m,SK$): Takes as input $SK$ and a message $m=(m[1],\ldots,m[n])$, and proceeds as follows.

  1. 1.

     Calculate $h_{j}=h(m[j]),1\leq j\leq n$. Compute a random string $r=$rand().

  2. 2.

     For each $1\leq i\leq t$, compute $c_{i}$ as the concatenation of all $h_{j}$ such that $\mathcal{M}_{i,j}=1,1\leq j\leq n$, and set $T[i]=h(c_{i})||r||id(i,t+1)$, where $id(i,t+1)$ encodes the numbers $i$ and $t+1$.

  3. 3.

     Compute $h^{*}=h(m)$, set $T[t+1]=h^{*}||r||id(t+1,t+1)$ and set $T=(T[1],\ldots,T[t+1])$.

  4. 4.

     Calculate $\sigma^{\prime}[i]=\Sigma$.Sign($T[i],SK$), for each $1\leq i\leq t+1$ and set $\sigma^{\prime}=(\sigma^{\prime}[1],\sigma^{\prime}[2],\ldots,\sigma^{\prime}[t+1])$. Output signature $\sigma=(\sigma^{\prime},r)$.

• •

  MTSS-verify($m,\sigma,PK$): takes as input a message $m=(m[1],\ldots,m[n])$, a signature $\sigma=(\sigma^{\prime},r)$, and a public key $PK$, and proceed as follows.

  1. 1.

     Check if $\Sigma$.Verify$(h(m)||r||id(t+1,t+1),\sigma^{\prime}[t+1],PK)=1$. Stop and output $(1,\emptyset)$ if that is the case; continue otherwise.

  2. 2.

     Use $\mathcal{M}$, $m$, $r$ and do the same process as in steps 1-3 of MTSS-sign to produce tuple $T^{\prime}=(T^{\prime}[1],\ldots,T^{\prime}[t])$.

  3. 3.

     For each $1\leq i\leq t$ such that $\Sigma$.Verify$(T^{\prime}[i],\sigma^{\prime}[i],PK)=1$, compute the set of indices of intact blocks $V_{i}=\{j:\mathcal{M}_{i,j}=1\}$ and do $V=V\cup V_{i}$. Compute $I=\{1,\ldots,n\}\setminus V$. Output $(1,I)$ if $|I|\leq d$; output $0$ otherwise.

• •

  MTSS-redact($m,\sigma,R$): takes as input a message $m=(m[1],\ldots,m[n])$, a signature $\sigma=(\sigma^{\prime},r)$, and a set $R\subseteq\{1,\ldots,n\}$ of blocks to be redacted, with $|R|\leq d$, and proceeds as follows.

  1. 1.

     If $R=\emptyset$, then stop and output $(m,\sigma)$.

  2. 2.

     Create copies of the message and signature: $\overline{m}=m$, $\overline{\sigma}={\sigma}$, so that $\overline{\sigma}=(\overline{\sigma}^{\prime},r)$.

  3. 3.

     Set $\overline{\sigma}^{\prime}[t+1]=\blacksquare$.

  4. 4.

     For each $j\in R$: set $\overline{m}[j]=\blacksquare$ and for each index $i$ such that $\mathcal{M}_{i,j}=1$ set $\overline{\sigma}^{\prime}[i]=\blacksquare$

  5. 5.

     Output $(\overline{m},\overline{\sigma}=(\overline{\sigma}^{\prime},r))$.

The correctness of the first three algorithms follows similar reasoning using the CFF properties as argued in Theorem 4.2, taking into account the different approach used here where $t$ CDSS signatures and $t$ CDSS verifications are required. The redaction offers total privacy in the sense of information theory, as no information related to the redacted blocks is kept in the signature, which are erased in steps 3 and 4 of MTSS-redact. The redacted blocks and redacted parts of the signature will only affect the verification of the parts of the signatures involving redacted blocks; all other block indices will be indicated as unmodified in the output of line 3 of MTSS-verify, as long as no more than $d$ blocks have been redacted.