LWW Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups (LSAGS) | From: "Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups" | Published in: | Available from: http://eprint.iacr.org/2004/027.pdf | Notes: Implemented in one night by one person, so probably NOT good enough * type: signature * setting: cyclic groups of pr…

LSAGS with python-charms

from charm.toolbox.ecgroup import ECGroup
from charm.toolbox.PKSig import PKSig
from charm.toolbox.ecgroup import G

"""
LWW Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups (LSAGS)

| From: "Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups"
| Published in:
| Available from: http://eprint.iacr.org/2004/027.pdf
| Notes: Implemented in one night by one person, so probably NOT good enough

* type: signature
* setting: cyclic groups of prime order where the decisional Diffie–Hellman problem is hard
"""

class LWW(PKSig):
    """
    >>> from charm.toolbox.eccurve import secp256k1
    >>> group = ECGroup(secp256k1)
    >>> lsags = LWW(group, group.random(G))
    >>> [(A, a), (B, b), (C, c)] = [lsags.keygen() for _ in 'abc']
    >>> msg = b'Hi!'
    >>> L = [group.random(G)] + [A] + [group.random(G)] + [B] + [group.random(G)]
    >>> sig_a, sig_b = lsags.sign(L, a, msg), lsags.sign(L, b, msg)
    >>> lsags.verify(L, sig_a, msg) and lsags.verify(L, sig_b, msg)
    True
    >>> lsags.sign(L, c, msg)
    Traceback (most recent call last):    
        ...
    ValueError: Cannot sign as somebody else
    >>> sig_bad = (group.random(G), group.random(), [group.random() for _ in L])
    >>> lsags.verify(L, sig_bad, msg)
    False
    >>> sig_prim = lsags.sign(L, a, b'Bye!')
    >>> lsags.link(sig_a, sig_b)
    False
    >>> lsags.link(sig_a, sig_prim)
    True
    >>> sig_hidden = lsags.sign(L, a, b'Nothing', b'HIDDEN')
    >>> lsags.link(sig_a, sig_hidden)
    False
    """

    def __init__(self, groupObj, g_):
        PKSig.__init__(self)
        global group
        group = groupObj
        global g
        g = g_

    def keygen(self,_=0):
        x = group.random()
        y = g**x
        return (y, x)

    def sign(self, L, x_pi, m, tag=b''):
        """ Sign message m anonymously as one of L with private key x_pi"""
        try:
            pi = L.index(g**x_pi)
        except ValueError:
            raise ValueError("Cannot sign as somebody else")
        h = group.hash((tag,repr(L)), G)
        y_tilde = h**x_pi
        hLym = group.hash(( repr(L), y_tilde, m ))
        u = group.random()
        c = [None for _ in L]
        s = [None for _ in L]
        i = (pi + 1) % len(L)
        c[i] = group.hash(( hLym, g**u ,h**u ))
        while i != pi:
            s[i] = group.random()
            c[(i+1)%len(L)] = group.hash(( hLym,
                g**s[i] * L[i]**c[i],
                h**s[i] * y_tilde**c[i]
            ))
            i = (i + 1) % len(L)
        s[pi] = (u - x_pi*c[pi]) % group.order()
        return (y_tilde, c[0], s)

    def verify(self, L, sig, m, tag=b''):
        y_tilde, c0, s = sig
        h = group.hash((tag,repr(L)), G)
        hLym = group.hash(( repr(L), y_tilde, m ))
        c_i = c0
        for i in range(len(s)):
            c_i = group.hash(( hLym,
                g**s[i] * L[i]**c_i,
                h**s[i] * y_tilde**c_i
            ))
        return c0 == c_i

    def link(self, sig1, sig2):
        return sig1[0] == sig2[0]