A basic cryptographic accumulator can be implemented by simply multiplying prime numbers to form a composite number such that the membership of any given prime can be determined simply by dividing it into the composite and ascertaining the quotient is a whole number (and not 1 or the composite number).

Imagine that Alice and Bob have a shared secret prime number. They communicate over a nymserver implemented as a distributed index number based PIR (allowing retrieval of padded mail buckets associated with usernames) by writing E-mails to a server. The server is used by numerous unrelated interlocutors. Participants send symmetrically encrypted messages through remailer networks, with all of the them receiving -- via a separate fan-out PIR mechanism -- a complete copy of the [index number : email address] index into the padded (to the same size) buckets, which are by the nymserver filled (up to their maximum capacity) with incoming E-mails addressed to a given [email protected] address. This system is essentially the nymserver Pynchon Gate.

In addition, participants retrieve a constant number of the fixed sized buckets, via the index number based PIR mechanism, every "cycle," which is just a fixed period of time (an hour, say). Every cycle, the complete list of E-mail addresses of all registered users is published via the fan-out PIR mechanism, and participants check it to see which index number to query the PIR mechanism for, as is done to retrieve the associated (padded to a fixed size) bucket.

Now, instead of imagining that an E-mail is written to a given [email protected], imagine that, in order to maintain unlinkability, an ECDH key exchange between Alice and Bob takes place (either out-of-band or through the previous method of using a username), with the resultant shared secret S between them being used as an input into a hash function H such that H(S) = C1, H(S || C1) = C2, H(S || C2) = C3, H(S || C3) and so on, with || denoting concatenation, and with each Cn denoting a contact signal, with even contact signals being used by Alice and odd contact signals being used by Bob (perhaps determined alphabetically).

Now, instead of writing messages to [email protected], Alice writes her first message to Bon to [email protected], and her second to [email protected]. Likewise, instead of writing messages to [email protected], Bob writes a message to [email protected], and then to [email protected] for his second message. The reason for this is to allow Alice and Bob to communicate through the nymserver without it being able to determine the message volume sent to any of the given participants, and without messages being linkable as sent to the same entity in general. Participants use the fan-out PIR to retrieve the [index number : e-mail address] list as before -- after receiving it, Bob will check for any E-mail addresses with an even Cn as the prefix, and will use the PIR mechanism to get those buckets as before, with the distinction that E-mail addresses in the form of Cn (perhaps a 256 bit hash), as opposed to those in the previous form (e.g., [email protected]), are only listed upon an E-mail having been sent to them in a given cycle, rather than repeatedly after that.

An issue with the previous solution is the difficulty of maintaining synchronization, as Bob needs to know which of the [email protected] to check for messages from Alice. One solution is to use a prime accumulator as previously described. Alice and Bob can use ECDH as before, in order to have a shared secret between them. However, they now use it to seed a PRNG that is used to generate a prime number (i.e., Rabin's primality testing on the outputs until the first prime, P, is generated, which is then a shared secret prime between them). Now, when Alice wants to write Bob, she generates her own secret prime number and multiplies it by the shared secret prime number to form a composite number Cn. She writes to Bob then at [email protected] (assuming that such a number can be used for E-mail, irrespective of feasibility). Bob, as before, uses the fan-out PIR mechanism in order to retrieve the complete list of [index number : email address]. Now, for each listed E-mail address in the form [email protected], Bob divides C by P in order to see if the shared secret prime P is a member of the prime accumulator Cn. If it is, this signals to Bob that it is a message written to him by Alice, and he knows to fetch that bucket from the nymserver to retrieve that message from Alice.

This solution is very nice, as it allows Alice and Bob to not have difficulty staying synchronized. They don't need to keep track of which Cn will be the next from their interlocutor, or otherwise to check for a large swathe of Cn in order to try to re-synchronize. They just need to generate an arbitrary prime number to multiply into the shared secret prime number. An attacker at the nymserver should have just as hard of a time linking multiple Cn to the same interlocutors as in the previous solution, as they would need to factor the Cn into the shared secret prime P and the arbitrary prime generated to multiply the shared secret prime with. The multiplication step is to unlink the resultant Cn from the static shared secret prime P, as determining that Cn was constructed from P requires either factoring a large composite number (the RSA problem) or else having access to either the secret prime P, or the randomly generated prime it was multiplied with.

In this system, seeing as Alice and Bob share a secret prime P, and that Bob can detect composite numbers Cn that are formed by the multiplication of P with arbitrary primes simply by dividing P into them to see if the resultant quotient is a whole number (and not 1 or the composite number itself), and that the quotient of this division is a different prime previously unknown to Bob (the prime that Alice generated to multiply the shared secret prime with), couldn't this second prime number, which again requires either having the shared secret prime P or a prime factorization of the composite Cn, be used as an input into a hash function that generates the session string used for the symmetric encryption of the associated ciphertext?

If so, it seems like it would function as both the session string sharing mechanism of a hybrid cryptosystem (as an atypical RSA like system, where the session string is effectively one of two primes used in the construction of a public key used as the contact signal, with the second prime being a static shared secret between the interlocutors and used to allow them to factor the composite without running into the RSA problem), as well as to signal contact unlinkably. Are there any issues with this system? Are you aware of any research into similar things, where there is a mechanism for two parties to signal through a server that a communication is intended for the other, in such a way that the server cannot link the signals together yet the participating communicators can identify signals intended for them (and thereby the party communicating to them)?

  • 1
    $\begingroup$ TL:DR; ${}{}{}{}$ $\endgroup$
    – kelalaka
    Commented May 24, 2020 at 9:31

1 Answer 1


An attacker at the nymserver should have just as hard of a time linking multiple Cn to the same interlocutors as in the previous solution, as they would need to factor the Cn into the shared secret prime P and the arbitrary prime generated to multiply the shared secret prime with.

No, it's actually straightforward for the attacker; all they need to do is compute $\gcd( C_x, C_y )$ for the various $C_x, C_y$ values they see. If they do use the same shared secret prime $P$, then the $\gcd$ will be that prime (which will tell the attacker both that the same two people are communicating, as well as their secret value).

A better approach might be just to have the two sides share a secret symmetric key $K$, when one side wants to signal the other, they just select a random $r$ and output $r, HMAC(K, r)$. This is cheap for the other side to test (cheaper than your original idea of checking divisibility), and without knowing $K$, it looks completely random (and so the attacker has no way to distinguish whether the same pair was used to communicate with the same pair).

  • $\begingroup$ You got it, thanks. I'm going to also look into RSA accumulator -- I thought it was just n = pq essentially, and then divide n by p or q to test for membership, but that is actually just the most basic example of an accumulator, not actually the RSA accumulator. I think the way you put it forth is the proper way to do it now. $\endgroup$
    – cyborg
    Commented May 25, 2020 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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