Code-Based Secret Handshake Scheme, Revisited

Secret handshake (SH) allows two users to authenticate each other anonymously only when they are in the same group. Recently, due to the concern of developments on large-scale quantum computers, designing post-quantum SH has been investigated and three constructions were proposed: One is code-based [21] and two others are lattice-based [1, 2]. However, it turns out that the code-based construction [21] has a security flaw that the adversary easily impersonates an honest user to activate a handshake. In this paper, we show how to construct a code-based SH scheme in the framework of CA-oblivious encryption by utilizing the recently proposed code-based signature scheme, called LESS-FM, whose security is based on the hardness of the code equivalence problem. Our proposed scheme is the first secure code-based SH and has the smallest communication cost among all known post-quantum SH schemes. For example, for 80-bit security, our scheme has communication costs of about 260 KB and 3.4 KB when instantiated with Classic McEliece and BIKE, respectively, while other existing post-quantum constructions have communication costs of megabytes or gigabytes.