4
$\begingroup$

Question

Is it possible to create a public key encryption scheme, with $n$ parties, where a party can send all other parties a bit unique to each party in less than $n$ bits?

Assume we can set up a PKI and there exists some public broadcast channel like a trusted forum or a personal webpage. All users including adversaries are polynomial bound.

Here's an example (completely made up):

I host a website in which people can register their public keys. Later on the site gets hacked and t accounts got their password stolen. I post a data-blob on my site and users should be able to use their private key to derive either 1, their account got hacked and they should change their password or 0, they didn't get hacked (but should change their password anyway for security reasons). At the end no one (but me) should know how many users got hacked or the result of any other person.

In addition my site has over eight million keys registered and I would like to minimize the amount of data sent because I have limited bandwidth. Naively I would think that I would have to host this > 1 MB file and whenever a person visits give them a copy of the file. After all the users check it would have used over 8 TB of bandwidth.

Ideas

One idea I had was to use a cryptographic accumulator and to somehow insert users based on their public key and post the result. Later users could check if they are in the accumulator with their secret key. If they are in the accumulator then their value is 1, otherwise it is 0.

I was considering users generate (sk, pk) pairs like ($sk$, $sk^r$ mod $p$) where $sk$ is a random prime number less than $p$, $r$ is a random number in integers mod $p$ and $p$ is a large prime number. Next to generate the accumulator I would take all the $pk$ that I want to send 1 to and multiply them together mod p, lets call this $A$. Then, after I post it, if a user want to check if they are in it they check if their $sk$ divides $A$, if so their value is a 1 otherwise their value is a 0.

A small optimization is that if I have more 1's than 0's then I could create a 0-accumulator instead which identify the users who have 0's. The problem with this is that users learn if there are more 1's than 0's. In my application I don't mind if users learn this information.

To throw some numbers around, if I let $p$ = $2^{64} - 59$ then the accumulator will never grow above 64 bits. The number of keys is about $4.158 \times 10^{17}$ and the odds of a collision in the 8 million keys would be about $7.695\times 10^{-5}$. In this case I just need to host the 64 bits for all 8 million users which would only cost 64 MB.

I came up with this idea in a few hours so I doubt it would actually work...

$\endgroup$
  • $\begingroup$ Note that the integers mod $p$ form a field. This means that every non-multiple of $p$ divides every other non-multiple of $p$. $\endgroup$ – rikhavshah Sep 28 '18 at 0:08
1
$\begingroup$

No, if you publish an N bit message it can hold at most N bits of information.

An N-bit accumulator value doesn't magically hold more than N bits of information in the same way a hash value does not hold the string it is calculated from. Verifying accumulator membership of a given element X requires storing a witness value for that X (essentially CurrentValue - X). Membership is tested by checking if witness + X = CurrentValue. Accumulators work only because computing a witness value for an arbitrary X is a hard problem, though such a value is guaranteed to exist.

$\endgroup$
  • $\begingroup$ that's not that easy, part of the information can be Embedded in the secret keys for each user. Let's say I have a functional encryption scheme for inner-products, that would allow me to give a key to each person that decrypts $a_i * m$, where $a_i$ is different for each person, by just sending a ciphertext for $m$. Of course, that would mean differing the problem to the key generation, but this would be done offline, so still an interesting solution. In general, if you are able to express all the messages as functions of 1 input, you can use FE to encrypt just that input $\endgroup$ – Florian Bourse Jul 31 '18 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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