Kevin Wampler wrote:
> commonly used encryption algorithms which are believed to be NP-hard to 

Diffie Hellman is based on discrete log. Isn't that NP?

-- 
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

Darren New wrote:
> Kevin Wampler wrote:
>> commonly used encryption algorithms which are believed to be NP-hard to 
> 
> Diffie Hellman is based on discrete log. Isn't that NP?
> 

Yes, although not in the way that you mean.  It's trivially shown to be 
in NP in the sense that many things are in NP which are not NP-hard (for 
instance anything in P is also in NP).  Although that's a common 
misconception, both discrete log and integer factorization are not 
believed to be NP-hard problems.  Hence the worry that quantum computers 
would break these cryptographic methods despite the face that very few 
people believe that they'd be able to solve NP-complete problems in 
polynomial time.

Post a reply to this message

Kevin Wampler wrote:
> Darren New wrote:
>> Kevin Wampler wrote:
>>> commonly used encryption algorithms which are believed to be NP-hard to 
>>
>> Diffie Hellman is based on discrete log. Isn't that NP?
>>
> 
> Yes, although not in the way that you mean.  It's trivially shown to be 
> in NP in the sense that many things are in NP which are not NP-hard (for 
> instance anything in P is also in NP). 

Well, obviously that's what I meant. I just wasn't being pedantic.

> Although that's a common 
> misconception, both discrete log and integer factorization are not 
> believed to be NP-hard problems.  

OK. That's what I wasn't sure of.  I thought discrete log was proven NP-hard.

So, no, I don't know of any crypto algorithms that depend on p!=np.

-- 
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

Darren New wrote:
>>> Diffie Hellman is based on discrete log. Isn't that NP?
>>>
>>
>> Yes, although not in the way that you mean.  It's trivially shown to 
>> be in NP in the sense that many things are in NP which are not NP-hard 
>> (for instance anything in P is also in NP). 
> 
> Well, obviously that's what I meant. I just wasn't being pedantic.

I figured, I commented on it more for the benefit of other people who 
might be following along and who are less familiar with the area :)


> So, no, I don't know of any crypto algorithms that depend on p!=np.

I wonder why this is.  It seems like it would be (relatively) 
straightforward to construct an encryption method which would be NO-hard 
to crack, so there must be a reason why this doesn't seem to be done. 
Perhaps instances of NP-hard problems tend to be much harder to analyze 
and predict the properties of, and thus it's easier to get an encryption 
algorithm which is susceptible to attacks in practice, despite the 
appearance of stronger theoretical guarantees.

Post a reply to this message

Kevin Wampler wrote:
> straightforward to construct an encryption method which would be NO-hard 
> to crack, so there must be a reason why this doesn't seem to be done. 

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.

-- 
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

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.

-- 
                                                          - Warp

Post a reply to this message

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

Darren New <dne### [at] sanrrcom> wrote:
> 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.

  One thing is certain: Creating a truly secure encryption system based on
an NP-hard algorithm is far from trivial. For example, all of these are
based on known NP-hard problems, yet can be cracked in a matter of weeks
with some hundreds of computers:

http://en.wikipedia.org/wiki/McEliece_cryptosystem
http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem
http://en.wikipedia.org/wiki/Naccache%E2%80%93Stern_knapsack_cryptosystem

  It seems that research on "future-proof" encryption systems which cannot
be cracked quickly even by a quantum computer is a hot topic of research,
and cryptosystems based on NP-hard problems is one line of study, but it's
actually surprisingly hard to come up with an actual cryptosystem which
cannot be cracked even with regular computers (much less quantum computers).

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> 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.
> 
>   One thing is certain: Creating a truly secure encryption system based on
> an NP-hard algorithm is far from trivial. For example, all of these are
> based on known NP-hard problems, yet can be cracked in a matter of weeks
> with some hundreds of computers:

Yeah. The basic problem is you *want* them to be crackable by someone with 
the key.  It's easy to make a system that can't be broken. It's hard to make 
a system that can't be broken *unless* you know some relatively small number 
of bits.

NP-Hard isn't difficult. NP-Hard with a private/public key is difficult. :-)

-- 
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

>> I'm sure you've already heard about this if you've been anywhere near
>> the internet today, but there's apparently a new claim at a proof of
>> P!=NP which at least looks pretty worth taking seriously:
>
>> http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf
>
>    If the proof results to be correct, I think a *lot* of people out there
> are going to sigh in relief (because an enormous amount of math and
> practical computer code out there rely on the assumption that P != NP).

http://en.wikipedia.org/wiki/P_versus_NP_problem#Claimed_solutions

...so I guess not then. :-(

Post a reply to this message