Privacy-Aware Range Proofs using Borromean Ring Signatures

Privacy-Aware Range Proofs using Borromean Ring Signatures

In 2018, Poelstra et al. defined a range-proof method that uses a ring signature —and focused on Borromean Ring Signatures (BRS) [1][here]:

Let’s create a privacy-preserving range proof using BRS.

Borromean Ring Signatures

In 2015, Georgy Maxwell and Andrew Poelstra published a classic paper on the Borromean Ring Signature [here][2]:

A Borromean ring, in maths, is defined as three closed curves that cannot be separated from each other but can be unknotted when one of the rings is cut or removed.

Ring signatures

And so there has been a leak of information at the White House. Donald Trump calls in his Cyber Security leads, and tells them, “I know one of you leaked the information, but I can’t tell which one”. How can Donald tell that one of his leads has leaked the information, but not know which one? Well, this can be achieved with a ring signature, and which provides anonymity, unforgivably and collusion resistance.

A ring signature is a digital signature that is created by a member of a group that each have their own keys. It is then not possible to determine the person in the group who has created the signature. The method was initially created by Ron Rivest, Adi Shamir, and Yael Tauman in 2001, and in their paper, they proposed the White house leak dilemma.

Creating the ring

In a ring signature, we define a group of entities who each have their own public/private key pairs of (P1, S1), (P2, S2), …, (Pn, Sn). If we want an entity i to sign a message (message), they use their own secret key (si), but the public keys of the others in the group (m,si,P1…Pn). It should then be possible to check the validity of the group by knowing the public key of the group, but not possible to determine a valid signature if there is no knowledge of the private keys within the group.

So let’s say that Trent, Bob, Eve and Alice are in a group, and they each have their own public and secret keys. Bob now wants to sign a message from the group. He initially generates a random value v, and then generates random values (xi) for each of the other participants, but takes his own secret key (si) and uses it to determine a different secret key, and which is the reverse of the encryption function.

Borromean ring signing

With the Borromean Ring signer method, we can create a number of rings, and then sign a message with one of the private keys on each of the rings. In this case, we will create one ring with three keys and another ring with three keys, and we will then sign with one key from each ring. This should be verified. We will then replace one of the private keys so that there will be no public key on the rings, and which should negatively verify. The code used is [here]:

import sys
from ecpy.curves     import Curve
from ecpy.keys       import ECPrivateKey
import borromean
import binascii
import secrets
m1 = 'Hello'
if (len(sys.argv)>1):
  m1=str(sys.argv[1])print ("Message: ",m1)
m1=m1.encode()cv = Curve.get_curve('secp256k1')seckey0  = ECPrivateKey(secrets.randbits(32*8), cv)
seckey1  = ECPrivateKey(secrets.randbits(32*8), cv)
seckey2  = ECPrivateKey(secrets.randbits(32*8), cv)
seckey3  = ECPrivateKey(secrets.randbits(32*8), cv)
seckey4  = ECPrivateKey(secrets.randbits(32*8), cv)
seckey5  = ECPrivateKey(secrets.randbits(32*8), cv)pubkey0 = seckey0.get_public_key()
pubkey1 = seckey1.get_public_key()
pubkey2 = seckey2.get_public_key()pubkey3 = seckey3.get_public_key()
pubkey4 = seckey4.get_public_key()
pubkey5 = seckey5.get_public_key()print(f"Key ring 1: secret keys: {seckey0.d},{seckey1.d},{seckey2.d}")
print(f"Key ring 2: secret keys: {seckey3.d},{seckey4.d},{seckey5.d}")
borromean = borromean.Borromean()pubring1 = [pubkey0, pubkey1, pubkey2]
pubring2 = [pubkey3, pubkey4, pubkey5]
secring1 = [seckey0, seckey1, seckey2]
secring2 = [seckey3, seckey4, seckey5]
s1=1
s2=1pubset = (pubring1 , pubring2)
secset = [secring1[s1] , secring2[s2]]
secidx = [s1,s2]sigma = borromean.sign(m1, pubset, secset, secidx )
print ("\ne0=",binascii.hexlify(sigma[0]))
print ("Signature (s):")
for s in sigma[1]:
  print (binascii.hexlify(s))rtn=borromean.verify( m1, sigma, pubset)print ("\nChecking with valid key (Key 2 in Ring 1, Key 2 in Ring 2: ",rtn)
seckey1  = ECPrivateKey(secrets.randbits(32*8), cv)
pubring1 = [pubkey0, pubkey1, pubkey2]
pubring2 = [pubkey3, pubkey4, pubkey5]
secring1 = [seckey0, seckey1, seckey2]
secring2 = [seckey3, seckey4, seckey5]
s1=1 # seckey1 wrong for pubkey1
s2=1 # seckey3 okay for pubkey3pubset = (pubring1 , pubring2)
secset = [secring1[s1] , secring2[s2]]
secidx = [s1,s2]
sigma = borromean.sign(m1, pubset, secset, secidx )
rtn=borromean.verify(m1, sigma,  pubset)print ("Checking with non-valid key (Key 2 in Ring 1) and valid Key 2 in Ring 2: ",rtn)

A sample run [here]:

Message:  Hello
Key ring 1: secret keys: 29875636843252127507955771140493761058745571354380727422781883818399443737006,97218495476827164225347692618071712330690381390998678394112169358916634197973,115676391249222958503558958505064309953121480304377021022672178145871691693856
Key ring 2: secret keys: 23755527786469626298119838665469887802365884775146742464420183004417306811346,37301517688390233590722677956221422785988140595590490774518256329076480299102,97160227373003091865407598081510266465466948946312479036443319324502948855317e0= b'd0551fa12507e4338e9fe1460dcae7ee09e769857c615b08dee8fc3b7eba11cd'
Signature (s):
b'53a5f4657992ff875fc5a9bc23f682fed5e9f8d8b5150882ef8a0b884959e564'
b'2df3bde7e1e142491d06e71988fa56fceded189b3620be13f9fdbf18f1eaf42e'
b'b5cb16690e7d096a3e774319796d369a5a01f0a69dfbb93b55d38a3729620522'
b'5c135236bbba5ef39aad2d7db19535df384eac5c038ae310140abfeb1386e889'
b'b86d0352a7c4b6ab044522625ec0914862f69b0ea5370eebf7715ba10fa61267'
b'30937a6fc60b0cc2eb558dfc52fbf890bd1fd1a4c18030108f2af5e4b9834f89'Checking with valid key (Key 2 in Ring 1, Key 2 in Ring 2:  True
Checking with non-valid key (Key 2 in Ring 1) and valid Key 2 in Ring 2:  FalseVerified!

Range proof using BRS

The following is some simple coding to prove that a value (x) is in the range of 0 to u^l [here]:

package main
import (
 "fmt"
 "math/big"
 "os"
 "strconv"
 "math"
 "github.com/blockchain-research/crypto/brs"
 "github.com/btcsuite/btcd/btcec"
)
func GetBigInt(value string) *big.Int {
 i := new(big.Int)
 i.SetString(value, 10)
 return i
}
func powInt(x, y int) int {
 return int(math.Pow(float64(x), float64(y)))
}
func main() {
 xval := 7
 a := 2
 b := 3
 argCount := len(os.Args[1:])
 if argCount > 0 {
  xval, _ = strconv.Atoi(os.Args[1])
 }
 if argCount > 1 {
  a, _ = strconv.Atoi(os.Args[2])
 }
 if argCount > 2 {
  b, _ = strconv.Atoi(os.Args[3])
 }
 h := GetBigInt("18560948149108576432482904553159745978835170526553990798435819795989606410925")
 curve := btcec.S256()
 hx, hy := curve.ScalarBaseMult(h.Bytes())
 br := brs.SetupUL(int64(a), int64(b)) //range should be within [0,u^l), [0,10^2)
 x := new(big.Int).SetInt64(int64(xval))
 // Generate proof for value
 proof, rsum := br.ProveUL(x)
 // Compute Commitment
 cmx1, cmy1 := brs.Commit(x, rsum, hx, hy)
 //verify proof
 result := br.VerifyUL(proof, cmx1, cmy1)
 if result == true {
  fmt.Printf("Verification. %d is between 0 and %d\n", xval, powInt(a, b))
  fmt.Printf("Proof: C=%v\n", proof.C)
  fmt.Printf("Verfication: cmx1=%v\n", cmx1)
  fmt.Printf("Verfication: cmy1=%v\n", cmy1)
 } else {
  fmt.Printf("No verification. %d is not between 0 and %d", xval, powInt(a, b))
 }
}

A sample run is [here]:

Verification. 54 is between 0 and 243
Proof: C=[[113753976595824139106847729527612404984193536309387661733544557855090100941380 49704350862069682507333390099500344808224662375865172571834952302823703187226] [44132788630552368824702818647405520276854471082681621183903059164673148453409 112657428173711757619335890179844033349042944849902694787235847608514501843406] [52452370281191851376137816637221205089673851614356566817625613050006752482651 26095884236216696716580985911448489366340587283313030963467652662661218687401] [38999714362692500644515725532625384429326142472225179478472958705100481149829 97281927999034188696117227831994295123966596543465085276245298943223822158312] [56713049156232941875526987754177683047257784872751007115880183444449896674824 57441451640577174448163019277766892409802826143730188598380570618727364418730]]
Verfication: cmx1=31898815640990248918016416243147760064413228226691848701658981147561996974896
Verfication: cmy1=12671447146411625797483012721123908722197979907030180782218801345466075069509

and for [here]:

No verification. 54 is not between 0 and 27

References

[1] Poelstra, A., Back, A., Friedenbach, M., Maxwell, G., & Wuille, P. (2018, February). Confidential assets. In International Conference on Financial Cryptography and Data Security (pp. 43–63). Berlin, Heidelberg: Springer Berlin Heidelberg.

[2] Maxwell, G., & Poelstra, A. (2015). Borromean ring signatures. Accessed: Jun, 8, 2019.