A fuzzy vault encrypts a message using fuzzy data such as user’s biometric data as the vault key. Fuzzy vault can be used to protect users’ cryptographic keys in smart cards and inside applications. We consider fuzzy vault based on behavioral data. A behavioral profile of a user consists of a set of features that collectively authenticates the user. Compared to biometric vault behavioral vault has the advantages of being revocable and less privacy sensitive. Fuzzy vaults for behavioral data, however, introduces significant challenges including feature representation, and feature matching algorithms that can provide the required correctness, security, and efficiency. We design and analyze a fuzzy vault based on the user’s behavioral data that employs a novel soft-decision decoding algorithm and implement our design for two behavioral authentication (BA) systems. Our approach is general and can be used for other BA systems. We discuss our results and directions for future research.