Cryptography-Digest Digest #569, Volume #14 Fri, 8 Jun 01 16:13:01 EDT
Contents:
Re: National Security Nightmare? (nemo outis)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mok-Kong Shen)
Re: Def'n of bijection ("Douglas A. Gwyn")
Re: practical birthday paradox issues ("Douglas A. Gwyn")
Re: Def'n of bijection ([EMAIL PROTECTED])
Re: National Security Nightmare? (John Myre)
Re: National Security Nightmare? ("Douglas A. Gwyn")
Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and ("Douglas A.
Gwyn")
Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and ("Douglas A.
Gwyn")
Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and ("Douglas A.
Gwyn")
Re: Notion of perfect secrecy ("Douglas A. Gwyn")
Re: shifts are slow? ("Douglas A. Gwyn")
Prime Directive was _Re: National Security Nightmare? ("Dramar Ankalle")
Re: Def'n of bijection (Mok-Kong Shen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (nemo outis)
Subject: Re: National Security Nightmare?
Date: Fri, 08 Jun 2001 19:17:24 GMT
As a pedant and sciolist I should point out that it's "Let *him* who is
without blame cast the first stone."
:-)
Regards,
In article <[EMAIL PROTECTED]>, Phil Carmody
<[EMAIL PROTECTED]> wrote:
..snip...
>Let he who is without blame cast the first stone.
..snip...
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Fri, 08 Jun 2001 21:24:35 +0200
Tom St Denis wrote:
>
> Not to be "a naive kid" but I doubt even PhD math types could read a thesis
> and understand it in one pass.
>
> I find often the biggest problem with math papers/discussions is the lack of
> a good language to discuss it in. For example, my book on Group Theory I
> got (From Dover) only has 13 words in the entire text. The rest is vague
> human egyptian art work that future archeologists will look at and say "this
> means fire, and that's water, and ...".
>
> For example, look at some of the papers by Vaudenay. Typically he goes
> overboard when trying to say the simplest thing. The benefits of
> decorrelation in GF(2^w) wrt to diff/linear analysis can be summed up with
> two simple proofs. Yet he brings in all these wierd symbols like
>
> ||A||^d_{oo}, etc..
>
> Which looks neat, but doesn't mean anything to me. (I know ||A|| means
> normal form, but what "normal form" means is beyond me).
>
> In my MDFC paper I proved in about 1/2 a page that pair-wise decorrelation
> in GF(2^w) leads to functions immune to differential and linear analysis.
>
> [N.B His papers go far into more formal notions of randomness which is why
> he uses the funny notation. But to simply prove immunity to 1st order
> attacks you don't need such a lengthly paper]
I remember we had discussed over similar topics in the
past. Different books are written for people with different
'pre-knowledge' (my term). Thus not everything is explained
in all details and with all rigor, it being assumed that
the (intended) readers already know stuffs above a
certain level. Certainly, there are differences in the
writing capabilities of the authors. Some are good
pedagogically, i.e. good teachers, others less so.
But I would be very careful in criticizing textbooks
written by academics or papers in respected journals
as vague, imprecise etc. etc. For it is the current
tradition that these are well peer-reviewed. Further,
common textbooks (those that sell en mass) are subjected
to a selection process (in the Darwinian sense) so the
probability of having very poor quality such books on
the market is not very likely. If I have acquired
enough knowledge in a scientific field and am able to
read a lot of books with ease and then discover (on
looking back) that a certain book is really poorly or
carelessly written (with respect to the class of readers
that I am sure that the book is intended), I would
eventually venture to express my critiques, but not
before that time point. Of course, that's my personal
'philosophy', you may have yours that is quite different.
You said that some authors are explaining too much, i.e.
with unnecessary details. But this is probably because
you have known more in that particular point than the
average reader that the authors have in mind. For one
who doesn't have that 'pre-knowledge', one would be very
grateful to the authors for easing their way of capturing
the stuff with these details. There are literatures of
diverse levels. If you find one class too easy/simplistic
for you, switch to a higer class. Sometimes one has to
switch in the reverse direction. (At least this is often
my personal experience.) This is analogous to what I knew
in school education when I was young. (I have no
knowledge of the current systems.) At that time pupils
that were exceptionally good were allowed to jump
classes. Transfers in the reverse direction did also
happen sometimes.
Your experience with Dover books vastly surprised me.
Dover books are mostly old books but they don't have
a bad 'image' for me up till the present. I could hardly
imagine that a Dover math book on group theory has only
13 words in it. Could you please give the full title and
author name? I'll order it immediately and keep it as a
piece of curiosity for my personal library.
M. K. Shen
===========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Fri, 8 Jun 2001 18:14:38 GMT
Mok-Kong Shen wrote:
> What I wonder is whether in a concrete case in practice,
> i.e. for the opponent having in hand a bunch of
> messages, he can assign any (concrete) probability or
> likelihood values to the individual messages, without
> invoking wild speculations or doing similar things.
Hmm, the messages he has in hand are likely; in fact they're
certain. I think you mean, given one or more ciphertexts,
how does one estimate relatively likelihood of possible
plaintexts. Well, as I said, likelihood is contextual, and
to assess it accurately, all available information must be
properly (fully) used. There is no simple recipe for that,
or else cryptanalysis would be a turn-key operation. Some
available information (constraints on the solution) is easy
to extract most of the benefit of; e.g., knowledge of the
ciphertext length plus knowledge that the general system
preserves length (or expands it no more than a known amount)
already allows one to totally eliminate most possible
plaintexts (assign 0 likelihood to them). For good security,
there should be a tolerable number of such "patent"
characteristics that provide only a relatively small amount
of information to the enemy. That information should not
raise the likelihood of any single plaintext above some
minimum security threshhold.
The reason a 1-bit ciphertext seems so informative is that
it narrows the set from near-infinite to some choice set
that must be have a function similar to {"Yes","No"}. Thus,
although one doesn't know the particular choice nor what
function it affects, one *does* learn that some choice had
to be communicated. Sometimes that fact alone is of value.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: practical birthday paradox issues
Date: Fri, 8 Jun 2001 18:18:23 GMT
Dirk Bruere wrote:
> > > One might make a guess at h/w capability given that the old WW2 custom
> > > electromech system was roughly as powerful as a Pentium 100MHz.
> "The Bombe was an electro-mechanical device but so tuned to its one task
> that a simulation on a modern PC takes 15 hours to do what a Bombe did in 15
> minutes."
That doesn't make it "more powerful". It makes it better suited for
its specific task.
------------------------------
Subject: Re: Def'n of bijection
From: [EMAIL PROTECTED]
Date: 08 Jun 2001 15:49:25 -0400
"Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
>> [EMAIL PROTECTED] wrote:
>>: Um, it's a mathematical term, Tim. A statement is vacuously true when it
>>: cannot possibly be false.
>
> Actually, Len gave a woefully misleading explanation.
True. I wasn't trying to define the term; I was briefly (and not very
precisely) alluding to the meaning. As I said later, ``it's a
mathematical term; you can look it up.'' The original stamement, ``It's
a mathematical term,'' of course implies ``you can look it up,'' and I
was content to let the thorough reader do so.
> A statement is "vacuously true" only when it asserts some
> property of a member of a set whose specification ensures
> that the set contains no elements.
That's equivalent, by the way, to the definition I eventually gave:
an implication whose premise can never be true.
Len.
--
Sorry. I don't write untestable code to satisfy religious fanatics.
-- Dan Bernstein
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: National Security Nightmare?
Date: Fri, 08 Jun 2001 13:45:34 -0600
JPeschel wrote:
<snip>
> No, Phil, the English of Americans and the British is one language.
<snip>
Barely.
JM
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: National Security Nightmare?
Date: Fri, 8 Jun 2001 18:42:15 GMT
Derek Bell wrote:
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> : Well, if there is a UFO cover-up, they have also managed to hide
> : it from people with *very* extensive access to intelligence archives.
> Amusingly enough, some UFO fanatics have claimed the Dundee
> Society worked on UFOs!
There is no doubt that at least one member of the Dundee Society
(its founder, LDC) did develop an interest in questions of alien
communication, so the topic likely came up at DS meetings, although
it wasn't the group's focus. So far as I can determine, this
interest first became visible when he volunteered to provide a
cryptologist's insight into the issue for a Congressional panel.
A revised version of his assessment was published in the NSA Tech.
J. and is available as a bitmapped PDF on the NSA Web site in their
FOIA UFO area. LDC prepared at least two more papers on related
issues, although they weren't widely circulated; those are also on
the Web site. The Editor of the NSA Tech. J., HC, published his own
paper further developing the encoding theme, but it's apparently
still classified, like a lot of old stuff that hasn't yet undergone
declassification review. (I think the EO requiring review missed
out by not imposing automatic declassification 10 years, say, after
scheduled review time. That would surely have helped prioritize
what gets done first. Right now it seems to be concentrating
mostly on nontechnical aspects having historical interest for a
large segment of the public, e.g. Korean war military operations.)
The important point is that this was a personal interest of LDC
(and HC), not a major corporate (NSA) interest. Even if the
specific notions held by UFO enthusiasts are wrong, there are still
some intellectually interesting issues involved. How *would* one
communicate with an entity so alien that it has almost nothing
in common with us, including methods of thinking? What *would* be
the impact on our society of contact with an alien civilization
(that could be presumed to be far more advanced than we in most
areas)? NOTE: I'm not asking for a UFO discussion in sci.crypt,
which is certainly the wrong place for it. But if you read the
cited papers and want to talk about extreme forms of communication,
that might be appropriate. (A new subject line is suggested.)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and
Date: Fri, 8 Jun 2001 19:00:29 GMT
sisi jojo wrote:
> Now you go back to the original article. You wonder what sophisticated proof
> requires a sophisticated metric space definition...
> To your surprise, nothing sophisticated at all! The author is only talking
> about the number of bits that are different between 2 messages! A 5 year old
> knows what that means!
Actually, no, a 5-year-old doesn't know diddly about this.
Even if you can get a 5-year-old to grasp the idea of a count
of differences, which is moderately sophisticated already,
the importance of, and uses for, metricity (e.g. triangle
inequality) are completely beyond him. If the fact that
Hamming distance imposes a metric on the code space deserves
mention in the article, then some of the properties of
metricity are important to the development, and a 5-year-old
will not be able to follow the ideas.
The idea that there is value in naivete as such is naive.
What is of potential value is a fresh outlook combined with
sound basic tools that allow one to proceed effectively in a
new direction. Proceeding blindly is not valuable.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and
Date: Fri, 8 Jun 2001 19:10:03 GMT
Tom St Denis wrote:
> Genius is such a relative thing.
Nope.
> ... But fresh ideas rarely hurt !
*Informed* fresh ideas might not hurt, but a slew of crackpot ideas
in fact easily can get in the way of doing real work. Why do you
think that most professional scientists don't want cranks sending
offbeat ideas to them? It's *not* because they are closed to new
ideas; most would welcome *good* new ideas. It's because they have
a realistically low expectation that enough of value would emerge
to justify the time spent.
For every ... (what? I'm trying to think of something of indisputable
value around me that was invented by a youngster, hmm, no luck) ...
there are a zillion Perpetual Motion Machines.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and
Date: Fri, 8 Jun 2001 19:18:46 GMT
Mark Wooding wrote:
> Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> > Take a simpler problem 1+1=2, ... it takes a doctorate in mathematics,
> > and a few hundred pages of very intricate math to prove it without
> > assuming things.
> I don't have such a doctorate, but... What other meaning of the symbol
> `2' did you have in mind that might conflict with it being the value
> formed by adding the multiplicative identity of the ring of integers to
> itself? (Proof that 1 + 1 is not equal to 0 or 1, the two integers
> actually named in the integer axioms, is immediate from the properties
> of the ordering on integers, so a separate symbol is justified.)
I think Joseph overstated the case, but usually 2 is defined as the
successor of 1, and connecting that with addition is tedious when
successor is not defined in terms of addition. More accurate would
have been "Every schoolchild learns mathematical 'facts' that he
can't even come close to proving rigorously." Indeed, many such
"facts" turn out to be false, or at best misleadingly expressed.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Notion of perfect secrecy
Date: Fri, 8 Jun 2001 19:32:02 GMT
Tom St Denis wrote:
> Ok this has gone on too long.
Usually when one hears that, the speaker thinks that he can make a
definitive statement that will show everybody else the error of
their ways. That's very arrogant, and foolish when you're wrong.
> Typically what you guys are missing is that the length of the message is not
> the secret. It's the contents of the message.
Part of the information content of a (plaintext) message is
inherent in its length, assuming that a priori you have no
information that constrains the expected length.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: shifts are slow?
Date: Fri, 8 Jun 2001 19:25:33 GMT
Joseph Ashwood wrote:
> such deep pipelines addition now takes multiple clocks but commonly you can
> get a througput of 1 add/clock.
Basically, what is fastest in an ALU depends on what the designers were
trying to optimize. Barrel shifters help a lot to speed up shifts.
In principle one can shift a register by an arbitrary count in one clock
cycle, but the circuitry is somewhat complicated.
As to pipelines, I was interested to note that the Motorola M*CORE
pipelining is so complete that one can get a close estimate of timing
by simply counting one clock per (linear) instruction. Out of
complexity, simplicity emerges.
------------------------------
From: "Dramar Ankalle" <[EMAIL PROTECTED]>
Subject: Prime Directive was _Re: National Security Nightmare?
Date: Fri, 8 Jun 2001 16:04:10 -0400
Douglas:
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Derek Bell wrote:
> > Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> > : Well, if there is a UFO cover-up, they have also managed to hide
> > : it from people with *very* extensive access to intelligence archives.
> > Amusingly enough, some UFO fanatics have claimed the Dundee
> > Society worked on UFOs!
>
> There is no doubt that at least one member of the Dundee Society
> (its founder, LDC) did develop an interest in questions of alien
> communication, so the topic likely came up at DS meetings, although
> it wasn't the group's focus. So far as I can determine, this
> interest first became visible when he volunteered to provide a
> cryptologist's insight into the issue for a Congressional panel.
> A revised version of his assessment was published in the NSA Tech.
> J. and is available as a bitmapped PDF on the NSA Web site in their
> FOIA UFO area. LDC prepared at least two more papers on related
> issues, although they weren't widely circulated; those are also on
> the Web site. The Editor of the NSA Tech. J., HC, published his own
> paper further developing the encoding theme, but it's apparently
> still classified, like a lot of old stuff that hasn't yet undergone
> declassification review. (I think the EO requiring review missed
> out by not imposing automatic declassification 10 years, say, after
> scheduled review time. That would surely have helped prioritize
> what gets done first. Right now it seems to be concentrating
> mostly on nontechnical aspects having historical interest for a
> large segment of the public, e.g. Korean war military operations.)
>
> The important point is that this was a personal interest of LDC
> (and HC), not a major corporate (NSA) interest. Even if the
> specific notions held by UFO enthusiasts are wrong, there are still
> some intellectually interesting issues involved. How *would* one
> communicate with an entity so alien that it has almost nothing
> in common with us, including methods of thinking?
Or consider beings that communicate via some sort of electrical or other
``waveguide" method whose thoughts are deadly.NOt purposefully, but in
trying to talk end up destroying or burning out those they attempt to talk
to.
One would picture this society just arranging the ``reality" of the target
civilization just so as to be noticed, since they could not actually
``talk".
The problem then would be what would happen to the poor confused
civilization, as their internal factions fought to descibe what was
happening, or deny it.
I think Star Trek is still the way to go, no contact until fully ready,
Prime Directive, ect ect ect.
Then you would wonder what do they come here for?I have already suggested on
the physics groups that since there is a red shift in all directions you
look, that the big bang happened right in our neighborhood first, and thus
attracts the tourists.Or not
``Hey look he's right side up" (what confused people might say in an
alternate ``elevator" reality)
What *would* be
> the impact on our society of contact with an alien civilization
> (that could be presumed to be far more advanced than we in most
> areas)? NOTE: I'm not asking for a UFO discussion in sci.crypt,
> which is certainly the wrong place for it. But if you read the
> cited papers and want to talk about extreme forms of communication,
> that might be appropriate. (A new subject line is suggested.)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Fri, 08 Jun 2001 22:02:59 +0200
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > What I wonder is whether in a concrete case in practice,
> > i.e. for the opponent having in hand a bunch of
> > messages, he can assign any (concrete) probability or
> > likelihood values to the individual messages, without
> > invoking wild speculations or doing similar things.
>
> Hmm, the messages he has in hand are likely; in fact they're
> certain. I think you mean, given one or more ciphertexts,
> how does one estimate relatively likelihood of possible
> plaintexts. Well, as I said, likelihood is contextual, and
> to assess it accurately, all available information must be
> properly (fully) used. There is no simple recipe for that,
> or else cryptanalysis would be a turn-key operation. Some
> available information (constraints on the solution) is easy
> to extract most of the benefit of; e.g., knowledge of the
> ciphertext length plus knowledge that the general system
> preserves length (or expands it no more than a known amount)
> already allows one to totally eliminate most possible
> plaintexts (assign 0 likelihood to them). For good security,
> there should be a tolerable number of such "patent"
> characteristics that provide only a relatively small amount
> of information to the enemy. That information should not
> raise the likelihood of any single plaintext above some
> minimum security threshhold.
You are right. I suppose that this implies that it is
a good idea to send a mixture of messages of various
types. As long as the bandwidth is economically not an
issue, one can send also stuffs that actually don't need
much protection. This increases the work load of the
opponent and results in less ascertainable probability
estimates of the messages intercepted. Note on the
other hand that in certain theoretical contexts it is
assumed that certain probabilities are precisely known.
> The reason a 1-bit ciphertext seems so informative is that
> it narrows the set from near-infinite to some choice set
> that must be have a function similar to {"Yes","No"}. Thus,
> although one doesn't know the particular choice nor what
> function it affects, one *does* learn that some choice had
> to be communicated. Sometimes that fact alone is of value.
Indeed, in special situations the fact that a communication
between two partners takes place at all could convey
essential informations to the opponent.
M. K. Shen
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
