Re: Are there...one-way encryption algorithms
Bodo Moeller wrote: > The Pohlig-Hellman cipher is the modular scheme that you describe, but > observe there is a connection to the protocol above: that protocol > works only if encryption and decryption has a certain commutativity > property (decrypting B(A(M)) with key A must leave B(M), not > just some A^-1(B(A(M))) that might look entirely different), and > the Pohlig-Hellman cipher has this property. A useful property for all sorts of things. I'm using P-H to improve Golle et al's universal encryption methods, http://www.zenadsl6186.zen.co.uk/ICURpaper3.pdf but it's a pity that Pohlig-Hellman is still slow, and that there isn't a faster algorithm with similar properties. There's lots of potential uses for one of those :) -- Peter Fairbrother - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Are there...one-way encryption algorithms
Anton Stiglic wrote: >"David Wagner" <[EMAIL PROTECTED]> wrote: >> martin f krafft wrote: >> > - Bob encrypts A(M) with key B and sends it to Alice >> > - Alice decrypts B(A(M)) with key A, leaving B(M), sends it to Bob >> > - Bob decrypts B(M) with key B leaving him with M. >> > >> >Are there algorithms for this already? What's the scheme called? >> >> It's called Pollig-Hellman. > >If I'm not mistaken you are wrong. You're right. The above protocol is essentially Shamir's 3-pass protocol, not Pohlig-Hellman. Pohlig-Hellman is the encryption scheme A(M) = M^A mod p. If you instantiate Krafft's proposal with the Pohlig-Hellman encryption scheme, you get a working (and secure) instance of Shamir's 3-pass protocol. Thank you for correcting my error! - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Are there...one-way encryption algorithms
On Tue, Nov 18, 2003 at 09:19:48AM -0800, Anton Stiglic wrote: > "David Wagner" <[EMAIL PROTECTED]>: >> martin f krafft wrote: >>> it came up lately in a discussion, and I couldn't put a name to it: >>> a means to use symmetric crypto without exchanging keys: >>> >>> - Alice encrypts M with key A and sends it to Bob >>> - Bob encrypts A(M) with key B and sends it to Alice >>> - Alice decrypts B(A(M)) with key A, leaving B(M), sends it to Bob >>> - Bob decrypts B(M) with key B leaving him with M. >>> >>> Are there algorithms for this already? What's the scheme called? >> It's called Pollig-Hellman. > If I'm not mistaken you are wrong. Pohlig-Hellman proposed an encryption > scheme based on discret log, the description of the OP was for a > key transport protocol. > In Pohlig-Hellman, what you do is have Alice and Bob share secret > keys k and d such that k*d == 1 mod (p-1), where p is some prime. > To encrypt a message M Alice computes M^k mod p, and Bob > can decrypt by computing (M^k)^d mod p == M mod p. [...] > The algorithm that was described by the OP is really Shamir's > three-pass algorithm, also known as Shamir's no-key protocol. The Pohlig-Hellman cipher is the modular scheme that you describe, but observe there is a connection to the protocol above: that protocol works only if encryption and decryption has a certain commutativity property (decrypting B(A(M)) with key A must leave B(M), not just some A^-1(B(A(M))) that might look entirely different), and the Pohlig-Hellman cipher has this property. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Are there...one-way encryption algorithms
Ah sure, that's why I said "irksome" and not "worrying" :-) It was more a curiosity of theoretical nature than a practical concern. Enzo - Original Message - From: "Sidney Markowitz" <[EMAIL PROTECTED]> To: "Enzo Michelangeli" <[EMAIL PROTECTED]> Cc: <[EMAIL PROTECTED]> Sent: Tuesday, November 18, 2003 3:48 PM Subject: Re: Are there...one-way encryption algorithms > Enzo Michelangeli wrote: > > but the slight risk of collision, > > although practically negligible, is a bit irksome > > If you quantify the "practically negligible" risk, it might be less > irksome: SHA-1 is a 160 bit hash. The birthday paradox says that you > would need to hash 2^80 different credit card numbers before you had a > 50% probability of having even one collision in your database keys. Very > roughly that means you would need to have a trillion different credit > card numbers in your database in order to get as much as a one in a > trillion chance of a collision. You would probably find dealing with a > trillion different credit card numbers more irksome than the negligible > chance of a collision even that many would give you. > > -- sidney > - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Are there...one-way encryption algorithms
"David Wagner" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > martin f krafft wrote: > >it came up lately in a discussion, and I couldn't put a name to it: > >a means to use symmetric crypto without exchanging keys: > > > > - Alice encrypts M with key A and sends it to Bob > > - Bob encrypts A(M) with key B and sends it to Alice > > - Alice decrypts B(A(M)) with key A, leaving B(M), sends it to Bob > > - Bob decrypts B(M) with key B leaving him with M. > > > >Are there algorithms for this already? What's the scheme called? > > It's called Pollig-Hellman. If I'm not mistaken you are wrong. Pohlig-Hellman proposed an encryption scheme based on discret log, the description of the OP was for a key transport protocol. In Pohlig-Hellman, what you do is have Alice and Bob share secret keys k and d such that k*d == 1 mod (p-1), where p is some prime. To encrypt a message M Alice computes M^k mod p, and Bob can decrypt by computing (M^k)^d mod p == M mod p. This is commonly referred to as the Pohlig-Hellman symmetric-key exponentiation cipher. It is described in patent 4,424,414 which you can find here http://patft.uspto.gov/netahtml/search-bool.html Also mentioned in HAC, chapter 15, section 15.2.3, (iii). The algorithm that was described by the OP is really Shamir's three-pass algorithm, also known as Shamir's no-key protocol. --Anton - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Are there...one-way encryption algorithms
Enzo Michelangeli wrote: but the slight risk of collision, although practically negligible, is a bit irksome If you quantify the "practically negligible" risk, it might be less irksome: SHA-1 is a 160 bit hash. The birthday paradox says that you would need to hash 2^80 different credit card numbers before you had a 50% probability of having even one collision in your database keys. Very roughly that means you would need to have a trillion different credit card numbers in your database in order to get as much as a one in a trillion chance of a collision. You would probably find dealing with a trillion different credit card numbers more irksome than the negligible chance of a collision even that many would give you. -- sidney - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Are there...one-way encryption algorithms
Amir and others, First, I'd like to thank all who have taken time to reply, either on- or off-list. All suggestions so far are related to public-key algorithms; I had myself thought about simply raising a generator g to the plaintext, or to a suitable injective function of the plaintext, in a GF(p): that doesn't even require a key to throw away. One drawback is that, with the possible exception of ECC-based methods, the minimum size of the cryptotext becomes larger than I'd like. Anyway, the intended use is for primary keys in transaction databases, in replacement of the PAN (a.k.a. credit card number). Using secure hashes is the usual way of doing such things, but the slight risk of collision, although practically negligible, is a bit irksome (especially considering that the plaintext is of fixed size, and therefore injectivity is not a priori impossible), and I was wondering if something better can be done. Enzo - Original Message - From: "Amir Herzberg" <[EMAIL PROTECTED]> To: "'Enzo Michelangeli'" <[EMAIL PROTECTED]>; <[EMAIL PROTECTED]> Sent: Sunday, November 16, 2003 10:44 PM Subject: RE: Are there...one-way encryption algorithms > Enzo asked, > > Are there one-way encryption algorithms guaranteed to be injective > > (i.e., deterministically collision-free)? Or are there > > theoretical reasons against their existence? > > > > I'm looking for algorithms where every piece of code and data > > is public, thus excluding conventional enciphering with a secret key. > > Sounds like you look for One Way Permutations... which of course exist > (if one-way functions do). But before we get into details, it'll be > useful if you specify your needs more precisely since imprecision is the > mother of weaknesses and break-ins. > > BTW I've updated my foils on encryption and hashing which cover much of > this topic (see in site if interested). > > Best, Amir Herzberg > http://amir.herzberg.name > > - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Are there...one-way encryption algorithms
Enzo Michelangeli wrote: >Anyway, the intended use is for primary keys in transaction databases, in >replacement of the PAN (a.k.a. credit card number). Using secure hashes is >the usual way of doing such things, but the slight risk of collision, >although practically negligible, is a bit irksome (especially considering >that the plaintext is of fixed size, and therefore injectivity is not a >priori impossible), and I was wondering if something better can be done. I'd ignore the risk. If you've got a 160-bit hash function (and you probably should), then the risk of a collision is truly negligible. If you try to come up with some fancy alternative, there will be a greater risk that the fancy alternative is insecure than the risk that you ever experience a collision in SHA. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RE: Are there...one-way encryption algorithms
Enzo asked, > Are there one-way encryption algorithms guaranteed to be injective > (i.e., deterministically collision-free)? Or are there > theoretical reasons against their existence? > > I'm looking for algorithms where every piece of code and data > is public, thus excluding conventional enciphering with a secret key. Sounds like you look for One Way Permutations... which of course exist (if one-way functions do). But before we get into details, it'll be useful if you specify your needs more precisely since imprecision is the mother of weaknesses and break-ins. BTW I've updated my foils on encryption and hashing which cover much of this topic (see in site if interested). Best, Amir Herzberg http://amir.herzberg.name - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
