# 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