is breaking RSA at least as hard as factoring or vice-versa?
So I'm reading up on unconditionally secure authentication in Simmon's Contemporary Cryptology, and he points out that with RSA, given d, you could calculate e (remember, this is authentication not encryption) if you could factor n, which relates the two. However, the implication is in the less useful direction; namely, that factoring n is at least as hard as breaking RSA. As of the books publication in 1992, it was not known whether the decryption of almost all ciphers for arbitrary exponents e is as hard as factoring. This is news to me! What's the current state of knowledge? -- Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Unforgeable Blinded Credentials
I came across the same problem a couple of years ago (and indeed iterated through private/public key solutions with a colleague). The problem is that you can still give your private key to somebody else. There's no real deterrent unless that private key is used for many other purposes, thereby discouraging sharing. But if that's the case, there's no real anonymity anymore, since the private key is tied to the person's identity. I found that Chameleon Certificates had nice properties. You have a master certificate that lists all your attributes. For authentication, you generate an unlinkable slave certificate with any subset of attributes. You have to possess the master certificate at time of use to generate the slave certificate, so you can't pass a slave certificate to a friend for later use. Then you just need to ensure that the master certificate includes personal details like credit card number, SSN, etc. to deter sharing of master certificates. Note that the slave certificates won't have this information, so this personal information is safe as long as the master certificate is not leaked. Since sharing an attribute amounts to sharing all your attributes, including personal information, this property serves as a good deterrent. Maybe somebody else can comment on the technical viability + crypto details of the paper. P. Persiano and I. Visconti. An Anonymous Credential System and a Privacy-Aware PKI. In Information Security and Privacy, 8th Australasian Conference, ACISP 2003, volume 2727 of Lecture Notes in Computer Science. Springer Verlag, 2003. http://springerlink.metapress.com/openurl.asp? genre=articleissn=0302-9743volume=2727spage=27 Here's the abstract: In this paper we present a non-transferable anonymous credential system that is based on the concept of a chameleon certificate. A chameleon certificate is a special certificate that enjoys two interesting properties. Firstly, the owner can choose which attributes of the certificate to disclose. Moreover, a chameleon certificate is multi-show in the sense that several uses of the same chameleon certificate by the same user cannot be linked together. We adopt the framework of Brands [2] and our construction improves the results of Camenisch et al. [5] and Verheul [16] since it allows the owner of a certificate to prove general statements on the attributes encoded in the certificate and our certificates enjoy the multi-show property. Apu -- Apu Kapadia, Ph.D. Research Fellow, Institute for Security Technology Studies (ISTS) Dartmouth College, Hanover NH 03755, USA http://www.cs.dartmouth.edu/~akapadia/ On Apr 1, 2006, at 6:35 AM, Ben Laurie wrote: It is possible to use blind signatures to produce anonymity-preserving credentials. The general idea is that, say, British Airways want to testify that I am a silver BA Executive Club cardholder. First I create a random number (a nonce), I blind it, then send it to BA. They sign it with their “this guy is a silver member” signing key, I unblind the signature and then I can show the signed nonce to anyone who wants to verify that I am silver. All they need to do is check the signature against BA’s published silver member key. BA cannot link this nonce back to me because they have never seen it, so they cannot distinguish me from any other member. However, anyone I show this proof to can then masquerade as a silver member, using my signed nonce. So, it occurred to me that an easy way to prevent this is to create a private/public key pair and instead of the nonce use the hash of the public key. Then to prove my silver status I have to show that both the hash is signed by BA and that I possess the corresponding private key (by signing a nonce, say). It seems to me quite obvious that someone must have thought of this before - the question is who? Is it IP free? Obviously this kind of credential could be quite useful in identity management. Note, though, that this scheme doesn’t give me unlinkability unless I only show each public/private key pair once. What I really need is a family of unlinkable public/private key pairs that I can somehow get signed with a single “family” signature (obviously this would need to be unlinkably transformed for each member of the key family). Permalink: http://www.links.org/?p=88 Cheers, Ben. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Unforgeable Blinded Credentials
On Sat, Apr 01, 2006 at 12:35:12PM +0100, Ben Laurie wrote: However, anyone I show this proof to can then masquerade as a silver member, using my signed nonce. So, it occurred to me that an easy way to prevent this is to create a private/public key pair and instead of the nonce use the hash of the public key. Then to prove my silver status I have to show that both the hash is signed by BA and that I possess the corresponding private key (by signing a nonce, say). It seems to me quite obvious that someone must have thought of this before - the question is who? Is it IP free? Well I thought of this a few years ago also. However I suspect you'd find the same idea earlier as a footnote in Stefan Brands book. (Its amazing how much stuff is in there, I thought I found something else interesting -- offline transferable cash, turns out that also was a footnote referring to someone's MSc thesis.) Obviously this kind of credential could be quite useful in identity management. Note, though, that this scheme doesn’t give me unlinkability unless I only show each public/private key pair once. What I really need is a family of unlinkable public/private key pairs that I can somehow get signed with a single “family” signature (obviously this would need to be unlinkably transformed for each member of the key family). This is harder, I thought about this a bit also. I was thinking a way to do this would be to have a self-reblindable signature. Ie you can re-blind the certificate signature such that the signature remains, but it is unlinkable. I didn't so far find a way to do this with any of the schemes. So it would for example be related to the more recent publicly re-encryptable Elgamal based signatures. (Third party can re-encrypt the already encrypted message with out themselves being able to decrypt the message). Brands also has a mechanism to simplify the use each cert once method. He can have the CA reissue you a new cert without having to go through the attribute verification phase. Ie you present an old cert and get it reblinded, and the CA does not even if I recall see what attributes you have. So you just periodically get yourself another batch. Mostly does what you want just with some assistance from the CA. Adam - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: is breaking RSA at least as hard as factoring or vice-versa?
On 4/2/06, Travis H. [EMAIL PROTECTED] wrote: So I'm reading up on unconditionally secure authentication in Simmon's Contemporary Cryptology, and he points out that with RSA, given d, you could calculate e (remember, this is authentication not encryption) if you could factor n, which relates the two. This implication runs both ways. Given d and e (and pq), one can compute p and q. Proving this is an exercise left to the reader. -- Taral [EMAIL PROTECTED] You can't prove anything. -- Gödel's Incompetence Theorem - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: is breaking RSA at least as hard as factoring or vice-versa?
At 1:41 -0600 2006/04/02, Travis H. wrote: So I'm reading up on unconditionally secure authentication in Simmon's Contemporary Cryptology, and he points out that with RSA, given d, you could calculate e (remember, this is authentication not encryption) if you could factor n, which relates the two. However, the implication is in the less useful direction; namely, that factoring n is at least as hard as breaking RSA. As of the books publication in 1992, it was not known whether the decryption of almost all ciphers for arbitrary exponents e is as hard as factoring. This is news to me! What's the current state of knowledge? It's conceivable that there might be a way to decrypt RSA messages without knowing d. If you don't know d, you still can't factor n. Whereas if you can factor n, you can find d, and decrypt messages. So the problems are not equivalent, and the RSA problem might be easier than the integer factorization problem. (At least, the above is my understanding.) Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
