Camenisch-Shoup Verifiable Encryption using Kryptology and Golang

So Alice has some ciphertext. How does Bob prove to Alice that he has used a certain key to encrypt the message? Well, one way is for Bob…

Photo by Glenn Carstens-Peters on Unsplash

Camenisch-Shoup Verifiable Encryption using Kryptology and Golang

So Alice has some ciphertext. How does Bob prove to Alice that he has used a certain key to encrypt the message? Well, one way is for Bob to provide a Non-interactive Zero-Knowledge Proof (NIZK), and which will not only prove the party who encrypted the message but also the party who has the secret key.

The encryption key might have been sourced from Trent and who has a public key (pk) and a secret key (sk). Then Bob might encrypt his secret key with Trent’s public key (pk) and then give this to Alice. Alice might then ask Bob to prove that the ciphertext will be decrypted using Trent’s secret key (sk). Bob is thus a proxy in-between and using Trent’s public key to encrypt his secret key.

For this, we bind to some public data —known as a label — within the encryption and decryption processes. Alice thus attaches a label to the ciphertext that defines the conditions for decryption, such as related to the expiration time or to Alice’s identity. If the decryption then takes place with a different label, it will not reveal anything about the original message. Along with this, verifiable encryption can be used by Alice to ask Trent for a proof that he has decrypted the ciphertext correctly.

Another application is within a fair exchange of data, and where Bob and Alice exchange data. With this, either both of them will receive the data or none of them. If one party pulls out, it should not be possible for the other party to get the other party’s data. Bob and Alice will then use Trent’s public key to encrypt the data. The label within the verifiable encryption will ensure that the exchange mechanism is properly enacted and the verifiable decryption ensures that it is performed correctly by Trent.

The method we will implement will use the Coinbase Krytology library and is based on a classic paper from Jan Camenisch and Victor Shoup [here]:

With this, we create ciphertext with the secret key, and then which can be decrypted with the public key. There is also a proof created that it has been encrypted with a defined public key. Each ciphertext has a proof triplet of {u, e, v} and which relates to a challenge (c) and responses of m and r.

We can use the Kryptology library developed by Coinbase [here] to implement the Camenisch-Shoup method [here]:

package main

import (
	"fmt"
	"math/big"
	"os"

	"github.com/coinbase/kryptology/pkg/verenc/camshoup"
)

var (
	testP  = B10("37313426856874901938110133384605074194791927500210707276948918975046371522830901596065044944558427864187196889881993164303255749681644627614963632713725183364319410825898054225147061624559894980555489070322738683900143562848200257354774040241218537613789091499134051387344396560066242901217378861764936185029")
	testQ  = B10("89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164815053566739")
	testP1 = B10("153739637779647327330155094463476939112913405723627932550795546376536722298275674187199768137486929460478138431076223176750734095693166283451594721829574797878338183845296809008576378039501400850628591798770214582527154641716248943964626446190042367043984306973709604255015629102866732543697075866901827761489")
	testQ1 = B10("66295144163396665403376179086308918015255210762161712943347745256800426733181435998953954369657699924569095498869393378860769817738689910466139513014839505675023358799693196331874626976637176000078613744447569887988972970496824235261568439949705345174465781244618912962800788579976795988724553365066910412859")
)

func B10(s string) *big.Int {
	x, ok := new(big.Int).SetString(s, 10)
	if !ok {
		panic("Couldn't derive big.Int from string")
	}
	return x
}

func main() {

	argCount := len(os.Args[1:])
	val := "1000"
	if argCount > 0 {
		val = os.Args[1]
	}

	fmt.Printf("Message: %s\n", val)

	fmt.Printf("\n=== Generating keys ===\n")
	group, _ := camshoup.NewPaillierGroupWithPrimes(testP, testQ)

	domain := []byte("My Domain")

	ek, dk, _ := camshoup.NewKeys(1, group)

	res1, _ := dk.MarshalBinary()
	fmt.Printf(" Decryption key (first 25 bytes): %x\n", res1[:50])
	res2, _ := ek.MarshalBinary()
	fmt.Printf(" Encryption key (first 25 bytes): %x\n", res2[:50])

	fmt.Printf("\n=== Encrypting data with proof ===\n")
	msg, _ := new(big.Int).SetString(val, 10)

	cs, proof, _ := ek.EncryptAndProve(domain, []*big.Int{msg})

	res3, _ := cs.MarshalBinary()
	fmt.Printf(" Encrypted data (first 25 bytes): %x\n", res3[:50])

	res4, _ := proof.MarshalBinary()
	fmt.Printf(" Proof (first 25 bytes): %x\n", res4[:50])

	rtn := ek.VerifyEncryptProof(domain, cs, proof)

	if rtn != nil {
		fmt.Printf("We have not proven the key\n")
	} else {
		fmt.Printf("We have proven the key\n")
	}

	fmt.Printf("\n=== Let's try with the wrong keys ===\n")
	group, _ = camshoup.NewPaillierGroupWithPrimes(testP, testQ)

	ek2, _, _ := camshoup.NewKeys(1, group)

	_, proof1, _ := ek2.EncryptAndProve(domain, []*big.Int{msg})

	rtn1 := ek.VerifyEncryptProof(domain, cs, proof1)

	if rtn1 != nil {
		fmt.Printf("We have not proven the key\n")
	} else {
		fmt.Printf("We have proven the key\n")
	}

	fmt.Printf("\n=== Now decrypted ciphertext ===\n\n")
	dmsg, _ := dk.Decrypt(domain, cs)

	enc, _ := cs.MarshalBinary()
	fmt.Printf("Encrypted (showing first 25 bytes): %x\n", enc[:50])

	fmt.Printf("Decrypted: %s\n", dmsg[0])

A sample run shows that a valid encryption key produces a valid proof, and then an invalid one generates an incorrect proof [here]:

Message: 1000

=== Generating keys ===
 Decryption key (first 25 bytes): 01ff037949f368fc3ac355ecc9eab7c2b6d1e099981acb477654aed35dcfaf12946359fca1d553bedecebd1c40389408d057
 Encryption key (first 25 bytes): 01ff034019af1c7dfa022c9bf17e2bfe5909d67a202b7203ff0ca1152a9e5f8bfcc82d890f76aa810c6857a245ec5a8a5d28

=== Encrypting data with proof ===
 Encrypted data (first 25 bytes): 01800401753d8c131446725e7d6d7b8613d5b966063aba8a59bb9df1c776b725c67c5c8e2861b397b0dc55933d8eafa85edc
 Proof (first 25 bytes): 01800209e575d9bf533322f513cda8c44d5d0413401f189b77ac9f1365552dbef03d1ce4b098358b4e635577bfae7e76f231
We have proven the key

=== Let's try with the wrong keys ===
We have not proven the key

=== Now decrypted ciphertext ===

Encrypted (showing first 25 bytes): 01800401753d8c131446725e7d6d7b8613d5b966063aba8a59bb9df1c776b725c67c5c8e2861b397b0dc55933d8eafa85edc
Decrypted: 1000

Conclusions

We need to move to a world where we provide proofs of knowledge, without leaking information.

References

[1] Camenisch, J., & Shoup, V. (2003, August). Practical verifiable encryption and decryption of discrete logarithms. In Annual International Cryptology Conference (pp. 126–144). Springer, Berlin, Heidelberg.