5
$\begingroup$

I am trying to implement a mixnet using post-quantum public-key crypto. Each message may be encrypted by up to 10 levels of public keys, shuffled, before the layers of encryption are stripped off one by one.

This is traditionally achievable in RSA, because the ciphertext is barely larger than the plaintext, but in the many popular post-quantum public key cryptosystems (based on lattice crypto), such as NTRU, it appears the ciphertext becomes an order of magnitude larger than the plaintext. So encapsulating a message in multiple layers of encryption is infeasible as the ciphertext doesn't scale.

Are there post-quantum public key exchange schemes suitable for this purpose? I've looked at the Open quantum safe project, but am unsure whether any of protocols there mitigate this issue, or are mature enough.

Improve this question
$\endgroup$
1
  • $\begingroup$ Depending on what you mean by "or are mature enough", that may warrant its own question. That could easily become an entire discussion thread by itself! $\endgroup$ – Mike Ounsworth Jul 24 '17 at 16:43
3
$\begingroup$

Might I suggest using traditional hybrid cryptography to cut down on the ciphertext growth size? This is the straight-forward approach where you don't directly encrypt the message with the public key; instead, you pick a random symmetric (e.g. AES) key, encrypt the symmetric with the public key, and then AES encrypt the message with the symmetric key.

That way, the message expansion is the size of the encrypted symmetric key (which is fixed, independent of message size), and the message expansion caused by the AES encryption (which is tiny, perhaps 16 bytes).

If we estimate that an encrypted symmetric key is about 1kbyte (roughly true for NTRU), then iterating this 10 times with 10 public keys will cause a total expansion of about 10kbytes; certainly tolerable.

And, this can be done postquantum, by using a postquantum symmetric encryption (256 bit keys), and a postquantum public key encryption algorithm (that is, I haven't solved that problem for you...)

Improve this answer
$\endgroup$
2
  • $\begingroup$ A good suggestion, but it's not possible in the mixnet scheme I'd like to implement as untrusted participants share public keys in order to encrypt each other's messages. $\endgroup$ – J. Doe Jul 26 '17 at 7:46
  • $\begingroup$ @J.Doe: I don't understand; in my suggestion, someone can encrypt a message with someone else's public key, and only someone with the private key can decrypt it. Now, that untrusted party could select nonrandom symmetric keys to try to leak data in the ciphertext (e.g. tag which ciphertext is which), however that sort of thing can be done with any nondetermanistic encryption method; what specifically are you worried about? If you want us to suggest a mechanism, we need to know the constraints. $\endgroup$ – poncho Jul 26 '17 at 12:09
0
$\begingroup$

Adding an answer as it is a very interesting idea. In the context of latest innovations in post quantum cryptography implementations, we could construct mixnets using solutions such as newhope . Interestingly, there is a recent research publication in IACR on construction a verifiable and auditable mixnet using lattice cryptography.

Improve this answer
$\endgroup$

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.