I am implementing an anonymous credential system following Lysyanskaya, 2002, specifically much of chapter 3. We assume that the user (not anonymous) U has a user public key PK^(U) (I will try to do my best without LaTeX support here re: notation) and user private key, SK^(U.) When creating the pseudonym N, this user creates a key pair (PK^(N,) SK^(N),) but will not store these credentials. Upon pseudonym creation only, U will provide the pseudonym public key PK^N and the pseudonym private key SK^(N), but encrypted with their own public key PK^(U). That is, Encrypt(message: SK^(N), withKey: PK^(U)). Let's call this value EK^(N) for encrypted key since the notation will become quite unwieldy otherwise.
If I want to allow this user to authenticate as N, my thinking is the server (organization O in Lysyanskaya) stores the pseudonym N, the pseudonym public key PK^(N) and the encrypted pseudonym private key, EK^(N). This way if the user really is who they claim to be, then O can encrypt some random message m with the pseudonym public key, provide the user only with the encrypted message Encrypt(message: m, withKey: PK^(N)) and the encrypted private key EK^(N).
If the user is not U, all this info will be useless to them. If the user is U and thus has SK^(U), they can then return to O the original message m, and I will know that they have the private key SK^(U) and thus are authenticated as pseudonym N.
I would be storing the following tuples in the database (in two separate tables).
Users table: (U, PK^(U))
Pseudonyms table: (N, PK^(N,) EK^(N))
Is this safe to store in the database?
I don't plan on exactly broadcasting this value, but say if there was a data breach, would it still be safe and not risk de-anonymizing the user?
It’s worth adding that I have since asked this question to ChatGPT and it said that we must always assume that PK^(U) is public and even if someone could not *decrypt* EK^(N), that they could tell that PK^(U) was used to encrypt it if provided with PK^(U), thus de-anonymizing the user U. It suggested using a key derivation function instead to derive SK^(N). That is, the server would not even send EK^(N) and would only send the encrypted message E(message: m, withKey: PK^(N)).