What's the state of the art in factorization?

[Zooko O'Whielacronx]

On Wed, Apr 21, 2010 at 8:49 PM, Jerry Leichter <leichter at 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 majordomo at metzdowd.com