2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Accumulators look like a attractive solution but have various challenges especially dynamic accumulaotrs (which support addition/removals). Apart from guarding the factors of RSA modulus, updating the proof of membership/non-membership as the accumulator changes is also cumbersome for the prover $\endgroup$ – lovesh Jan 11 at 7:19
2
$\begingroup$

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? :-)

$\endgroup$
  • 1
    $\begingroup$ You can request to merge your accounts. $\endgroup$ – kelalaka Jan 11 at 5:40
  • $\begingroup$ Hi Daniel. Thanks for taking the time to write this helpful post! The key thing I'm hoping to understand a little deeper is the second-to-last paragraph about what exactly one trades off by having fewer bits in the accumulator. Your post mentions computation hardness as one tradeoff, and that's certainly interesting and relevant given the application, but I'm still wondering about whether and how correctness is one of the tradeoffs: is there a bit cutoff above which we are guaranteed no false positives (no collisions), or is it always probabilistic, and what exactly is the relationship? $\endgroup$ – Louis Semprini Jan 11 at 5:47
  • $\begingroup$ @lovesh Comments are not for extended discussion. If you want to provide an answer given the concerns of Louis please do so. Otherwise leave it up to the answerer to correct the question. Louis, this is also for you, please don't thank Daniel for his answer by performing a deep discussion with somebody else in the comments. $\endgroup$ – Maarten Bodewes Jan 11 at 10:22
  • $\begingroup$ @LouisSemprini I was wrong in some of the comments over here, we can chat at chat.stackexchange.com/rooms/88146/… $\endgroup$ – lovesh Jan 11 at 16:53
  • $\begingroup$ I deleted my comments and moved all to the chat at chat.stackexchange.com/rooms/88146/… $\endgroup$ – Louis Semprini Jan 11 at 17:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.