Cryptography-Digest Digest #177, Volume #9 Wed, 3 Mar 99 03:13:19 EST
Contents:
Re: sci.crypt.randomness (Somniac)
Re: True Randomness - DOES NOT EXIST!!! ("Douglas A. Gwyn")
Re: idea for random numbers ("Douglas A. Gwyn")
Re: Fingerprinting as a password ("Douglas A. Gwyn")
Re: New Concepts on Pseudorandomness (David A Molnar)
Re: Randomness based consciousness?. (Was: Re: *** Where Does The Randomness Come
From ?!? *** ) (Ralph Frost)
Re: Pseudorandomness (Nicol So)
Re: Pseudorandomness (Serge Vaudenay)
Re: One-Time-Pad program for Win85/98 or DOS (Sorcerer)
Intel/Microsoft ID ("Roger Schlafly")
Re: New Concepts on Pseudorandomness (Matthias Meixner)
Re: smart cards (Jaap-Henk Hoepman)
----------------------------------------------------------------------------
From: Somniac <[EMAIL PROTECTED]>
Subject: Re: sci.crypt.randomness
Date: Tue, 02 Mar 1999 18:11:19 -1000
John Curtis wrote:
>
> Is it time to start a newsgroup sci.crypt.randomness?
>
> We seem to be spending 90% of our recent bandwidth
> discussing randomness and it mathematical underpinnings
> and <10% discussing cryptography.
>
> This used to be a great newsgroup to kibbitz on and
> learn something (my use).
>
> Maybe we need sci.crypt.philosophy for discussions of
> underpinnings.
>
> I'm getting very bored.
>
> ciao,
>
> jcurtis
I agree, but new groups are not formed by complainers, they
are created by enthusiasts. You cannot evict R. Knauer from
the crypto group, this is where he gets to use the "royal we"
in front of cryptographers. I doubt he wants to leave this
audience just based on our complaints.
If randomness enthusiasts want to form a new group, I will
join it too. I would visit sci.crypt.randomness and contribute.
If anyone else wants to start it, please sign on now.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness - DOES NOT EXIST!!!
Date: Wed, 03 Mar 1999 02:36:43 GMT
BRAD KRANE wrote:
> Explain to me then how this Supreme Being came into existance.
Please DON'T. Some of us are interested in the advertised subject,
but few of us want to wade through religious arguments in *this*
newsgroup. Carry on that debate in a more suitable newsgroup, or
off-line.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: idea for random numbers
Date: Wed, 03 Mar 1999 02:43:21 GMT
bob taylor wrote:
> Only use the LSB (bit 0) for the random sample, and you can even take
> the next bit (bit 1) to control the sample interval(stagger). You get
> random data sampled at random intervals. It maybe slow but I dont see
> any statistical problems.
How could you not see any statistical problems??
For example, suppose the LSB is consistently biased;
then no matter when you "randomly" sample it the
resulting substream will also be biased.
Good hardware RNGs already exist, why not just buy one.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Fingerprinting as a password
Date: Wed, 03 Mar 1999 03:11:46 GMT
MC1148 User wrote:
> Hi. I am a student at Bloomsburg University. I am working on a project
> that would explain how fingerprinting works, and the information I have
> found has not given me the mathematical information that I am searching
> for.
Presumably you have already checked every reference found in such
places as
http://dir.yahoo.com/Business_and_Economy/Companies/Security/Identification_Systems/Fingerprinting/
In which case, what specific "mathematical information" do you need?
Typically, the raw image is low-pass filtered, edge enhanced, and
then the various "points" of identification are located via
localized template matching. The point structure is matched
against a fingerprint database, with all rotations considered.
Except for the routine use of Fourier transform methods,
this isn't an especially "mathematical" process.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: New Concepts on Pseudorandomness
Date: 3 Mar 1999 02:13:46 GMT
Raul <[EMAIL PROTECTED]> wrote:
> It is a very new and nice theory, but how can I apply it?
> How can I calculate the goodness of a pseudorandom generator?
> How can I generically analyze a string in order to decide it is
> pseudorandom or not?
not an expert, but I think this
has to play into the computationally indistinguishable from random
business. if you can distinguish the string from random with some
given computing power, then it's shown not random. so you can kill
bad generators by applying the right tests, and perfect ones will pass
all tests.
except moderately good ones will pass some tests and fail others. it's
just that the better the generator is, the larger the set of tests it
happens to pass.
the problem is
"how do I prove that this generator is impossible to tell apart from random
from random (or at least, indistinguishable with a very very low
probability) for ALL strings, and not just the ones in Diehard
or Knuth vol 2, or whatever other test I'm running?"
there's discussion of that on the next page with the "Indeed, at best,
these generators [ones which pass tests] are shown to pass SOME ad-hoc
statistical test. However, the fact that a 'pseudo-random generator
passes some statistical tests does not mean that it will pass a new test
and is good for some future (untested) application."
then the computational indistinguishability business is brought up as
a math criterion that you can evaluate the generator against. instead of
testing the strings against some model of what "random" is, you test the
_generator_ by trying to prove that no possible adversary could
tell a string from the generator from a random string
*assuming some limit on the adversary's amount of computing power*.
it's something you can look for in the (mathematical) construction of a pseudo-random
generator. so when you ask "how do I tell how good a generator is"
the answer shifts from "try lots of tests" to "try to prove its output
is computationally indistinguishable from random."
and you seem to apply it by building pseudo-random generators that are
easy to prove things about. :-)
I think it's come up in some of the other raging threads that
"you can't tell if a string is random, only if a means of generating
it is." I'm not sure about that, but I think that's what this leads
towards. (I can distinguish between "ASSASSIN" and "ABCDEFGH" from the strings
alone).
> In the beginning of page 78, Godreich talks about a "randomness
> complexity" associated to a probabilistic algorithm. What is this
> concept about? and how can I calculate it?
I'm not too sure about that.
Best guess is that it means something about how many queries to the
random number source you need to compute the algorithm, since it goes
on to talk about "well, if this really is indistinguishable, then we use
a PRG instead of 'real' random numbers for randomized algorithms." but
don't know much about randomized complexity.
-David
------------------------------
From: Ralph Frost <[EMAIL PROTECTED]>
Crossposted-To:
sci.skeptic,sci.philosophy.meta,sci.psychology.theory,alt.hypnosis,sci.logic
Subject: Re: Randomness based consciousness?. (Was: Re: *** Where Does The Randomness
Come From ?!? *** )
Date: Thu, 25 Feb 1999 01:12:20 -0500
tiger9 wrote:
>
> That's my point: a lot of theories and absolutely no proof! We will
> have to wait until we die before any proof can or will be apparant,
> or we may just cease to exist and never find out anyway.
>
Not necessarily. Something must leak through before death or else you
wouldn't even be aware of the options.
If you are young, you can hope to attain some wisdom, or better yet,
peace of mind at a some later age, through reverent practice of one of
the many practices.
Also, the proof you seek is all around you but you must read it and
decide that it is proof, and of what, by yourself for yourself.
Do a good deed every day, notice what happens.
There are many paths through the wood. As Castenada's Don Juan said,
"choose a path with heart."
Or, as you say, you can just wait around to die. It's your choice, no
one
else's.
> >I would not go that far. There are well-developed metaphysical systems
> >which attempt to give reasons for existence. The one developed by
> >Thomas Aquinas comes to mind.
> >
> >Bob Knauer
> >
Or earlier, the few teachings of that other fine fellow, Jesus.
Best regards
Ralph Frost
[EMAIL PROTECTED]
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Pseudorandomness
Date: Wed, 03 Mar 1999 00:36:27 -0500
Raul wrote:
>
> I would like to know the lastest researches done in randomness and
> pseudorandomness.
> Nowadays, I am reading Goldreich's book: "Modern Cryptography,
> Probabilistic Proofs and Pseudorandomness".
> I think it is a good book. However, there are some concepts not very
> well explained and not very clear, as:
>
> � Computational Indistinguishability
> � Negligible functions and noticeable functions
> � Oracle machines
I haven't been following the field, so I can't point you to the latest
research, but I can try to explain to you these concepts (no guarantee
that I'll do any better than the book though). Here's the game plan,
I'll point out interesting concepts and the "obvious" ways to capture
them, and then some reasons why we want to modify/refine our
formalization.
Indistinguishability is a concept that applies to a pair of
(probability) distributions, say X and Y. In the context of
computational complexity, the distributions are often on sets of
strings. It is a useful concept, as it can be used to define several
concepts with more obvious connection to security.
For example, we can define a pseudorandom generator can an "efficient"
algorithm that expands a k-bit string chosen uniformly at random to
strings of length |f(k)|, where f(k) is a polynomial function, such that
the resulting distribution of |f(k)|-bit strings are not
"distinguishable" from... |f(k)|-bit strings chosen uniformly at
random... by any "efficient" algorithm. (Note the way I break up the
sentence). Here, the connection goes like this: pseudorandomness =>
ability to "fake" uniformly distributed |f(k)|-bit strings =>
indistinguishability.
The notion of "indistinguishability" in the above is a computational
one. Actually, we can distinguish three flavors of
indistinguishability: perfect, statistical, and computational.
Saying that two distributions are "perfectly indistinguishable" is just
another way of saying that they are identical.
Two distributions are "statistically indistinguishable" iff their
"statistical difference" is "negligible". (The last two concepts need to
be formalized).
Two distributions are "computationally indistinguishable" iff their
"distinguishing probability" w.r.t. any "efficient" algorithm is
"negligible". (Again, we need to formalize our informal notions).
Theoretical computer scientists like to define complexity in terms of
asymptotic behaviors. To do so, we need to introduce the concept of a
"security parameter" (usually denoted k). Only when we are allowed to
increase the security parameter without bounds can we talk about
asymptotic behavior.
We need to modify our formulations here--so far we haven't tied anything
in our definitions to the security parameter k.
We say a (non-negatively valued) function f(k) is "negligible" if it
converges to 0 faster than any function of the form 1/k^c as k -->
infinity, where c is a positive constant. (We can further formalize the
definition, but it doesn't make things any more intuitive nor does it
yield any more insight).
We need to link the two distributions X and Y to the security parameter
k. To do so, we modify our formulation so that we don't talk about two
distributions, but two *indexed collections of distributions* instead.
Of course, the natural interpretation of the index here is the security
parameter. So now we talk about X_1, X_2, ..., X_k, ... instead of X;
and Y_1, Y_2, ..., Y_k, ... instead of Y.
We now go back to formalizing "statistical difference" and
"distinguishing probability".
We define the "statistical difference" between X_k and Y_k as:
sum |Pr(X_k = a) - Pr(Y_k = a)|,
where the sum is taken over all strings a. You can visualize
statistical difference by imagining the graphs of the probability mass
functions of X_k and Y_k, the statistical difference is the area bound
by the two curves.
Now it's the turn for "distinguishing probability". To define the
notion, we need to reference the notion of an "efficient algorithm",
which has several flavors. (For the time being, we won't concern
ourselves with those details). Given an "efficient algorithm" A, the
"distinguishing probability" of X_k and Y_k is:
|Pr(A(X_k) = 1) - Pr(A(Y_k) = 1)|
Some explanation is in order here. The job of A is supposed to tell
apart the distributions X_k and Y_k. We can interpret an output of 1
from A as meaning "I conclude that my input has been chosen according to
X_k". The "distinguishing probability" is a measure of how differently
A responds to inputs chosen according to the two distributions.
Computational indistinguishability is best understood in terms of the
informal notions we've just formalized. Two indexed collections of
distributions (random variables) are computationally indistinguishable
iff all "efficient algorithms" respond to both of them pretty much the
same way as k --> infinity. If there is any difference in the way an
"efficient algorithm" respond to the two collections of distributions,
it is felt so rarely that it is "negligible". That's the intuition
behind the concept.
As I said, there are different choices for the formalization of
"efficient algorithm", common ones include: polynomial-time Turing
machine,
probabilistic polynomial-time Turing machine, family of polynomial-size
circuits. (The last one is a non-uniform model of computation). I
think most theoreticians use polynomial-size circuits, because it allows
more/stronger results to be proved. Goldreich seems to prefer PPTM.
(Personally I think PPTM is more reasonable).
"Oracle" is a standard concept in computability theory. An oracle is a
magic device that can answer membership question for some language. An
oracle Turing machine M^A (written M subscript A) is a Turing machine
equipped with an oracle that can answer membership question for a
language A. We think of an oracle as a blackbox that has no structure.
Each query to the oracle counts as one elementary operation (computation
step) regardless of how complex the language may be.
As I said earlier, indistinguishability can be used to define several
other useful concepts. Examples of such include: computational
zero-knowledge (property), security of encryption, resilience etc.
Hope that helps.
Nicol
------------------------------
From: Serge Vaudenay <[EMAIL PROTECTED]>
Subject: Re: Pseudorandomness
Date: Wed, 03 Mar 1999 14:59:10 +0900
Raul wrote:
>
> I would like to know the lastest researches done in randomness and
> pseudorandomness.
> Nowadays, I am reading Goldreich's book: "Modern Cryptography,
> Probabilistic Proofs and Pseudorandomness".
> I think it is a good book. However, there are some concepts not very
> well explained and not very clear, as:
>
> $B(B Computational Indistinguishability
> $B(B Negligible functions and noticeable functions
> $B(B Oracle machines
>
> Does anyone know a good book, HTML-reference or papers that define these
> concepts preciselly, and with examples?
>
> Ra$B(Bl Gonzalo D$B(Baz
> [EMAIL PROTECTED]
You can have a look to the decorrelation theory.
http://www.dmi.ens.fr/~vaudenay/decorrelation.html
(this will be updated soon)
Serge
------------------------------
Date: 3 Mar 1999 03:55:44 -0000
From: [EMAIL PROTECTED] (Sorcerer)
Subject: Re: One-Time-Pad program for Win85/98 or DOS
Crossposted-To: alt.security,alt.privacy
On Tue, 02 Mar 1999 16:34:22 GMT [EMAIL PROTECTED] (R. Knauer)
wrote:
>On Tue, 02 Mar 1999 15:37:54 GMT, [EMAIL PROTECTED] (Daniel
>Kinnaer) wrote:
>
>>Perhaps if you check your sample of numbers and within this sample
>>_every_ number has a 50% chance of being picked out of the bunch...
>>
>>Translate this to XOR being used in a OneTimeKey : this means that in
>>the OTK every bit (in a byte) has as much chance to be picked out as
>>every other bit standing next to him. There are very nice tools which
>>can check a sample on "bit-randomness" within a given file. If you
>>would check a bitmap with this tool, you immediately would spot that
>>the first bit of a byte has about 70% chance of being 1 instead of
>>0... Thus, one can not use a bitmap as a good/valid OTK. The same
>>goes for exe-files and every other kind of "structured" information.
>
>There is a fatal flaw in doing that - it only gives the *appearance*
>of randomness.
>
>For example, the digit expansion of pi meets the criteria you stated
>above, but it is hardly a true random number.
>
>Bob Knauer
Geiger counter and a tape recorder.
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Intel/Microsoft ID
Date: Tue, 2 Mar 1999 22:37:59 -0800
While the debate rages over Intel's unique ID and its plans to use
it for identification over the internet, the NY Times reports that
Microsoft uses the unique ID on the network card (or generates
a substitute) and secretly inserts it into MS Word and Excel
documents for purposes of identification.
http://www.nytimes.com/library/tech/99/03/biztech/articles/03privacy.html
------------------------------
From: [EMAIL PROTECTED] (Matthias Meixner)
Subject: Re: New Concepts on Pseudorandomness
Date: 3 Mar 1999 07:58:13 GMT
Raul ([EMAIL PROTECTED]) wrote:
> Godreich's book: "Modern Cryptography, Probabilistic Proofs and
> Pseudorandomness" presents the new theory conceived by Blum, Goldwasser,
> Micali and Yao in which a pseudorandom generator is described as an
> algorithm that expands short random seeds into longer strings which
> cannot be told appart from the uniform distribution by any efficient
> procedure (in polinomical-time).
>
> It is a very new and nice theory, but how can I apply it?
> How can I calculate the goodness of a pseudorandom generator?
> How can I generically analyze a string in order to decide it is
> pseudorandom or not?
A pseudo random generator has only a fixed number of bits for storing
its state, therefore there needs to be a cycle in the generated output.
If its 10 bits, the cycle cannot be longer than 1024 values, but it may
be shorter and there may be some pre cycle values.
So to find out, if the output was generated by a pseudo random generator
you can check for cycles. This should be independed of the random
generator used. However this approach is limited by the number of bits
used for storing the state, since e.g. for 32 bits the cycle length is
2**32.
> In the beginning of page 78, Godreich talks about a "randomness
> complexity" associated to a probabilistic algorithm. What is this
> concept about? and how can I calculate it?
>
> Thank you.
>
> Raul Gonzalo
> [EMAIL PROTECTED]
>
--
Matthias Meixner [EMAIL PROTECTED]
------------------------------
From: Jaap-Henk Hoepman <[EMAIL PROTECTED]>
Subject: Re: smart cards
Date: 03 Mar 1999 08:59:15 +0100
MC1148 User <[EMAIL PROTECTED]> writes:
>
> I am a student in need of information regarding smart cards.
> Anything from what they are to how the microprocessor works. This is
> for a cryptography class so any information about the coding aspects
> would be greatly appreciated. Send all messages to
> [EMAIL PROTECTED] Thanks.
>
Here's some links from my bookmark file. Enjoy,
Jaap-Henk
Smart Cards
Resources
http://www.smart-card.com/
http://www.iat.unc.edu/guides/irg-35.html
http://cardtech.faulknergray.com/
http://www.lafferty.co.uk/
http://www.compinfo.co.uk/tpsmrt.htm
http://www.intercai.com/cards.htm
http://www.cardshow.com/welcome.html
http://www.ubiqinc.com/tourpage.cfm
Literature & References
http://www.cl.cam.ac.uk/users/rja14/tamper.html
http://www.itanz.org.nz/pubs/smartcards/smartcards.html
http://www.SecurityServer.com/
http://www.cardshow.com/applications/EP/contents.html
http://www.systemics.com/docs/papers/BIS_smart_security.html
http://cfec.vub.ac.be/cfec/purses.htm
http://www.intellect.com.au/WP/wpaper3.html
http://www.calpoly.edu/~pirate/magcard/index.html
http://www1.shore.net/~bauster/cap/s-card/
Organisations
http://www.scard.org/
http://ramresearch.com/
http://www.gzs.de/en/index.html
http://www.tech.purdue.edu/it/adc/smcard.htm
Research
http://www.dice.ucl.ac.be/~dhem/cascade/cascade.html
http://www.aitworld.com/techvalley/smartcrd.html
http://www.cwi.nl/cwi/projects/cafe.html
http://www.darmstadt.gmd.de/TKT_DEUTSCH/BEREICHE/SmCa.html
Associations
http://www.smartcrd.com/
http://www.gold.net/users/ct96/
http://www.smartcardclub.co.uk/home.html
http://www.dds.nl/~ncp/index.html
Cards
http://www.tref.nl/betalen/
http://www.chipper.com/
http://www.cardshow.com/applications/VisaCash/contents.html
http://www.europay.com/brand/clip.htm
http://www.mondex.com/
http://www.slb.com/et/
http://www.digicash.com/products/blue/blue.html
http://www.europe.ibm.com/finance/inter/smart/smart.html
http://www.gemplus.com/
Standards
http://csrc.nist.gov/fips/fips1401.htm
http://www.setco.org/
http://www.imaginet.fr/~cb-mail/
http://www.banksys.be/nl/index3p5.html
http://www.cartes-bancaires.com/icset.htm
http://www.smartcardsys.com/
http://www.visa.com/cgi-bin/vee/nt/chip/circuit.html?2+0
http://www.mastercard.com/emv/
http://tobbi.iti.is/cen/welcome.html
http://www.etsi.fr/
http://www.javasoft.com:80/products/commerce/
http://www.nc.com/opencard/
--
Jaap-Henk Hoepman | Sure! We've eaten off the silver
Dept. of Computer Science | (when even food was against us)
University of Twente | - Nick Cave
Email: [EMAIL PROTECTED] === WWW: www.cs.utwente.nl/~hoepman
PGP ID: 0xFEA287FF Fingerprint: 7D4C 8486 A744 E8DF DA15 93D2 33DD 0F09
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
