Security device and method of provenance verification

A method of provenance verification comprises providing a plurality of security devices, each security device being provided with a key set comprising: a secret key, and a plurality of shared keys, each shared key being derived by generating a hash of the secret key and a salt value that is specific to a pair consisting of said security device and another of the plurality of security devices. The method also comprises configuring each security device to: generate and/or receive one or more messages; and perform at least one cryptographic operation on the message or messages, and/or on data derived therefrom, using a respective secret key of the security device and/or one of said shared keys.