To　ensure　the　security　of　outsourced　data　without　affecting　data　availability,　one　can　use　Symmetric　Searchable　Encryption　(SSE)　to　achieve　search　over　encrypted　data.　Considering　that　query　users　may　search　with　misspelled　words,　the　fuzzy　search　should　be　supported.　However,　conventional　privacy-preserving　fuzzy　multi-keyword　search　schemes　are　incapable　of　achieving　the　result　verification　and　adaptive　security.　To　solve　the　above　challenging　issues,　in　this　paper　we　propose　a　Verifiable　Fuzzy　multi-keyword　Search　scheme　with　Adaptive　security　(VFSA).　VFSA　first　employs　the　locality　sensitive　hashing　to　hash　the　misspelled　and　correct　keywords　to　the　same　positions,　then　designs　a　twin　Bloom　filter　for　each　document　to　store　and　mask　all　keywords　contained　in　the　document,　next　constructs　an　index　tree　based　on　the　graph-based　keyword　partition　algorithm　to　achieve　adaptive　sublinear　retrieval,　finally　combines　the　Merkle　hash　tree　structure　with　the　adapted　multiset　accumulator　to　check　the　correctness　and　completeness　of　search　results.　Our　formal　security　analysis　shows　that　VFSA　is　secure　under　the　IND-CKA2　model　and　achieves　query　authentication.　Our　empirical　experiments　using　the　real-world　dataset　demonstrate　the　practicality　of　VFSA.　©　1989-2012　IEEE.