Replication reduces the security of data in a distributed environment. In this paper, we address the issue of maintaining security in a fault-tolerant replicated database. We present a protocol that combines both security and reliability aspects in a database system. Although this protocol provides the desired level of security, it does so at the expense of availability. By integrating a propagation mechanism with our protocol, we are able to achieve a high level of security and availability.