A method and system is provided for a tamper-proof storage of one or more records of an audit trail in a database. Since the integrity of the database records may be vulnerable to actions taken by a user such as a privileged database administrator, a mechanism is provided to efficiently detect any changes made by him to the database records. The method creates one or more authentication tokens, and generates one or more validation tokens from the authentication tokens through a combination of a hashing process and an encryption process. Once the validation tokens are created, they are further integrated into the records in the database. The authentication tokens are written to a secured information storage in a predetermined format by a writing machine inaccessible by the user but accessible by the auditor. When an authorized person such as an independent auditor who needs to check the integrity of the records, he can detect a tampering of the records by comparing a validation token computed from the stored validation token with the validation token integrated in the record.