RSA Accumulators And Proving Knowledge

RSA Accumulators And Proving Knowledge

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]. So, here’s a basic method of proving knowledge of something, without revealing other things:

The outline code is [here]:

package main

import (
	"crypto/rand"
	"fmt"
	"math/big"
	"os"
	"unsafe"

	"golang.org/x/crypto/sha3"
)

func HashToPrime(data []byte) *big.Int {
 h := sha3.NewShake256()
 h.Write(data)
 p, err := rand.Prime(h, 256)
 if err != nil {
  panic(err)
 }
 return p
}

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 [here]:

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

Conclusions

If you want to know more about zero-knowledge proofs, try here:

https://asecuritysite.com/zero/

or on Golang here:

https://asecuritysite.com/golang/