Searchable　Encryption　(SE)　is　a　popular　cryptographic　primitive　for　building　ciphertexts　retrieval　systems　with　far-reaching　applications.　However,　existing　SE　schemes　generally　do　not　support　threshold　access　control　(i.e.,　data　users　must　collaboratively　issue　search　and　decryption　operations　over　encrypted　cloud　data)　in　a　group-oriented　cloud　data　sharing　setting,　which　is　increasingly　receiving　much　attention　in　the　research　community.　Thus,　in　this　article,　we　first　propose　a　Threshold　Multi-keyword　Search　(TMS)　scheme　for　cloud-based　group　data　sharing　(referred　to　as　basic　TMS　scheme)　by　utilizing　Shamir＇s　secret　sharing　technique,　to　achieve　threshold　multi-keyword　search,　threshold　decryption,　and　short　record　ciphertext　size.　Then,　we　extend　this　basic　TMS　to　realize　threshold　result　verification　and　threshold　traceability　(referred　to　as　enhanced　TMS).　Furthermore,　the　enhanced　TMS　is　extended　to　support　public　result　verification　and　dynamic　operations　with　the　public　verifier　and　improved　hash　tables,　respectively.　Our　formal　security　analysis　proves　that　both　basic　TMS　and　enhanced　TMS　are　semi-adaptively　secure　and　can　resist　Chosen-Keyword　Attack　(CKA).　Our　theoretical　evaluation　and　empirical　experiments　demonstrate　the　potential　utility　of　both　schemes.　©　2013　IEEE.