Abstract The security and utilization of cloud storage are well-known open issues. Public key encryption with keyword search (PEKS) provides an important primitive to discuss applications in the field of cloud storage, where the receiver can use the trapdoor of the keyword to search. However, the internal attack derived by the cloud server is an inherent issue of PEKS. There are two breakthroughs, so-called authenticated PEKS (APKES) and witness-based searchable encryption (WBSE), to tackle this issue by modifying framework of PEKS. The existing schemes of APEKS and WBSE can offer security against the internal attacks, but they require the trapdoor size is proportional to c n where n is the total number of senders, and c is the constant size of the ciphertext or proportion to the security parameter. In this paper, we propose a new WBSE scheme with constant overhead as long as n is bounded. We analyze the security of our scheme based on homomorphic encryption and digital signature. Finally, we provide implementations to show the effectiveness on the cloud-edge model.