Question regarding common modulus on elliptic curve cryptosystems

James A. Donald jamesd at
Wed Mar 24 18:31:36 EDT 2010

On 2010-03-22 11:22 PM, Sergio Lerner wrote:
> Commutativity is a beautiful and powerful property. See "On the power 
> of Commutativity in Cryptography" by Adi Shamir.
> Semantic security is great and has given a new provable sense of 
> security, but commutative building blocks can be combined to build the 
> strangest protocols without going into deep mathematics, are better 
> suited for teaching crypto and for high-level protocol design. They 
> are like the "Lego" blocks of cryptography!
> Now I'm working on an new untraceable e-cash protocol which has some 
> additional properties. And I'm searching for a secure  commutable 
> signing primitive.

The most powerful primitive, from which all manner of weird and 
wonderful protocols can be concocted, are gap diffie helman groups.  
Read Alexandra Boldyreva "Threshold Signatures, Multisignatures, and 
Blind Signatures based on Gap-Diffie-Helman Group Signatures.

I am not sure what you want to do with commutativity, but suppose that 
you want a coin that needs to be signed by two parties in either order 
to be valid.

Suppose we consider call the operation that combines two points on an 
elliptic curve to be generate a third point multiplication and division, 
so that we use the familiar notation of exponentiation, thereby 
describing elliptic point crypto systems in the same notation as prime 
number crypto systems (a notation I think confusing, but everyone else 
uses it)

Suppose everyone uses the same Gap Diffie Helman group, and the same 
generator g.

A valid unblinded coin is the pair {u, (u^(b*c)}, yielding a valid DDH 
tuple {g, g^(b*c), u, u^(b*c)}, where u is some special format (not a 
random number)

Repeating in slightly different words.  A valid unblinded coin is a coin 
that with the joint public key of Bob and Carol yields a valid DDH 
tuple, in which the third element of the tuple has some special form.

Edward wants Bob and Carol to give him a blinded coin.  He already knows 
some other valid coin, {w, w^(b*c)).  He generates a point u that 
satifies the special properties for a valid coin, and a random number 
x.  He asks Bob and Carol to sign u*(w^(-x)), giving him a blinded coin, 
which he unblinds.

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list