A processor of an aspect includes a decode unit to decode a keyed-hash message authentication code instruction. The keyed-hash message authentication code instruction is to indicate a message, to indicate at least one value that is to represent at least one of key information and key indication information, and to indicate a destination storage location. An execution unit is coupled with the decode unit. The execution unit, in response to the keyed-hash message authentication code instruction, is to store a message authentication code corresponding to the message in the destination storage location. The message authentication code is to be consistent with a keyed-hash message authentication code algorithm that is to use a cryptographic hash algorithm. The message authentication code is to be based on a cryptographic key associated with the at least one value. Other processors, methods, systems, and instructions are disclosed.