2 ms·
Generally speaking, attacks which rely on more structure are hard to adapt to situations where there is less structure. Conversely, attacks which require no str
by djao 13y ago
Generally speaking, attacks which rely on more structure are hard to adapt to situations where there is less structure. Conversely, attacks which require no structure are easy to generalize to a wide variety of situations.
Something like Pollard rho requires no structure. It works in any group. The number field sieve is an intermediate case. It requires a norm (basically you need some elements to be bigger than others). For arbitrary finite fields, the NFS still represents the fastest known attack. The latest attack is a version of the function field sieve. The FFS uses, in an essential way, the algebraic structure of polynomials over a field. Coppersmith pioneered the use of the FFS in the 80s, when he showed that small characteristic fields (which consist primarily of polynomials) admit faster discrete logarithm solutions. The latest work goes far beyond Coppersmith's work, but tends towards increasing specialization, not generalization, since it adds the new requirement that the field contain an intermediate subfield.
Given that the direction of specialization appears, if anything, to be going in the other direction, there would have to be a substantial further breakthrough in order to apply these results more generally. My own opinion and intuition is that these results are not likely to apply to prime field discrete logs, never mind RSA and/or composite moduli.
- ColinWright 13y agoThat's an excellent and useful reply, and you've given me much to think about. Thank you.