"Shifting" a dual-Regev keypair away from a trapdoored instance

Question

This question pertains to identity-based key encapsulation mechanisms (IB-KEMs). To recap the functionality:

• $\mathsf{KeyGen}(1^\lambda) \to (\mathsf{msk}, \mathsf{mpk})$ Generates the master keypair
• $\mathsf{Extract}(\mathsf{mpk}, \mathsf{msk}, \mathsf{id}) \to \mathsf{usk}$ Constructs an identity-bound private key $\mathsf{usk}$ that can be used for decapsulation.
• $\mathsf{Encap}(\mathsf{mpk}, \mathsf{id}) \to (\mathsf{ss}, \mathsf{ct})$ Creates a shared secret $\mathsf{ss}$ and encrypts it to the recipient denoted by $\mathsf{id}$.
• $\mathsf{Decap}(\mathsf{mpk}, \mathsf{usk}, \mathsf{ct}) \to \mathsf{ss}$ Decrypts the ciphertext and returns the shared secret.

I'd like to construct an IB-KEM with a particularly strong anonymity property (anonymity is the wrong word, but that's what we'll use). We want that the output $\mathsf{ct}$ of $\mathsf{Encap}$ should be indistinguishable from randomness even to an observer with knowledge of $\mathsf{msk}$. This is harder than it seems.

Initial attempt: First, we can describe an IB-KEM from LWE with a slightly weaker notion of anonymity, one where $\mathsf{ct}$ is indistinguishable from randomness to an observer with knowledge of $\mathsf{usk}$ (but not $\mathsf{msk}$). This is simple enough, using any lattice trapdoor mechanism (e.g., GPV08 or MP12). Let's ignore the fact that the following construction doesn't have perfect correctness, i.e., the sender's $\mathsf{ss}$ and the receiver's $\mathsf{ss}$ are not quite the same. For my case, this is OK.

• $\mathsf{KeyGen}(1^\lambda)$ Returns $\mathsf{TrapGen}(1^\lambda)$. That is $\mathsf{mpk}$ is some parity-check matrix $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$, and $\mathsf{msk}$ is some trapdoor information on $\mathbf{A}$ (this allows someone with $\mathsf{msk}$ to find short preimages to the function $\mathbf{z} \mapsto \mathbf{Az}$).
• $\mathsf{Extract}(\mathsf{mpk}, \mathsf{msk}, \mathsf{id})$ Returns $\mathsf{SamplePre}(\mathsf{mpk}, \mathsf{msk}, \mathbf{u})$ where $\mathbf{u} = H(\mathsf{id}) \in \mathbb{Z}_q^n$ the hash of the ID. Concretely, this produces some short $\mathbf{e} \in \mathbb{Z}_q^m$ such that $\mathbf{A}\mathbf{e} = \mathbf{u}$
• $\mathsf{Encap}(\mathsf{mpk}, \mathsf{id})$ Generates a uniform $\mathsf{ss} \in \mathbb{Z}_q$ and lets $\mathsf{ct} = (\mathbf{c}_1 = \mathbf{A}^T\mathbf{s} + \mathbf{x}, c_2 = \mathbf{u}^T\mathbf{s} + \mathsf{ss})$ where $\mathbf{u} = H(\mathsf{id})$ and $\mathbf{s} \in \mathbb{Z}_q^n$ and $\mathbf{x} \in \mathbb{Z}_q^m$ are Gaussian iid with sufficiently small stddev.
• $\mathsf{Decap}(\mathsf{mpk}, \mathsf{usk}, \mathsf{id})$ Returns $c_2 - \mathbf{e}^T\mathbf{c}_1$

Notice that $\mathsf{Encap}$ is almost the dual-Regev encryption scheme, except it doesn't do any cleartext-to-plaintext encoding. By avoiding the encoding, $c_2$ is perfectly uniform. Also $\mathbf{c}_1$ is indistinguishable from uniform under the LWE assumption wrt $\mathsf{mpk} = \mathbf{A}$. Thus the above scheme achieves our weak notion of anonymity.

Problem: A adversary with knowledge of $(\mathsf{mpk},\mathsf{msk})$ can very easily distinguish $\mathbf{c}_1$ from uniform randomness, using the LWE inversion algorithm described in MP12 section 5.3. This means the above scheme fails our stronger notion of anonymity. The trouble arises from the fact that we're using a trapdoored lattice for encryption in the $\mathsf{Encap}$ procedure.

Question: Is there a way to keep the equation $\mathbf{A}\mathbf{e} = \mathbf{u}$, but "shift" it to a non-trapdoored lattice in a publicly computable way? Specifically, is there a set of public maps (known to everyone) $\mathbf{A} \mapsto \mathbf{A}'$, $\mathbf{u} \mapsto \mathbf{u}'$ and a private map (known to the owner of $\mathsf{usk}$) $\mathbf{e} \mapsto \mathbf{e}'$ such that

1. $\mathbf{A}\mathbf{e} = \mathbf{u} \implies \mathbf{A}'\mathbf{e}' = \mathbf{u}'$,
2. $\mathbf{e}$ is short $\implies$ $\mathbf{e}'$ is short, and
3. a trapdoor for $\mathbf{A}$ cannot be used to build a trapdoor for $\mathbf{A}'$.

I suspect that #3 will require, at the very least, that the $\mathbf{u} \mapsto \mathbf{u}'$ map be unpredictable in some sense. If it were easily invertible, for example, then you could use the trapdoor on $\mathbf{A}$ to find a short $\mathbf{e}'$ for any $\mathbf{u}'$. That is, you'd immediately get a trapdoor for $\mathbf{A}'$.

---

What doesn't work: I tried a few angles:

• Multiplying by a random matrix - An immediate thought would be to simply pick a uniform, non-right-invertible matrix $\mathbf{M}$ and let $\mathbf{A}' = \mathbf{M}\mathbf{A}$. This lets the decapsulator keep $\mathbf{e}' = \mathbf{e}$ so the encapsulator can easily compute $\mathbf{u}' = \mathbf{M}\mathbf{u}$. This looks like it could be an entirely fresh LWE instance, but it's actually exactly the same as before. Observe what happens when you encapsulate: $$(\mathbf{c}_1, c_2) = ((\mathbf{A}')^T\mathbf{s} + \mathbf{x}, (\mathbf{u}')^T\mathbf{s} + \mathsf{ss}) = (\mathbf{A}^T(\mathbf{M}^T\mathbf{s}) + \mathbf{x}, \mathbf{u}^T(\mathbf{M}^T\mathbf{s}) + \mathsf{ss}).$$ This is an encryption wrt instance $\mathbf{A}$ and pubkey $\mathbf{u}$, and the only thing different is that the sender secret is $\mathbf{M}^T \mathbf{s}$ rather than $\mathbf{s}$! Since the instance didn't change (and the LWE inverter works for any distribution of $\mathbf{s}$), this fails the strong anonymity property just as badly as the original construction.
• Trapdoor puncturing - MP12 describes a puncturing procedure, i.e., a public function $\mathbf{A} \mapsto \mathbf{A}'$ such that $\mathbf{A}'$ is no longer trapdoored. We can't use this directly because there's no obvious public map $\mathbf{u} \mapsto \mathbf{u}'$. More specifically (using notation from the paper), we map $\mathbf{A} = [\bar{\mathbf{A}} \mid \mathbf{G} - \bar{\mathbf{A}}\mathbf{R}]$ to $\mathbf{A}' = [\bar{\mathbf{A}} \mid -\bar{\mathbf{A}}\mathbf{R}]$, where $\bar{\mathbf{A}}$ is uniform, $\mathbf{G}$ is a gadget matrix and $\mathbf{R}$ is the trapdoor info. If we let $\mathbf{e}' = \mathbf{e}$, then $\mathbf{u}' = \mathbf{A}'\mathbf{e}' = \mathbf{u} - [0 \mid -\mathbf{G}]\mathbf{e}$. Someone without knowledge of $\mathbf{e}$ will be unable to compute the RHS of this expression, so this doesn't work.
• Updatable public-key encryption - This seems relevant, but it's kind of the opposite of what we want here. There are updatable encryption schemes on top of dual-Regev, but they are concerned with updating the secret $\mathbf{e}$ while leaving the instance $\mathbf{A}$ unchanged.
• Dimension/modulus reduction - You could try to truncate $\mathbf{A}$ until the trapdoor no longer works. but this has the same problem as the puncturing case: it's unclear how to update $\mathbf{u}$ without knowledge of $\mathbf{e}$. Similarly, you could modulus-switch everything to a new modulus $q' \ll q$ where the trapdoor quality isn't so great. But I'm pretty sure this would imply that $\mathbf{e}'$ is no longer a sufficiently short vector for decryption.

What kinda works: I have a solution that adds few extra rounds of communication to the protocol, and lets the encapsulator use $\mathbf{A}' = \mathbf{A} + \mathbf{B}$ and $\mathbf{u}' = \mathbf{u} + \mathbf{Be}$ for encryption, where $\mathbf{B}$ is a random matrix. This requires the decapsulator to send their pubkey $\mathbf{v} = \mathbf{Be}$ (and a proof of knowledge of $\mathbf{e}$). Adding rounds is possible, but really not ideal in my case, so I'd like to know if a noninteractive solution is out there.

I'm pretty stuck here, so any intuition would be much appreciated!

Answer 1

To clarify a bit: "We want that the output ct of Encap should be indistinguishable from randomness even to an observer with knowledge of msk" seems a bit too strong, since if we know msk, we can distinguish that the output ct was not encapsulated to a specific id by generating usk and playing the role of the user trying to decapsulate. Your goal is something where there is enough entropy in id that it's infeasible to guess a user's id?

A few ideas:

1. Why not take simple approaches like encrypting ct with a symmetric cipher and a key derived from id? Once someone knows id, they can easily decrypt it, but otherwise it should look random.

2. If you want to keep the lattice structure somewhat, you could hash id to a random vector v and set c$_1$ to v+A$^T$s+x.

3. If you really want to keep the LWe structure, you could use your random matrix idea but multiply on the right. That is, hash id to a matrix U with small, sparse entries and set $\mathbf{A}'=\mathbf{A}\mathbf{U}^{-1}$. Then encapsulate as normal, to get $\mathbf{c}_1 = \mathbf{A}'^T\mathbf{s}+\mathbf{x}$. I think this is no longer trapdoored. To decapsulate, the user with id will find $\mathbf{U}$ and compute $\mathbf{U}^T\mathbf{c}_1 = \mathbf{A}^T\mathbf{s}+\mathbf{U}\mathbf{x}$. If $\mathbf{U}$ is sparse and small, then $\mathbf{U}\mathbf{x}$ should still be a small Gaussian error and the resulting ciphertext can be decapsulated with the trapdoor.

It should be easy to prove that 1 is secure if you assume enough entropy in id (which you need to anyway?), and similarly for 2. I don't know how to prove that 3 is secure; ideally $\mathbf{U}^{-1}$ should be large and random, which is probably true but I don't know how to show this.