Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> It is. The problem is that you don't want it to be NP-hard for *everyone*.
> 
>> You only want it NP-hard for people who don't know the key.
> 
>   Well, by definition an answer to an NP problem can be verified in
> polynomial time.

Right. But here what you want is that people can verify it in polynomial 
time *with* the key, but can't verify it in polynomial time *without* the 
key.  "Verifying" would be "decrypting the message and getting something 
reasonable" for example.

I imagine it can be done. I just don't imagine it's easy to come up with a 
system like that, nor that it's easy to prove a mathematical problem is easy 
with the key and NP-hard without.

-- 
Darren New, San Diego CA, USA (PST)
    C# - a language whose greatest drawback
    is that its best implementation comes
    from a company that doesn't hate Microsoft.

Post a reply to this message