Re: high-workload function, checkable in p

Mike Rosing (eresrch@msn.fullfeed.com)
Wed, 3 Jun 1998 08:41:40 -0500 (CDT)

• Next message: Kurt J. Lidl: "Re: Looking for Symmetric Key Hardware Accelerators"
• Previous message: dstoler: "Looking for Symmetric Key Hardware Accelerators"

On 3 Jun 1998, Julian Assange wrote:

>
> I'm looking for a high workload function, with a large domain, NP hard
> to compute but verifyable that the computation is correct in P and
> preferably not requiring big-nums. (e.g would knapsacks fit this goal?)
>

I've got a dumb question. What do you mean by "high workload
function"?

You can use polynomial (or normal basis) representations and use
logarithms of elliptic curve points for the NP hard problem. Verification
would be to do an elliptic curve multiply of the found factor times the
base point. In math:

let E be the curve y^2 + xy = x^3 + ax^2 + b over GF(2^n). Pick two
points P != Q at random on E. Then your problem is to find k such that
Q = kP. Verification is to multiply out kP and see that you get Q. You
don't need any bignums, just XOR and rotation. Finding k requires
exponential effort, verification goes as n^3, i.e. polynomial.

You can ensure a hard problem by picking a curve which has one very large
prime and a couple of small orders: #E = rp where r << p and p is the
large prime. (#E means the order of curve E.) Finding such curves is
"straight forward", but requres a bignum package. You can just pick a
known curve and avoid that problem.

Code is available: see http://msn.fullfeed.com/~eresrch
I'm in the process of writing specific cracking code for the Certicom
challenge, if you want preliminary stuff I'll be happy to send what I
have.

Patience, persistence, truth,
Dr. mike

• Next message: Kurt J. Lidl: "Re: Looking for Symmetric Key Hardware Accelerators"
• Previous message: dstoler: "Looking for Symmetric Key Hardware Accelerators"