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