NSA Unveils Decades-Old Study Linking Math Puzzles to Cryptology After Long FOIA Battle

The National Security Agency has finally released a 1966 study titled "Coupon Collecting and Cryptology" after a nine-year legal battle through the Freedom of Information Act (FOIA). The document, authored by Marie Capozza and published in the NSA Technical Journal's Fall 1966 edition, explores how classic probability problems can be applied to assess the randomness of cryptographic sequences.

The Black Vault initially requested the paper on August 6, 2017, but it took until September 9, 2026, for the NSA to respond and release a redacted version of the document. The study delves into how mathematicians can determine the expected number of random selections needed to collect all possible items in a set, which has direct implications for evaluating the randomness of cryptographic systems.

Capozza's work begins with an everyday example: cereal-box coupons. She posits that if a manufacturer includes one randomly selected coupon from a stock of K different types in each box, how many boxes must be purchased to collect all K coupons? This problem, known as the "coupon collector’s problem," is used as a foundation for more complex cryptographic analyses.

The paper explains that when there are ten possible coupons, on average, 29.29 selections are required to complete the set. For an alphabet with 26 letters, approximately 100.20 selections would be necessary before all letters appear. These calculations provide a basis for assessing whether sequences generated by cryptographic systems exhibit true randomness or contain hidden patterns.

The significance of this study lies in its application to cryptology. Cryptographic systems rely on sequences that are unpredictable and free from discernible patterns. By using the coupon collector framework, NSA mathematicians can test if these sequences behave as expected under random conditions. Deviations from the predicted behavior could indicate weaknesses or biases in cryptographic methods.

While the document has been available for years through declassified indexes of NSA publications, the actual content remained secret until now. The release offers unprecedented insight into how mathematical theories have historically informed and enhanced national security practices at the NSA. However, portions of the released document are still redacted under FOIA Exemptions 1 and 3, suggesting that some aspects of the study's application to current cryptographic techniques remain classified.

This long-awaited disclosure underscores both the enduring relevance of foundational research in mathematics and the ongoing challenges faced by transparency advocates seeking access to government-held information.