### Re: Question regarding common modulus on elliptic curve cryptosystems

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

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

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

[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

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

[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

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

[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

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

[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