In medical cloud computing, a patient can remotely outsource her medical data to the cloud server. In this case, only authorized doctors are allowed to access the data since the medical data is highly sensitive. Encrypting the data before outsourcing is a commonly used approach, where the patient only needs to send the corresponding encryption key to the authorized doctors. This, however, significantly limits the usability of outsourced medical data due to the difficulty of searching over the encrypted data. This project, we propose two Secure and Efficient Dynamic Searchable Symmetric Encryption (SEDSSE) schemes over medical cloud data. Firstly, we leverage the secure k-Nearest Neighbor (kNN) and Attribute Based Encryption (ABE) techniques to propose a dynamic searchable symmetric encryption scheme, which can achieve two important security features, i.e., forward privacy and backward privacy which are very challenging in the area of dynamic searchable symmetric encryption. Then, we propose an enhanced scheme to solve the key sharing problem which widely exists in the kNN based searchable encryption scheme. Compared with existing proposals, our schemes are better in terms of storage, search and updating complexity. Extensive experiments demonstrate the efficiency of our schemes on storage overhead, index building, trapdoor generating and query.