Mailing List Archive: GnuPG: users

Quantum computing

Index | Next | Previous | View Threaded

skrewz at skrewz

Apr 18, 2007, 12:10 AM

Post #1 of 18 (1540 views)
Permalink

Quantum computing

On 200704172359, Robert J. Hansen wrote:
> 1. We are unlikely to ever be able to brute-force a 256-bit
> keyspace. Ever. Not until computers are made of something other
> than matter, occupy something other than space, run on something
> other than energy, according to rules other than physics.

I was under the impression that quantum computers were about to provide
a break in factorization. From quick grep on Wikipedia, I find that:

http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity:
the best published asymptotic running time is for the general number
field sieve (GNFS) algorithm, which, for a b-bit number n, is:
O(exp(64/9b)^(1/3)(log b)^(2/3))

But for quantum computers, it'd seem that Shor's algorithm provides a
leap:

http://en.wikipedia.org/wiki/Shor's_algorithm:
Shor's algorithm is a quantum algorithm for factoring a number N in
O((log N)^3) time and O(log N) space.

However, since large quantum computers are rather expensive, getting log
N space is so costly that it isn't relevant just yet.

However, I assume you know what you talk about, when you say that we
aren't likely to factor 256-bit-numbers ever. So please restate that --
even in the face of quantum computers -- we won't ever factor 256 bit
numbers.

By the way, I realize that this is a more general question of gnupg's
life expectancy in a quantum computer world. But it's interesting to get
answered.

Regards, skrewz.

Attachments:

signature.asc (0.18 KB)

sven at radde

Apr 18, 2007, 3:27 AM

Post #2 of 18 (1450 views)
Permalink

Re: Quantum computing [In reply to]

Hi!

Anders Breindahl schrieb:
> So please restate that --
> even in the face of quantum computers -- we won't ever factor 256 bit
> numbers.
Apart from the fact that 256bit is about symmetric keys (a 256bit number
would be factored quite easily -- that's why we have 4096 bit RSA keys),
possible advances in cryptology are nothing that would require key
lifetimes. Once you do not feel comfortable enough with your current
keylength anymore, you can simply revoke the key manually.
Actually, predicting possible advances in fields like quantum computing
is very hard, so it would be far easier to follow the news on this topic
rather than decide *today* when your current key might become insecure
(to make a sensible decision about the expiry-date). Consequently, your
choice would have to be over-conservative (which is not necessarily a
bad thing).

Key expiry, to my understanding, is more of an automatic fallback
mechanism to limit the possible damage/inconvenience in the case that
you cannot take care of revoking the key yourself.
This does very well justify the short lifetimes that we see on keys today.

cu, Sven

_______________________________________________
Gnupg-users mailing list
Gnupg-users [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-users

malayter at gmail

Apr 18, 2007, 4:41 AM

Post #3 of 18 (1488 views)
Permalink

Re: Quantum computing [In reply to]

On 4/18/07, Anders Breindahl <skrewz [at] skrewz> wrote:
>
> However, I assume you know what you talk about, when you say that we
> aren't likely to factor 256-bit-numbers ever. So please restate that --
> even in the face of quantum computers -- we won't ever factor 256 bit
> numbers.
>
> By the way, I realize that this is a more general question of gnupg's
> life expectancy in a quantum computer world. But it's interesting to get
> answered.

Robert was referring to a 256-bit key space, which refers to symmetric
encryption, such as AES,

Factoring, on the other hand, applies only to public-key RSA
encryption. There "bits" mean something totally different; a bit of
RSA key length is "worth less" than a bit of symmetric key length.
Numbers have already been factored in the ~600 bit range, so at least
1024 bits are recommended for RSA, and 2048 bits is a good idea.

The "keyspace" size of RSA is roughly equivalent to the
O(exp(64/9b)^(1/3)(log b)^(2/3)) that you quote; That is the number of
operations that must be performed to break the algorithm by brute
force. For strong symmetric algorithms,like AES or Twofish, the number
of operations required is simply two to the power of the number of
bits in the key,

Note that breaking Diffie-Hellman and other discrete logarithm based
algorithms is thought to be nearly equivalent to factoring, but has
not been proven to be so.

I suggest you borrow a copy of Bruce Schneier's _Applied
Cryptography_; it is a very good primer.

Regards,
Ryan

_______________________________________________
Gnupg-users mailing list
Gnupg-users [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-users

malayter at gmail

Apr 18, 2007, 5:23 AM

Post #4 of 18 (1490 views)
Permalink

Re: Quantum computing [In reply to]

On 4/18/07, Ryan Malayter <malayter [at] gmail> wrote:
> Factoring, on the other hand, applies only to public-key RSA
> encryption. There "bits" mean something totally different; a bit of
> RSA key length is "worth less" than a bit of symmetric key length.
> Numbers have already been factored in the ~600 bit range, so at least
> 1024 bits are recommended for RSA, and 2048 bits is a good idea.

This page represents a reasonable snapshot of the state of the art in factoring:
http://www.rsa.com/rsalabs/node.asp?id=2093

One must assume that a governmental entity like China's Ministry of
State Security can factor significantly larger numbers than the 640
bit factorization done by academic researchers. Which is why you often
see recommendations for 1500+ bit RSA keys.

--
Ryan

_______________________________________________
Gnupg-users mailing list
Gnupg-users [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-users

rjh at sixdemonbag

Apr 18, 2007, 7:05 AM

Post #5 of 18 (1490 views)
Permalink

Re: Quantum computing [In reply to]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

> On 200704172359, Robert J. Hansen wrote:
>> 1. We are unlikely to ever be able to brute-force a 256-bit
>> keyspace. Ever. Not until computers are made of something other
>> than matter, occupy something other than space, run on something
>> other than energy, according to rules other than physics.
>
> I was under the impression that quantum computers were about to
> provide
> a break in factorization. From quick grep on Wikipedia, I find that:

They've been "about to provide" a break in factorization for the last
30 years.

> However, I assume you know what you talk about, when you say that we
> aren't likely to factor 256-bit-numbers ever. So please restate
> that --
> even in the face of quantum computers -- we won't ever factor 256 bit
> numbers.

We're already factoring 256-bit numbers. Fortunately, I didn't claim
256-bit composites would forever be secure. I claimed 256-bit
keyspace searches would be secure.

Keyspace search is a different set of problems than factorization.
For a brute-force search the best we can do is Grover's quantum
database algorithm, which reduces it down to an equivalent 128-bit
keyspace. From there we use quantum thermodynamics--namely the
Margolus-Levitin theorem--to get some reasonable bounds on how much
time, energy, etc., are required to do it.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)

iQEcBAEBCgAGBQJGJiWiAAoJELcA9IL+r4EJCTcH/RUOxI6RNuuu2WaCpAeJLfHs
0u+KzJ6MALtonHQOkAbhDTw8zTC+OTHEuN/t2+dwli6E8r7F61RIMpLyPiZpfS0y
rQjHMqJPMdr7Xerhn1haGdov2MzbvtloqHBEP9T65fstTEYBXoYMDSNhYVRV1Fpz
g+is39fVr6D3LZ5W50VQhtTwmcpGM7ZKl4XSgqtv2UwwPM7dYjMQ+Qgz+5MnPLe3
wZlD06/bvrbY5InFRQFMaFhNtVAC6v42G6W8AOv8WD0kXJCopUGOwYelQ40qhdug
DvXWxpApv7jgmStms63AlG3TjQemwF3rkreFsk9IClAZ5T3EpTafqVd3HC4oYBc=
=OqFT
-----END PGP SIGNATURE-----

_______________________________________________
Gnupg-users mailing list
Gnupg-users [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-users

rjh at sixdemonbag

Apr 18, 2007, 7:14 AM

Post #6 of 18 (1489 views)
Permalink

Re: Quantum computing [In reply to]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

> Note that breaking Diffie-Hellman and other discrete logarithm based
> algorithms is thought to be nearly equivalent to factoring, but has
> not been proven to be so.

Going off the top of my head, the DLP is known to be greater than or
equal to the difficulty of the IFP. You can make strong arguments
that they're equal difficulty in a computational-theoretic sense, and
you can make strong arguments that in real silicon DLP will be
stronger due to our current lack of understanding of how to
efficiently use the general number field sieve for the DLP. The
current state of the art in the GNFS requires a large amount of
storage overhead for the DLP, while the storage overhead for the IFP
is comparatively minimal.

As a word of warning, comparing DLP to IFP is a spectacularly black
art. There are so many nuances to it that just expressing some of
the ideas in English is difficult.

As further warning: it's 9:10am, I haven't yet had my morning cup of
coffee, and I'm working without my references. This being the
internet, there's also a nonzero chance that I'm barking mad.
Confirm this information before relying on it.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)

iQEcBAEBCgAGBQJGJierAAoJELcA9IL+r4EJSgoH/jz2SyN/4ZfAsnoJossJn6cp
/b/CND53iaqPnIv6vKcjDNfseBYdp2ZRHTZPw1ZVhd9+zdUwKr8IfVmFh8+XA/Ra
ayEnbf/OzfVw+VK9nSJfvroHBZnW/UQYFkwFsCpwYpXLDSab1JjNPV1Ys67lqx3e
gnM2w0fjDoXwE0hI+InCceL+bptOIpZL+xQN3AgYRovsUGG5rwngjOPk31+5SCFV
iMe1msmNhOV8KWcIkOFHeRZQxHKMtDVoZfSnv7BLYh4Ufh/moNDpIF9RI1/JuwJI
5eSXPEAzNAOXSxqyyrd5YC9ykMxMss69/BD7I6yfBQxHCcskUBjDsynxjLg+2NQ=
=Qxyo
-----END PGP SIGNATURE-----

_______________________________________________
Gnupg-users mailing list
Gnupg-users [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-users

dshaw at jabberwocky

Apr 18, 2007, 7:24 AM

Post #7 of 18 (1489 views)
Permalink

Re: Quantum computing [In reply to]

On Wed, Apr 18, 2007 at 09:10:17AM +0200, Anders Breindahl wrote:
> On 200704172359, Robert J. Hansen wrote:
> > 1. We are unlikely to ever be able to brute-force a 256-bit
> > keyspace. Ever. Not until computers are made of something other
> > than matter, occupy something other than space, run on something
> > other than energy, according to rules other than physics.
>
> I was under the impression that quantum computers were about to provide
> a break in factorization. From quick grep on Wikipedia, I find that:

Robert was commenting on a symmetric cipher (like AES), not asymmetric
(like RSA). Factoring a 256-bit RSA key is trivial and can be done on
regular home PCs in fairly short order. However, factoring is not an
attack against symmetric ciphers.

My favorite comment (from Jon Callas at PGP, Inc) about brute forcing
keys is one I think I've posted here before, but still:

Modern cryptographic systems are essentially unbreakable, particularly
if an adversary is restricted to intercepts. We have argued for,
designed, and built systems with 128 bits of security precisely
because they are essentially unbreakable. It is very easy to
underestimate the power of exponentials. 2^128 is a very big
number. Burt Kaliski first came up with this characterization, and
if he had a nickel for every time I tell it, he could buy a latte or
three.

Imagine a computer that is the size of a grain of sand that can test
keys against some encrypted data. Also imagine that it can test a
key in the amount of time it takes light to cross it. Then consider
a cluster of these computers, so many that if you covered the earth
with them, they would cover the whole planet to the height of 1
meter. The cluster of computers would crack a 128-bit key on average
in 1,000 years.

If you want to brute-force a key, it literally takes a planet-ful of
computers. And of course, there are always 256-bit keys, if you
worry about the possibility that government has a spare planet that
they want to devote to key-cracking.

Note that he's talking about brute-forcing keys here. If someone
finds a weakness in AES (or whatever), then this math may change
radically. Pure brute-forcing without such a weakness is just not
viable.

David

_______________________________________________
Gnupg-users mailing list
Gnupg-users [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-users

rjh at sixdemonbag

Apr 18, 2007, 5:56 PM

Post #8 of 18 (1492 views)
Permalink

Re: Quantum computing [In reply to]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

I'm going to talk about Grover's algorithm and Shor's algorithm, plus
a good bit on computational complexity theory. The two algorithms
are completely different and tackle completely different problems.
When I talk about computational complexity theory I'll tie the two
algorithms together to show how and when each one is used.

Please bear with me. This is going to be long.

> So I take your word for it, that 256 bit keyspace searches are
> infeasible, even in the quantum-computer world. I assume that advances
> in factorization are comparably insignificant...?

As mentioned, Grover's is the best we can do for quantum speedups to
brute-forcing. Grover's algorithm is a technique for using quantum
mechanics to search through a database of N entries in time
proportional to the square root of N, using an amount of storage
proportional to the logarithm of N.

This is important because brute-forcing a key can be thought of as
searching through an unsorted database trying to find the right
entry. In math we'd say these two problems are isomorphic to each
other. "Isomorphic", for the purposes of this email, just means that
we can convert one problem into a different problem with some trivial
transformation. As with most things in math the real definition is a
little more involved, but this one will work for our purposes.

For instance, multiplication and division are isomorphic to each
other. To divide by 3, just multiply by 1/3. To multiply by 3, just
divide by 1/3. Etcetera. That's isomorphism in a nutshell. Please
remember what isomorphism means; you're going to see it again later
in this email.

Searching through an unsorted database and brute-forcing a key are
isomorphic to each other. So we do a trivial transformation on the
brute-forcing math problem to convert it into a database search
problem, and then we sic Grover's on it.

Now, that said, Grover's has limits. Its first constraint is that it
doesn't make problems trivial. It just increases our ability to deal
with them. Brute-forcing a 128-bit cipher using a traditional
computer is a ridiculous proposition, but using Grover's, it becomes
as hard as brute-forcing a 64-bit cipher... hard, but possible.

So the best way to defend against exhaustive key search in a quantum
world is to either (a) trust that quantum computing is going to
remain "in just a couple of years" for the next few decades (which
may very well be true), or (b) multiply your key sizes by a factor of 2.

The principal reason why AES supports a 256-bit key is because of the
possibility of quantum computing and Grover's algorithm. Brute-
forcing a 256-bit cipher with Grover's is as hard as brute-forcing a
128-bit cipher with a conventional computer... absolutely
ridiculous. :)

> Then... It would seem that quantum computers poses no threat to
> traditional cryptography -- helped by increases in key sizes...?

Quantum computing poses no threat to symmetric cryptography.
Asymmetric cryptography, however, gets a little funky.

Shor's algorithm uses quantum mechanics to solve the integer
factorization problem (and, I believe, the discrete logarithm
problem) in extraordinary short time. The downside of Shor's is it
requires an insane amount of memory--you need two qubits for each and
every bit of the number you're trying to factor. So if you're trying
to factor a 2048-bit RSA key, you need over four _thousand_ qubits.

Our current largest quantum computer is about fifteen qubits.

When this monstrously huge quantum computer was demonstrated by IBM,
it created a huge hue and cry in the press. Most cryptographers
dismissed this as much ado over nothing. Schneier is apocryphally
quoted as saying "yeah, any RSA modulus with fewer than eight bits is
now truly fucked."

But wait, the good news doesn't stop there. Not only is quantum
computing a long way off from being able to tackle RSA and/or El
Gamal, but Shor's algorithm is _only_ applicable against asymmetric
systems built on the integer factorization problem and/or the
discrete logarithm problem.

For instance, Lamport signatures are a perfectly valid asymmetric
signature scheme that are secure even against quantum computing. If
and when quantum computing develops to the point where a research lab
gets a couple of hundred qubits together, the OpenPGP working group
will almost certainly add asymmetric algorithms that are highly
resistant to quantum computing.

Now for the real head-bending things. Why is it there's such an
efficient way to solve the integer factorization problem and the
discrete logarithm problem, but such an inefficient way to brute-
force a key?

Computational theory is the branch of mathematics that's concerned
with the fundamental limits of what computers can do. In
computational theory, we have several different classifications of
problems, depending on how much time and space are required to solve
them.

There are _tons_ of different complexity classes. The ones we're
going to be talking about here are P, NP, and NP-COMPLETE.

A problem is said to be in P if and only if it can be solved in an
amount of time proportional to its input. For instance, the bubble
sort runs in time proportional to the square of its input.
Bubblesorting one hundred elements takes a hundred times larger than
bubblesorting ten elements.

A problem is said to be in NP if and only if verifying the answer for
the problem is in P. For instance, factorization is clearly in NP.
If I tell you that 37 and 73 are the two factors of 2701, you can
easily multiply 37 and 73 together to prove it. Since, once given an
answer, proving the answer is in P, we know that the problem of
finding the answer must be in NP.

NP-COMPLETE means "this problem is one of the hardest problems in
NP". "Hardest" here has a very precise meaning which I'm going to
mostly gloss over. You can think of it as "a problem is in NP-
COMPLETE if it is isomorphic to another NP-COMPLETE problem".

(This raises the question of "so how do we find the first NP-COMPLETE
problem?" Ah, well, that's why we have so much respect for Stephen
Cook, who thunked down a couple of hundred pages of mathematical
proof establishing a problem called SAT as the hardest problem in
complexity class NP. Once Cook had done his heroic feat of
mathematical hacking, all that us Johnny-Come-Latelies have had to do
is show other problems are isomorphic to SAT.)

Finally, you can always punt a problem into a higher complexity
class. If you want to, you can convert a P problem into an NP-
COMPLETE problem... but you can't convert an NP-COMPLETE problem into
a P problem. That would be a downward punt, and it's not allowed.

Got all that? Great. Now it should be easy to follow the rest.

When we brute-force a key, we are effectively punting the problem up
into NP-COMPLETE. That means it's _really, really hard_.

When we discover mathematical weaknesses or flaws in a cryptographic
algorithm, if there's determinism we can exploit, then we're tackling
the problem in a much lower complexity class. That means it's much
easier.

Shor's Algorithm applies to two specific problems that live in NP.

Grover's Algorithm applies to _every_ NP-COMPLETE problem.

Shor's Algorithm is as fast as it is because it's (a) highly
specialized and (b) solves an easy problem. Grover's Algorithm is as
slow as it is because it's (a) highly general and (b) solves a very
hard problem.

... One last word. Computational theory purists will tear this email
to absolute shreds. After all, how can I talk about quantum
computing without talking about complexity classes BQP or the P=NP
problem or...?

The worst part about it is, _they're absolutely right_.

You're asking a very, very detailed and technical question that
requires a ton of disciplined study just to learn the language needed
to describe the boundaries of the problem. If you really want to
know this material, you need to take a graduate-level course in
computational theory and a strong undergraduate course in quantum
physics. You'll also need enough background in mathematics not to go
running screaming from the room when people start talking about
Hadamard matrices and discrete Fourier transforms and everything else
that goes along with it.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)

iQEcBAEBCgAGBQJGJr5QAAoJELcA9IL+r4EJn/YIAIxyk7mP5SH/rxOxjCe3M+AH
A8NOgKDMf8Ty9DtRRVedLVOjnZccHJaiK2IqHWu5IcvYQSMK4ljHkclqvtnp9QWq
VVquVUakq7gceG4R1BYukdsIoZJY9eatH6n8/wZTdG6V+mzw3RQQyrzuPA6azStr
iFaGuPraKXndnCVYqvsu3sMPq59ZBU4biAn0H59WGlZ8nr8a6GY8JFSu26aE3jUJ
QLJLj6xPU7cS2+a0v3bZYWdTdwjDp9vrc26QzIk1gnX51Ity9+fJb7SO1/ZKvban
LGXg6fKkKB0E5wDP8P6mLuSkm94a9oTAaQ+L0zHMVLtGJ+xP4FjbsrHoOiAF130=
=YkAE
-----END PGP SIGNATURE-----

_______________________________________________
Gnupg-users mailing list
Gnupg-users [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-users

skrewz at skrewz

Apr 19, 2007, 4:11 PM

Post #9 of 18 (1478 views)
Permalink

Re: Quantum computing [In reply to]

Hi,

On 200704181956, Robert J. Hansen wrote:
> Please bear with me. This is going to be long.

Introductory cryptography in the middle of the night. Why would I miss
it? :)

Thanks for answering.

> As mentioned, Grover's is the best we can do for quantum speedups to
> brute-forcing. Grover's algorithm is a technique for using quantum
> mechanics to search through a database of N entries in time
> proportional to the square root of N, using an amount of storage
> proportional to the logarithm of N.
>
> Now, that said, Grover's has limits. Its first constraint is that it
> doesn't make problems trivial. It just increases our ability to deal
> with them. Brute-forcing a 128-bit cipher using a traditional
> computer is a ridiculous proposition, but using Grover's, it becomes
> as hard as brute-forcing a 64-bit cipher... hard, but possible.

The executive summary being that increases in key sizes makes
traditional symmetric cryptography keep up with advances in quantum
computing, such as Grover's algorithm for searching the keyspace.

> > Then... It would seem that quantum computers poses no threat to
> > traditional cryptography -- helped by increases in key sizes...?
>
> Quantum computing poses no threat to symmetric cryptography.
> Asymmetric cryptography, however, gets a little funky.
>
> Shor's algorithm uses quantum mechanics to solve the integer
> factorization problem (and, I believe, the discrete logarithm
> problem) in extraordinary short time. The downside of Shor's is it
> requires an insane amount of memory--you need two qubits for each and
> every bit of the number you're trying to factor. So if you're trying
> to factor a 2048-bit RSA key, you need over four _thousand_ qubits.
>
> Our current largest quantum computer is about fifteen qubits.

Which I also remarked in the original post. However, when (if?)
commercial interests grab a hold of quantum computing, huge leaps in
cost of production perhaps could be achieved, making memory-rich quantum
computers abundant -- at least, from my chair, there's no obstruction to
this future. (?)

> If and when quantum computing develops to the point where a research
> lab gets a couple of hundred qubits together, the OpenPGP working
> group will almost certainly add asymmetric algorithms that are highly
> resistant to quantum computing.

Although this fight between attacking and defending computer security
measures is probably inevitable -- no final solution will probably be
found -- this pragmatism causes me to ponder the scenario in which
something like Rice' theorem could be established for quantum computers'
ability (or traditional computers' inability): Something that pops out
of the blue and shatters all hope for traditional cryptography...
Perhaps only in the long run, but still inevitably forces a move towards
other measures of security.

It's somewhat a political issue, too. Not that it can be solved
politically, but it has political consequences -- will cryptography (or
computer security in a more general sense) once again be for those who
can afford it?

-- But leave that be. For now, it's technical.

> You're asking a very, very detailed and technical question that
> requires a ton of disciplined study just to learn the language needed
> to describe the boundaries of the problem. If you really want to
> know this material, you need to take a graduate-level course in
> computational theory and a strong undergraduate course in quantum
> physics. You'll also need enough background in mathematics not to go
> running screaming from the room when people start talking about
> Hadamard matrices and discrete Fourier transforms and everything else
> that goes along with it.

I'm already on it.

Regards, skrewz.

Attachments:

signature.asc (0.18 KB)

rjh at sixdemonbag

Apr 19, 2007, 5:25 PM

Post #10 of 18 (1478 views)
Permalink

Re: Quantum computing [In reply to]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

> Which I also remarked in the original post. However, when (if?)
> commercial interests grab a hold of quantum computing, huge leaps in
> cost of production perhaps could be achieved, making memory-rich
> quantum
> computers abundant -- at least, from my chair, there's no
> obstruction to
> this future. (?)

Eh. I'm still unconvinced. It wasn't until last year that the final
physics hurdle to large-scale QC was addressed (large systems have a
strong tendency to near spontaneously decohere, turning your quantum
computer into an expensive paperweight). We still have no idea how
to apply this physics knowledge, however.

Just knowing that something is possible doesn't mean the ability to
do it is around the corner. We can teleport atoms in laboratories at
the speed of light and we know how to do it for macro-scale items,
but the engineering difficulties are so large that I doubt we'll see
it in our lifetimes.

While I agree that commercial development _may_ lead to developments
in QC, I think it's equally likely that the engineering difficulties
will be insurmountable. Which means that, from where I sit, we
should just shrug and say "we really can't say with any confidence
what the future will or will not hold".

> found -- this pragmatism causes me to ponder the scenario in which
> something like Rice' theorem could be established for quantum
> computers'
> ability (or traditional computers' inability):

What do you mean? Rice's theorem applies to QC.

Computational theory is computational theory. We've already got very
robust mathematics to describe the computational properties of QC.
We know that BQP is a superset of P, that it does not encompass NP-
COMPLETE, that it has some overlap with NP, etc., etc.

It's true that in mathematics there could always be a proof delivered
tomorrow by some hungry graduate student which will utterly shatter
our knowledge of math as we know it. But this is true for all of
mathematics. It's not as if this risk is special to QC. You should
be just as concerned about the prospect of P=NP.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)

iQEcBAEBCgAGBQJGKAhmAAoJELcA9IL+r4EJPM4H/3lBPfZa9Uo+86whHTtKX2Vi
Y7tm/jXSdy0JVCXXjpOfl8tlb7vllX7OeG2PzCwjX8mbn20OaaEFccBLSRhKga00
YBKB6xdcaXtPDBHVq/bgFO2wFQyc77xdpdd6Uoem34OCx8H65XC/4N+pgvTC0LDj
JkAGVaAABaCKwS4wIWrVNiFZRpVfuXDYx6QTaAWw789vDmVR3I06elbYVYHANnr4
R7KzTl+Y46qp2XMoKSLBore+xrvjqdailkMYP97D7rsYyCE5V3CtntoUYMerMiWy
DgXjHR/kM06Ja1jaOTu4SKstE1zJjMGgHwj3qeCLgqvijiiuTmSYVdvhjMU4ROE=
=wy/G
-----END PGP SIGNATURE-----

_______________________________________________
Gnupg-users mailing list
Gnupg-users [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-users

skrewz at skrewz

Apr 20, 2007, 12:09 AM

Post #11 of 18 (1487 views)
Permalink

Re: Quantum computing [In reply to]

On 200704191925, Robert J. Hansen wrote:
> While I agree that commercial development _may_ lead to developments
> in QC, I think it's equally likely that the engineering difficulties
> will be insurmountable. Which means that, from where I sit, we
> should just shrug and say "we really can't say with any confidence
> what the future will or will not hold".

Well. Yeah. But the thing that was and is fascinating about cryptography
is that it -- assuming some model of computing -- is ``provable too
hard'' to bypass. I'm worried that the future holds in store revolutions
in computability that will shake those assumptions on ``too hard''.

This is in contrast to quantum cryptography, which, IINM, is provably
uninterceptable (but, unlike traditional cryptography, has many
weaknesses beyond the purely theoretical ones).

> > found -- this pragmatism causes me to ponder the scenario in which
> > something like Rice' theorem could be established for quantum
> > computers'
> > ability (or traditional computers' inability):
>
> What do you mean? Rice's theorem applies to QC.

Again, if I got it correctly, Rice' theorem came into a world where
science was occupied with proving that this and that property was
undecidable. Something ``like'' Rice' theorem would in a similar way
alter the way that the scientific field is on.

> It's true that in mathematics there could always be a proof delivered
> tomorrow by some hungry graduate student which will utterly shatter
> our knowledge of math as we know it. But this is true for all of
> mathematics. It's not as if this risk is special to QC.

I was mostly focusing on positive proofs, by which I mean those that
define what _is_ doable or assumable, rather than the negative proofs
that define what is undoable.

Both are convenient. However, the proofs that consolidate the security
of programs like gnupg, assume some model of computation... And in the
face of quantum computing, that assumption may (=has the potential to)
radically change.

So what I would love to see is some proof that -- even when faced with
this new model of computing, ignoring its practical limitations -- the
best-known attack on gnupg's algorithms takes factor ten of the lifetime
of the universe or would cost twice the energy of the sun.

Which can't be said of RSA on a huge quantum computer, if I understood
you correctly.

> You should be just as concerned about the prospect of P=NP.

I haven't had my introductory courses in computability theory yet. I
don't know what that is, and will patiently wait for it.

Thanks for the lecture.

Regards, skrewz.

Attachments:

signature.asc (0.18 KB)

wk at gnupg

Apr 20, 2007, 12:56 AM

Post #12 of 18 (1494 views)
Permalink

Re: Quantum computing [In reply to]

On Fri, 20 Apr 2007 09:09, skrewz [at] skrewz said:

> This is in contrast to quantum cryptography, which, IINM, is provably
> uninterceptable (but, unlike traditional cryptography, has many
> weaknesses beyond the purely theoretical ones).

While you mention this, I can't resist to forward Perry E. Metzger's
comments:

To: cryptography at metzdowd
Subject: my periodic rant on quantum crypto
From: "Perry E. Metzger"
Date: Mon, 12 Apr 2004 15:37:33 -0400

/. is running yet another story on quantum cryptography today, with
the usual breathless hype:

http://science.slashdot.org/article.pl?sid=04/04/12/133623

I'm especially unimpressed with the "Does this spell the
end of the field of cryptography?" comment.

For those who don't know much about what it is, "Quantum Cryptography"
is a very expensive way of producing an unauthenticated link
encryption device. It is useless for any application other than link
encryption over a short distance and requires a dedicated optical
fiber to work.

QC has no properties that render it especially better for link
encryption than, say, a box from one of several vendors running AES on
the link instead. It is perhaps theoretically safer, but in practice
no one is going to break AES either -- they're going to bribe the
minimum wage guard at your colo to have 20 minutes alone with your box
while they install a tap on the clear side of it (or worse, they'll
slip in while the guard is asleep at his desk.)

QC still requires link authentication (lest someone else other than
the people you think you're talking to terminate your fiber
instead). As a result of this, you can't really get rid of key
management, so QC isn't going to buy you freedom from that.

QC can only run over a dedicated fiber over a short run, where more
normal mechanisms can work fine over any sort of medium -- copper, the
PSTN, the internet, etc, and can operate without distance limitation.

QC is fiendishly costly -- orders of magnitude more expensive than an
AES based link encryption box.

QC is extremely hard to test to assure there are no hardware or other
failures -- given the key in use, I can use intercepted traffic to
assure my AES link encryption box is working correctly, but I have no
such mechanism for a QC box.

On top of all of this, the real problems in computer security these
days have nothing to do with stuff like how your link encryption box
works and everything to do with stuff like buffer overflows, bad
network architecture, etc.

Given that what we're dealing with is a very limited technology that
for a very high price will render you security that is at best not
particularly better than what much more economical solutions will
yield, why do people keep hyping this? Indeed, why do people buy these
boxes, if indeed anyone is buying them?

It is stunning that a lab curiosity continues to be mentioned over
and over again, not to mention to see venture capitalists dump money
after it.

BTW, none of this has anything to do with "Quantum Computing", which
may indeed yield breakthroughs someday in areas such as factoring but
which is totally unrelated...

Perry

Salam-Shalom,

Werner

_______________________________________________
Gnupg-users mailing list
Gnupg-users [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-users

rjh at sixdemonbag

Apr 20, 2007, 2:41 AM

Post #13 of 18 (1483 views)
Permalink

Re: Quantum computing [In reply to]

Anders Breindahl wrote:
> Well. Yeah. But the thing that was and is fascinating about cryptography
> is that it -- assuming some model of computing -- is ``provable too
> hard'' to bypass. I'm worried that the future holds in store revolutions
> in computability that will shake those assumptions on ``too hard''.

I forget who said this, but it's my favorite quote about predicting the
future. "The future never comes to us well-ordered." It's always
punctuated with unpredictable advances and inexplicable delays. You can
either obsess over the fact that crypto is a branch of mathematics, and
thus a human endeavor subject to the disordered-future rule, or you can
smile and shrug and say "well, we'll do the best with what we have, and
keep our eyes open for the future."

My best advice is to not worry about it. :)

> This is in contrast to quantum cryptography, which, IINM, is provably

There is no such thing as quantum cryptography. "Cryptography" is a
broad term encompassing a great many subjects, and we simply don't have
that for the quantum world.

Quantum key exchange is an interesting trick of physics. But that's all
"quantum cryptography" is at this point--a simple key exchange
algorithm. There are no quantum encryption algorithms, no quantum
signature schemes, no quantum hash functions. Just quantum key
exchange... which is nowhere near as cool as people make it out to be.

It's an interesting parlor trick. It's not anything new in the world of
crypto.

> Again, if I got it correctly, Rice' theorem came into a world where
> science was occupied with proving that this and that property was
> undecidable. Something ``like'' Rice' theorem would in a similar way
> alter the way that the scientific field is on.

[scratches head] Are you talking about the second Hilbert problem? That
one generally goes to G�del or Turing. Rice's theorem is an interesting
bit of work with some deep consequences for computer science, but it's
not anywhere near as big of a shakeup as incompleteness.

> Both are convenient. However, the proofs that consolidate the security
> of programs like gnupg, assume some model of computation...

What proofs? There are none. There are just lines of reasoning which
we believe to have substantial weight, but nobody has delivered an
actual proof of security for any cipher or hash. To do so you'd have to
prove P != NP, and that's one of the Holy Grails of CompSci.

Look at something as simple as RSA. There are three major conjectures
that go into RSA.

1. The RSA problem (RSAP) is equivalent to the integer
factorization problem.

2. The Integer Factorization Problem is not in P.

3. P != NP.

None of those have been proven. None. We like to pretend that they
have been, we like to handwave them, but the reality is those
conjectures are unproven... and, in fact, #1 is probably false.

See Boneh and Venkatesan, "Breaking RSA May Be Easier than Factoring".

http://theory.stanford.edu/~dabo/papers/no_rsa_red.pdf

> So what I would love to see is some proof that -- even when faced with
> this new model of computing, ignoring its practical limitations --

Why? Seriously. Why? By and large, cryptanalysis of intercepts is a
dead issue. Nobody with half a brain does it.

According to the best information available, during the entire Cold War
the KGB and GRU were never able to break a single United States cipher
cleared for top-secret information. That's not to say the KGB and GRU
weren't reading top-secret cables on a regular basis. Instead of
cryptanalyzing the traffic, they just sent expensive hookers and good
bourbon to cipher clerks in the American embassy.

There are literally thousands of ways to skin this cat. Focusing on
purely the mathematical aspect is very shortsighted.

_______________________________________________
Gnupg-users mailing list
Gnupg-users [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-users

skrewz at skrewz

Apr 20, 2007, 4:57 AM

Post #14 of 18 (1477 views)
Permalink

Re: Quantum computing [In reply to]

[ Please interrupt if this is getting too off-topic. ]

On 200704200441, Robert J. Hansen wrote:
> Anders Breindahl wrote:
> > Well. Yeah. But the thing that was and is fascinating about cryptography
> > is that it -- assuming some model of computing -- is ``provable too
> > hard'' to bypass. I'm worried that the future holds in store revolutions
> > in computability that will shake those assumptions on ``too hard''.
>
> I forget who said this, but it's my favorite quote about predicting the
> future. "The future never comes to us well-ordered." It's always
> punctuated with unpredictable advances and inexplicable delays. You can
> either obsess over the fact that crypto is a branch of mathematics, and
> thus a human endeavor subject to the disordered-future rule, or you can
> smile and shrug and say "well, we'll do the best with what we have, and
> keep our eyes open for the future."
>
> My best advice is to not worry about it. :)

Yeah, again. I completely agree on the practical aspect of it, but would
nevertheless like to see proofs of complexity that weren't dependent on
the current models of computations.

However, then you'll just invent the hardware-coming-in-3050 model, that
does all its calculations by solving RSA. Or whatever I aim to defend.

> > This is in contrast to quantum cryptography, which, IINM, is provably
>
> There is no such thing as quantum cryptography. "Cryptography" is a
> broad term encompassing a great many subjects, and we simply don't have
> that for the quantum world.

I was referring to the subject that is mentioned on the Wikipedia page:
http://en.wikipedia.org/wiki/Quantum_cryptography

Saying that ``there is no such thing'' seems harsh and as if you ignore
reality. The European Union put its hopes up for implementing a
``quantum cryptography'' network of communications. That sort of makes
the term real in itself.

Link to that statement in Danish:
http://ing.dk/apps/pbcs.dll/article?AID=/20040826/IT/108270093

That doesn't mean that it (quantum cryptography) by any means is
practical. It would seem from Werner's forward that it's so deeply
buried in its own infancy or -- more seriously -- inherent
technicalities, that it won't find any practical use ever.

However, quantum cryptography does have that nice inherent benefit, that
it _can't_ be eavesdropped, according to said article. That is, after
authenticity has been established and the line has been paid for:

http://en.wikipedia.org/wiki/Quantum_cryptography#Attacks:
In Quantum Cryptography, traditional man-in-the-middle attacks are
impossible due to the Observer Effect. If Mallory attempts to
intercept the stream of photons, he will inevitably alter them. He
cannot re-emit the photons to Bob correctly, since his measurement has
destroyed information about the photon's full state and correlations.

I suppose that this is the feature that got the European Union's
attention.

> > Again, if I got it correctly, Rice' theorem came into a world where
> > science was occupied with proving that this and that property was
> > undecidable. Something ``like'' Rice' theorem would in a similar way
> > alter the way that the scientific field is on.
>
> [scratches head] Are you talking about the second Hilbert problem? That
> one generally goes to G�del or Turing. Rice's theorem is an interesting
> bit of work with some deep consequences for computer science, but it's
> not anywhere near as big of a shakeup as incompleteness.

Then take that for an example. My point is that proofs can alter the
heading of a scientific field in the time it takes to they're generally
accepted.

> > Both are convenient. However, the proofs that consolidate the security
> > of programs like gnupg, assume some model of computation...
>
> What proofs? There are none.

I was merely assuming that such proofs existed. But, when I think again,
formal proofs of correctness are hard to get, too, so why would
common cryptography be provable?

> > So what I would love to see is some proof that -- even when faced with
> > this new model of computing, ignoring its practical limitations --
>
> Why? Seriously. Why? By and large, cryptanalysis of intercepts is a
> dead issue. Nobody with half a brain does it.

It's the you-don't-know-that-question. *Probably*, it's secure, and all
data supports it, but it hasn't been proved to be secure. Therefore,
it's restricted to being ``probably'' or ``very probably'' secure.
Right?

Contrary to one time pads, which are provably secure -- where ``secure''
means ``unbreakable from theoretical standpoint, but with no thought
given to practical limits''.

I was told that one time pads were also used by the KGB, by the way.
Mini-books whose pages were to be burned after using.

> According to the best information available, during the entire Cold War
> the KGB and GRU were never able to break a single United States cipher
> cleared for top-secret information. That's not to say the KGB and GRU
> weren't reading top-secret cables on a regular basis. Instead of
> cryptanalyzing the traffic, they just sent expensive hookers and good
> bourbon to cipher clerks in the American embassy.

Though it sounds sweet, it's beyond the scope of cryptography to ensure
such protection (to some extent, though, security should limit room for
personnel ``breakage'').

And you're right. Nobody needs a formal proof for any of this, since it
probably (in lack of a better word) is good/secure/strong enough.

> There are literally thousands of ways to skin this cat. Focusing on
> purely the mathematical aspect is very shortsighted.

Or rather, it's very unproductive.

Many a problem stands open in mathematics and scientists spend their
lives on solving or proving them. However, progress is overall slow, and
computer science's overall more pragmatic approach gives *results*. And
many of us are grateful for that.

But the attractive part of focusing on the mathematical aspects are that
-- if provable -- it could give some guarantee ( > reassurance)
of the unbreakability of the ciphers out there.

You may not be interested in that, but I am. I too however neither will
end up a mathematician whose life is focused on solving some single
problem.

But I would be interested in the result. I could pick the cipher that
provably could withstand any battering thinkable over the cipher that
perhaps couldn't.

Regards, skrewz.

Attachments:

signature.asc (0.18 KB)

rjh at sixdemonbag

Apr 20, 2007, 9:13 AM

Post #15 of 18 (1486 views)
Permalink

Re: Quantum computing [In reply to]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

> Yeah, again. I completely agree on the practical aspect of it, but
> would
> nevertheless like to see proofs of complexity that weren't
> dependent on
> the current models of computations.

I don't mean to sound flip, but as soon as you invent a hypercomputer
I would love to revisit this issue with you. For now, all our
computational theoretic proofs will be limited by the the lambda
calculus. I don't mean to sound blunt there, but our current model
of computation is extraordinarily robust, and there are very strong
arguments that hypercomputation is both physically and mathematically
impossible. (If any problem in UNDECIDABLE can be solved by an
oracle, then math goes from incomplete and inconsistent straight into
pervasively self-contradictory and broken. That's the rationale for
hypercomputation being physically and mathematically impossible.)

> I was referring to the subject that is mentioned on the Wikipedia
> page:
> http://en.wikipedia.org/wiki/Quantum_cryptography

Wikipedia is not an authoritative reference.

"Quantum cryptography" is a nice catchphrase. I'm unaware of any
respected authority in the field of crypto who takes the phrase
seriously.

The phrase is used in nontechnical media, and in that environment its
usage is probably defensible. After all, people reading the
newspaper don't want to be bothered with the details of what QKE is
all about. But we're trying to be precise here, and for that reason,
let's not talk about quantum cryptography. Let's be precise and talk
about QKE.

> Contrary to one time pads, which are provably secure -- where
> ``secure''
> means ``unbreakable from theoretical standpoint, but with no thought
> given to practical limits''.
>
> I was told that one time pads were also used by the KGB, by the way.
> Mini-books whose pages were to be burned after using.

The NSA was breaking the KGB's one-time pads. Look into Project
VENONA. Soviet cipher clerks were making technical errors in using
their one-time pads and the NSA was able to start reading their traffic.

So yeah, I'm not sure why you want flawless perfect proofs of
security when reality shows that provably secure systems never are.

> Though it sounds sweet, it's beyond the scope of cryptography to
> ensure
> such protection (to some extent, though, security should limit room
> for
> personnel ``breakage'').

It's beyond the realm of mathematical cryptography, but not the field
as a whole.

My day job involves security analysis of electronic voting machines
for the National Science Foundation [*]. We spend far, far more time
scrutinizing the human side of the cryptography than the mathematical
side. Probably an order of magnitude.

[*] I'm not speaking for the NSF here, obviously, I'm completely
responsible for any errors I make, etc., etc.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)

iQEcBAEBCgAGBQJGKOavAAoJELcA9IL+r4EJ0cUIAKtWkRqLLXEfUfUzGmCTLXep
rsaxL2M3pBooQ9IIrnaTqKJxGkwyctYELZj94q+qcO+UZQ63HQGs7cslK7o1/Wyl
lN23aBlio7lABDT+jqyZYg2RWj2Urb6TKpYdTqsKiYM7MA2oxLpvIw9ear5s3Nxe
33uGKb5S3rZzjoYPgz35KXaqX7Qq9STbXFkiP70PsA8CazYXo3F9Tlqa+/n2/Wwf
Ti18Ga3DVjQoFx3uuU2U/+99gAQKrU9f6J6Q0N4WDFJO3Elst+7eCB89FEuoQYOl
iM2/bxTvJ+2/Uk022b++nlc7agtgMtJaVTsec7mbDqyaNinD5BR3jQgRl3oG7E8=
=p91A
-----END PGP SIGNATURE-----

_______________________________________________
Gnupg-users mailing list
Gnupg-users [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-users

alex at bofh

Apr 20, 2007, 9:48 AM

Post #16 of 18 (1482 views)
Permalink

Re: Quantum computing [In reply to]

On Fri, Apr 20, 2007 at 01:57:46PM +0200, Anders Breindahl wrote:

> Saying that ``there is no such thing'' seems harsh and as if you ignore
> reality. The European Union put its hopes up for implementing a
> ``quantum cryptography'' network of communications. That sort of makes
> the term real in itself.

This is because they are a governement and gov't usually wants to have
super secure comm network for gov't super secret communication.

> However, quantum cryptography does have that nice inherent benefit, that
> it _can't_ be eavesdropped, according to said article. That is, after
> authenticity has been established and the line has been paid for:

It can be eavesdropped, but it is impossible to intercept information
that way and the eavesdropping is detectable. Or rather should be:
eavesdropping on QC link is detectable if by rule single photons are
used as transmission units. This is because there's no way to
intercept a photon and reinject it without destroying its quantum
state. However, in commercial installations pulses (batches of
photons) are used, so its perfectly possible to intercept a piece of
the pulse. My quantum-fu is too weak to really know if this makes the
eavesdropping undetectable, but the intuition says that yes.

> I suppose that this is the feature that got the European Union's
> attention.

EU is know for sinking money in very bizarre projects.

> But the attractive part of focusing on the mathematical aspects are that
> -- if provable -- it could give some guarantee ( > reassurance)
> of the unbreakability of the ciphers out there.
>
> You may not be interested in that, but I am. I too however neither will
> end up a mathematician whose life is focused on solving some single
> problem.
>
> But I would be interested in the result. I could pick the cipher that
> provably could withstand any battering thinkable over the cipher that
> perhaps couldn't.

But the point is that the ciphers live in the real world and in the
real world it is much easier to do HUMINT (like "ale and whores"
mentioned before, or rubberhose cryptanalysis) instead of trying to
break the mathematically unbreakable. Be it provably unbreakable or
not.

OpenPGP and GPG is about making the idea-based mathematic apparatus
suited to survive in the real world. If you want to see what it takes,
find a movie called "In ascolto" or "The Listening" (it was shot in
Italy by Italians, and was released both in Italian and English), it
is a somewhat loose on technical side, but shows the difference
between mathematical/theoretical and real life security. P2P file
details on (encrypted) request.

Alex
--
JID: alex [at] hell
PGP: 0x46399138
od zwracania uwagi na detale s� lekarze, adwokaci, programi�ci i zegarmistrze
-- Czerski

_______________________________________________
Gnupg-users mailing list
Gnupg-users [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-users

skrewz at skrewz

Apr 21, 2007, 1:22 PM

Post #17 of 18 (1484 views)
Permalink

Re: Quantum computing [In reply to]

On 200704201113, Robert J. Hansen wrote:
> > Yeah, again. I completely agree on the practical aspect of it, but
> > would nevertheless like to see proofs of complexity that weren't
> > dependent on the current models of computations.
>
> I don't mean to sound flip, but as soon as you invent a hypercomputer
> I would love to revisit this issue with you.

I realise(d). See below.

> For now, all our computational theoretic proofs will be limited by
> the the lambda calculus. I don't mean to sound blunt there, but our
> current model of computation is extraordinarily robust, and there are
> very strong arguments that hypercomputation is both physically and
> mathematically impossible. (If any problem in UNDECIDABLE can be
> solved by an oracle, then math goes from incomplete and inconsistent
> straight into pervasively self-contradictory and broken. That's the
> rationale for hypercomputation being physically and mathematically
> impossible.)

A pretty good one, too.

In any case, if I want a model-of-computation-unbound proof of
difficulty, you'll simply invent a new model-of-computation that handles
my problem efficiently.

The point that you're telling me and I'm telling you is that such proofs
can't exist and aren't feasible to pursue.

> So yeah, I'm not sure why you want flawless perfect proofs of
> security when reality shows that provably secure systems never are.

``never'' is in this case based on one case of provable secure scheme
(that was notably difficult in implementation)?

> > Though it sounds sweet, it's beyond the scope of cryptography to
> > ensure such protection (to some extent, though, security should
> > limit room for personnel ``breakage'').
>
> It's beyond the realm of mathematical cryptography, but not the field
> as a whole.
>
> My day job involves security analysis of electronic voting machines
> for the National Science Foundation [*]. We spend far, far more time
> scrutinizing the human side of the cryptography than the mathematical
> side. Probably an order of magnitude.

I could easily imagine. Also, I assume that your systems limit room of
human control.

Regards, skrewz.

Attachments:

signature.asc (0.18 KB)

rjh at sixdemonbag

Apr 21, 2007, 3:05 PM

Post #18 of 18 (1481 views)
Permalink

Re: Quantum computing [In reply to]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

> ``never'' is in this case based on one case of provable secure scheme
> (that was notably difficult in implementation)?

I wouldn't be so quick to place blame on the difficulty of
implementing the one-time pad. Implementing the OTP is really pretty
simple: use each pad once and burn it when you're done. The
difficulty lies in trying to make fallible human nature rise to the
level of competency required to use the OTP.

Anyway, to answer your question, no. It's based on a couple of things.

1. Many provably secure schemes are isomorphic to the one-time pad.
This means that the other provably secure schemes share the same
flaws as the OTP.

2. The provably secure schemes that aren't isomorphic to the OTP
typically get broken pretty quickly.

As an example of #2, look at IBM's Atjai-Dwork, which was released at
CRYPTO97. Atjai-Dwork was some nice work, really, with a beautiful
mathematical proof of security. I emphasize this: _proof_. It
wasn't built on conjecture.

Within a year there were three different breaks against Atjai-Dwork.
Turns out the axioms Atjai and Dwork used to build the algorithm
weren't quite as robust as they thought.

Moral of the story: proofs of security are nice. They give us
something to point and laugh at.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)

iQEcBAEBCgAGBQJGKoqZAAoJELcA9IL+r4EJ0NAH/iITpey1J+7LSzmOEhQXmx07
neLiSqeTb++9yy2mWWlYt8WyfvALbljNWrgmyZqFoRrMRVkkF+MhbqEPm9PcyOcp
ndE78mqt+9xI+H7SY6heFyWRemKtXVpGBYalHeFh3P+K/1xzmAio6SwfTw6PxYl+
gvAy1pvvNY1HNi/jux6PzCyI3AVSZGudV92/6cQJkED0UOPIdWcuoyu1PHY2g8St
hhLmVXewBe41P883wV1y3/5mwQBTGp+j6yH9i1FZ/46vzVhRbwidJgtYSZpnB9Yn
fsXfZlazX5MFVIJQyeUOzkARYmD4Go+sALw6TP75HhRrXYBlv7CWAqsMkm57WPg=
=sGBb
-----END PGP SIGNATURE-----

_______________________________________________
Gnupg-users mailing list
Gnupg-users [at] gnupg
http://lists.gnupg.org/mailman/listinfo/gnupg-users

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads