# Scheme that encrypt with $n$ pk that any sk of the pks can decrypt?

Suppose there are $n$ users each with public/private key pair $(pk_i,sk_i)$ $i=1,\cdots,n$. Is there any scheme that I can encrypt $m$ using the set of public keys $(pk_1,\cdots,pk_n)$, and can decrypt it using any $sk_i$? That is $C=Enc_{(pk_1,\cdots,pk_n)}(m)$ and $m=Dec_{any\ sk_i}(C)$.

This is meaningful when these $n$ users are just a small portion of a group of $N$ users. A bit like "ring encryption" (opposite to ring signature). Thank you!

This is in no way practical, but it's relatively easy to describe a scheme.

If the public key contains (or allow easy derivation of) a unique prime (just has to be unique among the recipients - If every recipient knows the public key of any other recipient, and public keys can be ordered, we can use the first $n$ primes.), say $r_i$, you can use: $$C=\prod_{i=1}^n r_i^{\operatorname{enc}_{pk_i}(m)}$$ (where $\operatorname{enc}$ is the function for encrypting to one recipient).

Then for decryption you "just" need to determine factor $C$ and determine the highest power of $r_i$ that divides it, and put the exponent into the function for decryption to one recipient.

I haven't tried to prove that it isn't easier to break this than to break than to break the scheme it's based on. I can't see why it would be though, and given how impractical this is, I don't think it matters much.

• How is this different than storing the message n times, per public key? – zetaprime Sep 4 '18 at 14:51
• It's basically not. – Henrik Sep 4 '18 at 19:37
• Sir, it is important in block chain scheme when the log is encrypted and we only want qualified users to filter the message. Can you please give more details about enc and the way to decrypt? Thank you! – Felix LL Sep 5 '18 at 13:25

This is doable under RSA.

For clarity, I'm going to rename the number of users to be $u$ and the total number of users to $U$, since mod $n$ is important in RSA.

I'm going to use the following notations for RSA:

A message M is transformed via padding to an integer $m$.

Under standard RSA the message would be encrypted as $m^e$ mod $n$. The recipient would then decrypt by performing $(m^e)^d$ mod $n$. $e$ and $n$ make up the public key. $d$ is the private key.

We're going to establish some minimal value, $n_{\min}$ (which is sufficiently large). All the users will have the exact same value for $e$. Each will then generate their own $n_i \geq n_{\min}$ so that $e$ is "legal" for it (i.e., if $n_i=p_iq_i$, then $e < \lambda(n_i)=lcm(p_i-1,q_i-1)$ and $e$ is co-prime to $\lambda(n_i)$). Each will have their own private key $d_i$.

In order to send a message $M$ it is padded to an integer $0 \leq m < n_{\min}$. Let $N = \prod n_i$ (it's actually sufficient to take $N$ as the lcm of all the $n_i$ for the users receiving the message, but of course the sender doesn't know the factors of the $n_i$). Then the encrypted message is $m^e$ mod $N$.

Let the encrypted message be $x$. Then, there exists some $c$ such that $m^e = cN + x$. Therefore $m^e$ mod $n_i$ is $x$ for all $i$. Thus, $(m^e)^{d_i}$ mod $n_i$ is $m$ for all $i$.

Threats to validity: if $N$ is so large that w.h.p $m^e < N$, then any other user could decrypt the message, since $m^e$ would be plaintext. To avoid this, the padding scheme should ensure that $m$ is sufficiently large. Similarly we may need $e$ to be sufficiently large to support groups of up to $R$ users. For simplicity, if we assume that $n$ is of length $b$-bits, then we need that $e\log m >> Rb$. While Håstad's broadcast attack shouldn't be relevant, one can take $e > R$ in any case to be on the safe side.

While some messages may be encrypted to short lengths, the output is likely to be about as large as $\log N$ which would be $ub$ - where $b$ is the bit-size for the $n$'s (e.g. let $n_\min=2^b$ and let all the $n_i$'s be $b$ bits long). It's an open and interesting question if we could somehow transform the output so that it's on the order of $b$ bits (after all, the number of messages we have is $n_\min$). For example, if we could compactly encode an additional multiplier $c$ such that $cm^e$ is small, and that we could easily divide out $c$.

• This is equivalent to encrypting the message separately using each public key. That is, $x=m^e\mod N$ can be constructed using CRT from all the $m^e\mod n_i$ that would be sent if encryption was done separately; conversely $m^e\mod n_i$ can all be construed from $x$ as you state. – rikhavshah Sep 5 '18 at 22:32
• I think so. But this will make the ciphertext be a very large number. I am thinking to use ECC instead of RSA : ) – Felix LL Sep 6 '18 at 1:46
• Sir, as your mentioned in "While some messages may be encrypted to short lengths, the output is likely to be about as large as $\log N$ which would be $ub$ - where $b$ is the bit-size for the $n$'s", the complexity of this scheme may be the same as encrypt $m$ with the all the $pk_i$ one by one. And I don't quite understand your last wors " For example, if we could compactly encode an additional multiplier c such that cme is small, and that we could easily divide out c." – Felix LL Sep 6 '18 at 4:07
• I don't think we can actually ensure short messages. From a conceptual level, each user needs to be able to get what is effectively $b$-bits of private information out, so we can't really go down below $ub$ bits. If we're willing to shorten our starting message space, we could dedicate padding space to bits that we'd search through in order to shorten the message, but at exponential cost. For example, if dedicate an additional $2^8$ bits, we can then search through $2^8$ different $m$'s and take the one with the smallest length - but we should only expect 8 bits of savings. – MotiN Sep 6 '18 at 6:34
• Sorry that should read dedicate an additional 8 bits not $2^8$ bits. – MotiN Sep 6 '18 at 10:53

I think the most straight forward and obvious solution is using the standard practices of Public-key cryptography and encrypting the same key with all the public keys that you want to grant access to.

And encrypt m with that key.

Say $k$ is your key to encrypt the message $m$. Store such an array: $\{E_k(m), (pk_1,E_{pk_1}(k)), (pk_2,E_{pk_2}(k)), ... \}$

And any interested party, owning a private key key for any $pk_i$ can decrypt the respective tuple and get $k$ and decrypt the ciphertext stored at position $0$

• Yeah, I know this method. But if we have $2^{32}$ users in total and I want to send a message $m$ to $2^{16}$ of them. The length of the prefix may be too long. – Felix LL Sep 6 '18 at 12:12