Signature Redaction (Johnson-Merkle)With a redactable signaure, we can removed elements of the data and still create a valid signature that can be checked. For the example, the message is "Alice. This is my contact to you, and I believe this is correct". We will produce a signature for each of the words, and then redact the first word, and regenerate a redacted signature: |
Method
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. For this we can use a Merkle Tree approach that uses the fast ECDSA method for signing.
Overall, it uses a GGM (Goldreich, Goldwasser and Micali) tree [2] and where a pseudorandom value related to at each of the leaves - and working down the tree. Next, we create the root hash by working up the tree. Figure 1 outlines a message \(x\), and which has \(n\) words (aka symbols). With this, we have a message \(x\) of words (\(x000\), \(x001\), . . . , \(x111\)). We first create k-values by moving down the tree with the random value (\(G\)). Next the v-values by recursing up through the tree to give \(H\). In the last step, we sign \(v\) using a conventional signature method.
Figure 1: Merkle-Johnson method [1]
The following is the Golang code (based on code]):
// Code based on https://github.com/Romern/redactionschemes package main import ( "crypto" "crypto/ecdsa" "crypto/elliptic" "crypto/rand" "fmt" "strings" "os" "encoding/json" "github.com/Romern/redactionschemes" ) //StringToPartitionedData partitions a string s word-wise func StringToPartitionedData(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 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 := StringToPartitionedData(input_string) incorrect_data := StringToPartitionedData(input_string + "test") redacted_data := make([]int, 1) redacted_data[0] = 0 // first word var sig redactionschemes.JohnsonMerkleSignature fmt.Printf("\nData input: %s\n", input_string) fmt.Printf("Data input: %v\n", data_input) fmt.Printf("Redacted data: %v\n", redacted_data) var priv crypto.PrivateKey = private_key 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 { r, _ := newSig.Marshal() var v map[string]string _ = json.Unmarshal([]byte(r), &v) fmt.Printf("\nSuccessful redaction %x\n", v["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 word is:
Private key: 89395459608785498343782051775121378612653296761552734416939400533027650656999 Public key: 43451700981256044358125656299851329227533031662320871029541768138073863488454, 86455138277885457045217693891544142428138817743049933559782184157800119470341 Data input: Alice. This is my contract to you, and I believe this is correct. Data input: .[[65 108 105 99 101 46] [84 104 105 115] [105 115] [109 121] [99 111 110 116 114 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 46]] Redacted data: [0] Successful signing 3045022100fa05ed9538f2c1e086115c1a1f07c1c1f22ea55e3f3dcdf99c178d30ec8b5f6702207d140430db288d9454967bea924ea70a28077a149c2439011cf9d3098b328261 Successful Verification Successful redaction 4d45554349514436426532564f504c423449595258426f66423848423869366c586a38397a666d6346343077374974665a774967665251454d4e736f6a5a52556c6e76716b6b366e43696748656853634a446b4248506e5443597379676d453d Successful Redaction Successful Checking against incorrect data
References
[1] Johnson, R., Molnar, D., Song, D., & Wagner, D. (2002, February). Homomorphic signature schemes. In Topics in Cryptology—CT-RSA 2002: The Cryptographers’ Track at the RSA Conference 2002 San Jose, CA, USA, February 18–22, 2002 Proceedings (pp. 244-262). Berlin, Heidelberg: Springer Berlin Heidelberg.
[2] Goldreich, O., Goldwasser, S., & Micali, S. (1986). How to construct random functions. Journal of the ACM (JACM), 33(4), 792–807.