[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