An apparatus and method for providing replay protection integrity protection of a database accessible by an electronic device is provided, wherein the database is capable of protecting a plurality of records. When at least one protected record in the database is modified in an authorized manner, a record tag corresponding to the at least one protected record is stored in the database, and the at least one protected record and the corresponding record tag are copied into a cache. Upon retrieval of the at least one protected record from the database, the copied record tag stored in the cache is compared with the corresponding record tag stored in the database. Use of the retrieved protected record is inhibited if the copied record tag stored in the cache does not correspond to the record tag stored in the database, and otherwise use of the retrieved protected record is enabled.