2
$\begingroup$

I have one problem about cryptography which I don't if someone already solved it. I want one device (master) to receive one encrypted package from each one of the other $n$ devices (normal) and I want the master to be able to decrypt each package without being able to identify from which device it came, knowing that the master knows from which device he received the encrypted package.

Is it possible to do this if the encrypted packages were not shuffled betewen the $n$ normal devices, like some kind of group decryption in which the information is preserved but the order is randomized, so that the device of origin is untraceable? Can it be achived without comunication betwen the normal devices?

Also I couldn't find any tags besides encryption that were appropriate to the question, could anyone help me choose another tag?

$\endgroup$
  • $\begingroup$ Is it ok for the normal devices to be able to read each other's packets? $\endgroup$ – SEJPM May 2 at 17:46
  • 1
    $\begingroup$ @SEJPM: or have one device forward the packet to a random device, which would forward the packet to the master? $\endgroup$ – poncho May 2 at 17:50
  • $\begingroup$ I think I understand your solution, I wanted a solution which wouldn't not require the package to be shared betwen the devices. Do you think a solution with these conditions is possible? $\endgroup$ – chris May 2 at 19:47
2
$\begingroup$

This is at least feasible if you allow a one-time setup where related keys are distributed among the $n$ devices and the master device. There is a primitive known as aggregated encryption which has the following properties:

  • The $n$ devices $(D_0, \cdots, D_{n-1})$ each receive a secret key $(s_0, \cdots, s_{n-1})$.
  • The master device receives an "aggregated secret key"; concretely, this will in general be $s = \sum_i s_i$.
  • Each device $D_i$ can encrypt some message $m_i$ with the key $s_i$.
  • Given $n$ encrypted messages $(E_0,\cdots, E_{n-1}) = (E_{s_0}(m_0), \cdots, E_{s_{n-1}}(m_{n-1}))$ and the aggregated secret key $s$, the master device can decrypt $\sum_i s_i$, and cannot learn anything more.

This is relatively easy to build using cryptosystem with appropriate homomorphic properties. The article I link to builds it from the ElGamal cryptosystem, however there also exists constructions from the Paillier cryptosystem, which will be more suited to your problem.

Now, given such a primitive, there is a natural way to ensure that the master device can learn all messages, but without knowing from which device they come: in the one-time setup phase, also give to each device $D_i$ his secret index $j = \pi^{-1}(i)$ ($\pi$ is a uniformly random permutation of $\{0, \cdots, n-1\}$, $\pi^{-1}$ is the reverse permutation, $\pi^{-1}(i)$ will be the "pseudonymous index" of the device $D_i$). Let $\ell$ be a bound on the size (in bit) of each message $m_i$ (I assume $\ell$ to be publicly known) Then, to send $n$ message while concealing the identity of the device each message came from, each device $D_i$ with message $m_i$ computes and sends:

$E_i = E_{s_i}(2^{\ell\cdot\pi^{-1}(i)}\cdot m_i)$

Given $(E_0, \cdots, E_{n-1})$ and his aggregated key $s$, the master device can only recover

$M = \sum_{i=0}^{n-1} 2^{\ell\cdot\pi^{-1}(i)}\cdot m_i = \sum_{j=0}^{n-1} 2^{\ell \cdot j}\cdot m_{\pi(j)}$

Which is exactly the value $m_{\pi(0)} || m_{\pi(1)} || \cdots || m_{\pi(n-1)}$ (when padding each message $m_i$ with zeroes such that it is exactly $\ell$ bit long), id est, all the messages of the devices in some fixed secret permuted order.

Note that an ElGamal-based scheme would not work here since you need your aggregated scheme to support a very large message space, but the Joye-Libert scheme has no restriction on the message space, and should work fine here.

$\endgroup$
  • $\begingroup$ Wow, such an awesome answer! I will defnetely read those papers. Thank you!!! $\endgroup$ – chris May 4 at 4:40
0
$\begingroup$

This appears to be a public key cryptography problem. Have the master generate a public/private key pair. $n$ devices encrypt their message under master's public key and the master can decrypt with its private key. Unless there is explicit information in the encrypted message about which device the encrypted message came from this should solve your problem. This does not require communication between the normal devices but just a broadcast of the public key by the master to the normal devices.

$\endgroup$
  • $\begingroup$ I didn't explain it well. The master knows from which device the encrypted message came from $\endgroup$ – chris May 2 at 16:55
  • 1
    $\begingroup$ In this case you may want to look at mixnets or similar techniques that encrypt, shuffle and forward $\endgroup$ – Natanael May 2 at 17:12

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.