From: Vaughan Pratt <pratt@cs.Stanford.EDU>
Date: Fri, 29 Dec 1995 17:58:18 +0800
To: cypherpunks@toad.com
Subject: Re: Fwd: Re: Fwd: Re: FH radios [Dave Emery] [Vaughan Pratt]
In-Reply-To: <9512270551.AA23874@pig.die.com>
Message-ID: <199512290049.QAA28702@Coraki.Stanford.EDU>
MIME-Version: 1.0
Content-Type: text/plain



	That is not what Mr Shannon says,  Shannon's law relates date
	rate, bandwidth and signal to noise ratio - the "channel
	capacity" of 26 mhz of spectrum is determined by the signal to
	noise ratio in the 26 mhz channel and ranges from much less
	than 26 mbs to several times that rate depending on the signal
	to noise ratio (and of course how clever the modulation
	technology is at exploiting it).  Witness a 28.8 kb modem which
	stuffs 28.8 kb into less than 3.2 khz given about 32 db gross
	SNR.

Oops, mega*samples*, not megabits, how embarassing.  I agree with your
numbers, I was low by an order of magnitude or so on the quantity of
data one would need to examine to reconstruct the message.

But now that I think about what 902-928 MHz looks like in practice, I
think I underestimated how hard things could get.  If you're just
trying to track a frequency-hopping signal where the rest of the power
in the band is some mix of Gaussian noise and non-hopping signals, the
carrier should be clearly visible as a spike hopping around in the
band.  As soon as you have two or more frequency-hopping signals
however, keeping track of which carrier is which as they hop around
looks *much* harder.  If they hop at discernibly different times then
you can correlate a carrier that disappeared with the one that appeared
elsewhere at the same time.  This easily described and implemented
approach breaks down when two or more signals hop at the same time.
Here you might try to associate some sort of signature with each signal
to allow you to pair up the new carriers with the old, but you'd have
to know more about the situation to say what signatures would be good.

Similarly a single spread-spectrum signal should be easy to pick out,
but multiple such sounds like an even bigger headache than multiple
hoppers.

	But even the security of mathematical crypto is mostly unproven
	as of yet - we merely think things are difficult to compute
	because we don't know an easy way to do it, not because there
	is a clear proof that is true.

Yes, this is a very important point (but presumably an obvious one to
cypherpunks, maybe I should subscribe).  Worse, even if we *could*
prove a certain protocol secure, the proof will typically apply only to
the protocol and not to any particular message transmitted using that
protocol.  There is a very big difference between proving the absence
of a fast decryption algorithm for a given encryption scheme and
proving that every message so encrypted is secure.  One might call this
distinction existential security vs. universal security.  A universally
T-secure channel is one for which every message is secure from all
T-bounded attacks (algorithms taking time at most T expressed as a
function T(n) of the length n of the message).  An existentially
T-secure channel is one such that for every T-bounded attack there
exists an infinite set of messages all of which are secure from that
attack, though not necessarily the same messages as you vary the
attack.

(As a practical matter it would be more useful to replace the function
T by a fixed long duration such as a googol seconds, provided this
could be achieved with messages of size at most say a kilobyte, a point
of view advocated by e.g. Leonid Levin.  This requires taking the
state-symbol product of the computational model into account when
measuring computational complexity since constant factors can no longer
be neglected; here Kolmogorow complexity is a particularly natural
setting.  This still only addresses algorithmic attacks; for security
against hardware attacks one should also appeal to limits set by physical
constants like c and h-bar.)

The danger is that someone will eventually demonstrate existential
security for a protocol, the proof will as usual be trumpeted in the
New York Times, and it will be interpreted by many as proving universal
security.

An intermediate notion is that of a uniformly existentially secure
channel: there exist some messages secure from all attacks.  But if
those messages can be efficiently identified then such a channel can be
converted to a universally secure channel simply by only transmitting
secure messages.  Modulo the identification problem, this shows that it
is no easier to come up with a uniformly existentially secure protocol
than a universally secure one.

With a few exceptions, arising in e.g. quantum cryptography, we don't
even have existentially secure protocols yet, let alone universally
secure ones.

Vaughan Pratt