[cryptography] NSA IDA Cryptological Research Centers
The Institute for Defense Analyses, based in Alexandria, VA,
is a 50-year partner of NSA. It has two Centers for Communications
Research at Princeton, NJ, and La Jolla, CA, both doing cryptological
research for NSA:
http://www.idaccr.org/
http://www.ccrwest.org/
The latter's web site lists only this offering:
[Quote]
La Jolla Covering Repository
A (v,k,t)-covering design is a collection of k-element subsets,
called blocks, of {1,2,...,v}, such that any t-element subset is
contained in at least one block. This site contains a collection of
good (v,k,t)-coverings. Each of these coverings gives an upper bound
for the corresponding C(v,k,t), the smallest possible number of
blocks in such a covering design.
The limit for coverings is v100, k=25, and t=8 just to draw the
line somewhere. Only coverings with at most 10 blocks are given,
except for some which were grandfathered in. Some Steiner systems
(coverings in which every t-set is covered exactly once) which are
too big for the database will be included in the link below.
[Unquote]
What is covering and how does it related to cryptology?
-
Eyeballs of the two centers:
http://cryptome.org/2013-info/09/nsa-ccr/nsa-ccr.htm ___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] NSA IDA Cryptological Research Centers
JY == John Young j...@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 cl...@jhcloos.com OpenPGP: 1024D/ED7DAEA6
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] NSA IDA Cryptological Research Centers
On Sun, Sep 29, 2013 at 09:43:54AM -0400, John Young wrote:
http://www.ccrwest.org/
The latter's web site lists only this offering:
La Jolla Covering Repository
A (v,k,t)-covering design is a collection of k-element subsets,
called blocks, of {1,2,...,v}, such that any t-element subset is
contained in at least one block. This site contains a collection of
good (v,k,t)-coverings. Each of these coverings gives an upper bound
for the corresponding C(v,k,t), the smallest possible number of
blocks in such a covering design.
[snip]
What is covering and how does it related to cryptology?
As is common in math, they define what they mean in the first paragraph.
To paraphrase, they're considering ways to arrange a large number of
sets of things so that a minimum number of blocks is used to enclose
all of the sets.
I'm not a mathematician but that looks like set theory to me. It's the
kind of fundamental mathematical research that frequently arises when
considering some more applied problem space. Such fundamental
approaches frequently have applications in wide-ranging fields; to
compare to a more well-documented example, the 4-color problem first
solved in the 70s generated techniques which ended up being critical to
optimizing C compiler designs for RISC processors in the 90s.
http://en.wikipedia.org/wiki/Four_color_theorem
http://en.wikipedia.org/wiki/Register_allocation#Isomorphism_to_graph_colorability
I doubt that much can be concluded about the activities at the research
site based on their publishing one database in such a rarefied field.
-andy
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
