class Paillier::ZKP::ZKP

The ZKP class is used for performing zero-knowledge content proofs. Initialization of a ZKP object generates a commitment that the user can send along with a ciphertext to another party. That party can then use the commitment to confirm that the ciphertext exists in the set of pre-determined valid messages.

Attributes

ciphertext[R]

Ciphertext generated by the ZKP object; accessible using both myZKP.ciphertext and myZKP.cyphertext

commitment[R]

Commitment generated by the ZKP object on initialization, used in ZKPVerify? function

cyphertext[R]

Ciphertext generated by the ZKP object; accessible using both myZKP.ciphertext and myZKP.cyphertext

Public Class Methods

new(public_key, plaintext, valid_messages) click to toggle source

Constructor function for a ZKP object. On initialization, generates a ZKPCommit object for use in verification

Example:

>> myZKP = Paillier::ZKP::ZKP.new(key, 65, [23, 38, 52, 65, 77, 94])
        => [#<@p = plaintext>, #<@pubkey = <key>>, #<@ciphertext = <ciphertext>>, #<@cyphertext = <ciphertext>>, #<@commitment = <commitment>>]

Arguments:

public_key: The key to be used for the encryption (Paillier::PublicKey)
plaintext: The message to be encrypted (Integer)
valid_messages: The set of valid messages for encryption (Array)

NOTE: the order of valid_messages should be the same for both prover and verifier

# File lib/paillier/zkp.rb, line 38
def initialize(public_key, plaintext, valid_messages)
        @p = plaintext
        @pubkey = public_key
        @r, @ciphertext = Paillier.rEncrypt(@pubkey, @p)
        @cyphertext = @ciphertext
        @a_s = Array.new()
        @e_s = Array.new()
        @z_s = Array.new()
        @power = nil
        @commitment = nil

        # we generate a random value omega such that omega is coprime to n
        while( true )
                big_n = BigDecimal( @pubkey.n )
                @omega = Primes.generateCoprime(BigMath.log(big_n, 2).round, @pubkey.n)
                if( @omega > 0 and @omega < @pubkey.n)
                        break
                end
        end
        
        # a_p = omega ^ n (mod n^2); 'a' calculation for the plaintext
        a_p = @omega.to_bn.mod_exp( @pubkey.n, @pubkey.n_sq)

        valid_messages.each_with_index do |m_k, k|
                # g_mk = g ^ m_k (mod n^2)
                g_mk = @pubkey.g.to_bn.mod_exp(m_k.to_bn, @pubkey.n_sq)
                
                # u_k = c / g_mk (mod n^2)
                # NOTE: this is modular algebra, so u_k = c * invmod(g_mk) (mod n^2)
                u_k = @ciphertext.to_bn.mod_mul(Paillier.modInv(g_mk, @pubkey.n_sq), @pubkey.n_sq)
                unless ( @p == m_k )
                        # randomly generate a coprime of n for z_k
                        while( true )
                                big_n = BigDecimal(@pubkey.n)
                                z_k = Primes::generateCoprime(BigMath.log(big_n, 2).round, @pubkey.n)
                                if( z_k > 0 and z_k < @pubkey.n )
                                        break
                                end
                        end
                        @z_s.push(z_k.to_bn)

                        # generate a random e < 2^BitStringLength
                        e_k = SecureRandom.random_number((2 ** 256) - 1)
                        @e_s.push(e_k.to_bn)

                        # calculate z_k
                        # z_nth = z^n (mod n^2)
                        z_nth = z_k.to_bn.mod_exp(@pubkey.n, @pubkey.n_sq)
                        # u_eth = u^e_k (mod n^2)
                        u_eth = u_k.to_bn.mod_exp(e_k.to_bn, @pubkey.n_sq)
                        # a_k = z_nth / u_eth (mod n^2) = z_nth * invmod(u_eth) (mod n^2)
                        a_k = z_nth.to_bn.mod_mul( Paillier.modInv(u_eth, @pubkey.n_sq), @pubkey.n_sq )

                        @a_s.push(a_k.to_bn)
                else
                        @power = k
                        @a_s.push(a_p.to_bn)
                end
        end
        # attempting to craft a ZKP object with an invalid message throws exception
        if(@power == nil)
                raise ArgumentError, "Input message does not exist in array of valid messages.", caller
        end
        # we have now generated all a_s, and all e_s and z_s, save for e_p and z_p
        # to generate e_p and z_p, we need to generate the challenge string, hash(a_s)
        # to make the proof non-interactive
        sha256 = OpenSSL::Digest::SHA256.new
        for a_k in @a_s do
                sha256 << a_k.to_s
        end
        challenge_string = sha256.digest.unpack('H*')[0].to_i(16)

        # now that we have the "challenge string", we calculate e_p and z_p
        e_sum = 0.to_bn
        big_mod = 2.to_bn
        big_mod = big_mod ** 256
        for e_k in @e_s do
                e_sum = (e_sum + e_k).to_bn % big_mod
        end
        # the sum of all e_s must add up to the challenge_string
        e_p = (OpenSSL::BN.new(challenge_string) - e_sum).to_bn % big_mod
        # r_ep = r ^ e_p (mod n)
        r_ep = @r.to_bn.mod_exp(e_p.to_bn, @pubkey.n)
        # z_p = omega * r^e_p (mod n)
        z_p = @omega.to_bn.mod_mul(r_ep.to_bn, @pubkey.n)

        @e_s.insert(@power, e_p.to_bn)
        @z_s.insert(@power, z_p.to_bn)
        @commitment = ZKPCommit.new(@a_s, @e_s, @z_s)
        
end