ACJT2000 group signature scheme

We present the group signature scheme given by Ateniese, Camenisch, Joye and Tsudik in their paper A Practical and Provably Secure Coalition-Resistant Group Signature Scheme.

Let us first give some auxiliary functions.

In [1]:
from algorithms.euclidean import gcd, inverse

def safe_prime(n):
    """
    Return a safe prime p in [n/2, n],
    i.e., such that (p-1)/2 is also a prime.
    """
    while True:
        p = random_prime(n, lbound=n/2)
        if Integer((p-1)/2).is_prime():
            return p

def is_QRroot(a, n):
    """
    Assuming n = pq,
    return True if a^2 has order (p-1)(q-1)/4.
    """
    return gcd(a+1, n) == 1 and gcd(a-1, n) == 1

def is_QR(a, p, q):
    """
    Return True if a is a quadratic residue
    modulo n = (2*p+1) * (2*q+1) of order p*q.
    """
    n = (2*p+1) * (2*q+1)
    return is_QRroot(a, n) and pow(a, p*q, n) == 1

def find_QR(n):
    """
    Assuming n = pq, where p and q are safe primes,
    find an element of order (p-1)(q-1)/4.
    """
    while True:
        a = randint(2, n-2)
        if is_QRroot(a, n):
            return Integer(a^2 % n)

def find_element(n):
    """
    Find an element in Z^*_n.
    """
    while True:
        x = randint(2, n-1)
        if gcd(x, n) == 1:
            return Integer(x)

Scheme parameters

Let us now set the scheme parameters.

In [2]:
class ACJTParams:
    """
    A class for parameters of the ACJT group signature scheme.
    """

    def __init__(self, H, e, k, lp, lm1=None, lm2=None, gm1=None, gm2=None):
        """
        Object constructor.
        """
        self.H = H
        self.e = e
        self.k = k
        self.lp = lp
        llm2 = 4 * self.lp
        if lm2 is None:
            self.lm2 = llm2 + 1
        else:
            assert lm2 > llm2
            self.lm2 = lm2
        llm1 = self.e * (self.lm2 + self.k) + 2
        if lm1 is None:
            self.lm1 = floor(llm1) + 1
        else:
            assert lm1 > llm1
            self.lm1 = lm1
        lgm2 = self.lm1 + 2
        if gm2 is None:
            self.gm2 = lgm2 + 1
        else:
            assert gm2 > lgm2
            self.gm2 = gm2
        lgm1 = self.e * (self.gm2 + self.k) + 2
        if gm1 is None:
            self.gm1 = floor(lgm1) + 1
        else:
            assert gm1 > lgm1
            self.gm1 = gm1

        self.pgm1 = 2 ^ self.gm1
        self.pgm2 = 2 ^ self.gm2
        self.plm1 = 2 ^ self.lm1
        self.plm2 = 2 ^ self.lm2
        self.plp = 2 ^ self.lp
        self.pg1 = 2 ^ ceil(self.e * (self.gm1 + 2*self.lp + self.k + 1))
        self.pg2 = 2 ^ ceil(self.e * (self.gm2 + self.k))
        self.pl2 = 2 ^ ceil(self.e * (self.lm2 + self.k))
        self.plk = 2 ^ ceil(self.e * (2*self.lp + self.k))

    def prove_discrete_log(self, values, bases, logs, n, lm=None, X=0):
        """
        Provide a zero-knowledge proof of the fact that
        the values can be expressed as a product of the elements in bases
        raised to the corresponding exponents in logs modulo n.
        """
        assert len(values) == len(bases)
        assert all(len(bb) == len(logs) for bb in bases)
        assert all(v == prod(pow(b, x, n) for b, x in zip(bb, logs)) % n for v, bb in zip(values, bases))
        if lm is None:
            lm = 4 * self.lp
        l = 2^(ceil(self.e * (lm + self.k))) - 1
        tt = [randint(-l, l) for _ in logs]
        c = self.H(*sum([[v, prod(pow(b, t, n) for b, t in zip(bb, tt)) % n] + bb for v, bb in zip(values, bases)], []))
        return (c, ) + tuple(t - c*(x-X) for t, x in zip(tt, logs))

    def verify_discrete_log(self, values, bases, proof, n, lm=None, X=0):
        """
        Verify the proof of the discrete logarithm.
        """
        assert len(values) == len(bases)
        assert all(len(bb) + 1 == len(proof) for bb in bases)
        if lm is None:
            lm = 4 * self.lp
        l = 2^(ceil(self.e * (lm + self.k)) + 1) - 1
        c = proof[0]
        ss = proof[1:]
        return all(-l <= s <= l for s in ss) and \
            c == self.H(*sum([[v, prod(pow(b, s - c*X, n) for b, s in zip(bb, ss)) * pow(v, c, n) % n] + bb
                              for v, bb in zip(values, bases)], []))

    def verify(self, pubkey, m, sig):
        """
        Verify the signature of the given message.
        """
        n, a, a0, y, g, h = pubkey
        c, s1, s2, s3, s4, T1, T2, T3 = sig
        return -2*self.pg2 < s1 < 2*self.pg2 and -2*self.pl2 < s2 < 2*self.pl2 and \
            -2*self.pg1 < s3 < 2*self.pg1 and -2*self.plk < s4 < 2*self.plk and \
            c == self.H(g, h, y, a0, a, T1, T2, T3,
                        Integer(pow(a0, c, n) * pow(T1, s1 - c * self.pgm1, n) /
                                (pow(a, s2 - c * self.plm1, n) * pow(y, s3, n)) % n),
                        Integer(pow(T2, s1 - c * self.pgm1, n) / pow(g, s3, n) % n),
                        Integer(pow(T2, c, n) * pow(g, s4, n) % n),
                        Integer(pow(T3, c, n) * pow(g, s1 - c * self.pgm1, n) * pow(h, s4, n) % n), m)

    def verify_opening(self, pubkey, m, sig, A, proof):
        """
        Verify that the signer has been correctly identified.
        """
        assert self.verify(pubkey, m, sig)
        n, a, a0, y, g, h = pubkey
        c, s1, s2, s3, s4, T1, T2, T3 = sig
        return self.verify_discrete_log([y, T1 / A % n], [[g], [T2]], proof, n)
In [3]:
import hashlib

def H(*largs):
    """
    Compute the MD5 hash of the input as an integer.
    """
    return Integer(hashlib.md5(str(list(largs)).encode()).hexdigest(), 16)

pars = ACJTParams(H, 1.1, 128, 128)

Key generation

George, the group manager, can now generate his secret key together with the group public key.

In [4]:
class ACJTJoinTranscript:
    """
    A class representing an ACJT join protocol transcript.
    """
    pass

class ACJTGroupManager:
    """
    A class representing the ACJT group manager.
    """

    def __init__(self, pars):
        """
        Object constructor.
        """
        self.pars = pars
        p = safe_prime(self.pars.plp)
        q = safe_prime(self.pars.plp)
        self.p = (p-1)/2
        self.q = (q-1)/2
        self.n = p * q
        self.a = find_QR(self.n)
        self.a0 = find_QR(self.n)
        self.g = find_QR(self.n)
        self.h = find_QR(self.n)
        self.x = find_element(self.p * self.q)
        self.y = Integer(pow(self.g, self.x, self.n))
        self.members = {}
        self.certificates = {}

    def public_key(self):
        """
        Return the group public key.
        """
        return (self.n, self.a, self.a0, self.y, self.g, self.h)

    def secret_key(self):
        """
        Return the group manager's secret key.
        """
        return (self.p, self.q, self.x)

    def join_init(self, name, msg):
        """
        Respond to joining initiation.
        """
        assert name not in self.members
        client = self.members[name] = ACJTJoinTranscript()
        client.C1, client.C1_proof1 = msg
        assert is_QR(client.C1, self.p, self.q)
        assert self.pars.verify_discrete_log([client.C1], [[self.g, self.h]], client.C1_proof1, self.n)
        client.alpha = Integer(randint(1, self.pars.plm2 - 1))
        client.beta = Integer(randint(1, self.pars.plm2 - 1))
        return (client.alpha, client.beta)

    def join_gen(self, name, msg):
        """
        Generate the group member's exponent.
        """
        client = self.members[name]
        client.C2, client.C2_proof1, client.C2_proof2, client.C1_proof2 = msg
        assert is_QR(client.C2, self.p, self.q)
        assert self.pars.verify_discrete_log([client.C2], [[self.a]], client.C2_proof1, self.n,
                                             self.pars.lm2, self.pars.plm1)
        assert self.pars.verify_discrete_log([Integer(client.C2 / pow(self.a, self.pars.plm1, self.n) % self.n)],
                                             [[self.a]], client.C2_proof2, self.n, self.pars.lm2)
        assert self.pars.verify_discrete_log([Integer(pow(client.C1, client.alpha, self.n) *
                                                      pow(self.g, client.beta, self.n) % self.n)],
                                             [[self.g, self.h]], client.C1_proof2, self.n, 2 * self.pars.lm2 + 1)
        client.e = random_prime(self.pars.pgm1 + self.pars.pgm2 - 1, lbound=self.pars.pgm1 - self.pars.pgm2 + 1)
        d = inverse(client.e, 4 * self.p * self.q)
        client.A = Integer(pow(client.C2 * self.a0, d, self.n))
        self.certificates[client.A] = name
        return (client.A, client.e)

    def open(self, m, sig):
        """
        Identify the signer of the signature sig to the message m.
        """
        assert self.pars.verify(self.public_key(), m, sig)
        c, s1, s2, s3, s4, T1, T2, T3 = sig
        A = Integer(T1 / pow(T2, self.x, self.n) % self.n)
        proof = self.pars.prove_discrete_log([self.y, T1 / A % self.n], [[self.g], [T2]], [self.x], self.n)
        return (self.certificates[A], A, proof)
        
In [5]:
set_random_seed(0)
george = ACJTGroupManager(pars)
print("Public key: {}".format(george.public_key()))
print("Secret key: {}".format(george.secret_key()))
Public key: (48752383569372781142179077891223791805566417844967383456604147865028689893521, 8784518326656962296441164723311076927317891516529277255771403524637626238121, 48565132551605088931120445197806080634109774219181087444748537528353370549533, 13596766191053589374927429285386846485733124217017277834532851010238133243335, 10645638839042559737305974437628969558943760323557740660522035849511242219602, 12028669766907673160645481306630038112263705279145149236394871092561759051105)
Secret key: (91052685114734783791970726488410028199, 133857621848109915527416916190455681039, 9371451885282338936378840407923812328926093446744871770554154869925480206419)

Note that the group manager should also provide a proof that $n$ really is a product of two safe primes, see Camenisch & Michels.

Joining the group

Alice now wants to join the group. She performs the following protocol with George over an authenticated and encrypted channel.

In [6]:
class ACJTGroupMember:
    """
    A class representing a group member.
    """

    def __init__(self, name, gm):
        """
        Object constructor.
        """
        self.name = name
        self.pars = gm.pars
        self.n, self.a, self.a0, self.y, self.g, self.h = gm.public_key()

    def join_init(self):
        """
        Initiate group joining.
        """
        self.xx = Integer(randint(1, self.pars.plm2 - 1))
        self.r = Integer(randint(1, self.n^2 - 1))
        self.C1 = Integer(pow(self.g, self.xx, self.n) * pow(self.h, self.r, self.n) % self.n)
        C1_proof1 = self.pars.prove_discrete_log([self.C1], [[self.g, self.h]], [self.xx, self.r], self.n)
        return (self.C1, C1_proof1)

    def join_gen(self, msg):
        """
        Generate personal private key.
        """
        self.alpha, self.beta = msg
        assert 1 <= self.alpha < self.pars.plm2
        assert 1 <= self.beta < self.pars.plm2
        self.x = self.pars.plm1 + (self.alpha * self.xx + self.beta) % self.pars.plm2
        self.C2 = Integer(pow(self.a, self.x, self.n))
        C2_proof1 = self.pars.prove_discrete_log([self.C2], [[self.a]], [self.x], self.n, self.pars.lm2, self.pars.plm1)
        C2_proof2 = self.pars.prove_discrete_log([Integer(self.C2 / pow(self.a, self.pars.plm1, self.n) % self.n)],
                                                 [[self.a]], [self.x - self.pars.plm1], self.n, self.pars.lm2)
        C1_proof2 = self.pars.prove_discrete_log([Integer(pow(self.C1, self.alpha, self.n) *
                                                          pow(self.g, self.beta, self.n) % self.n)], [[self.g, self.h]],
                                                 [self.alpha * self.xx + self.beta, self.alpha * self.r],
                                                 self.n, 2 * self.pars.lm2 + 1)
        return (self.C2, C2_proof1, C2_proof2, C1_proof2)

    def join_verify(self, msg):
        """
        Verify the correctness of the exponent.
        """
        self.A, self.e = msg
        return pow(self.a, self.x, self.n) * self.a0 % self.n == pow(self.A, self.e, self.n)

    def sign(self, m):
        """
        Produce a group signature of the message m.
        """
        w = Integer(randint(0, self.pars.plp^2 - 1))
        T1 = Integer(self.A * pow(self.y, w, self.n) % self.n)
        T2 = Integer(pow(self.g, w, self.n))
        T3 = Integer(pow(self.g, self.e, self.n) * pow(self.h, w, self.n) % self.n)
        r1 = Integer(randint(-self.pars.pg2+1, self.pars.pg2-1))
        r2 = Integer(randint(-self.pars.pl2+1, self.pars.pl2-1))
        r3 = Integer(randint(-self.pars.pg1+1, self.pars.pg1-1))
        r4 = Integer(randint(-self.pars.plk+1, self.pars.plk-1))
        d1 = Integer(pow(T1, r1, self.n) / (pow(self.a, r2, self.n) * pow(self.y, r3, self.n)) % self.n)
        d2 = Integer(pow(T2, r1, self.n) / pow(self.g, r3, self.n) % self.n)
        d3 = Integer(pow(self.g, r4, self.n))
        d4 = Integer(pow(self.g, r1, self.n) * pow(self.h, r4, self.n) % self.n)
        c = H(self.g, self.h, self.y, self.a0, self.a, T1, T2, T3, d1, d2, d3, d4, m)
        s1 = r1 - c * (self.e - self.pars.pgm1)
        s2 = r2 - c * (self.x - self.pars.plm1)
        s3 = r3 - c * self.e * w
        s4 = r4 - c * w
        return (c, s1, s2, s3, s4, T1, T2, T3)
In [7]:
alice = ACJTGroupMember("Alice", george)
alice_join_send1 = alice.join_init()
print("Alice sends {} to George".format(alice_join_send1))
Alice sends (33822086356785117577478344380699594706407625703296727475716936761098120615176, (164909897355417254532485461974265266652, 36893210708143067070656600461795525188275209658792657067946263210360688472128212283206057096754886220062643974948992266660477151742533940471732485410933359441241070619855915498103341923118620967312334483572446458, -8339518339678548738887259425185610180629972179654439537069687238967234797846214980703683666486051623679521605283977707390067866659363393568638758990375103898873223982282615161483363815624748674175809315870668863)) to George
In [8]:
alice_join_recv1 = george.join_init(alice.name, alice_join_send1)
print("George sends {} to Alice".format(alice_join_recv1))
George sends (4559284618349907120477578413592183960647506702936696829215154110207728104001456573962803236010410461492900947680732288920570502973140472443478473280846452, 23629950588962756401123237840427055770350289407514793002510799440160463761475082049864974970082928355961575420302791221662580109848950733618329367537678990) to Alice
In [9]:
alice_join_send2 = alice.join_gen(alice_join_recv1)
print("Alice sends {} to George".format(alice_join_send2))
Alice sends (32865504218787120571718704269712688467353384152871539427951785282857853110087, (329962777434983881667458844757761267895, 167246121399241366685896326586904096389506202959710697408784139412195360505171138358426209926882331223569294520693289957120506244858775148783956674325500272658748260969752358302868069425224102747739077467783132390), (303156577421344691185439508269989856257, -120376238783394673858144209398388200931439099160795716116122810109757844746259468314336374652436787274169457012319334686535409082206293123795865415440398618873393434855680034658221225205225130847434920634398538930), (117273412352664175170472701568236786515, 9345561646881288707521243609723836001089066384004558072697272947626176500038213755424667019505725744465011258435521943933848249511347508632913546355374069623720153879124983855806480434425939366449185278367566199014486388366036669711062262207765786582038702095484624054270900314695853093784057288189215869249763118721696049334776476372017129378900986766315307427736024541910900769834, -38439946697384783529577433062053225299374701793062543608464768178660220726568779210072037697457926800425231602685421902372576300235176501118212653381142931742800272327176462424152446213108527535872724743371989690703449550719695832425045135501528567282285768197812407189162705831042535714306159247517380657836272198828792247136883718571221203508265128465953110260259421682886866699543)) to George
In [10]:
alice_join_recv2 = george.join_gen(alice.name, alice_join_send2)
print("George sends {} to Alice".format(alice_join_recv2))
George sends (44129769602566099154715025357813824076521515978025804431305048310541026193459, 283625966735416996535885333662014114404918709117773906527666446557161513697116645635100557222165608059666024775903947307027612536349376392949552402353085683438429330182528554791581908055207389145353008160019999881226082428572834755940758377065565138390238100850894456113476462747) to Alice
In [11]:
alice.join_verify(alice_join_recv2)
Out[11]:
True

Signing

Alice can now sign a message $m$ on behalf of the group.

In [12]:
m = 2
sig = alice.sign(m)
sig
Out[12]:
(109778790217050522516162735293783827009,
 21179522599964195859865647936686679123840488131247431520398568152949663488724535502473189938048846985613659379752582647193366730764811414459800009256948419509108621530666840038897539542630216627328319729970543199335057546619565141225952875327631018050548205478108584664361073225,
 -264788396641919048328608085313561952923956343984648086303344703447341311306459604527042305344376573993801541771898532147336603362942527610907378939496235241263030265182338490665386725119591640674625534146242436269,
 75076611983499243494328059164464137646419063375869376886985549381938343119793681588372844543675201372222283787738071792909855314122580356486529586795805169699082172026641512992769431491326229691119335395544726593088253838375737427207395464991133307410145365765903775169311304628411195891319819836988747902140734340623272479683273024705767871886542778625763042144273842278572849332464945197147711753787423315990171346478550850590896597,
 14101755198843497164242595498494151808303097298425870951364369812204627588864253226717854479275300787910253827031110700084825951,
 37852620621991001841946054107785861155333730861861824818104595471409994318522,
 31944439039264829096756863335297085431212872787898218715365099547647000364869,
 25676948870736163620291239850016509457444605223069382849448527793230118023152)

Verifying

Anyone in possession of the group public key can verify that the signature was created by a group member.

In [13]:
pars.verify(george.public_key(), m, sig)
Out[13]:
True

Opening

Only the group manager can identify the signer.

In [14]:
signer, A, proof = george.open(m, sig)
(signer, A, proof)
Out[14]:
('Alice',
 44129769602566099154715025357813824076521515978025804431305048310541026193459,
 (233764237472059205545888757145252402374,
  52139932038045287849654148493876724112001866985620940903275634941364733580088104356090695308306076024680624079946239570298313476034480161543814242816096652265909863264529617187080309333639773332239324808726376659))

Anyone can now verify that the signer was correctly identified.

In [15]:
pars.verify_opening(george.public_key(), m, sig, A, proof)
Out[15]:
True