I am not understanding the following from "Lattice Cryptography for the Internet" by C. Peikert (pages 9):

We remark that a work of Ding et al. DXL14 proposes a different reconciliation method for lower bandwidth "approximate agreement," in the context of a key exchange against a passive adversary. However, we observe that the agreed-upon bit produced by their protocol is necessarily biased, not uniform, so it should not be used directly as a secret key (and the protocol as described does not satisfy the standard definition of passive security for key exchange).

I don't understand the biased part and how it is related to passive security for key exchange. Maybe I just don't understand the definition of passive security for key exchange. I don't know. Any help would be appreciated.


1 Answer 1


The usual definition of (passive) security for key exchange requires the agreed-upon key to be indistinguishable from uniformly random. That's not the case for DXL14 because the bits of the key are biased, not uniform. You can check that yourself if you implement the DXL 14 algorithm in (for example) SageMath. It shows that bits are biased and not uniform.

Now, you may wonder: is it because it uses Polynomial instead of Vector of polynomials, because of limited domain of $\mathit{Sig}$ function (i.e. $E= {-\lfloor {\frac {q}{4}}\rfloor ,...,\lfloor {\frac {q}{4}}\rceil \}}$), or if there’s some other reason?

Well, it's simply because any deterministic map from $\mathbb{Z}_q$ to 0,1 must be biased when $q$ is odd.

  • $\begingroup$ In the paper they defined two signal function which is for avoiding bias. Early versions of the paper indeed generate biased keys. $\endgroup$
    – 9f241e21
    Dec 18, 2017 at 5:22

Your Answer

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

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