Basically it works like this: You encrypt the data with a long, symmetric key. This data key can be used to decrypt the data itself, which may be large, and thus expensive to re-crypt. Now you encrypt this data key with the user key, and store that encrypted decryption key in addition to the encrypted data. You can also create multiple copies the data key encrypted with different user keys to enable shared access to the encrypted document. This way, you can decommission individual user's access by dropping their copy of the key, and efficiently re-crypt the data key because you don't have to encrypt the full data, but only the key.

In scenarios where you don't have multiple users, you can also just prepend the encrypted data key to the payload (as in, `<encrypted data key>.<encrypted payload>`), so effectively you'll only have to store an encrypted blob and the user key.

Edit: The AWS docs explain this way better than I do: https://docs.aws.amazon.com/encryption-sdk/latest/developer-...