A novel and efficient unlinkable secret handshakes scheme

An unlinkable secret handshakes is a two-party authentication protocol which protects the privacy of parties' affiliation and identity to everyone except for the intended parties. However, we find that the latest solution proposed by Jarecki et al. is not very efficient. In particular, each party requires O(log n) exponentiations where n is the number of parties affiliated with a single organization. In this paper, we propose a novel unlinkable secret handshakes protocol. Compared with Jarecki et al's scheme, our proposal is simple intuitionally and requires only constant exponentiations.