Authentication Via Group Signatures

A computer program product for authenticating a message μ, at a user computer of a group signature scheme, to a verifier computer, said computer program product comprising a computer readable storage medium having program instructions embodied therein, the program instructions being executable by the user computer to cause the user computer to:

• store a user id m for the user computer and a user signing key which comprises a signature on the user id m under a secret key of a selectively-secure signature scheme, wherein the user id m is an element of a predetermined subring, isomorphic to q[x]/(g(x)), of a ring R=q[x]/(f(x)), where f(x) and g(x) are polynomials of degree deg(t) and deg(g) respectively such that deg(f)>deg(g)>1;
• generate a first cryptographic proof Π1 comprising a zero-knowledge proof of knowledge of said user signing key and including the message μ in said proof of knowledge;
• and
• send the message μ and a group signature, comprising the first proof Π1, to the verifier computer.

A system for authenticating a message μ, the system comprising a user computer of a group signature scheme and a verifier computer, wherein the user computer is adapted to:

• store a user id m for the user computer and a user signing key which comprises a signature on the user id m under a secret key of a selectively-secure signature scheme, wherein the user id m is an element of a predetermined subring, isomorphic to q[x]/(g(x)), of a ring R=q[x]/(f(x)), where f(x) and g(x) are polynomials of degree deg(f) and deg(g) respectively such that deg(f)>deg(g)>1;
• generate a first cryptographic proof Π1 comprising a zero-knowledge proof of knowledge of said user signing key and including the message μ in said proof of knowledge;
• and
• send the message μ and a group signature, comprising the first proof Π1, to the verifier computer;
• and wherein the verifier computer is adapted, in response to receipt of the message μ and the group signature, to authenticate the message μ by verifying the first proof Π1 using a public key of said selectively-secure signature scheme.