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!


1 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.

  • $\begingroup$ Thank you for this response. Clarifying: "We want that the output ct of Encap should be indistinguishable from randomness even to an observer with knowledge of msk" I really do need this property. Specifically: if a challenger generates msk₀ and msk₁, flips a coin b, and makes a ciphertext ct using msk_b; then an efficient adversary given (ct, msk₀, msk₁)` has negl advantage at guessing b. This is related to ambiguity (see here Definition 6). Btw the interactive scheme I allude to is in my paper now. $\endgroup$
    – rozbb
    Mar 16 at 4:26
  • $\begingroup$ Regarding secret user IDs: this is a neat idea. It does require id to be high-entropy, which makes it more like a key agreement protocol with preshared secrets. It doesn't fit my use case exactly, but regardless I wonder if something like this has been done before. $\endgroup$
    – rozbb
    Mar 16 at 4:27
  • $\begingroup$ Thanks for the link, the paper seems to make the problem more clear. The game you define in Figure 3 seems only possible with a KEM, since the adversary has decapsulation keys $\mathbf{usk}_i$ for both parties, so the adversary should be able to decapsulate the true ciphertext. The decapsulated key must be random, then. But in an implementation, wouldn't the decapsulated key access to non-random things? As in, the adversary can try to decrypt some communication, and if it worked, they know whose key they have? $\endgroup$
    – Sam Jaques
    Mar 16 at 11:19
  • 1
    $\begingroup$ Yes, ordinarily this would be the case. This is why the resulting key can only be used as the password input to a PAKE. One of the properties of a PAKE is that it does not reveal the pw to passive observers, even ones that might be able to efficiently make guesses. Also, the usk-uniform ambiguity is only a subset of the property necessary. In the paper, I describe a stronger form of ambiguity, called keygen coin independence, that also accounts for knowledge of msk. $\endgroup$
    – rozbb
    Mar 17 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.