Re: [cryptography] What's the state of the art in factorization?
On 23/04/2010 11:57, Paul Crowley wrote: [2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf My preferred signature scheme is the second, DDH-based one in the linked paper, since it produces shorter signatures - are there any proposals which improve on that? There is RSA or Rabin using a signature scheme with message recovery. With a public modulus of n bits, and a hash of h bits, signing a message adds only h bits, as long as - the message to sign is at least (n-h) bits and - you do not care about spending a few modular multiplication to recover some (n-h) bits of the message [where few is 17, 2 or 1 for popular public exponents e of 65537, 3, 2] This is standardized by ISO/IEC 9796-2 (which add a few bits of overhead to h, like 16 when n is a multiple of 8). It is used (with a deprecated and not-quite-perfect option set of ISO/IEC 9796-2) in many applications where size matters, in particular EMV Smart Cards, and the European Digital Tachograph. With e=2 and the newer (randomized) schemes of ISO/IEC 9796-2, you get security provably related to factoring or breaking the hash. François Grieu [I suddenly got a batch of old messages, and wonder what is the appropriate list address] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
What's the state of the art in digital signatures? Re: What's the state of the art in factorization?
By the way, the general idea of One Hundred Year Security as far as digital signatures go would be to combine digital signature algorithms. Take one algorithm which is bog standard, such as ECDSA over NIST secp256r1 and another which has strong security properties and which is very different from ECDSA. Signing is simply generating a signature over the message using each algorithm in parallel. Signatures consist of both of the signatures of the two algorithms. Verifying consists of checking both signatures and rejecting if either one is wrong. Since the digital signature algorithms that we've been discussing such as [1] are related to discrete log/Diffie-Hellman and since an efficient implementation would probably be in elliptic curves, then those are not great candidates to pair with ECDSA in this combiner scheme. Unfortunately I haven't stumbled on a digital signature scheme which has good properties (efficiency, simplicity, ease of implementation) and which is based on substantially different ideas and which isn't currently under patent protection (therefore excluding NTRUSign). Any ideas? [1] http://eprint.iacr.org/2007/019 Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote: There is some interesting work in public key cryptosystems that reduce to a *random* instance of a specific problem. Here is a very cool one: http://eprint.iacr.org/2009/576 ... Unless I misunderstand, if you read someone's plaintext without having the private key then you have proven that P=NP! It is not known, and considered extremely unlikely, that P \neq NP implies symmetric-key cryptography, much less public-key cryptography. The paper you cite reduces security to a hard-on-average problem, whereas all that P \neq NP guarantees is hardness in the worst case. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote: On Wed, Apr 21, 2010 at 5:29 PM, Samuel Neves sne...@dei.uc.pt wrote (on the cryptography@metzdowd.com list): [2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf As one of the authors of the above paper, I have an obvious interest in this thread. =) Later I discovered this paper [2] which appears to be an improvement on that one in terms of performance (see Table 1 in [2]) while still having a tight reduction to the Computational Diffie-Hellman (CDH) problem. Strangely, this paper [2] doesn't appear to have been published anywhere except as an eprint on eprint.iacr.org. I wonder why not. Is there something wrong with it? While I don't know of any attack, the proof of security does not appear to be correct. On the other hand, there is one published scheme that gives a slight improvement to our paper (it has fewer on-line computations): it is a paper by Chevallier-Mames in Crypto 2005 titled An Efficient CDH-Based Signature Scheme with a Tight Security Reduction. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [cryptography] What's the state of the art in factorization?
Jonathan Katz wrote: [2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf On the other hand, there is one published scheme that gives a slight improvement to our paper (it has fewer on-line computations): it is a paper by Chevallier-Mames in Crypto 2005 titled An Efficient CDH-Based Signature Scheme with a Tight Security Reduction. My preferred signature scheme is the second, DDH-based one in the linked paper, since it produces shorter signatures - are there any proposals which improve on that? Incidentally, the paper doesn't note this but that second scheme has a non-tight reduction to the discrete log problem in exactly the way that Schnorr does. -- __ \/ o\ Paul Crowley, p...@ciphergoth.org /\__/ http://www.ciphergoth.org/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [cryptography] What's the state of the art in factorization?
On Fri, Apr 23, 2010 at 3:57 AM, Paul Crowley p...@ciphergoth.org wrote: My preferred signature scheme is the second, DDH-based one in the linked paper, since it produces shorter signatures - are there any proposals which improve on that? http://eprint.iacr.org/2007/019 Has one. Caveat lector. Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
What's the state of the art in digital signatures? Re: What's the state of the art in factorization?
On Thu, Apr 22, 2010 at 12:40 PM, Jonathan Katz jk...@cs.umd.edu wrote: On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote: Unless I misunderstand, if you read someone's plaintext without having the private key then you have proven that P=NP! … The paper you cite reduces security to a hard-on-average problem, whereas all that P \neq NP guarantees is hardness in the worst case. I see. I did misunderstand. So although cracking the Lyubashevsky, Palacio, Segev encryption scheme [1] doesn't mean that you've proven P=NP, because NP is about worst-case rather than average-case, it *does* mean that you've solved the subset sum problem for a random instance. If you can do that for all keys that people use in real life then you can solve the subset sum problem for almost all random instances, which seems like it would still be a breakthrough in complexity theory. If you can do it for only a few keys then this means that the Lyubashevsky, Palacio, Segev scheme is susceptible to weak keys. Is that right? Anyway, although this is not one, there do exist proposals for public key crypto schemes where breaking the scheme implies solving a worst case instance of a supposedly hard problem, right? Here is a recent paper which surveys several of them (all lattice-based) and estimates secure key sizes: [2]. None of the signature schemes mentioned therein appear to have the sort of efficiency that we are used to. For example the ecdonaldp (ECDSA) signature schemes measured on http://bench.cr.yp.to/results-sign.html have key sizes on the order of tens of bytes, where the most efficient digital signature algorithm described in [2] has key sizes on the order of thousands of bytes. (And that one is a one-time signature scheme!) Okay, so I'm still searching for a signature algorithm which has the following properties (or as many of them as I can get): 1. efficient (signing time, verification time, key generation time, key size, signature size) 2. some kind of strong argument that it really is secure (the gold standard would be reduction to a worst-case instance of an NP-complete problem) or, if we can't have (2) then at least we want (3) and (4): 3. rather different from ECDSA, so that a breakthrough is unlikely to invalidate both ECDSA and this other scheme at once and 4. not known to be vulnerable to quantum computers and finally but importantly: 4. easy to understand and to implement Suggestions welcome! Regards, Zooko Wilcox-O'Hearn [1] http://eprint.iacr.org/2009/576 [2] http://eprint.iacr.org/2010/137 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in digital signatures? Re: What's the state of the art in factorization?
On Wed, 28 Apr 2010, Zooko O'Whielacronx wrote: Anyway, although this is not one, there do exist proposals for public key crypto schemes where breaking the scheme implies solving a worst case instance of a supposedly hard problem, right? Not to worst-case hardness of an NP-complete problem, no. Quite the contrary, there has been some body of work showing that a result of this sort is unlikely. (Though, as with all things related to complexity theory where our state of knowledge is so limited, such a statement must be taken wit ha grain of salt. In any case, such a result is well beyond anything we can currently prove.) 2. some kind of strong argument that it really is secure (the gold standard would be reduction to a worst-case instance of an NP-complete problem) See above. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
On Apr 21, 2010, at 7:29 PM, Samuel Neves wrote: EC definitely has practical merit. Unfortunately the patent issues around protocols using EC public keys are murky. Neither RSA nor EC come with complexity proofs. While EC (by that I assume you mean ECDSA) does not have a formal security proof, i.e., it is as hard as the EC discrete log, it it much closer to one than RSA is to factoring. In particular, Pointcheval and Stern, and later Brown come close to a formal proof for ECDSA [1] It's perhaps worth pointing out again how little formal complexity proves tell you about security. Suppose we could show that RSA was as hard as factoring. So? Nothing is really known about how hard factoring is. At worst, it's NP- complete (though that's actually considered unlikely). But suppose *that* was in fact known to be the case. What would it tell us about the difficulty of factoring any particular product of two primes? Absolutely nothing. NP-completeness is a worst-case result. In principle, it could be the case that factoring is easy for numbers less than a billion bits long - it just becomes much harder eventually. (I put easy in quotes because it's usually taken to mean there's a poly-time algorithm, and that's a meaningless statement for a finite set of problems. *Every* finite set of problems has a O(1) time solution - just make a lookup table.) There are some concrete complexity results - the kind of stuff Rogoway does, for example - but the ones I've seen tend to be in the block cipher/cryptographic hash function spaces. Does anyone one know of similar kinds of results for systems like RSA? -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
Victor Duchovni wrote: On Tue, Apr 20, 2010 at 08:58:25PM -0400, Thierry Moreau wrote: The DNS root may be qualified as a high valued zone, but I made the effort to put in writing some elements of a risk analysis (I have an aversion for this notion as I build *IT*controls* and the consultants are hired to cost-justify avoiding their deployments, basically -- but I needed a risk analysis as much as a chief financial officer needs an economic forecast in which he has no faith.) The overall conclusion is that the DNS root need not be signed with key sizes that would resist serious brute force attacks. See http://www.intaglionic.org/doc_indep_root_sign_proj.html#TOC:C. (document annex C. Risk Analysis Elements for DNSSEC Support at the Root). This conclusion is arrived at in a rather ad-hoc fashion. One can equally easily reach opposite conclusions, since the majority of administrators will not configure trust in static keys below the root, and in many cases domains below the root will have longer keys, especially if the root keys are not conservative. Do you have a suggestion for a less ad-hoc fashion? Sure, cracking the root will not be the easiest attack for most, but it really does need to be infeasible, as opposed to just difficult. Otherwise, the root is very much an attractive target for a well funded adversary. For which purpose(s) is the DNS root signature key an attractive target? Given these purposes, who are the potential adversaries (Dan Bernstein claims that they don't need to be well funded)? I am not really seeking an answer, but these question are investigated (indeed in a rather ad-hoc fashion) in the above referenced annex. Even if in most cases it is easier to social-engineer the domain registrar or deliver malware to the desktop of the domain's system administrator. Indeed. And maybe social-engineering the zone signature function comes in this category. You may observe that the DNS root zone signature function is also subject to social-engineering attack. This should be a basic concern for the DNS root key management procedures, independently for both the official DNS root signature and the Intaglio NIC alternative source. By the way, state-of-the-art in factorization is just a portion of the story. What about formal proofs of equivalence between a public key primitive and the underlying hard problem. Don't forget that the USG had to swallow RSA (only because otherwise its very *definition* of public key cryptography would have remained out-of-sync with the rest) and is still interested in having us adopt ECDSA. EC definitely has practical merit. Unfortunately the patent issues around protocols using EC public keys are murky. Neither RSA nor EC come with complexity proofs. Correct. In this perspective, the Rabin-Williams cryptosystem is superior. But nowadays nobody seeks to make this advantage available in standardized protocols. This is a fascinating area, ... Regards, -- - Thierry Moreau CONNOTECH Experts-conseils inc. 9130 Place de Montgolfier Montreal, QC, Canada H2M 2A1 Tel. +1-514-385-5691 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
Jerry Leichter wrote: On Apr 21, 2010, at 7:29 PM, Samuel Neves wrote: EC definitely has practical merit. Unfortunately the patent issues around protocols using EC public keys are murky. Neither RSA nor EC come with complexity proofs. While EC (by that I assume you mean ECDSA) does not have a formal security proof, i.e., it is as hard as the EC discrete log, it it much closer to one than RSA is to factoring. In particular, Pointcheval and Stern, and later Brown come close to a formal proof for ECDSA [1] It's perhaps worth pointing out again how little formal complexity proves tell you about security. Suppose we could show that RSA was as hard as factoring. So? Nothing is really known about how hard factoring is. At worst, it's NP-complete (though that's actually considered unlikely). But suppose *that* was in fact known to be the case. What would it tell us about the difficulty of factoring any particular product of two primes? Absolutely nothing. NP-completeness is a worst-case result. In principle, it could be the case that factoring is easy for numbers less than a billion bits long - it just becomes much harder eventually. (I put easy in quotes because it's usually taken to mean there's a poly-time algorithm, and that's a meaningless statement for a finite set of problems. *Every* finite set of problems has a O(1) time solution - just make a lookup table.) There are some concrete complexity results - the kind of stuff Rogoway does, for example - but the ones I've seen tend to be in the block cipher/cryptographic hash function spaces. Does anyone one know of similar kinds of results for systems like RSA? -- Jerry E.g. Koblitz, Neal; Menezes, Alfred, Another Look at ``Provable Security'', Cryptology ePrint Archive: Report 2004/152, available at http://eprint.iacr.org/2004/152.pdf. - Thierry Moreau - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
* Thierry Moreau: For which purpose(s) is the DNS root signature key an attractive target? You might be able to make it to CNN if your spin is really good. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
Florian Weimer wrote: * Thierry Moreau: For which purpose(s) is the DNS root signature key an attractive target? You might be able to make it to CNN if your spin is really good. Thanks for this feedback. No, no, and no. No, because I asked the question as a matter of security analysis methodology. My conclusion is that no purpose justifying an attack on the overall DNSSEC scheme particularly threatens the DNS root. No, because while someone else's answer might be formulated based on non-rationale anti-USG paranoia (leading to a nice media story), the pervasive USG influence in the DNSSEC key management has very different impacts, the foremost one being that the DNS root may actually be signed soon (hey, great!). No, because I don't want to handle the trouble of high visibility in a field where the public relations are already mixing up things (e.g. .org is signed but a registrant can't have a secure delegation for a .org domain as of today). Caveat: I stopped volunteering information about specific elements of official DNSSEC root key management which might be criticized. It is time for the DNS root signature project to move forward. Also, the Intaglio NIC project has no value unless the official DNS root holds secure delegations. But even without this self-restraint, there would be no spin for a CNN story. Dedication to good cryptographic key management is squarely dull and boring for a typical person. Regards, -- - Thierry Moreau CONNOTECH Experts-conseils inc. 9130 Place de Montgolfier Montreal, QC, Canada H2M 2A1 Tel. +1-514-385-5691 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
* Thierry Moreau: Florian Weimer wrote: * Thierry Moreau: For which purpose(s) is the DNS root signature key an attractive target? You might be able to make it to CNN if your spin is really good. But even without this self-restraint, there would be no spin for a CNN story. Dedication to good cryptographic key management is squarely dull and boring for a typical person. I was referring to news of a breach (whether through factoring or otherwise), not the key management procedures as such. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
On Wed, Apr 21, 2010 at 8:49 PM, Jerry Leichter leich...@lrw.com wrote: There are some concrete complexity results - the kind of stuff Rogoway does, for example - but the ones I've seen tend to be in the block cipher/cryptographic hash function spaces. Does anyone one know of similar kinds of results for systems like RSA? There is some interesting work in public key cryptosystems that reduce to a *random* instance of a specific problem. Here is a very cool one: http://eprint.iacr.org/2009/576 Public-Key Cryptographic Primitives Provably as Secure as Subset Sum Vadim Lyubashevsky and Adriana Palacio and Gil Segev Abstract: We propose a semantically-secure public-key encryption scheme whose security is polynomial-time equivalent to the hardness of solving random instances of the subset sum problem. The subset sum assumption required for the security of our scheme is weaker than that of existing subset-sum based encryption schemes, namely the lattice-based schemes of Ajtai and Dwork (STOC '97), Regev (STOC '03, STOC '05), and Peikert (STOC '09). Additionally, our proof of security is simple and direct. We also present a natural variant of our scheme that is secure against key-leakage attacks, as well as an oblivious transfer protocol that is secure against semi-honest adversaries. Unless I misunderstand, if you read someone's plaintext without having the private key then you have proven that P=NP! Nice. :-) Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
On Wed, Apr 21, 2010 at 5:29 PM, Samuel Neves sne...@dei.uc.pt wrote (on the cryptography@metzdowd.com list): [2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf I've been looking at that one, with an eye to using it in the One Hundred Year Cryptography project that is being sponsored by Google as part of the Google Summer of Code (see recent discussions on the tahoe-dev archives for April 2010 [1]). Later I discovered this paper [2] which appears to be an improvement on that one in terms of performance (see Table 1 in [2]) while still having a tight reduction to the Computational Diffie-Hellman (CDH) problem. Strangely, this paper [2] doesn't appear to have been published anywhere except as an eprint on eprint.iacr.org. I wonder why not. Is there something wrong with it? I still have some major questions about the funky hash into a curve part of these schemes. I'm hoping that [3] will turn out to be wrong and a nice simple dumb efficient hack will be secure for these particular digital signature schemes. Of course if the newfangled schemes which reduce to a random instance of a classic hard problem work out, that would provide an even stronger assurance of long-term safety than the ones that reduce to CDH. See for example the paper [4] that I mentioned previously on the cryptography@metzdowd.com mailing list. Unless I misunderstand, if you can break that scheme by learning someone's plaintext without knowing their private key, then you've also proven that P=NP! Unfortunately that one in particular doesn't provide digital signatures, only public key encryption, and what I most need for the One Hundred Year Cryptography project is digital signatures. Regards, Zooko [1] http://allmydata.org/pipermail/tahoe-dev/2010-April/date.html [2] http://eprint.iacr.org/2007/019 [3] http://eprint.iacr.org/2009/340 [4] http://eprint.iacr.org/2009/576 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
On Tue, Apr 20, 2010 at 08:58:25PM -0400, Thierry Moreau wrote: The DNS root may be qualified as a high valued zone, but I made the effort to put in writing some elements of a risk analysis (I have an aversion for this notion as I build *IT*controls* and the consultants are hired to cost-justify avoiding their deployments, basically -- but I needed a risk analysis as much as a chief financial officer needs an economic forecast in which he has no faith.) The overall conclusion is that the DNS root need not be signed with key sizes that would resist serious brute force attacks. See http://www.intaglionic.org/doc_indep_root_sign_proj.html#TOC:C. (document annex C. Risk Analysis Elements for DNSSEC Support at the Root). This conclusion is arrived at in a rather ad-hoc fashion. One can equally easily reach opposite conclusions, since the majority of administrators will not configure trust in static keys below the root, and in many cases domains below the root will have longer keys, especially if the root keys are not conservative. Sure, cracking the root will not be the easiest attack for most, but it really does need to be infeasible, as opposed to just difficult. Otherwise, the root is very much an attractive target for a well funded adversary. Even if in most cases it is easier to social-engineer the domain registrar or deliver malware to the desktop of the domain's system administrator. By the way, state-of-the-art in factorization is just a portion of the story. What about formal proofs of equivalence between a public key primitive and the underlying hard problem. Don't forget that the USG had to swallow RSA (only because otherwise its very *definition* of public key cryptography would have remained out-of-sync with the rest) and is still interested in having us adopt ECDSA. EC definitely has practical merit. Unfortunately the patent issues around protocols using EC public keys are murky. Neither RSA nor EC come with complexity proofs. -- Viktor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
On 21-04-2010 02:40, Victor Duchovni wrote: EC definitely has practical merit. Unfortunately the patent issues around protocols using EC public keys are murky. Neither RSA nor EC come with complexity proofs. While EC (by that I assume you mean ECDSA) does not have a formal security proof, i.e., it is as hard as the EC discrete log, it it much closer to one than RSA is to factoring. In particular, Pointcheval and Stern, and later Brown come close to a formal proof for ECDSA [1]. If one goes further into other schemes, there is Rabin-Williams for the factoring problem. There are also the schemes by Goh et al. [2] that are reducible to the CDH and DDH problems in generic abelian groups (like EC.) Would patents also apply to one of these schemes over an elliptic curve? Best regards, Samuel Neves [1] http://www.cacr.math.uwaterloo.ca/techreports/2000/corr2000-54.ps [2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
The state of the art in factorization is the same as for, e.g., the factorization of RSA-768 [1] --- there haven't been many advances in the number field sieve algorithm itself. The current effort, as Bernstein puts it, is in speeding up smoothness detection, as part of the relation collection process. Both the RSA-768 factorization paper and a previous one by the same authors [2] try to predict the effort needed for a 1024-bit prediction, which is estimated to be around 1000 times harder than a 768-bit modulus. [1] estimates to number of operations in the RSA768 factorization to be in the ballpark of 2^67 instructions: a thousand times harder puts this on about 2^77, which puts it in the realm of doable, but very hard, even for a well funded organization. We also have to take into account the logistics of doing such a factorization. Unlike an elliptic curve discrete logarithm computation, that takes (relatively) negligible storage and communication, the number field sieve requires massive amounts of data, and the linear algebra step could become (even more of) a problem. Best regards, Samuel Neves [1] http://eprint.iacr.org/2010/006 [2] http://eprint.iacr.org/2009/389 On 20-04-2010 16:45, Perry E. Metzger wrote: I was alerted to some slides from a talk that Dan Bernstein gave a few days ago at the University of Montreal on what tools will be needed to factor 1024 bit numbers: http://cr.yp.to/talks/2010.04.16/slides.pdf It has been a couple of years since there has been serious discussion on the list on this topic, and especially in the light of various technical decisions being undertaken on the size of DNS signing keys for high valued zones (like root), I was curious as to whether anyone had any interesting comments on the state of the art in factorization. Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
Perry E. Metzger wrote: I was alerted to some slides from a talk that Dan Bernstein gave a few days ago at the University of Montreal on what tools will be needed to factor 1024 bit numbers: http://cr.yp.to/talks/2010.04.16/slides.pdf I had the opportunity to listen to Prof. Dan Bernstein talk last Friday morning. I was very glad to see him as I respect his dedication to crypto maths, algorithm implementation, and very applied studies of computation complexity. The slides are pretty much representative of his talk. New material starts on slide 17. If you are familiar with the contents of slides 1-16 and elliptic curve methods (I am not), then you should appreciate the contents of slides 17 up to 45. Slides 46 to 47 deal with the computation speedups available with graphics processors. In the audience, there seemed to be some who followed the presentation more than I did but Dan made a great talk even for people like me. It has been a couple of years since there has been serious discussion on the list on this topic, and especially in the light of various technical decisions being undertaken on the size of DNS signing keys for high valued zones (like root), I was curious as to whether anyone had any interesting comments on the state of the art in factorization. According to my records, the state-of-the-art is reference Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra, and Peter L. Montgomery, On the Security of 1024-bit RSA and 160-bit Elliptic Curve Cryptography, version 2, August 7, 2009, 18 pages (published on pages 43-60 in Comments on the Transition Paper available at http://csrc.nist.gov/groups/ST/key_mgmt/documents/Transition_comments_7242009.pdf, which was listed at http://csrc.nist.gov/groups/ST/key_mgmt/index.html). plus this talk last Friday (and references). From these, you have to do your homework in guesswork about your actual enemy's power. In the Intaglio NIC project white paper I contributed towards the deployment of an alternate source for signed official DNS root data, I had to refer to the state-of-the-art. See http://www.intaglionic.org/doc_indep_root_sign_proj.html#TOC:3.6 (document section 3.6 Early Project Decisions about Protection Level). The DNS root may be qualified as a high valued zone, but I made the effort to put in writing some elements of a risk analysis (I have an aversion for this notion as I build *IT*controls* and the consultants are hired to cost-justify avoiding their deployments, basically -- but I needed a risk analysis as much as a chief financial officer needs an economic forecast in which he has no faith.) The overall conclusion is that the DNS root need not be signed with key sizes that would resist serious brute force attacks. See http://www.intaglionic.org/doc_indep_root_sign_proj.html#TOC:C. (document annex C. Risk Analysis Elements for DNSSEC Support at the Root). By the way, state-of-the-art in factorization is just a portion of the story. What about formal proofs of equivalence between a public key primitive and the underlying hard problem. Don't forget that the USG had to swallow RSA (only because otherwise its very *definition* of public key cryptography would have remained out-of-sync with the rest) and is still interested in having us adopt ECDSA. So, yes, it's always good to ask questions. I usually complain that one seldom gets a simple answer for a simple question addressed to a specialist. I don't feel I provided a simple answer, but I don't claim to be a specialist. Regards, - Thierry Moreau Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
