Re: Question regarding common modulus on elliptic curve cryptosystems

2010-03-25 Thread Matt Crawford

On Mar 21, 2010, at 4:13 PM, Sergio Lerner wrote:

 I looking for a public-key cryptosystem that allows commutation of the 
 operations of encription/decryption for different users keys
 ( Ek(Es(m)) =  Es(Ek(m)) ).
 I haven't found a simple cryptosystem in Zp or Z/nZ.
 
 I think the solution may be something like the RSA analogs in elliptic 
 curves. Maybe a scheme that allows the use of a common modulus for all users 
 (RSA does not).

If your application can work with a trusted authority generating all the 
keypairs, and you sacrifice the use of short public exponents *and* sacrifice 
the possession of the factors of the modulus by the key owners, making them do 
more work on decryption, I think you can have what you asked for. But that's a 
lot of ifs.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: Question regarding common modulus on elliptic curve cryptosystems

2010-03-25 Thread James A. Donald

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 majord...@metzdowd.com


Re: Question regarding common modulus on elliptic curve cryptosystems AND E-CASH

2010-03-25 Thread James A. Donald

On 2010-03-23 1:09 AM, Sergio Lerner wrote:
I've read some papers, not that much. But I don't mind reinventing the 
wheel, as long as the new protocol is simpler to explain.

Reading the literature, I couldn't  find a e-cash protocol which :

- Hides the destination / source of payments.
- Hides the amount of money transferred.
- Hides the account balance of each person from the bank.
- Allows off-line payments.
- Avoids giving the same bill to two different people by design. 
This means that the protocol does not need to detect the use of cloned 
bills.
- Gives each person a cryptographic proof of owning the money they 
have in case of dispute.


I someone points me out a protocol that manages to fulfill this 
requirements, I'd be delighted.
I think I can do it with a commutative signing primitive, and a 
special zero-proof of knowledge.


Gap Diffie Helman gives you a commutative signing primitive, and a 
zero-proof of knowledge.




-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: Question regarding common modulus on elliptic curve cryptosystems

2010-03-22 Thread Jonathan Katz

[Moderator's Note: please don't top post... --Perry]

Sounds like a bad idea -- at a minimum, your encryption will be 
deterministic.


What are you actually trying to achieve? Usually once you understand that, 
you can find a protocol solving your problem already in the crypto 
literature.


On Sun, 21 Mar 2010, Sergio Lerner wrote:



I looking for a public-key cryptosystem that allows commutation of the 
operations of encription/decryption for different users keys

( Ek(Es(m)) =  Es(Ek(m)) ).
I haven't found a simple cryptosystem in Zp or Z/nZ.

I think the solution may be something like the RSA analogs in elliptic 
curves. Maybe a scheme that allows the use of a common modulus for all users 
(RSA does not).
I've read on some factoring-based cryptosystem (like Meyer-Muller or 
Koyama-Maurer-Okamoto-Vantone) but the cryptosystem authors say nothing about 
the possibility of using a common modulus, neither for good nor for bad.


Anyone has a deeper knowledge on this crypto to help me?

Best regards,
Sergio Lerner.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: Question regarding common modulus on elliptic curve cryptosystems

2010-03-22 Thread Zacheusz Siedlecki
Hi,
Elliptic Curve Pohlig-Hellman is comutative. It's quite simple. I've
implemented it.
 Regards,
   Zacheusz Siedlecki

2010/3/21 Sergio Lerner sergioler...@pentatek.com:

 I looking for a public-key cryptosystem that allows commutation of the
 operations of encription/decryption for different users keys
 ( Ek(Es(m)) =  Es(Ek(m)) ).
 I haven't found a simple cryptosystem in Zp or Z/nZ.

 I think the solution may be something like the RSA analogs in elliptic
 curves. Maybe a scheme that allows the use of a common modulus for all users
 (RSA does not).
 I've read on some factoring-based cryptosystem (like Meyer-Muller or
 Koyama-Maurer-Okamoto-Vantone) but the cryptosystem authors say nothing
 about the possibility of using a common modulus, neither for good nor for
 bad.

 Anyone has a deeper knowledge on this crypto to help me?

 Best regards,
  Sergio Lerner.
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: Question regarding common modulus on elliptic curve cryptosystems

2010-03-22 Thread Sergio Lerner

[Moderator's Note: please don't top post --Perry]

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.


Best regards,
 Sergio Lerner.


On 22/03/2010 09:56 a.m., Jonathan Katz wrote:
Sounds like a bad idea -- at a minimum, your encryption will be 
deterministic.


What are you actually trying to achieve? Usually once you understand 
that, you can find a protocol solving your problem already in the 
crypto literature.


On Sun, 21 Mar 2010, Sergio Lerner wrote:



I looking for a public-key cryptosystem that allows commutation of 
the operations of encription/decryption for different users keys

( Ek(Es(m)) =  Es(Ek(m)) ).
I haven't found a simple cryptosystem in Zp or Z/nZ.

I think the solution may be something like the RSA analogs in 
elliptic curves. Maybe a scheme that allows the use of a common 
modulus for all users (RSA does not).
I've read on some factoring-based cryptosystem (like Meyer-Muller or 
Koyama-Maurer-Okamoto-Vantone) but the cryptosystem authors say 
nothing about the possibility of using a common modulus, neither for 
good nor for bad.


Anyone has a deeper knowledge on this crypto to help me?

Best regards,
Sergio Lerner.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: Question regarding common modulus on elliptic curve cryptosystems

2010-03-22 Thread Sergio Lerner
As far as I understand, Elliptic Curve Pohlig-Hellman is not public-key. 
It's a private key cipher.


Regards,
 Sergio.


On 22/03/2010 09:56 a.m., Zacheusz Siedlecki wrote:

Hi,
Elliptic Curve Pohlig-Hellman is comutative. It's quite simple. I've
implemented it.
  Regards,
Zacheusz Siedlecki

On Sun, Mar 21, 2010 at 10:13 PM, Sergio Lerner
sergioler...@pentatek.com  wrote:
   

I looking for a public-key cryptosystem that allows commutation of the
operations of encription/decryption for different users keys
( Ek(Es(m)) =  Es(Ek(m)) ).
I haven't found a simple cryptosystem in Zp or Z/nZ.

I think the solution may be something like the RSA analogs in elliptic
curves. Maybe a scheme that allows the use of a common modulus for all users
(RSA does not).
I've read on some factoring-based cryptosystem (like Meyer-Muller or
Koyama-Maurer-Okamoto-Vantone) but the cryptosystem authors say nothing
about the possibility of using a common modulus, neither for good nor for
bad.

Anyone has a deeper knowledge on this crypto to help me?

Best regards,
  Sergio Lerner.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: Question regarding common modulus on elliptic curve cryptosystems

2010-03-22 Thread Jonathan Katz

[Moderator's Note: Please please don't top post. --Perry]

That paper was from 1980. A few things have changed since then. =)

In any case, my point still stands: what you actually want is some e-cash 
system with some special properties. Commutative encryption is neither 
necessary nor (probably) sufficient for what you want. Have you at least 
looked at the literature (which must be well over 100 papers) on e-cash?


On Mon, 22 Mar 2010, 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.


Best regards,
Sergio Lerner.


On 22/03/2010 09:56 a.m., Jonathan Katz wrote:
Sounds like a bad idea -- at a minimum, your encryption will be 
deterministic.


What are you actually trying to achieve? Usually once you understand that, 
you can find a protocol solving your problem already in the crypto 
literature.


On Sun, 21 Mar 2010, Sergio Lerner wrote:



I looking for a public-key cryptosystem that allows commutation of the 
operations of encription/decryption for different users keys

( Ek(Es(m)) =  Es(Ek(m)) ).
I haven't found a simple cryptosystem in Zp or Z/nZ.

I think the solution may be something like the RSA analogs in elliptic 
curves. Maybe a scheme that allows the use of a common modulus for all 
users (RSA does not).
I've read on some factoring-based cryptosystem (like Meyer-Muller or 
Koyama-Maurer-Okamoto-Vantone) but the cryptosystem authors say nothing 
about the possibility of using a common modulus, neither for good nor for 
bad.


Anyone has a deeper knowledge on this crypto to help me?

Best regards,
Sergio Lerner.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: Question regarding common modulus on elliptic curve cryptosystems AND E-CASH

2010-03-22 Thread Sergio Lerner
I've read some papers, not that much. But I don't mind reinventing the 
wheel, as long as the new protocol is simpler to explain.

Reading the literature, I couldn't  find a e-cash protocol which :

- Hides the destination / source of payments.
- Hides the amount of money transferred.
- Hides the account balance of each person from the bank.
- Allows off-line payments.
- Avoids giving the same bill to two different people by design. This 
means that the protocol does not need to detect the use of cloned bills.
- Gives each person a cryptographic proof of owning the money they have 
in case of dispute.


I someone points me out a protocol that manages to fulfill this 
requirements, I'd be delighted.
I think I can do it with a commutative signing primitive, and a special 
zero-proof of knowledge.


Regards,
 Sergio Lerner.


On 22/03/2010 10:25 a.m., Jonathan Katz wrote:

That paper was from 1980. A few things have changed since then. =)

In any case, my point still stands: what you actually want is some 
e-cash system with some special properties. Commutative encryption is 
neither necessary nor (probably) sufficient for what you want. Have 
you at least looked at the literature (which must be well over 100 
papers) on e-cash?


On Mon, 22 Mar 2010, 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.


Best regards,
Sergio Lerner.


On 22/03/2010 09:56 a.m., Jonathan Katz wrote:
Sounds like a bad idea -- at a minimum, your encryption will be 
deterministic.


What are you actually trying to achieve? Usually once you understand 
that, you can find a protocol solving your problem already in the 
crypto literature.


On Sun, 21 Mar 2010, Sergio Lerner wrote:



I looking for a public-key cryptosystem that allows commutation of 
the operations of encription/decryption for different users keys

( Ek(Es(m)) =  Es(Ek(m)) ).
I haven't found a simple cryptosystem in Zp or Z/nZ.

I think the solution may be something like the RSA analogs in 
elliptic curves. Maybe a scheme that allows the use of a common 
modulus for all users (RSA does not).
I've read on some factoring-based cryptosystem (like Meyer-Muller 
or Koyama-Maurer-Okamoto-Vantone) but the cryptosystem authors say 
nothing about the possibility of using a common modulus, neither 
for good nor for bad.


Anyone has a deeper knowledge on this crypto to help me?

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


Re: Question regarding common modulus on elliptic curve cryptosystems

2010-03-22 Thread Zacheusz Siedlecki
[Moderator's note. Please please please don't top post. --Perry]

I think you should look for multisignature schemes. There are lots of it.
And BTW - right EC Pohlih-Hellman is not public key cryptosystem. I
missed your requirement.
   Regards,
 Zacheusz

2010/3/22, Jonathan Katz jk...@cs.umd.edu:
 [Moderator's Note: Please please don't top post. --Perry]

 That paper was from 1980. A few things have changed since then. =)

 In any case, my point still stands: what you actually want is some e-cash
 system with some special properties. Commutative encryption is neither
 necessary nor (probably) sufficient for what you want. Have you at least
 looked at the literature (which must be well over 100 papers) on e-cash?

 On Mon, 22 Mar 2010, 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.

 Best regards,
 Sergio Lerner.


 On 22/03/2010 09:56 a.m., Jonathan Katz wrote:
 Sounds like a bad idea -- at a minimum, your encryption will be
 deterministic.

 What are you actually trying to achieve? Usually once you understand
 that,
 you can find a protocol solving your problem already in the crypto
 literature.

 On Sun, 21 Mar 2010, Sergio Lerner wrote:


 I looking for a public-key cryptosystem that allows commutation of the
 operations of encription/decryption for different users keys
 ( Ek(Es(m)) =  Es(Ek(m)) ).
 I haven't found a simple cryptosystem in Zp or Z/nZ.

 I think the solution may be something like the RSA analogs in elliptic
 curves. Maybe a scheme that allows the use of a common modulus for all
 users (RSA does not).
 I've read on some factoring-based cryptosystem (like Meyer-Muller or
 Koyama-Maurer-Okamoto-Vantone) but the cryptosystem authors say nothing
 about the possibility of using a common modulus, neither for good nor
 for
 bad.

 Anyone has a deeper knowledge on this crypto to help me?
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com