approaches to crypto

approaches to crypto

[Al Vilcius]

Dear friends: has anyone in CT-land been thinking about cryptography?
I'm looking for a structuralists' spin to the now classical approaches,
primarily relating to public key cryptosystems as initiated by [DH'76],
which complements the standard number theory approach [K'94].
In [D'88] Diffie suggests that abstractions which have proven to be useful
in addressing many other classical problems will also be needed in crypto.
Of course!
The classical central problem is to find suitable "one-way" functions or
algorithms: easy in one direction but "hard" in the other. Factoring is one
example, as well as discrete logs in finite fields and groups of elliptic
curves where the arithmetic is computationally difficult. A delightful
survey (translated from German) is given in the little MAA monograph [B'94]
by Beutelspacher, worth reading for its enjoyment alone.
Provably secure cryptosystems do exist; this occurs when there is an iso
between messages and random keys, although "truly random" is still
problematic. However, these are not practical in general, and are not used
commercially. Consequently, in trying to break cryptosystems, most
approaches to the crypanalysis are analytic, focusing on digital
computation. However I have this feeling that an "analogue" approach may be
fruitful. After all, one of the most successful attacks to date is DPA
(differential power analysis) [NYT'98] which is essentially an analogue or
non-computational method of extracting keys and other information. But in
addition to physical engineering methods, there may other logical analogue
approaches such as quantum computing that might be useful, and arise
categorically.
The property that small changes in a message should result in large changes
in the cryptogram may suggest some application of chaotic or non-linear
dynamical systems. This has indeed been tried, but again on a mechanical
rather than structural level.
It feels like time should be fundamental (temporal thinking?) since that
seems to provide the uniqueness to distinguish messages. However, this
should also involve a deeper understanding of variation (perhaps via time
sheaves) which might provide superior approaches in terms of thinking about
crypto problems.
An indication that crypto may be interesting to categorists is that
protocols could be viewed in game theoretic terms, the latter having already
been considered structurally. Furthermore, perhaps all attack scenarios can
be formulated in game theoretic terms, hence also defense strategies.
Another inspiration (at least to me) is induced by the nice treatment given
by Steve Vickers to the example of bit strings as topological systems that
threads through [V'89]. After all, 2-star-omega is the crypto base space.
As a final inducement, it is worth noting that there is real money in this
stuff. Commercial applications of crypto have great value in this security
conscious information society of ours.

Your thoughts would be most welcome, but no flames please. ... Al Vilcius
(retread algebraist).

References:
[B'94] Albrecht Beutelspacher, "Crypyology", Mathematical Association of
America, 1994
[D'88] Whitfield Diffie, "The First Ten Years of Public-Key Cryptograohy",
Proc IEEE, Vol 76, No. 5, May 1988, pp.560-77
[DH'76] Whitfield Diffie and Martin Hellman, "New Directions in
Cryptography", IEEE Transactions on Information Theory, Vol IT-22, No. 6,
Nov 1976, pp. 644-54
[K'94] Neal Koblitz, "A Course in Number Theory and Cryptography",
Springer-Verlag 1994
[NYT'98] "Cryptographers Discuss Finding Of Security Flaw in Smart Cards",
New York Times, June 10, 1998
[V'89] Steven Vickers, "Topology via Logic", Cambridge UP 1989