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