An accumulator allows Bob to add values onto a fixed-length digest, and to provide proof of the values added, without revealing them within the accumulated value. In this case we will use a basic RSA method to make commitments to data elements, and then create proofs that these elements exist within the commitment [1].
RSA accumulators |
Method
Within an accumulator we can add and remove data elements, without actually revealing the contents of the accumulator. In this way, we can have the elements of \(\{A,B,C,D\}\) and show a proof that one of the elements is \(A\) without revealing the other elements. The method we will select for this is based on RSA encryption. Initially, Peggy can have four secret elements of \(\{A,B,C,D\}\). These are then converted into prime numbers of \(\{p_1,p_2,p_3,p_4\}\), and then compute:
\(S=p_1 \times p_2 \times p_3 \times p_4\)
This will be a fairly unique representation of our data values. Now, as in normal RSA, we select two prime numbers (\(p\) and \(q\)) and compute the modulus with:
\(N=p \times q\)
We then agree as value of \(G\) and create the accumulator for this as:
\(C = G ^ S \pmod N\)
This is the commitment to the messages. Now we will define that two elements are secret \(v=\{p_1,p_2\}\) and two elements are revealed \(r=\{p_3,p_4\}\). For this we compute:
\(U=p_1 \times p_2\)
and can then reveal \(r=\{p_3,p_4\}\) and with the proof of:
\(P = G ^ U \pmod N\)
Victor can then prove this value (\(P\)) against the commitment (\(C\)) by computing:
\(C' = P^R \pmod N\)
and will check that this equals \(C\). This works because:
\(C' = {(G^{U})}^{R} = G^{U \times R} = G^U = C \pmod N \)
Coding
The outline code is:
package main import ( "crypto/rand" "fmt" "math/big" "os" "unsafe" "golang.org/x/crypto/sha3" ) func IntToByteArray(num int64) []byte { size := int(unsafe.Sizeof(num)) arr := make([]byte, size) for i := 0; i < size; i++ { byt := *(*uint8)(unsafe.Pointer(uintptr(unsafe.Pointer(&num)) + uintptr(i))) arr[i] = byt } return arr } func main() { P1 := "hello" P2 := "goodbye" P3 := "test" P4 := "yellow" argCount := len(os.Args[1:]) if argCount > 0 { P1 = os.Args[1] } if argCount > 1 { P2 = os.Args[2] } if argCount > 2 { P3 = os.Args[3] } if argCount > 3 { P4 = os.Args[4] } p, _ := rand.Prime(rand.Reader, 256) q, _ := rand.Prime(rand.Reader, 256) N := new(big.Int).Mul(p, q) p1 := HashToPrime([]byte(P1)) p2 := HashToPrime([]byte(P2)) p3 := HashToPrime([]byte(P3)) p4 := HashToPrime([]byte(P4)) U := new(big.Int).Mul(p1, p2) R := new(big.Int).Mul(p3, p4) S := new(big.Int).Mul(U, R) G, _ := rand.Prime(rand.Reader, 256) C := new(big.Int).Exp(G, S, N) P := new(big.Int).Exp(G, U, N) C_ := new(big.Int).Exp(P, R, N) fmt.Printf("\np1=%s\np2=%s\np3=%s\np4=%s\n", P1, P2, P3, P4) fmt.Printf("\np=%d\nq=%d\nN=%d\n", p, q, N) fmt.Printf("\nG=%d\n", G) fmt.Printf("\nS = %s\n", S) fmt.Printf("\nP = %s\n", P) fmt.Printf("\nReleasing knowledge of (p3,p4)\nR = %s\n", R) fmt.Printf("\nG^S (mod N) = %s\nP^R (mod N) = %s\n", C, C_) res := C.Cmp(C_) if res == 0 { fmt.Printf("\nProven that we know P3 and P4\n") } }
A sample run:
p1=the p2=answer p3=is p4=zero p=110168683034412078252988803384518192461321281590636541470923841354853562227161 q=106061937419946478161782395033407262147119196630712660390686349600646093730537 N=11684703965633733119730626988260683770178859331663262870658764338944455703690397454318854419752691305312517598662844168228915721322748755916289920716515457 G=109882133269984171833525276055943402855771397065772349770138551124912826630421 S = 85405504991969306250187501207436550862896023333220071452766118055669838353321328003093433781208372242886640336102289782523143086243067197407273626636841566181337670505713286114406276286951780308362311374996416591988528480105527082840463534283163833631234785070763124657054808259608152883680730531237585858249 P = 7556121527561387223324021172027229390936508462349223607543887062630848197281779700484520709324106749579280753567063415269444315921038261968470614160403312 Releasing knowledge of (p3,p4) R = 9260680609490568631505061149352494075652655651553247266288418681505142676989958155180233871692440124825796096030097720359703492181516388434443317192907683 G^S (mod N) = 10861782574840743370228521182599852228831786881953547813575402729301534006011601601602617019967426826128706755904563689615833031324765754225035474130168035 P^R (mod N) = 10861782574840743370228521182599852228831786881953547813575402729301534006011601601602617019967426826128706755904563689615833031324765754225035474130168035 Proven that we know P3 and P4
Coding
References
[1] Derler, D., Hanser, C., & Slamanig, D. (2015, April). Revisiting cryptographic accumulators, additional properties and relations to other primitives. In Cryptographers’ track at the rsa conference (pp. 127-144). Springer, Cham.