Threshold aggregation does not work for any arbitrary subset of t keys/signatures

The current implementation of signature (and verification key) aggregation won't work correctly if any subset other than the first t signatures/keys is used. Basically it always assumes the x coordinates used for the lagrange polynomials are [1, 2, ..., t], while this might not necessarily be true. That results in interpolating incorrect polynomial and hence failed verification of valid signatures. The following code explains the issue (for the simplicity sake, I ignore the verification key issue here, but it has exactly the same problem):

from coconut.scheme import *

def test():
        # normal setup as copied from the test file
        q = 7
        private_m = [10] * 2
        public_m = [3] * 1
        t, n = 2, 3
        params = setup(q)
        (d, gamma) = elgamal_keygen(params)
        (cm, c, pi_s) = prepare_blind_sign(params, gamma, private_m, public_m=public_m)
        (sk, vk) = ttp_keygen(params, t, n)
        aggr_vk = aggregate_vk(params, vk)
        sigs_tilde = [blind_sign(params, ski, cm, c, gamma, pi_s, public_m=public_m) for ski in sk]
        sigs = [unblind(params, sigma_tilde, d) for sigma_tilde in sigs_tilde]

        sigs2 = sigs[:-1] # uses first t signatures
        sigma = aggregate_sigma(params, sigs2) # calculates v(0) = v(1)*l_1 + v(2)*l_2
        sigma = randomize(params, sigma)
        (kappa, nu, pi_v) = show_blind_sign(params, aggr_vk, sigma, private_m)
        print blind_verify(params, aggr_vk, sigma, kappa, nu, pi_v, public_m=public_m) # verifies correctly

        sigs3 = sigs[1:] # uses last t signatures
        sigma = aggregate_sigma(params, sigs3) # calculates v(0) = v(2)*l_1 + v(3) * l_2 which is not true (actually what is calculated are not even proper l_1 and l_2)
        sigma = randomize(params, sigma)
        (kappa, nu, pi_v) = show_blind_sign(params, aggr_vk, sigma, private_m)
        print blind_verify(params, aggr_vk, sigma, kappa, nu, pi_v, public_m=public_m) # fails verification

        sigs4 = [sigs[0], sigs[2]]
        sigma = aggregate_sigma(params, sigs4)
        sigma = randomize(params, sigma)
        (kappa, nu, pi_v) = show_blind_sign(params, aggr_vk, sigma, private_m)
        print blind_verify(params, aggr_vk, sigma, kappa, nu, pi_v, public_m=public_m) # also fails verification

To fix it, there would need to be an additional parameter used in lagrange_basis function to represent the x coordinates of each point on the polynomial.

asonnino / coconut

Threshold aggregation does not work for any arbitrary subset of t keys/signatures #8