electricity_is_life's comment on reddit seems to explain it:

> Not sure if this is what happened to you, but one thing I ran into a while back is that even if you return Cache-Control: no-store it's still possible for a response to be reused by CloudFront. This is because of something called a "collapse hit" where two requests that occur at the same time and are identical (according to your cache key) get merged together into a single origin request. CloudFront isn't "storing" anything, but the effect is still that a user gets a copy of a response that was already returned to a different user.

> If your app authenticates based on cookies or some other header, and that header isn't part of the cache key, it's possible for one user to get a response intended for a different user. To fix it you have to make sure any headers that affect the server response are in the cache key, even if the server always returns no-store.

---

Though the AWS docs seem to imply that no-store is effective:

> If you want to prevent request collapsing for specific objects, you can set the minimum TTL for the cache behavior to 0 and configure the origin to send Cache-Control: private, Cache-Control: no-store, Cache-Control: no-cache, Cache-Control: max-age=0, or Cache-Control: s-maxage=0.

https://docs.aws.amazon.com/AmazonCloudFront/latest/Develope...