Updating cryptographic keys stored in non-volatile memory

Apparatus, comprising:

• a non-volatile memory (NVM), comprising a plurality of single-bit cells, configured to store an N-bit cryptographic key, unprogrammed ones of the cells having a particular binary value;
• and
• a processor, configured to:
• generate a random N-bit updating sequence in which each bit is generated with a probability of having the particular binary value that is greater than 0.5,
• generate a new instance of the N-bit cryptographic key by performing an operation that, for any value of a current instance of the N-bit cryptographic key and any value of the random N-bit updating sequence, negates each bit in a current instance of the N-bit cryptographic key that has the particular binary value and differs from a correspondingly-positioned bit in the random N-bit updating sequence but does not negate any bits in the current instance of the N-bit cryptographic key that do not have the particular binary value, and
• subsequently to generating the new instance of the N-bit cryptographic key, replace the current instance of the N-bit cryptographic key with the new instance of the N-bit cryptographic key in the NVM.

A method, comprising:

• calculating different respective probabilities {qi}, i=1 . . . U, each of the probabilities being greater than 0.5, for multiple updates of an N-bit cryptographic key stored in a non-volatile memory (NVM) in which unprogrammed cells have a particular binary value such that, for each ith one of the updates, an expected entropy of a new instance of the N-bit cryptographic key with respect to a current instance of the N-bit cryptographic key is not less than a predefined threshold entropy E that is less than N, provided that:
• the new instance of the N-bit cryptographic key is generated by performing an operation that, for any value of the current instance of the N-bit cryptographic key and any value of a random N-bit updating sequence, negates each bit in the current instance of the N-bit cryptographic key that has the particular binary value and differs from a correspondingly-positioned bit in the N-bit random updating sequence but does not negate any bits in the current instance of the N-bit cryptographic key that do not have the particular binary value, and
• each bit in the N-bit random updating sequence is generated with probability qi of having the particular binary value;
• and
• subsequently to calculating the probabilities, providing the probabilities for use in performing the updates.