cryptographic accumulators: accumulator size vs. max. number of set members?

Question

Here's a basic question about cryptographic accumulators, or at least ones based on fixed-size accumulator values (such as RSA ones based on modulo arithmetic), that is strangely not even mentioned in most of the key historical papers or Wikipedia.

Cryptographic accumulators are being touted as a magical solution for the application of distributed certification/licensing by government/corporate authorities. For example, I have heard claimed that the DMV (Department of Motor Vehicles) could publish a hash function and an accumulator, both of which were of constant size---or at least a size that does not grow linearly with the number of licensed drivers---and that would allow me (a driver) to present a proof to you (a car rental company) that I am licensed. The car rental company could then check that proof without learning the driver license number of any other licensed driver. All the crypto papers focus on the last property (privacy). For the purposes of this SE question, I will take that as granted.

I have a much more simple question:

This immediately strikes me as impossible. How can a constant-size accumulator contain set membership information for a variable number of members? That seems to violate basic information theory. How can, say, 512 bits of accumulator contain information for millions of "bits" of information (if we assume that somehow each licensed driver was only 1 bit of information)? I could then use an accumulator to compress anything to 512 bits :)

Clearly, I am missing something very fundamental about how this whole thing works, including that the claim itself may be wrong or my understanding of its application is wrong:

• does a, say, 512 or 2048 bit accumulator allow one to track only a limited amount of set members, but that number is much more than 512 or 2048? If so, how many, and how can this possibly work? Why does it not violate information theory?

• is the set membership test that is done by a cryptographic accumulator probabilistic and/or does it suffer false positives or negatives (e.g. like a Bloom filter), and does that explain why it seems information theory is being violated?

• does the DMV example I cited above require more than just a basic (fixed-size, e.g. RSA) cryptographic accumulator to work? Does it require an accumulator whose size is linear in the maximum number of set members?

• does the DMV example I cited above require other storage that I didn't mention above (for example, does each license holder have to store a constant amount of data that none of the other parties could generate even if everyone revealed their secrets to everyone else) and therefore the storage required across the system is, in fact, linear in the number of license holders?

• more generally, what is the relationship between the accumulator size in bits and the maximum number of members that can be tracked, and are there other tradeoffs (e.g. probability of getting the correct answer) that can also be tweaked in designing the hash function?

Another way to think about it: some folks like to introduce cryptographic accumulators using the (non-secure, non-private) example of assigning each member its own prime number and the published accumulator simply being the product of all the primes of the members in the set. Then my "proof" consists of handing you the product of all the primes in the set except my prime, and you can multiply them together to see they make the published product. Well, in this simplified case, clearly the accumulator is going to get bigger as there are more primes that may be factors inside it. But the other cryptographic accumulator algorithms (e.g. RSA) use modulo arithmetic and other methods that constrain the accumulator size...so how many members can be tracked given a particular limitation?

Thanks.

NOTE: Chat about this topic going on here: https://chat.stackexchange.com/rooms/88146/cryptographic-accumulators-accumulator-size-vs-max-number-of-set-members

Answer 1

Disclaimer: I am not a hard-core cryptographer, and I am only familiar with a subset of the various accumulator implementations. So this is a layman's answer.

Accumulators are not attempting to set a bit for every member of the set. The reason they can violate the intuition that they must have at least 1 bit for every potential set member is because they are lossy. Unlike a bit set, accumulators do not provide a 2-way lookup. You can put stuff in, but you can't get stuff out. Specifically, you can't start from the accumulator value and enumerate all members of the set; there is an infinite number of values "in" any given accumulator.

You can think of an accumulator like the hands of a clock. Perhaps the hands say 3:15. If I say to you, "3994 seconds have elapsed" as you look at the clock, your natural response would be, "Since when?" Without a reference start time and knowledge about how many times the hands of the clock have "wrapped", there could be an infinite number of valid assertions about elapsed time. (Accumulators depend on arithmetic in a modular field, which has this same wrapping property. 5 * 7 mod 4 = 35 mod 4 = 3. But I can give you lots of other factors that multiply together to yield 3 in a mod 4 field.)

You might be tempted to say, "Well, if a given accumulator value is compatible with an infinite number of set members, how can it "store" anything?"

To understand the answer, let me alter the clock situation a bit. You are standing in front of a clock that says 3:15 when Alice says, "4 billion 200 million 93 thousand 74 seconds have elapsed" Now you say to Alice, "Since when?" and Alice says, "Since the clock said midnight."

Even though there is an infinite number of explanations for the clock saying 3:15, Alice's assertion is testable. You can do the math that divides clock hand revolutions into the given number of seconds, and see if it's really the case that the clock said midnight at the interval that Alice claims.

Now, you can think of an accumulator as being the product of many numbers multiplied together in a wrapping, modular field. When you test set membership with the accumulator, you can't just assert "X is in the accumulator", any more than you can say "how much time has elapsed?" without a frame of reference. Instead, you have to make a claim that X is "in" the accumulator because X times Y produces that accumulator value in its modular field. That is easy to test. The Y in this example is like picking some other arbitrary reference point in a clock discussion to answer the question, "Since when?"

Notice that for X to be useful, Y must also be given. In information theory, the amount of information that must be known grows with each new set member--but the knowing is distributed to all the owners of the set members; it does not need to be held centrally. The value in the accumulator is the reference against which each set member's claims can be tested by them presenting both X and Y.

It turns out that it is computationally "hard" (meaning there is no practical way to brute-force a correct answer) to explain an accumulator as the product of X and Y, in large modular fields, unless you have been given X and Y. This is due to the irreversibility of modular math (you can't divide, any more than you can look at clock hands and know how many times they've gone around when they say 3:15). Thus, if you "own" a value that is a member of a set represented by an accumulator, and you have been told what the product of all the other set members are, you can show that your value is "in" the accumulator with some very simple math. But if you pick an arbitrary number and want to prove it is in the accumulator, you could compute till the end of the universe, and never find a solution.

It might sound like I'm claiming that accumulators can "hold" an infinite number of values. I believe that's not the case; there's a relationship between accumulator bit size and the number of possible factors (set members) and computational hardness. A mathematician could state it precisely, but I believe a simple summary is, "you can put as many set members into an accumulator as you like, but at some point, you begin to degrade computational hardness." And I think that the point where computational hardness degrades, for the 256-bit accumulators I'm used to, is very, very, very large. Certainly more than billions or trillions (which is a tiny fraction of a 256-bit number).

Cryptographers and mathematicians, is this answer accurate to one or two decimal places? :-)