Secret Handshake: Strong Anonymity Definition and Construction

Secret handshake allows two members in the same group to authenticate each other secretly. In previous works of secret handshake schemes, two types of anonymities against the group authority (GA) of a group

G

are discussed: 1)

Even

GA cannot identify members, namely nobody can identify them (No-Traceability), 2)

Only

GA can identify members (Traceability). In this paper, first the necessity of tracing of the identification is shown. Second, we classify abilities of GA into the ability of identifying players and that of issuing the certificate to members. We introduce two anonymities

Co-Traceability

and

Strong Detector Resistance

. When a more strict anonymity is required ever for GA, the case 2) is unfavorable for members. Then, we introduce

Co-Traceability

where even if

${\cal A}$

has GA’s ability of identifying members or issuing the certificate,

${\cal A}$

cannot trace members identification. However, if a scheme satisfies Co-Traceability, GA may be able to judge whether handshake players belong to the own group. Then, we introduce

Strong Detector Resistance

where even if an adversary

${\cal A}$

has GA’s ability of identifying members,

${\cal A}$

cannot make judgments whether a handshaking player belongs to

G

. Additionally, we propose a secret handshake scheme which satisfies previous security requirements and our proposed anonymity requirements by using group signature scheme with message recovery.