Shorter Post-quantum Secret Handshakes from Isogenies
Chao Chen, Zhiyuan An, Fangguo Zhang · 2023
Secret handshake schemes allow members from the same organization to authenticate each other anonymously. After its proposal, various schemes have been introduced to achieve advanced privacy protection. Regrettably, all the schemes based on number theoretic assumptions are insecure under quantum computers, and the known post-quantum designs are impractical because of the overhead cost ($\gg$ 100 MB). To fill the gap, we present the first isogeny-based secret handshake scheme with a friendly communication cost (132 KB). In particular, we apply the CSI-FiSh signature scheme to generate group keys and credentials. For each zero-knowledge transcript in the credential, we modify the CSI-FiSh signature by embedding the CSIDH ephemeral private key into the challenge space. After verifying the signature, two users recover the right ephemeral private key if they are in the same group, then they can authenticate each other and negotiate a session key. The security of our scheme relies on the multi-target group action inverse problems.