Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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. – mikeazo Apr 11 '13 at 18:59
up vote 1 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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