Steven M. Bellovin wrote:
> http:/
/www.tgdaily.com/content/view/33425/118/
>
> "Ann Arbor (MI) - University of Michigan
scientists have discovered a
> breakthrough way to utilize light in cryptography. The
new technique
> can crack even complex codes in a matter of seconds.
Scientists believe
> this technique offers much advancement over current
solutions and could
> serve to foil national and personal security threats if
employed."...
>
> I'll let those who know more physics comment in detail;
from reading
> the article, it appears to lead to a way to construct
quantum computers.
Which means, if Moore's Law still applies, that in a few
years no
current code created by one of the three letter agencies
will be
safe from prying.
So what is the statute of limitations on invasion of privacy
suits? Or, if it has expired, then me may have proof
available
that people weren't crying wolf.
I've always loved the old saw, "Be careful what you
wish for, you
just might get it." My addendum is that you will
probably not
like the unintended consequences.
Best,
Allen
------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomo metzdowd.com
|
Via Farber's list:
From: Rod Van Meter <rdvsfc.wide.ad.jp>
Date: August 18, 2007 11:39:47 AM EDT
To: davefarber.net
Subject: Re: [IP] Light pulses crack security codes within
seconds
http:/
/www.tgdaily.com/content/view/33425/118/
Wow, that's one of the most egregious quantum
computing-related
articles I've ever seen. I'm not even sure where to start.
First off, let's point at the real research paper:
http://www.sciencemag.org/cgi/content/abstract/317/58
40/929
Coherent Optical Spectroscopy of a Strongly Driven Quantum
Dot
Xiaodong Xu, Bo Sun, Paul R. Berman, Duncan G. Steel, Allan
S. Bracker, Dan Gammon, L. J. Sham
I read it. It's an advance, but does not yet mean anything
at all is
practical. Their work is on the optical properties of
self-assembled
quantum dots. There are two major categories of quantum
dots in
semiconductors, self-assembled and lithographically created
(and
within each of those, many types). The self-assembled dots
are a
compound grown on top of a substrate of a different kind.
Differences
in the crystalline structure mean that the deposited
material "beads
up", like water on a freshly-waxed car. The quantum
dot itself then
is a place where the motion of electrons can be confined to
a small
two-dimensional area at the interface between the materials,
creating
a place where quantum wave functions can behave like an
"artificial
atom".
The work presented in the paper is some of the first solid
experimental work on the optical properties of
self-assembled dots
that I have seen, though I'm not an expert. Various groups,
including
that of my adviser, Kohei M. Itoh (
http://www.app
i.keio.ac.jp/Itoh_group/ ), have been working for years
on the growth and mechanical characteristics (stress/strain,
size and
shape, etc.) of self-assembled dots. All of that has been
very hard
work, and as far as I know no one has a reliable way to grow
the dots
in a given place. I wish they had a micrograph of the
device, I'd
like to see it.
But the TG article talks only a little about the research
itself; it's
mostly breathless pie-in-the-sky reporting on the
possibilities of
quantum computers.
"Light pulses crack security codes within
seconds," the title reads.
Wow. Well, first off, it can't be done yet, and won't be
done for
years, despite the present tense. Second, saying it's done
with light
pulses is like saying we compute today with electrons. It's
true, but
tells you nothing about transistors or computer
architecture. Third,
"crack security codes" is as vague and
non-technical as it gets, not
to mention outright wrong (we'll come back to that).
Fourth, "within
seconds" presumes many things about a quantum computer
that are not
yet defined to any level of precision. This topic is the
focus of my
research: how do you build a large-scale quantum computer
out of a
given technology? No one really knows yet.
Which security codes does a paper on the spectroscopy of a
quantum
dot break? Well, none, really. But where they're headed
with that is
obviously Shor's algorithm for factoring large numbers on a
quantum
computer. If the algorithm can be efficiently implemented,
it is
theoretically capable of breaking RSA public-key
cryptography and
elliptic curve crypto.
HOWEVER, the advantage may well be with the defenders on
this one.
Shor turns a super-polynomial problem (factoring) into a
polynomial
one. Not coincidentally, the complexity of running Shor is
similar to
the complexity of doing the encryption in the first place.
And
running an algorithm of the same computational class on a
quantum
machine will probably always be harder than running an
algorithm on a
classical computer. So, raise your key length and you might
be okay.
Shor does nothing to affect symmetric key cryptography, or
any system
not dependent on the factoring problem.
I hesitate to mention this, for fear it will be
misinterpreted, but in
my opinion there is still some small doubt about whether
Shor can in
practice be scaled to large sizes, on theoretical grounds,
let alone
the practical difficulties of building using any given
technology.
The problem is the quantum Fourier transform (QFT) that is
the key to
Shor requires, in the abstract, exponentially precise gates
as the
problem size grows. Most researchers believe that the QFT
can be
truncated at some reasonable level and will still have a
high
probability of success. However, the several papers on the
topic
(including one by a collaborator of mine) in the last decade
have
taken different approaches to the calculation, and come up
with
substantially different answers, making different
assumptions about
the problem. The theorists seem confident, but I will give
only
provisional assent until I see it implemented. Perhaps I'm
just not
smart enough to fully grasp the arguments in the papers.
Breaking a code in seconds really depends on both the
problem and the
machine. A major factor is how many levels of quantum
error
correction (QEC) are necessary, which is directly dependent
on the
quality of the physical implementation. QEC is a major
topic of
research; USC is even sponsoring a conference on the topic
in December
( http://qserver.usc.edu/
qec07/ ).
Physical and logical clock speed, as well as the amount of
parallelism
in the system, determine how long it will take to run the
algorithm on
a particular problem, of course. This fact has gotten too
little
attention from both the experimentalists and the theorists,
in my
opinion. See http://arxiv.or
g/abs/quant-ph/0507023 .
Enough for now. I can talk about this topic all day,
including what
the boundaries of my knowledge are; take everything I say
with a grain
of salt.
--Rod
--
Rodney Van Meter
Assistant Professor of Environment and Information Studies
Keio University, Shonan Fujisawa Campus, Japan
http://web.sfc.keio.a
c.jp/~rdv/
------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com
|
--
Steven M. Bellovin wrote:
> http:/
/www.tgdaily.com/content/view/33425/118/
>
> "Ann Arbor (MI) - University of Michigan
scientists
> have discovered a breakthrough way to utilize light
in
> cryptography. The new technique can crack even
complex
> codes in a matter of seconds. Scientists believe this
> technique offers much advancement over current
> solutions and could serve to foil national and
> personal security threats if employed."...
>
> I'll let those who know more physics comment in
> detail; from reading the article, it appears to lead
> to a way to construct quantum computers.
It is another *in* *principle* design: The computer is
programmed and supplied with data at optical
frequencies. We cannot modulate light at that frequency
with sufficient precision and detail. Perhaps we will
be able to soon.
As Moore's law progresses, quantum effects get
relatively larger. Another way of stating this proposal
is to say that when we can build classical computers
with nanoscale line widths and hundred terahertz clocks,
*then* we can build quantum computers - indeed, we will
have to, as our classical computers will start acting
weirdly due to quantum effects.
Quantum computers are best done with the highest
possible frequencies and the lowest possible energies,
so become more feasible as conventional computers become
faster and more energy efficient. If we had optical
computing at optical frequencies with quantum dots
acting as the nonlinear elements, yes, quantum effects
would be quite large, making classical computers harder,
and quantum computers easier.
If we could build a quantum computer of this design, we
could build a classical computer that operated at five
hundred terahertz, and in order program and interface
with the proposed quantum computer, we are going to
*need* a classical computer that operates at five
hundred terahertz, that is to say five hundred thousand
gigahertz, that is to say five million megahertz.
It will be a while before you can buy that one at Fry's.
------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography"
to majordomometzdowd.com
|
