Jan Camenisch and Victor Shoup [1] created a discrete logarithm method which implements verifiable encryption. With this, Bob can prove to Alice that he has used a given encryption key with a NIZK (Non-interactive Zero Knowledge Proof). In this case we will encrypt an integer value, and then create a valid proof of the encryption key used, and then generate another encryption key which will fail the proof.
Camenisch-Shoup Verifiable encryption using Kryptology |
Background
We initially create a group with two safe primes: \(p\) and \(q\), and where \(p = 2p'+1\) and \(q = 2q'+1\). Also \(p'\) and \(q'\) are prime numbers. We compute:
\(n = p \cdot q\)
Generate a value of \(g'\) and which is less than \(n^2\). Next compute:
\(g = g'^{2n}\)
\(h = n + 1\)
Generate three random values: \(x_1\),\(x_2\),\(x_3\) and which are less than \(n^2/4\). The public keys are then:
\(y_1 = g^{x_1}\)
\(y_2 = g^{x_2}\)
\(y_3 = g^{x_3}\)
The keys are then {\(x_1,x_2,x_3\)} and the public keys are {\(y_1, y_2, y_3\)}. 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\).
Coding
We can use the Kryptology library developed by Coinbase [here] to implement the Camenisch-Shoup method.
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:
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
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.