Cyphernomicon Top
Cyphernomicon 5.8

Cryptology:
The Nature of Cryptology


    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.
  

Next Page: 5.9 Practical Crypto
Previous Page: 5.7 Related Ideas

By Tim May, see README

HTML by Jonathan Rochkind