At this work at section $2.2$ concerning a possible application for the BGN cryposystem the author points out that if you want to encrypt a unit vector $\overrightarrow{u_l}$ of size $l$ then the naive way is to encrypt each bit separately. And by following the idea of BGN the size of the ciphertext is reduced to $2\sqrt{l}$ from $l$. My question is why the naive way is to encrypt each bit seperately and not encrypt at once as a number in the specified group $\mathbb{G}$ as long as the value can let you efficiently compute the $DL$ as the discrete logarithm is needed for decryption as described at the original paper?

  • $\begingroup$ Perhaps there isn't a one-to-one mapping from every possible vector to field elements? I need to look at the math in more detail. $\endgroup$
    – mikeazo
    Apr 11, 2013 at 18:59

1 Answer 1


The answer can be found in the lecture notes you link to. You quoted from Section 2.2 of the lecture notes; if you read to the end of Section, you will find (on the very same page) the following statement:

This encryption of a unit vector has applications to “private information retrieval”; details are in the BGN paper [1, Section 4].

This suggests that you might want to read Section 4 of [1] (the paper that introduces the BGN cryptosystem). I suggest you particularly read Section 4.2, the part labelled "A SPIR scheme".

That part describes a scheme for private information retrieval. If you work through the details of the protocol, you will discover that it involves having Bob encrypt a number (the index of the database that he wants to read) using the scheme described in Section 2.2 of the lecture notes.

Encoding the number as an element of the group would be fine in many cases, but it would not work for that particular "private information retrieval" protocol. So, there's your reason. That should answer your question.


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.