[cryptography] NSA IDA Cryptological Research Centers
James Cloos
cloos at jhcloos.com
Sun Sep 29 11:59:51 EDT 2013
>>>>> "JY" == John Young <jya at pipeline.com> writes:
LJ>> La Jolla Covering Repository
LJ>> A (v,k,t)-covering design is a collection of k-element subsets, called
LJ>> blocks, of {1,2,...,v}, such that any t-element subset is contained in
LJ>> at least one block.
JY> What is "covering" and how does it related to cryptology?
That quote pretty much answers the question. Perhaps an example would help:
Let's choose v=52, like a deck of playing cards (we'll leave the Jokers
inside the beltway). Let's use 23-card blocks (k=23) and 5-card hands (t=5).
The goal to to find a set of 23-card blocks such that every possible
5-card hand can be found in at least one block. Hense, the set of 23-
card blocks covers the set of possible 5-card hands.
That can be done trivially by making the blocks be every possible
23-card hand. But ( 52 \choose 23 ) is about 352 trillion. So we
want to find a smaller set of blocks which cover every possible 5-
card hand.
Their site has one covering for (53,23,5) with 243 blocks. It also
shows that they started with a 272-block covering and worked their
way down to 243 blocks via "dynamic programming".
THe application the cryptography is probably something to do with
statistical cryptanalysis. Rainbow tables, maybe?
-JimC
--
James Cloos <cloos at jhcloos.com> OpenPGP: 1024D/ED7DAEA6
More information about the cryptography
mailing list