Re: cryptology, complexity, and quantum cryptology
From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 02/11/05
- Next message: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Previous message: Keith Ramsay: "Re: does sqrt(2) exist in CM?"
- In reply to: Ralph Hartley: "Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?"
- Next in thread: tchow_at_lsa.umich.edu: "Re: cryptology, complexity, and quantum cryptology"
- Reply: tchow_at_lsa.umich.edu: "Re: cryptology, complexity, and quantum cryptology"
- Reply: Ralph Hartley: "Re: cryptology, complexity, and quantum cryptology"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Fri, 11 Feb 2005 09:43:41 +0100
Ralph Hartley wrote:
> Mitch Harris wrote:
>> Ralph Hartley <hartley@aic.nrl.navy.mil> wrote:
>
>>> I was also under the impression that BPP is strongly suspected to be
>>> equal to P
>
> That is so. There are theorems that if some other complexity classes are
> different then P and BPP must be the same.
do you remember what the specifics are?
> Also, at least one of the most famous BPP problems (primality testing)
> turned out to be in P.
I never thought of it like that. (I always though of its easiest
inclusion as in coNP, intersect NP, and then by Miller-Rabin
On the other hand, I don't think BPP is known to be in NP (despite all
the expectations).
>>> Quite a bit of effort has gone into *trying* to find polynomial
>>> algorithms for those problems. Modern crypto protocols would
>>> essentially collapse if one were found.
>>
>> yes, but cryptology wouldn't collapse, because there -are- non-number
>> theoretic methods that use a provable NP-complete problem (I can't
>> remember exactly what these are, I just remember that there are some).
>
> NP completeness is not that relevant to cryptography, because it only
> deals with worst case. It isn't enough to have a code that is
> *sometimes* hard to break.
>
> There was once a public key code that used the knapsack problem. It
> turned out that it never generated hard instances of the NP complete
> problem, so it was broken.
- yes, but that doesn't mean there aren't others...
- (I just looked it up...) The method I was thinking of is the
Ajtai-Dwork (1997) cryptosystem (based on the closest vector problem.
They proved that worst case and average case for the problem were
equivalent. Unfortunately, that supposedly also has difficulties
(Nguyen and Stern (1998))
> A *proof* that a cypher is NP complete to break, can make it vulnerable
> to known (or is it chosen?) plaintext attacks. The reduction used in the
> proof lets you solve the NP complete problem if you can get plaintext
> cyphertext pairs.
That's neat. How does that work?
-- Mitch Harris (remove q to reply)
- Next message: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Previous message: Keith Ramsay: "Re: does sqrt(2) exist in CM?"
- In reply to: Ralph Hartley: "Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?"
- Next in thread: tchow_at_lsa.umich.edu: "Re: cryptology, complexity, and quantum cryptology"
- Reply: tchow_at_lsa.umich.edu: "Re: cryptology, complexity, and quantum cryptology"
- Reply: Ralph Hartley: "Re: cryptology, complexity, and quantum cryptology"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
