Information security plays an important role in every aspect of life to protect data from stealing and deciphering. However, most of the previously reported works were based on pure algorithm layer or pure physical layer encryptions, which have certain limitations in security. In this paper, a nondeterministic message encryption communication scheme is proposed based on a spin-space-frequency multiplexing metasurface (SSFMM), which integrates both algorithmic and physical layer encryptions, and can also produce multiple different ciphertexts for the same message to prevent the message from being cracked through frequency analysis, thus greatly enhancing the security of the information. To be specific, an SSFMM is first designed as a physical-layer meta-key, which can generate eight independent dot matrix holograms with different spin, space, and frequency characteristics. The target message is then encrypted based on these dot matrix holograms combined with algorithmic operations, and the encrypted message is converted into a quick response (QR) code for easy sending to the target users. Once the target user gets that QR code, he/she can scan it to obtain the encryption information, and then recover the target message according to the pre-agreed encryption protocol combined with the eight dot matrix holograms of SSFMM. Finally, the feasibility of the proposed encryption scheme was experimentally validated at the microwave frequency band.