With verifiable encryption, Bob can prove to Alice that he has used a given encryption key of a ciphertext with a NIZK (Non-interactive Zero Knowledge Proof). In this case we will use ElGamal encryption and generate a proof of the public key which has been used for the encryption. If Bob uses Trent's public key to encrypt some ciphertext for Alice, then Bob can produce a proof that it has been encrypted with Trent's public key. Alice will then be able to check this against Trent's public key. In this case, we will use the secp256k1 elliptic curve, and use AEAD encryption to perform the actual encryption on the message.
ElGamal Verifiable encryption using Kryptology and Golang |
Background
We initially create a private key as a random number (\(x\)) and a public key of:
\(Q=x \cdot G\)
With standard ElGamal encryption, we generate a random value (\(r\)) to give:
\(t=r \cdot Q\)
We then create a symmetric key from this elliptic curve point:
\(\textrm{AEADKey}=\textrm{Derive}(t)\)
and where \(\textrm{Derive}\) just converts a point on the curve to a byte array value that is the length of the required symmetric encryption key (such as for 32 bytes in the case of 256-bit AES). Next, we compute the ciphertext values of:
\(C_1 = r \cdot G \)
\(C_2 = M \cdot H + r \cdot Q \)
and where \(M\) is the \(msg\) value converted into a scalar value. We then append these together to create the additioanl data that will be used for the symmetric key encryption of the message:
\(AAD = C_1 \: || \: C_2\)
We then generate a nonce value (\(Nonce\)) and then perform symmetric key encryption on the message:
\(cipher = Enc_{\textrm{AEADKey}}(msg,Nonce,AAD)\)
The ciphertext then has values of \(C_1\), \(C_2\), \(Nonce\) and \(cipher\). \(C_1\), \(C_2\) are points on the curve, and the \(Nonce\) value and \(cipher\) are byte array values. To decrypt, we take the private key (\(x\)) and derive:
\(t = x \cdot C_1\)
\(\textrm{AEADKey}=\textrm{Derive}(t)\)
\(AAD = C_1 \: || \: C_2\)
\(msg = Dec_{AEADKey}(cipher,Nonce,AAD)\)
Here is an overview of the method:
To generate the proof, we generate a random value (\(r\)) and a blinding factor (\(b\)) to give two points on the elliptic curve:
\(R_1 = r \cdot G\)
\(R_2 = r \cdot Q + b \cdot H\)
Next we create the challenge bytes with:
\(chall = C_1 \: || \: C_2 || \: R_1 \: || \: R_2 \: || \: Nonce\)
We take this value and hash it (\(H()\)), and create a scalar value with (\(ek\)) to produce:
\(c = H(chall) \cdot ek\)
We then create two Schnorr proof values:
\(S_1 = b - c \cdot m\)
\(S_2 = r - c \cdot b\)
To verify the proof, we reconstruct \(R_1\):
\(R_1 = c \cdot C_1 + S_2 \cdot G = c \cdot ( b \cdot G ) + (r - cb) \cdot G\)
This reconstruct \(R_1\) as:
\( \begin{align} R_1 &= c \cdot C_1 + S_2 \cdot G & \\ & = c \cdot ( b \cdot G ) + (r - cb) \cdot G &\\ & = (cb + r - cb) \cdot G &\\ & = r \cdot G \end{align} \)
We reconstruct \(R_2\):
\(R_2 = c \cdot C_2 + S_1 \cdot Q + S_1 \cdot H\)
This works because:
\( \begin{align} R_2 & = c \cdot C_2 + S_1 \cdot Q + S_1 \cdot H & \\ & = c \cdot (b \cdot Q + m \cdot H) + (r - cb) \cdot Q + (b - c m) \cdot H & \\ & = (cb + r - cb) \cdot Q + (cm + b - cm) \cdot H &\\ & =r \cdot Q + b \cdot H \end{align} \)
We then reconstructure the challenge with:
\(chall = C_1 \: || \: C_2 \: || \: R_1 \: || \: R_2 || \: Nonce\)
We take this value and hash it (\(H()\)), and create a scalar value with (\(ek\)) to produce:
\(c = H(chall) \cdot ek\)
This value is then checked agains the challenge in the proof, and if they are the same, the proof is verified.
Coding
We can use the Kryptology library developed by Coinbase [here] to implement verifiable encryption using the ElGamal method.
package main import ( "fmt" "os" "github.com/coinbase/kryptology/pkg/core/curves" "github.com/coinbase/kryptology/pkg/verenc/elgamal" ) func main() { argCount := len(os.Args[1:]) val := "hello" if argCount > 0 { val = os.Args[1] } domain := []byte("MyDomain") k256 := curves.K256() ek, dk, _ := elgamal.NewKeys(k256) msgBytes := []byte(val) cs, proof, _ := ek.VerifiableEncrypt(msgBytes, &elgamal.EncryptParams{ Domain: domain, MessageIsHashed: true, GenProof: true, ProofNonce: domain, }) fmt.Printf("=== ElGamal Verifiable Encryption ===\n") fmt.Printf("Input text: %s\n", val) fmt.Printf("=== Generating keys ===\n") res1, _ := ek.MarshalBinary() fmt.Printf("Public key %x\n", res1) res2, _ := dk.MarshalBinary() fmt.Printf("Private key %x\n", res2) fmt.Printf("=== Encrypting and Decrypting ===\n") res3, _ := cs.MarshalBinary() fmt.Printf("\nCiphertext: %x\n", res3) dbytes, _, _ := dk.VerifiableDecryptWithDomain(domain, cs) fmt.Printf("\nDecrypted: %s\n", dbytes) fmt.Printf("\n=== Checking proof===\n") rtn := ek.VerifyDomainEncryptProof(domain, cs, proof) if rtn == nil { fmt.Printf("Encryption has been verified\n") } else { fmt.Printf("Encryption has NOT been verified\n") } fmt.Printf("=== Now we will try with the wrong proof ===\n") ek2, _, _ := elgamal.NewKeys(k256) cs, proof2, _ := ek2.VerifiableEncrypt(msgBytes, &elgamal.EncryptParams{ Domain: domain, MessageIsHashed: true, GenProof: true, ProofNonce: domain, }) rtn = ek.VerifyDomainEncryptProof(domain, cs, proof2) if rtn == nil { fmt.Printf("Encryption has been verified\n") } else { fmt.Printf("Encryption has NOT been verified\n") } }
A sample run shows that a valid encryption key produces a valid proof, and then an invalid one generates an incorrect proof:
=== ElGamal Verifiable Encryption === Input text: Hello === Generating keys === Public key 2103f8647f379938aecf076e08fe2612593abb9f2b4c528ee5192d801471debb92ca09736563703235366b31 Private key 20b6ac09315a6f38134c32dcba6bdb2d075e1acc76fa68de9630743a7aa7d2164409736563703235366b31 === Encrypting and Decrypting === Ciphertext: 2102eecf68362fbf3c611b1d093d7f73cca746e66095a4d2fe276f35549065a36ffe21037cde7d60f85ded441a405e72792d88b2200a3baaee05282c7c9901b920a36c040c24d788cc27a0863bc41b5a0215ee1e287a2dcb11c0727747e67a6f759e7b4cb54c7109736563703235366b3101 Decrypted: Hello === Checking proof=== Encryption has been verified === Now we will try with the wrong proof === Encryption has NOT been verified
In this we can see that the first proof will work, but the second one is generated from a different encryption key, and will fail.
Coding
Reference
[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.