A mathematical study published inside the National Security Agency six decades ago has been released through the Freedom of Information Act, more than nine years after The Black Vault requested it.
The paper, “Coupon Collecting and Cryptology,” was written by Marie Capozza and published in the Fall 1966 edition of the NSA Technical Journal. Although the title had been publicly identified for years in declassified indexes of NSA publications, searches conducted by The Black Vault did not locate a previously public copy of the paper itself. The 1966 study released in response to the FOIA request therefore provides a newly available look at how NSA mathematicians examined a classic probability problem and applied it to cryptologic questions.
The Black Vault requested the article from NSA on August 6, 2017. NSA’s response is dated September 9, 2026, more than nine years later. The agency released the responsive document with portions withheld under FOIA Exemptions 1 and 3.
Despite its complex pages of equations, the basic idea behind the paper is relatively straightforward: If items are selected randomly from a fixed number of possible types, how long should it take before every type has appeared; and can deviations from that expected behavior reveal that the selection process is not actually random?
For the NSA, that question had direct applications to cryptology.
From Cereal-Box Coupons to Cryptology
Capozza begins with a deliberately ordinary example.
“Let us assume that a manufacturer encloses in each package of his product one coupon that is chosen randomly from a stock of K different coupons.”
The manufacturer might offer a prize to someone who obtains every different coupon. The mathematical problem is determining how many packages, on average, a customer would have to purchase before completing the set.
That is what mathematicians call the coupon collector’s problem.
Capozza describes the purpose of the paper as presenting “some well-known and some new results found in the literature on coupon collecting and to point out some cryptologic applications.”
In plain English, imagine that there are ten different coupons and every box contains one, selected independently and with equal probability. Finding the first several different coupons is easy. The problem becomes progressively harder as the collection approaches completion. Once nine different coupons have been obtained, every new box has only a one-in-ten chance of containing the single missing coupon.
That last stubborn item substantially increases the average waiting time.
Capozza calculates that when there are ten possible coupons, the expected number of selections required to collect all ten is approximately 29.29. The paper notes:
“Suppose that we have decimal digits. Then the expected number of drawings to exhaust the entire population … [is]29.29.”
The same mathematics applies to an alphabet. For 26 equally probable letters, the paper calculates an expected collection time of approximately 100.20 selections before all 26 have appeared.
These examples provide the foundation for the paper’s more consequential subject: testing whether sequences used in cryptographic systems behave as though they are genuinely random.
Why Randomness Matters
Cryptographic systems depend heavily on sequences that cannot be readily predicted. A sequence may look chaotic to a person while still containing mathematical biases or patterns.
The coupon collector framework offers one way of testing those sequences.
Instead of asking how long it takes to collect every coupon, an analyst can ask how many generated symbols must be examined before every possible symbol has occurred. If that process repeatedly takes substantially more or fewer observations than mathematics predicts for genuinely random selections, something about the underlying generator may warrant scrutiny.
Capozza devotes much of the paper to deriving the probability distributions necessary to make those comparisons.
The equations determine, among other things, the probability of obtaining a particular number of distinct coupon types after a given number of selections, the average waiting time required to obtain every possible type, the variance around that average and the limiting behavior of the distribution when the number of possible symbols becomes very large.
One table illustrates how quickly the waiting time grows. For ten possible coupon types, the expected collection time is about 29.29 selections. For 20 types, it is about 71.95. For 30, approximately 119.85. At 40, the expected number rises to approximately 171.16, and for 50 possible types it reaches about 225.06.
The point is not that cryptographers were literally collecting coupons. The coupon story provides a convenient mathematical model for analyzing symbols drawn from a finite alphabet.
Testing Random Numbers
The paper eventually turns explicitly to what Capozza calls “Cryptologic Applications.”
One is a test of randomness.
Capozza describes the “Coupon Collector’s Test for Randomness” and applies the concept to decimal digits. Under the assumption that digits are random, analysts can calculate how frequently they should need a particular number of observations before seeing all ten digits.
The paper states:
“Using the 2035 decimal approximations to π given by G. W. Reitwiesner, Greenwood began with the initial position 3 and found that 33 positions were required to collect all ten digits.”
The procedure was then repeated through the sequence, producing 87 sequences of complete sets, according to the study.
Those observed results could be compared with the mathematically expected distribution.
This is an important distinction: the test does not prove that a sequence is random. Rather, it provides a statistical means of identifying behavior that is inconsistent with what would ordinarily be expected from random sampling.
The underlying technique was not unique to NSA. Robert E. Greenwood published “Coupon Collector’s Test for Random Digits” in Mathematical Tables and Other Aids to Computation in 1955, and the technique subsequently appeared in the literature on random-number testing.
Capozza’s NSA paper assembled that mathematical foundation and examined how it could be used in a cryptologic environment.
Generating Cryptographic Alphabets
A second application gets closer to operational cryptography.
Under the heading “Coupon Collecting and Key Card Generation,” Capozza describes a method in which randomly generated coordinates are used to place punches in a 12-by-12 field on a key card.
The goal was to populate the card while avoiding duplicate locations.
The document explains:
“If it takes too many trials to complete our matrix, then our ‘random’ process of position selecting is not truly random since it has a tendency to select one or more positions.”
Conversely, the study says that completing the matrix with unusually few selections could indicate another form of non-random behavior.
This is the practical significance of the otherwise abstract mathematics.
A random-number source might produce values that look unpredictable when examined casually. But if certain positions or symbols occur too frequently — or others appear too infrequently — coupon-collector statistics can expose that imbalance.
In cryptography, such bias can matter because the security of a system may depend on assumptions about the randomness of its keys or other generated values.
A Second Statistical Test
The paper also discusses what it calls a “Statistical Inference: Coupon Collector’s Test for the Number of Code Groups.”
Capozza asks analysts to imagine that there are K possible code groups, but that K itself is unknown. After observing a sample containing a certain number of different groups, the analyst can attempt to estimate the total number of groups that exist.
That reverses the original coupon problem.
Instead of knowing how many coupon types exist and calculating how long collecting them should take, the analyst observes repeated samples and attempts to infer the size of the unseen population.
Capozza notes that the underlying population is assumed to be flat — meaning the individual possibilities are treated as equally likely — an assumption that the paper explicitly acknowledges “is not easily satisfied.”
That caveat is important. The mathematics depends upon assumptions about how the underlying population behaves. If those assumptions are wrong, the resulting statistical conclusions may not accurately describe the real system.
A Paper Marked SECRET
Every page of the released article carries SECRET classification markings at the top and bottom. The released copy identifies it as Doc ID 6932166 and Doc Ref ID A3912410.
The first page now also bears a release notation:
“Approved for Release by NSA on 09-09-2026, FOIA Case # 102241.”
NSA did not release everything.
Its September 9 response states that portions remain classified under Executive Order 13526 and were withheld pursuant to FOIA Exemption 1. NSA said disclosure of the classified material “could reasonably be expected to cause serious damage to national security.”
The agency also invoked FOIA Exemption 3, citing statutes protecting intelligence-related information, including 50 U.S.C. §3024(i) and Section 6 of Public Law 86-36. NSA characterized the release as a partial denial of The Black Vault’s request.
Several portions of the article remain visibly blank or redacted. Most notably, a large section on page 115 under the heading “Coupon Collecting and Alphabet Generation” is withheld. Portions of the bibliography are also redacted.
The contents of those withheld passages cannot be established from the released record.
What the 1966 Study Means in Plain English
Stripped of its equations, Coupon Collecting and Cryptology addresses a fundamental problem: How can mathematics tell whether something that is supposed to be random is behaving the way randomness says it should?
The coupon analogy provides an intuitive way to answer it.
If a bag contains ten equally likely numbered tokens, repeated draws should eventually produce all ten. Mathematics can predict approximately how long that should take and how much variation around that average is normal.
If repeated experiments behave very differently from those predictions, the discrepancy becomes measurable.
Capozza’s paper develops that concept mathematically and then applies it to cryptologic problems involving random digits, code groups, key-card generation and alphabets.
The advanced formulas filling much of the 13-page article are therefore not describing an exotic cryptographic cipher. They are establishing the probability distributions required to distinguish expected random behavior from potentially significant statistical irregularities.
Sixty years after the study appeared inside the NSA Technical Journal — and more than nine years after The Black Vault asked NSA for a copy — the released portions of Coupon Collecting and Cryptology provide a window into how the agency applied classical probability theory to practical cryptologic problems.
The release also leaves part of that history unresolved. Portions of the 1966 paper remain withheld, including material in its discussion of alphabet generation, meaning the complete scope of the study remains unavailable in the public version released by NSA.
###
Document Archive
Coupon Collecting and Cryptology [21 Pages, 2.5MB]
Loading...
Reload document
Open in new tab 
