Reactable Signatures using A Naive Approach and The Johnson-Merkle Method
Reactable Signatures using A Naive Approach and The Johnson-Merkle Method
A story of (Boris) Johnson and (Robert) Johnson
Preface
Before I start, I must say that Boris Johnson is not a cryptographer! The Johnson referred to in this article is related to Rob Johnson [here], and Merkle is not Angela Merkel, but the mighty Ralph Merkle. Okay, that’s all cleared up, let’s do some proper crypto.
Introduction
And, so, in the UK, Boris Johnson has provided unredacted Whats App messages to the COVID inquiry [here]:
This seems a bit strange, as there are likely to be parts of his messages that are sensitive and should be redacted. And, so, we move into a world of digital signatures, and into a more trusted digital world. 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:
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):
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"
"encoding/json"
"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 {
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 and second word is [here]:
Private key: 4898338351181497662975613670207283868790281857649429380745833171094616512711
Public key: 66460198898513442690205434991163729304730870919596160687858862941411008439571, 53842295224933755462187283805397514776645865564734212573880515037661804711017
Data input: Dear Alice. This is my contract 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 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 1]
Successful signing 30440220252516d733a41466dd6f7210e5f5a93747278bb7c6e3623702ca592c6548f79502201ef8b3a295050c2f3d5d2df41d6efcddc43588dcdc30d356717a6e584439bc1e
Successful Verification
Successful redaction 4d4551434943556c4674637a7042526d33573979454f5831715464484a34753378754e694e774c4b5753786c53506556416941652b4c4f696c51554d4c7a31644c66516462767a6478445749334e777730315a78656d355952446d3848673d3d
Successful Redaction
Successful Checking against incorrect dataMerkle-Johnson
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 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.
he 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"
"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 dataConclusion
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.
References
[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.
[2] Goldreich, O., Goldwasser, S., & Micali, S. (1986). How to construct random functions. Journal of the ACM (JACM), 33(4), 792–807.