A method and apparatus for authenticating a message, said method including receiving, at a device, data representative of a first share, constructing a key using said first share and at least two additional shares, said at least two additional shares being stored at said device; and authenticating a message using said constructed key.