Redacting Data and Trusted Signatures

Redacting Data and Trusted Signatures

And, so we move into a world of digital signatures, and into a more trusted digital world. But, how do we redact data, but still be able to create a trusted signature for the redacted document:

In 2002, Johnson et al [1] outlined a signature scheme that supported redacted data with trusted signatures. Overall it used homomorphic signature methods, and outlined one that used a Merkle tree and the other using RSA:

The Merkle Tree approach has the advantage that redacted nodes which are neighbouring can be merged together into a single Merkle node but will lead to a large signature if there is not a great deal of redactions. While the Merkle Tree approach uses the fast ECDSA method for signing, the RSA method has much slower signing and thus is slow overall.

Naive signature method

So, let’s implement a naive signature method, and split a message into partitions (such as separated by spaces). We can then just sign each of the partitions, and where each partition has a count identifier. In the following, we have a message (m and which has n partitions:

Sig=Sig(H(n||ID))||Sig(H(ID||0||m_0))||…||Sig(H(ID||n||m_n))

and where “||” is appending data.

The following is the Golang code (based on code]) [here]:

// Code based on https://github.com/Romern/redactionschemes
package main

import (
	"crypto"
	"crypto/ecdsa"
	"crypto/elliptic"
	"crypto/rand"
	"fmt"
	"strings"

	"os"

	"github.com/Romern/redactionschemes"
)

func SplitIntoWords(s string) *redactionschemes.PartitionedData {
	var out redactionschemes.PartitionedData
	for _, v := range strings.Split(s, " ") {
		out = append(out, []byte(string(v)))
	}
	return &out
}

func main() {

	input_string := "This is a test"

	argCount := len(os.Args[1:])

	if argCount > 0 {
		input_string = string(os.Args[1])
	}

	private_key, _ := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)

	var sig redactionschemes.NaiveSignature

	var priv crypto.PrivateKey = private_key

	fmt.Printf("Private key: %s\n", private_key.D)

	fmt.Printf("Public key: %s, %s\n", private_key.X, private_key.Y)

	data_input := SplitIntoWords(input_string)

	incorrect_data := SplitIntoWords(input_string + "incorrect!")

	redacted_data := []int{0, 1} // Remove first and second word

	fmt.Printf("\nData input: %s\n", input_string)
	fmt.Printf("Data input: %v\n", data_input)
	fmt.Printf("Redacted data: %v\n", redacted_data)

	err := sig.Sign(data_input, &priv)

	if err == nil {

		//	sig_marshaled, _ := sig.Marshal()
		fmt.Printf("\nSuccessful signing %x\n", sig.BaseSignature)

		err = sig.Verify(data_input)

		if err == nil {

			fmt.Printf("Successful Verification\n")
		}

	}

	newSig, _ := sig.Redact(redacted_data, data_input)

	if err == nil {
		fmt.Printf("\nSuccessful redaction %x\n", sig.BaseSignature)

		redacted_strings, _ := data_input.Redact(redacted_data)

		err = newSig.Verify(redacted_strings)

		if err == nil {

			fmt.Printf("Successful Redaction\n")
		}

		err = sig.Verify(incorrect_data)

		if err != nil {

			fmt.Printf("Successful Checking against incorrect data\n")
		}
	}

}

And a sample run with the removal of the first and second word is [here]:

Private key: 7892691374776397176945990076229488440026840305224110851324294444637944082575
Public key: 32314589220251390072839399520370760737760658463312233535803805691986977178949, 109528457358308212075950073872281269974525244650952143209819196971919651796998

Data input: Dear Alice. This is my contact to you, and I believe this is correct
Data input: .[[68 101 97 114] [65 108 105 99 101 46] [84 104 105 115] [105 115] [109 121] [99 111 110 116 97 99 116] [116 111] [121 111 117 44] [97 110 100] [73] [98 101 108 105 101 118 101] [116 104 105 115] [105 115] [99 111 114 114 101 99 116]]
Redacted data: [0 1]

Successful signing 3045022049c1b591a23c13926af834f0954223fc08610e681968d84ff25f97c133ae52810221009e9a44efd6ee4ea7de0e9bfece3370bbc107f1f30bc100b1c1f230f68d5d685d
Successful Verification

Successful redaction 3045022049c1b591a23c13926af834f0954223fc08610e681968d84ff25f97c133ae52810221009e9a44efd6ee4ea7de0e9bfece3370bbc107f1f30bc100b1c1f230f68d5d685d
Successful Redaction
Successful Checking against incorrect data

Conclusion

The redaction of data is a natural part of our dissemination, and where there is private information. Thus redacted signatures allow data to be redacted, but still trusted.

Reference

[1] Johnson, R., Molnar, D., Song, D., & Wagner, D. (2002, February). Homomorphic signature schemes. In Cryptographers’ track at the RSA conference (pp. 244–262). Springer, Berlin, Heidelberg.