Cryptography-Digest Digest #500, Volume #14 Sun, 3 Jun 01 02:13:00 EDT
Contents:
Re: A Newbie Question (Boris Kazak)
Re: Top Secret Crypto (Ian Stirling)
Re: A Newbie Question ("Tom St Denis")
Re: And the FBI, too (Re: National Security Nightmare?) (Matthew Montchalin)
Re: practical birthday paradox issues ("Peter L. Montgomery")
Re: practical birthday paradox issues ("Tom St Denis")
Re: Uniciyt distance and compression for AES ("John A. Malley")
Re: practical birthday paradox issues ("Scott Fluhrer")
Re: Uniciyt distance and compression for AES (SCOTT19U.ZIP_GUY)
Re: And the FBI, too (Re: National Security Nightmare?) (Matthew Montchalin)
Re: practical birthday paradox issues (David Wagner)
Re: bent functions (David Wagner)
----------------------------------------------------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: A Newbie Question
Date: Sun, 03 Jun 2001 03:14:54 GMT
Tom St Denis wrote:
>
> "Robert J. Kolker" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> >
> >
> > Tom St Denis wrote:
> >
> > >
> > > Look for digraphs, etc... if you decrypt and it's ascii and has TZ or PM
> in
> > > it, it's probably not the key.
> >
> > Suppose the plain text was:
> >
> > "I saw the move ANTZ in the PM yesterday. I liked it."
> >
> > However I accept your chiding for overlooking your post.
>
> you don't discount those keys, you just put them at the bottom of your list.
>
> If you have say 200 bytes of ciphertext you should see something like 'e' or
> 'th' occur more then 'z' or 'pq'.
>
> Tom
====================
Absolutely correct, especially if the plaintext is in Russian:
"Я вчера смотрел этот ANTZ фильм в PM кинотеатре. Мне понравилось."
So much about digraphs, etc...
Best wishes BNK
------------------------------
From: Ian Stirling <[EMAIL PROTECTED]>
Subject: Re: Top Secret Crypto
Date: Sun, 03 Jun 2001 03:18:06 GMT
Mathew Hendry <[EMAIL PROTECTED]> wrote:
Sat, 2 Jun 2001 08:35:31 +0200, "awn" <[EMAIL PROTECTED]> wrote:
>>TOP SECRET CRYPTO
>>
>>The Most Powerful Data Encryption Program in the World
>Posted within one hour of the Snake Oil FAQ, how ironic. :)
>>Until now, unbreakable encryption methods have been possessed by only a few
>>government agencies, such as the National Security Agency (NSA) and the
>>Soviet KGB. With Top Secret Crypto you now have that ability. Privacy
>>maintained by mathematical law is now a reality.
>Uh huh.
Oddly enough, this was also posted on rec.pyrotechnics.
Maybe (Is awn a name?) just wants colourfull flames :)
--
http://inquisitor.i.am/ | mailto:[EMAIL PROTECTED] | Ian Stirling.
===========================+=========================+==========================
If you've been pounding nails with your forehead for years, it may feel strange
the first time somebody hands you a hammer.
But that doesn't mean that you should strap the hammer to a headband just to
give your skull that old familiar jolt. -- Wayne Throop, during the `TCL Wars'
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A Newbie Question
Date: Sun, 03 Jun 2001 03:28:09 GMT
"Boris Kazak" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > "Robert J. Kolker" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > >
> > >
> > > Tom St Denis wrote:
> > >
> > > >
> > > > Look for digraphs, etc... if you decrypt and it's ascii and has TZ
or PM
> > in
> > > > it, it's probably not the key.
> > >
> > > Suppose the plain text was:
> > >
> > > "I saw the move ANTZ in the PM yesterday. I liked it."
> > >
> > > However I accept your chiding for overlooking your post.
> >
> > you don't discount those keys, you just put them at the bottom of your
list.
> >
> > If you have say 200 bytes of ciphertext you should see something like
'e' or
> > 'th' occur more then 'z' or 'pq'.
> >
> > Tom
> ====================
> Absolutely correct, especially if the plaintext is in Russian:
>
> "Я вчера смотрел этот ANTZ фильм в PM кинотеатре. Мне понравилось."
>
> So much about digraphs, etc...
What is your point?
tom
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,us.misc
Subject: Re: And the FBI, too (Re: National Security Nightmare?)
Date: Sat, 2 Jun 2001 20:35:53 -0700
On Sat, 2 Jun 2001, David Schwartz wrote:
|He pushed a few keys and then she produced from an envelope his ID
|to enter that facility. She also handed him a card with his PIN on
|it and said that he had to destroy it.
|
| So he memorized it and then ate it.
Haha!
|She explained that it was actually supposed to go back into the
|envelope to be destroyed at Ft. Meade and she wasn't sure quite
|what to do in this case. He said, "You said I should destroy it".
|So she took a piece of scrap paper, wrote on it "he ate it", and
|sealed it in the envelope.
That's probably what I would do, too, if I were in her situation.
|Miraculously, he had no difficulty using his ID card and entering
|his PIN to get in.
Was the ID card a so-called 'stripe' card that one inserts into
a lock, and then leaves there, before manipulating a lever, or
before one pushes a button to activate a servo? Or is there an
attendant at a checkpoint, who reads it or scans it with a "wand?"
------------------------------
From: "Peter L. Montgomery" <[EMAIL PROTECTED]>
Subject: Re: practical birthday paradox issues
Date: Sun, 3 Jun 2001 03:38:23 GMT
In article <9fc7ep$fn0$[EMAIL PROTECTED]>
"Niels Ferguson" <[EMAIL PROTECTED]> writes:
>"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
>news:iTeS6.12347$[EMAIL PROTECTED]...
>> Well being the slowest math student on earth I figured out how the
>birthday
>> paradox applies to collision in the 2^(n/2) sense...
>>
>> 2^n/2 chosen texts is really (w^2)/2 pairs in this case it would be
>2^(n-1)
>> pairs.
>>
>> Wow.
>>
>> Problem is.... if we say something like SHA-1 has a 2^80 resistance to the
>> bday paradox, don't we need 2^80 memory for all the chosen texts and 2^159
>> work to find a match? I.e we first need all the texts, then we must try
>> them as pairs one by one to find the collision?
>
>You need 2^80 memory slots, but this is math so we are not limited by
>little things like equipment budgets.
>
>You can find the matches without doing 2^159 work. A simple
>general solution is to sort the 2^80 values (in n * ln n time), and
>then find the matches in linear time. In practice you use a hash-table
>like construction, which requires only 2^80 operations to find
>all matches.
You can avoid 2^80 memory.
Let f be the hash function. We will imagine its domain and
range as being the same. In practice you might append a fixed
string to a 160-value before re-hashing.
Starting with an x0, compute x_{j+1} = f(x_j) for
j = 1, 2, 3, ... 2^80, ... Eventually x_j = x_k for some j and k, j <> k.
Usually j and k are near 2^80.
There are many cycle-finding algorithms --
see Knuth's Seminumerical Algorithms, for example.
Floyd's method finds a j such that x_j = x_{2j}.
This j is a multiple of the period.
You can backtrack (starting with x_0 and x_j, for example)
to find an i such that x_i = x_{i + j} but
x_{i-1} <> x_{i + j - 1} -- then x_{i-1} and x_{i + j - 1}
have the same image. To protect against the unlikely case when x_0 = x_j,
choose x_0 to be the image of some longer string.
This requires 2^80 sequential applications of f but little memory.
We have solved the memory problem, but 2^80 operations is too many for
one machine.
We can replace the computation with one that generates about 2^40
different sequences each f length about 2^40, if we can detect when we get
a duplicate value. The different sequences can be done
on different machines.
Let x0 and y0 be two of the starting values.
If x_i = y_j, then x_(i+1) = y_(j+1).
We can postpone the comparisons if we plan to extend the sequence.
Now look for x_i (and y_j) of a special form,
perhaps having the ASCII encoding of LUCKY
in the first 40 bits of the 160-bit hash value.
Send x_i to a central site only if it has this form.
Along with x_i send the index i and an inverse image f^(-1)(x_0)
When x_{i1} = y_{i2} are two equal images, we are searching for
the least k such that x_{i1+k} = y_{i2+k} have the special form.
This k will be about 2^40. The network applies f 2^80 times, but
only one output in 2^40 is sent to the central site.
The central site needs storage for 2^40 values of special form.
Once the central site gets two equal images, it can backtrack
to get the pre-images.
--
The 21st century is starting after 20 centuries complete,
but we say someone is age 21 after 21 years (plus fetus-hood) complete.
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: practical birthday paradox issues
Date: Sun, 03 Jun 2001 03:58:43 GMT
"Peter L. Montgomery" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <9fc7ep$fn0$[EMAIL PROTECTED]>
> "Niels Ferguson" <[EMAIL PROTECTED]> writes:
> >"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> >news:iTeS6.12347$[EMAIL PROTECTED]...
> >> Well being the slowest math student on earth I figured out how the
> >birthday
> >> paradox applies to collision in the 2^(n/2) sense...
> >>
> >> 2^n/2 chosen texts is really (w^2)/2 pairs in this case it would be
> >2^(n-1)
> >> pairs.
> >>
> >> Wow.
> >>
> >> Problem is.... if we say something like SHA-1 has a 2^80 resistance to
the
> >> bday paradox, don't we need 2^80 memory for all the chosen texts and
2^159
> >> work to find a match? I.e we first need all the texts, then we must
try
> >> them as pairs one by one to find the collision?
> >
> >You need 2^80 memory slots, but this is math so we are not limited by
> >little things like equipment budgets.
> >
> >You can find the matches without doing 2^159 work. A simple
> >general solution is to sort the 2^80 values (in n * ln n time), and
> >then find the matches in linear time. In practice you use a hash-table
> >like construction, which requires only 2^80 operations to find
> >all matches.
>
> You can avoid 2^80 memory.
>
> Let f be the hash function. We will imagine its domain and
> range as being the same. In practice you might append a fixed
> string to a 160-value before re-hashing.
>
> Starting with an x0, compute x_{j+1} = f(x_j) for
> j = 1, 2, 3, ... 2^80, ... Eventually x_j = x_k for some j and k, j <> k.
> Usually j and k are near 2^80.
> There are many cycle-finding algorithms --
> see Knuth's Seminumerical Algorithms, for example.
> Floyd's method finds a j such that x_j = x_{2j}.
> This j is a multiple of the period.
> You can backtrack (starting with x_0 and x_j, for example)
> to find an i such that x_i = x_{i + j} but
> x_{i-1} <> x_{i + j - 1} -- then x_{i-1} and x_{i + j - 1}
> have the same image. To protect against the unlikely case when x_0 = x_j,
> choose x_0 to be the image of some longer string.
>
> This requires 2^80 sequential applications of f but little memory.
> We have solved the memory problem, but 2^80 operations is too many for
> one machine.
>
> We can replace the computation with one that generates about 2^40
> different sequences each f length about 2^40, if we can detect when we get
> a duplicate value. The different sequences can be done
> on different machines.
>
> Let x0 and y0 be two of the starting values.
> If x_i = y_j, then x_(i+1) = y_(j+1).
> We can postpone the comparisons if we plan to extend the sequence.
>
> Now look for x_i (and y_j) of a special form,
> perhaps having the ASCII encoding of LUCKY
> in the first 40 bits of the 160-bit hash value.
> Send x_i to a central site only if it has this form.
> Along with x_i send the index i and an inverse image f^(-1)(x_0)
>
> When x_{i1} = y_{i2} are two equal images, we are searching for
> the least k such that x_{i1+k} = y_{i2+k} have the special form.
> This k will be about 2^40. The network applies f 2^80 times, but
> only one output in 2^40 is sent to the central site.
> The central site needs storage for 2^40 values of special form.
>
> Once the central site gets two equal images, it can backtrack
> to get the pre-images.
Isn't the practical pollard-rho implementations based on this cycle finding
technique?
Tom/
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Uniciyt distance and compression for AES
Date: Sat, 02 Jun 2001 21:20:00 -0700
"SCOTT19U.ZIP_GUY" wrote:
>
[...]
>
> Look at it this way instead of 4 message think of 16 states.
> I have a curent encryption system that is not perfect. But uses
> a two bit key. WHen I use key one for example
> it maps message 1 to a 1 bit cipher text. And like wise maps
> message 2 to 3 bit cipher text and message 3 to 4 bit cipher
> text and message 4 to 5 bit cipher text. Key two map message one
> to 6 bits and so on so that message 4 goes to 9 bits. And so
> So that when done each Meassage key combination you want to send
> maps to a different bit combinaion. This clearly is not a perfect
> cipher. Also notice the 2 bit cipher out is not in the set of possible
> out ciphers at this time since no used message maps to it.
> Example you get three bits outs you know it was message #2
> encrypted with key 1.
Let me paraphrase the example to make sure I understand it.
There are four messages in the set M = { m1, m2, m3 , m4 } and P(m1) =
1/2, P(m2) = 1/4, P(m3) = P(m4) = 1/8 where P(m_i) means probability of
occurrence of m_i. We have the four keys k_i, k = 00, 01, 10, 11 for
four possible mappings from the set M = {m1, m2, m3, m4} to a set of 16
cryptograms {c1, c2, c3 ... c16} like this:
k1 = 00 selects this mapping:
m1 <-> c1
m2 <-> c2
m3 <-> c3
m4 <-> c4
k2 = 01 selects this mapping:
m1 <-> c5
m2 <-> c6
m3 <-> c7
m4 <-> c8
k3 = 10 selects this mapping:
m1 <-> c9
m2 <-> c10
m3 <-> c11
m4 <-> c12
k4 = 11 selects this mapping:
m1 <-> c13
m2 <-> c14
m3 <-> c15
m4 <-> c16
and the values of c1, c2, c3 ... c16 are all different from one another,
c_i = c_j only if i = j. These cryptograms could all differ in bit
length as well.
Alice and Bob know the four mappings relating m_i to c_i. Alice and Bob
chose a secret key (00, 01, 10 or 11) and exchange it only between
themselves. Alice and Bob send messages m1, m2, m3 and m4 to one
another as ciphertext c1, c2, c3 and c4. They decode them according to
the appropriate mapping as a function of the secret key value.
Eve knows the messages m_i, the probability of message m_i appearing and
the four mappings from m_i to c_i. The only thing Eve doesn't know is
the key k_i shared by Alice and Bob.
First, does this cipher have perfect secrecy?
Perfect secrecy means
P(m_i | c_j) = [ P(m_i) * P(c_j | m_i)] / P(c_j) = P(m_i).
So when Eve sees cryptogram c_j passing between Alice and Bob, the
probability of that cryptogram's plaintext being message m_i is still
just the a priori probability of Alice sending message m_i to Bob, which
Eve already knows. Eve learns nothing from the ciphertext that she
didn't already know.
Say Eve sees c3. What is the probability the actual message sent is
m1? If the cipher has perfect secrecy then the P( m3 | c1 ) should just
be P(m3).
P( m1 | c3 ) = [ P(m1) * P( m1 | c3 ) ] / P( c3 )
P(m1) = 1/2;
P( m1 | c3 ) = 0. Not one of the four mappings indicated by the key
values takes m1 to c3.
So P( m1 | c3 ) = 0 and != P( m1 ).
This cipher doesn't have perfect secrecy. In fact this cipher has no
security whatsoever! The cryptogram for each message is unique for each
key so the cryptogram value always reveals the key used and thus the
message sent. This cipher has perfect insecurity :-)
This can't be what you had in mind but it's what I got out of the text.
:-(
Could you provide example transformation mappings like those in this
thread, one for each of the key values, to show what you had in mind?
> When you test the other keys they map back if at all to sequences of
> symbols that are not messages.
This throws me for a loop. Alice and Bob AND Eve all know how the
messages m_i map to cryptograms c_i for each key value. That's the
threat model used by Shannon in his paper describing perfect secrecy.
Eve knows the four transformation mappings that are specified by the
four key values.
Again, I know this is not what you had in mind. :-(
[...]
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: practical birthday paradox issues
Date: Sat, 2 Jun 2001 21:53:31 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:sRhS6.13341$[EMAIL PROTECTED]...
>
> "Niels Ferguson" <[EMAIL PROTECTED]> wrote in message
> news:9fc7ep$fn0$[EMAIL PROTECTED]...
> > "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> > news:iTeS6.12347$[EMAIL PROTECTED]...
> > > Well being the slowest math student on earth I figured out how the
> > birthday
> > > paradox applies to collision in the 2^(n/2) sense...
> > >
> > > 2^n/2 chosen texts is really (w^2)/2 pairs in this case it would be
> > 2^(n-1)
> > > pairs.
> > >
> > > Wow.
> > >
> > > Problem is.... if we say something like SHA-1 has a 2^80 resistance to
> the
> > > bday paradox, don't we need 2^80 memory for all the chosen texts and
> 2^159
> > > work to find a match? I.e we first need all the texts, then we must
try
> > > them as pairs one by one to find the collision?
> >
> > You need 2^80 memory slots, but this is math so we are not limited by
> > little things like equipment budgets.
> >
> > You can find the matches without doing 2^159 work. A simple
> > general solution is to sort the 2^80 values (in n * ln n time), and
> > then find the matches in linear time. In practice you use a hash-table
> > like construction, which requires only 2^80 operations to find
> > all matches.
> >
>
> Hmm n ln n, is the expected time of quicksort right?
Well, it is, but (n log n) is the minimum expected time for any
comparison-based sorting algorithm, and it is achievable by a number of
different algorithms. If you are really sorting through 2^80, or even 2^40,
items, you're not likely to do quicksort. Instead, you're far more likely
to do a merge sort on a large number of tapes. For far more about sorting
than you ever wanted to know, see Knuth vol 3 (The Art of Computer
Programming, Sorting and Searching)
--
poncho
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Uniciyt distance and compression for AES
Date: 3 Jun 2001 05:12:52 GMT
[EMAIL PROTECTED] (John A. Malley) wrote in
<[EMAIL PROTECTED]>:
>
>"SCOTT19U.ZIP_GUY" wrote:
>>
>[...]
>>
>> Look at it this way instead of 4 message think of 16 states.
>> I have a curent encryption system that is not perfect. But uses
>> a two bit key. WHen I use key one for example
>> it maps message 1 to a 1 bit cipher text. And like wise maps
>> message 2 to 3 bit cipher text and message 3 to 4 bit cipher
>> text and message 4 to 5 bit cipher text. Key two map message one
>> to 6 bits and so on so that message 4 goes to 9 bits. And so
>> So that when done each Meassage key combination you want to send
>> maps to a different bit combinaion. This clearly is not a perfect
>> cipher. Also notice the 2 bit cipher out is not in the set of possible
>> out ciphers at this time since no used message maps to it.
>> Example you get three bits outs you know it was message #2
>> encrypted with key 1.
>
>Let me paraphrase the example to make sure I understand it.
>
>There are four messages in the set M = { m1, m2, m3 , m4 } and P(m1) =
>1/2, P(m2) = 1/4, P(m3) = P(m4) = 1/8 where P(m_i) means probability of
>occurrence of m_i. We have the four keys k_i, k = 00, 01, 10, 11 for
>four possible mappings from the set M = {m1, m2, m3, m4} to a set of 16
>cryptograms {c1, c2, c3 ... c16} like this:
No in the uncompressed system they map to
{c1,c3,c4 ... c17}
>
EDITING TO GET SYSTEM
k1 = 00 selects this mapping:
m1 <-> c1
m2 <-> c3
m3 <-> c4
m4 <-> c5
***notice for the 4 messages no mapping to c2 so no two bit output
at this point.***
k2 = 01 selects this mapping:
m1 <-> c6
m2 <-> c7
m3 <-> c8
m4 <-> c9
k3 = 10 selects this mapping:
m1 <-> c10
m2 <-> c11
m3 <-> c12
m4 <-> c13
k4 = 11 selects this mapping:
m1 <-> c14
m2 <-> c15
m3 <-> c16
m4 <-> c17
and the values of c1, c2, c3 ... c17 are all different from one another,
c_i = c_j only if i = j. These cryptograms could all differ in bit
length as well.
The bit length of cj is j.
At this point Alice Bob and Eve know enverything about the mappings.
>First, does this cipher have perfect secrecy?
No since when Cj is sent EVE will no which message and which
key was used.
>This cipher doesn't have perfect secrecy. In fact this cipher has no
>security whatsoever! The cryptogram for each message is unique for each
>key so the cryptogram value always reveals the key used and thus the
>message sent. This cipher has perfect insecurity :-)
Yes that is correct for the 4 messages with out compression
there is zero security. Kind of like PGP.
>
>This can't be what you had in mind but it's what I got out of the text.
>:-(
Well you missed that fact c2 was skipped at this point none of
the 4 message map there.
>
>Could you provide example transformation mappings like those in this
>thread, one for each of the key values, to show what you had in mind?
I just did by editing your statements.
>
>> When you test the other keys they map back if at all to sequences of
>> symbols that are not messages.
>
But look what happens when one decrypts any message of 2 bits.
since its not used in the message space. I maintain that this
decryption system maps each 2 bit value for c2 space back to four
values sa s1 s2 s3 and s4. The mapping are such they match you
example for the perfect security method you just explained.
I perform a compression ( bijective mapping ) so the 4 messages
I was using map to s1 s2 s3 s4. These statements all mapp to c2
two bit valuse. The same as you example. So know by using bijective
compression I have turned a not secure system to one of perfect
security by the use of bijective compression.
Take a look at what I wrote in this message and you will see you
quoted it wrong.
ALso EVE knows all about the compression
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,us.misc
Subject: Re: And the FBI, too (Re: National Security Nightmare?)
Date: Sat, 2 Jun 2001 22:17:08 -0700
On Sat, 2 Jun 2001, Matthew Montchalin wrote:
||Miraculously, he had no difficulty using his ID card and entering
||his PIN to get in.
|
|Was the ID card a so-called 'stripe' card that one inserts into
|a lock, and then leaves there, before manipulating a lever, or
|before one pushes a button to activate a servo? Or is there an
|attendant at a checkpoint, who reads it or scans it with a "wand?"
Did he type his PIN into a little keypad next to the door, or ...?
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: practical birthday paradox issues
Date: Sun, 3 Jun 2001 05:29:22 +0000 (UTC)
John Savard wrote:
>But yes, we do need all that memory, [...]
Actually, Wiener & van Oorschot's parallel collision search techniques
may allow to dramatically reduce the memory requirements, which may make
the attack much more probable.
Therefore, it would (IMHO) be unwise to rely on memory costs for security
against birthday attacks.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: bent functions
Date: Sun, 3 Jun 2001 05:32:28 +0000 (UTC)
Douglas A. Gwyn wrote:
>Tom St Denis wrote:
>> A function is bent iff all linear approximations have the same
>> probability right?
>
>I don't know what that would mean. A bent function is a Boolean
>function all of whose (discrete) Fourier coefficients have the same
>magnitude.
If I recall correctly:
If f is a boolean function and f^ is its discrete Fourier transform,
then f^(w) measures exactly the correlation of between f and the linear
map x |--> w.x, where w.x represents the dot-product of w and x.
So, I think that your statement and Tom St Denis's statement may be
equivalent. (But maybe I'm misremembering.)
------------------------------
** 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
******************************
