You might take a look here [1], using asymmetric crypto. We are still developing it but that is our approach. Yes, there is some overhead but you will need it anyway.

The doc is a bit outdated but the prototypes work.

[1] http://www.thesibyl.net