![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New <dne### [at] san rr com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> Darren New <dne### [at] san rr com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New <dne### [at] san rr com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> Darren New <dne### [at] san rr com> 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/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |