Neeum Zawan wrote:

> I hate you.

Oh good. Join the back of the queue. It's long enough. :-/

Post a reply to this message

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

Tim Cook <z99### [at] gmailcom> 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

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

Invisible <voi### [at] devnull> 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

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

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

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