DNA similarity search has proven to be an essential demand in human genomic researches. Since DNA sequences contain many sensitive personal information, the acquisition and dissemination of DNA data have been tightly controlled and restricted by authorities. Although the problem of private DNA similarity query has been an active research issue, the latest research findings are still inadequate in terms of security, functionality and efficiency. In this paper, we propose an Efficient DNA Similarity Search scheme (EDSS) which can achieve fine-grained query and data access control over encrypted cloud data. Our original contributions are fourfold. First, we creatively put forward a private edit distance approximation algorithm to realize the efficient and high accurate DNA similarity query. Second, we classify the whole DNA sequences and design a multiple genes search strategy to achieve complicated logic query such as mixed “AND” and “NO” operations on genes. Third, the proposed scheme can also efficiently support data access control by employing a novel polynomial based design. Finally, security analysis and extensive experiments demonstrate the high security and efficiency of EDSS compared with existing schemes.