It's the ePrivacy Directive (and not the GDPR) that prohibits storing any data on the user's machines unless they are a) strictly necessary to provide the service, or b) the user consents.
Thanks for the correction. But the point still stands. This isn't about cookies per se, but about not extracting value from a user beyond what the service needs when users do not consent.