5.8.1. "What are the truly basic, core, primitive ideas of
cryptology, crypto protocols, crypto anarchy, digital cash,
and the things we deal with here?"
- I don't just mean things like the mechanics of encryption,
but more basic conceptual ideas.
5.8.2. Crypto is about the creation and linking of private spaces...
5.8.3. The "Core" Ideas of Cryptology and What we Deal With
- Physics has mass, energy, force, momentum, angular
momentum, gravitation, friction, the Uncertainty Principle,
Complementarity, Least Action, and a hundred other such
concepts and prinicples, some more basic than others. Ditto
for any other field.
+ It seems to many of us that crypto is part of a larger
study of core ideas involving: identity, proof, complexity,
randomness, reputations, cut-and-choose protocols, zero
knowledge, etc. In other words, the buzzwords.
- But which of these are "core" concepts, from which others
are derived?
- Why, for example, do the "cut-and-choose" protocols work
so well, so fairly? (That they do has been evident for a
long time, and they literally are instances of Solomonic
wisdom. Game theory has explanations in terms of payoff
matrices, Nash equilibria, etc. It seems likely to me
that the concepts of crypto will be recast in terms of a
smaller set of basic ideas taken from these disparate
fields of economics, game theory, formal systems, and
ecology. Just my hunch.)
+ statements, assertions, belief, proof
- "I am Tim"
+ possession of a key to a lock is usually treated as proof
of...
- not always, but that's the default assumption, that
someone who unlocks a door is one of the proper
people..access privileges, etc.
5.8.4. We don't seem to know the "deep theory" about why certain
protocols "work." For example, why is "cut-and-choose," where
Alice cuts and Bob chooses (as in fairly dividing a pie),
such a fair system? Game theory has a lot to do with it.
Payoff matrices, etc.
- But many protocols have not been fully studied. We know
they work, but I think we don't know fully why they work.
(Maybe I'm wrong here, but I've seen few papers looking at
these issues in detail.)
- Economics is certainly crucial, and tends to get overlooked
in analysis of crypto protocols....the various "Crypto
Conference Proceedings" papers typically ignore economic
factors (except in the area of measuring the strength of a
system in terms of computational cost to break).
- "All crypto is economics."
- We learn what works, and what doesn't. My hunch is that
complex crypto systems will have emergent behaviors that
are discovered only after deployment, or good simulation
(hence my interest in "protocol ecologies").
5.8.5. "Is it possible to create ciphers that are unbreakable in any
amount of time with any amount of computer power?"
+ Information-theoretically secure vs. computationally-secure
+ not breakable even in principle, e.g., a one-time pad
with random characters selected by a truly random process
(die tosses, radioactive decay, certain types of noise,
etc.)
- and ignoring the "breakable by break-ins" approach of
stealing the one-time pad, etc. ("Black bag
cryptography")
- not breakable in "reasonable" amounts of time with
computers
- Of course, a one-time pad (Vernam cipher) is theoretically
unbreakable without the key. It is "information-
theoretically secure."
- RSA and similar public key algorithms are said to be only
"computationally-secure," to some level of security
dependent on modulus lenght, computer resources and time
available, etc. Thus, given enough time and enough computer
power, these ciphers are breakable.
- However, they may be practically impossible to break, given
the amount of energy in the universe.Not to split universes
here, but it is interesting to consider that some ciphers
may not be breakable in _our_ universe, in any amount of
time. Our universe presumably has some finite number of
particles (currently estimated to be 10^73 particles). This
leads to the "even if every particle were a Cray Y-MP it
would take..." sorts of thought experiments.
But I am considering _energy_ here. Ignoring reversible
computation for the moment, computations dissipate energy
(some disagree with this point). There is some uppper limit
on how many basic computations could ever be done with the
amount of free energy in the universe. (A rough calculation
could be done by calculating the energy output of stars,
stuff falling into black holes, etc., and then assuming
about kT per logical operation. This should be accurate to
within a few orders of magnitude.) I haven't done this
calculation, and won't today, but the result would likely
be something along the lines of X joules of energy that
could be harnessed for computation, resulting in Y basic
primitive computational steps.
I can then find a modulus of 3000 digits or 5000 digits, or
whatever,that takes more than this number of steps to
factor.
Caveats:
1. Maybe there are really shortcuts to factoring. Certainly
improvements in factoring methods will continue. (But of
course these improvements are not things that convert
factoring into a less than exponential-in-length
problem...that is, factoring appears to remain "hard.")
2. Maybe reversible computations (a la Landauer, Bennett,
et. al.) actually work. Maybe this means a "factoring
machine" can be built which takes a fixed, or very slowly
growing, amount of energy.
3. Maybe the quantum-mechanical idea of Shore is possible.
(I doubt it, for various reasons.)
I continue to find it useful to think of very large numbers
as creating "force fields" or "bobbles" (a la Vinge) around
data. A 5000-decimal-digit modulus is as close to being
unbreakable as anything we'll see in this universe.
By Tim May, see README
HTML by Jonathan Rochkind