Quantum computing

Anders Breindahl skrewz at skrewz.dk
Sat Apr 21 22:22:48 CEST 2007

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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : /pipermail/attachments/20070421/bfb41a4c/attachment.pgp 

More information about the Gnupg-users mailing list