Techniques for key ratcheting with multiple step sizes are described. For example, an apparatus may be configured to receive two or more encrypted messages, where the encrypted messages are encrypted according to a multi-dimensional ratcheting encryption scheme. Moreover, the apparatus may be configured to determine which of the encrypted messages was most-recently received and extract a message iteration count from the most-recent encrypted message, generate a decrypted message by decrypting the encrypted message based on a decryption key, decompose the message iteration count into a plurality of message chain key iteration counts, and determine the decryption key based on the plurality of message chain key iteration counts.