In medical cloud computing, a patient can send her medical data to a cloud server from afar. Because medical data is highly sensitive, only authorized doctors are allowed to access it in this case. A frequent solution is to encrypt data before outsourcing it, with the patient simply sending the corresponding encryption key to the authorized doctors. However, due to the difficulties of digging through the encrypted data, the usability of outsourced medical data is severely limited. Over medical cloud data, we propose Secure and Efficient Dynamic Searchable Symmetric Encryption (SEDSSE) schemes. To begin, we propose a dynamic searchable symmetric encryption scheme that uses the secure k-Nearest Neighbor (kNN) and Attribute-Based Encryption (ABE) techniques to achieve two important security features: forward privacy and backward privacy, both of which are difficult to achieve in the field of dynamic searchable symmetric encryption. Then, to address the key sharing problem that plagues the kNN-based searchable encryption strategy, we suggest an improved technique. In terms of storage, search, and update complexity, our solutions outperform prior proposals. Extensive tests show that our approaches are efficient in terms of storage overhead, index building, trapdoor generation, and query.