A method of establishing the integrity of an audit record set is described. The method comprises receiving a set of audit records and generating a first set of random values wherein each audit record in the set corresponds to at least one value of the first set. The method further comprises generating a second set of values based on an audit record and a corresponding value of the first set for each audit record in the set and generating a summary value based on the second set of values. The method further comprises certifying the summary value to generate an integrity certificate enabling verification of the integrity of the audit record set and storing the audit record set and at least one of the first set of values and the generated digital signature.