How Does Oscar Investigate Mallory — With Peggy Finding Out He Is A Suspect?

The other day I was asked by a media correspondent, “What got you into things like cryptography and blockchain?”, and I explained that it…
Photo by Michelle Ding on Unsplash

How Does Oscar Investigate Mallory — Without Peggy Finding Out He Is A Suspect?

The other day I was asked by a media correspondent, “What got you into things like cryptography and blockchain?”, and I explained that it all started with an amazing PhD student — Dr Zbigniew Kwecka — and who implemented Oblivious Transfer (OT) to preserve the privacy of an investigation. At the time, he used the RSA public key method, so let’s bring it up-to-date and into the current world of elliptic curves and crypto pairing methods.

Oscar suspects Mallory of committing a crime, and now needs to contact his employer — Peggy — to get some key evidence (his age). So how can Oscar do this, without revealing to Peggy that Mallory is a suspect? Well, one way is to define an oblivious transfer (OT) method, and where Oscar gets the required information, without revealing the Mallory is the target. Let’s say that Oscar wants the age of Mallory for their evidence gathering. First Oscar creates a list of identifiers which are employees in the company and , and which also includes Mallory:

1: Bob
2: Alice
3: Trent
4: Carol
5: Heidi
6: Dave
7: Mallory *

Let’s create these as an array (A). Peggy then creates another set of encrypted values for the ages of the people in the list. With the Camenisch Oblivious Transfer method [1] we follow this approach:

So let’s try for the ages of {17, 29, 35, 47, 20,16,47,48,19,55}. The outline coding using the library from the MIRACL library [here] is:

package main
import (
	"fmt"
	"github.com/miracl/core/go/core"
	"github.com/miracl/core/go/core/BN254"
	"math/rand"
	"time"	
	"os"
	"strconv"
)
func FP12toByte(F *BN254.FP12) []byte {
	const MFS int = int(BN254.MODBYTES)
	var t [12 * MFS]byte
	F.ToBytes(t[:])
	return(t[:])
}
func randval() *core.RAND {
    s1 := rand.NewSource(time.Now().UnixNano())
    r1 := rand.New(s1)
    rng := core.NewRAND()
    var raw [100]byte
    for i := 0; i < 100; i++ {
       raw[i] = byte(r1.Intn(255))
    }
    rng.Seed(100, raw[:])
    return rng
}

func main() {

	M := []int{17, 29, 35, 47, 20,16,47,48,19,55}
	A:=make([]*BN254.ECP2, len(M)) 
	B:=make([]*BN254.FP12, len(M)) 
	sig:=3 // Element to select
	argCount := len(os.Args[1:])
        if (argCount>0) {
		sig,_= strconv.Atoi(os.Args[1])
		if (sig>=len(M)) { sig=0; fmt.Printf("Setting search item to zero") }
	}
	fmt.Printf("\nData %d\n",M) 
	fmt.Printf("Element to OT %d\n\n",sig) 

    	q := BN254.NewBIGints(BN254.CURVE_Order)
//	r:=BN254.Randomnum(q,randval())
	s:=BN254.Randomnum(q,randval())
	x:=BN254.Randomnum(q,randval())
	P1 := BN254.ECP_generator()
	P2 := BN254.ECP2_generator()
//	g:=BN254.G2mul(P2,r)
	h:=BN254.G1mul(P1,s)
	 for i := 0;  i < len(M); i++ {
		ival:=BN254.NewBIGint(i)
		e := BN254.Modadd(x,ival,q)
		e.Invmodp(q)
		A[i]=BN254.G2mul(P2,e)
	}
	for i := 0;  i < len(M); i++ {
		Z := BN254.Ate(A[i],h); Z=BN254.Fexp(Z)
		Z.Mul(BN254.NewFP12int(M[i]))
		B[i]=Z
		fmt.Printf("Pairing %d e(Ai,h):\t%x\n",i,FP12toByte(B[i])[:20])
	}
//// Now send Ai, Bi to selector and choose one

	v:=BN254.Randomnum(q,randval())
	V:=BN254.G2mul(A[sig],v)
	fmt.Printf("\nSending v %s\n",V.ToString())
/// Sender sends back W
	W:=BN254.Ate(V,h); W=BN254.Fexp(W)
// Selector now gets W and recovers the message:

	fmt.Printf("\nPairing 1 e(Ai,h):\t%x\n",FP12toByte(B[sig])[:20])
	v.Invmodp(q)
	W=W.Pow(v)
	fmt.Printf("\nPairing 2 e(Ai,h):\t%x\n",FP12toByte(W)[:20])
	W.Inverse()
	Message:=BN254.NewFP12copy(B[sig])
	Message.Mul(W)
	fmt.Printf("\nResult:\t%x\n",FP12toByte(Message)[:20])
	for i := 0;  i <= 50; i++ {
		z:=BN254.NewFP12int(i)
		if Message.Equals(z)  { fmt.Printf("Success! Element %d is %d",sig,i) }
	}
}

A sample run is [here]:

Data [17 29 35 47 20 16 47 48 19 55]
Element to OT 7
Pairing 0 e(Ai,h): 1d70bdcd29f699bbc4bca4e01dfb87c0f0e023de
Pairing 1 e(Ai,h): 118f825d49c074f94b86ebdb2b97ef6b952764ea
Pairing 2 e(Ai,h): 082235a74ad3241197f6886db466e2f199d4070b
Pairing 3 e(Ai,h): 02a2b5e2e73fceed0a4495d18008c95e83b9f645
Pairing 4 e(Ai,h): 105e83504d71ea4e4009380cd4650fefe2064903
Pairing 5 e(Ai,h): 110546d09d8ba4d021561496ca95a31d75b9a965
Pairing 6 e(Ai,h): 0d8850515128394eae26b1a17885479e4d0bace9
Pairing 7 e(Ai,h): 0ba7bcc62463a3de61e21d78d95e1331dcee9d0f
Pairing 8 e(Ai,h): 13bbaf46f1f1efc8ae963d4b4ae45fcc966c69ad
Pairing 9 e(Ai,h): 0c04b9e3e1a11be387324d1bde388d49a3519fa6
Sending v ([20c36bd146a4fa2896b7fff29f537183e118b6e07de6ade081b5e825c30fd6df,0836dfc5c53e60b0a773a69afc7e84776df8b201b7a9d0133c6938847d3d0337],[085a922280bcbd9d692fc3789d11a0a076081e097a84720d2148c367546debdf,14aab968fab91ab135f099c553a211a80be4c96450ff6e4b6500d2e797e69985])
B value: 0ba7bcc62463a3de61e21d78d95e1331dcee9d0f
W value: 183a5a2d94c2136b14f67d552f31f5c11dff9df0
Result (B/W^{1/v}): 0000000000000000000000000000000000000000
Success! Element 7 is 48

Conclusion

I quote others … “Security is NOT privacy” … we need to build system which preserve (and not overrule) the rights of privacy. OT provides a way to discover things in an anonymous way.

References

Camenisch, J., & Neven, G. (2007, May). Simulatable adaptive oblivious transfer. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 573–590). Springer, Berlin, Heidelberg.