Abstract: Aiming at the computational efficiency of outsourcing database and the completeness of query results, we propose a publicly verifiable database model with efficient updates and low storage overhead. Its description and security model are formalized, besides, a specific publicly verifiable database scheme with efficient updates and low storage overhead using the prime order bilinear groups is also proposed. Our scheme allows a resource-constrained client to securely outsource a very large database to a professional database service provider so that it could later retrieve or update a database record and verify the integrity of the retrieved data. The security of our scheme can be reduced to the hardness of the Square-CDH problem. Compared with the existing schemes, our scheme improves the computational efficiency by using the prime order bilinear groups. We construct the constant size parameter which is independent of the database that reduces the storage overhead of the client. In the meanwhile, the verification phase in the scheme does not require the data owner’s private key so it can be publicly verifiable. In addition, our scheme not only supports the modification of data, but also supports the insertion and deletion on data. The performance analysis shows that the cost of query, verification and update is independent of the database size.