![](/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) |
Neeum Zawan wrote:
> I hate you.
Oh good. Join the back of the queue. It's long enough. :-/
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) |
On 2010-08-10 01:27, Warp wrote:
> If P != NP indeed is correct, then it's certain that no algorithm can
> exist that cracks an NP encryption in polynomial time. Not now, nor any
> time in the future.
You mean 'certain that no algorithm can brute-force *all combinations*
of an NP encryption in polynomial time.' Merely cracking is somewhat
more trivial, since you (usually) don't need to go through every
possibility.
--
Tim Cook
http://empyrean.freesitespace.net
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) |
Tim Cook <z99### [at] gmail com> wrote:
> On 2010-08-10 01:27, Warp wrote:
> > If P != NP indeed is correct, then it's certain that no algorithm can
> > exist that cracks an NP encryption in polynomial time. Not now, nor any
> > time in the future.
> You mean 'certain that no algorithm can brute-force *all combinations*
> of an NP encryption in polynomial time.' Merely cracking is somewhat
> more trivial, since you (usually) don't need to go through every
> possibility.
If P != NP, then there can't exist an algorithm which takes any given
input and solves a provably NP problem on that input in polynomial time.
Of course that doesn't mean that *no* inputs can be solved in polynomial
time (it's rather easy to give trivial individual examples of any NP problem
which can be solved very fast). It means that you can't write a program
which cracks all files encrypted with a certain algorithm in polynomial
time. (And in fact, due to the nature of most NP problems, it won't be
able to crack almost *any* such problem in polynomial time, except for
extremely trivial situations.)
(Of course we have to remember what the 'N' stands for in "NP". It
doesn't stand for "non", as many people erroneously think. It stands for
"non-deterministic". This means that a non-deterministic algorithm can
solve the problem in polynomial time. Of course implementing this would
need some new physics to be discovered. Quantum computing is the most
promising one, but might not lead anywhere.)
--
- 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:
> If P != NP, then there can't exist an algorithm which takes any given
> input and solves a provably NP problem on that input in polynomial time.
>
> Of course that doesn't mean that *no* inputs can be solved in polynomial
> time (it's rather easy to give trivial individual examples of any NP problem
> which can be solved very fast). It means that you can't write a program
> which cracks all files encrypted with a certain algorithm in polynomial
> time. (And in fact, due to the nature of most NP problems, it won't be
> able to crack almost *any* such problem in polynomial time, except for
> extremely trivial situations.)
Is it not also true that although, for example, factorising numbers is
an NP problem, factorising the product of two Mersenne primes might turn
out to have a polynomial-time algorithm?
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) |
Invisible <voi### [at] dev null> wrote:
> factorising numbers is an NP problem
It's actually not that simple.
NP problems are decision problems, where the answer is "yes" or "no".
Obviously "what are the factors of this number?" is not such a problem.
The integer factorization problem is an so-called function problem. It
trivially falls into FNP (the function-problem equivalent of NP), but it's
not known if it's also in FP (the function-problem equivalent of P).
You can make integer factorization into a decision problem by posing it
as "does n have a factor which is smaller tham m?" (posing it like this
is theoretically rational and useful because if you found an algorithm
to solve that problem quickly, you could use it to factorize the number
quickly by using binary search). Again, it's not known which complexity
class this decision version of the problem falls into either.
--
- 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:
> The vast majority of modern cryptography uses algorithms which have been
> proven to be NP, and their security relies on the assumption that P != NP.
Technically, I don't think this is true. Symmetric cyphers aren't based on
NP problems. DH is based on discrete log which I think is NP, but RSA is
based on an NP problem *with* a trap door, yes? Otherwise it would be hard
for everyone. I was pretty sure most of the algorithms involve something
that *would* be NP if it weren't for trap doors, but again maybe I'm
misremembering. This isn't really my domain.
> (Of course there's still the possibility that a new discovered physical
> phenomenon can be used to solve NP problems fast with enormously massive
> parallelism or other weirdness.)
There's always that. It's only NP for Turing machines.
--
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) |
Warp wrote:
>
> The vast majority of modern cryptography uses algorithms which have been
> proven to be NP, and their security relies on the assumption that P != NP.
>
> If P != NP indeed is correct, then it's certain that no algorithm can
> exist that cracks an NP encryption in polynomial time. Not now, nor any
> time in the future.
>
I was sort of asking if you actually had any specific examples of
commonly used encryption algorithms which are believed to be NP-hard to
crack, because the ones I can think of aren't and thus wouldn't
necessarily be safe even if P!=NP.
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:
> 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) |