With rapid developments of sensor, wireless and mobile communication technologies, Mobile Healthcare Social Networks (MHSNs) have emerged as a popular means of communication in healthcare services. Within MHSNs, patients can use their mobile devices to securely share their experiences, broaden their understanding of the illness or symptoms, form a supportive network, and transmit information (e.g. state of health and new symptoms) between users and other stake holders (e.g. medical center). Despite the benefits afforded by MHSNs, there are underlying security and privacy issues (e.g. due to the transmission of messages via a wireless channel). The handshake scheme is an important cryptographic mechanism, which can provide secure communication in MHSNs (e.g. anonymity and mutual authentication between users, such as patients). In this paper, we present a new framework for the handshake scheme in MHSNs, which is based on hierarchical identity-based cryptography. We then construct an efficient Cross-Domain HandShake (CDHS) scheme that allows symptoms-matching within MHSNs. For example, using the proposed CDHS scheme, two patients registered with different healthcare centers can achieve mutual authentication and generate a session key for future secure communications. We then prove the security of the scheme, and a comparative summary demonstrates that the proposed CDHS scheme requires fewer computation and lower communication costs. We also implement the proposed CDHS scheme and three related schemes in a proof of concept Android app to demonstrate utility of the scheme. Findings from the evaluations demonstrate that the proposed CDHS scheme achieves a reduction of 18.14% and 5.41% in computation cost and communication cost, in comparison to three other related handshake schemes. © 2016 IEEE.