Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

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

Imagine a tagging system whose security requirements imply to learn nothing from the tag about the encoded value.

We consider a plaintext space $X \in \mathbb{Z}_p$ and a group $\mathbb{G}$ where the DLP is computationally hard.

The sender sends $\sf{tag_1}=g^x_i$ where $g$ is a generator of $\mathbb{G}$. This is not really secure in the sense that we provide the attacker an oracle to verify its guess on values in $X$.

We change the tag to be of the form $\sf{tag_2}=g^{x_i+r_i}$ where $r_i$ is a random value from $\mathbb{Z}_p$

We consider another tagging scheme where $\sf{tag_3}=g^{a_ix_i+r_i}$ where $a_i, r_i$ are random values from $\mathbb{Z}_p$

Is $\sf{tag_3}$ more secure than $\sf{tag_2}$? Is there an attack in $\sf{tag_2}$ which is mitigated with $\sf{tag_3}$?

share|improve this question

closed as unclear what you're asking by D.W., tylo, e-sushi, CodesInChaos, rath May 25 '14 at 10:41

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

if $r_i$ is secret, how is $\sf{tag_2}$ used? If it is public, does not it have the same problem as $\sf{tag_1}$? – fgrieu May 21 '14 at 13:36
Nice question. $r_i$ is 'partially' secret. It is used to verify aggregate results. $g^{\sum{r_i}}$ is revealed – curious May 21 '14 at 13:38
What prevents an adversary from adding $1$ to $x_i$ and multiplying $\sf{tag_1}$ or $\sf{tag_2}$ by $g$? Or, for the system of $\sf{tag_2}$, adding $1$ to $x_0$ and $r_1$, and subtracting $1$ from $x_1$ and $r_0$, leaving $g^{x_0+r_0}$, $g^{x_1+r_1}$, and $g^{\sum{r_i}}$ unchanged? – fgrieu May 21 '14 at 13:49
The adversary doesn't know $x_i$ – curious May 21 '14 at 14:08
Why are you trying to invent some new mechanism? Why aren't you using standard "semantically secure" public-key encryption? (You can use additively homomorphic public-key encryption, if that's what you need.) Also, I agree with the comments that the requirements don't seem clear. Finally: please edit the question to include all relevant information in the question itself. Don't just drop them in the comment thread. Comments exist only to help you improve the question, and the question needs to stand on its own (without having to read the comments). – D.W. May 22 '14 at 22:37
up vote 2 down vote accepted

It is not entirely clear what your exact security requirements are and for which purpose you require this construction. I assume that the tags can not be manipulated by an adversary, e.g., are signed, and that users do not try to change their choice of $x_i$ after having a tag. Anyways, I give it a shot (although I may be wrong due to some information I do not have):

First Construction

Clearly, for the first construction you can simply try guessing $x_i$ and test against $g^{x_i}$ (which will be problematic if your $x_i$ come from a small set).

Second Construction

For your second construction, if $g^{\sum r_i}$ is revealed, then you can again test: Lets say for simplicity you have only one tag, then given the aggregate of the $r_i$ values (which happens to be $g^{r_1}$), you can just guess $x_1$ and test as in the first construction. Clearly, if there is more than one tag you can also test by cancelling out $g^{\sum r_i}$ from the aggregate of all tags, but the sum $x_1+\ldots+x_n$ in the remaining value $g^{\sum x_i}$ may not be unique anymore (so it depends if the $x_i$ can only take some specific values - then your sum could be unique but it must not be the case).

Thrid Construction

For the third approach with tags of the form $g^{a_ix_i +r_i}$: If the value $a_i$ is uniformly at random chosen by every user, then even when publishing $g^{\sum r_i}$ this will not give an advantage for testing, as even when cancelling out $g^{\sum r_i}$ in the full aggregate of all tags you still have $g^{\sum a_i x_i}$. Without knowing any of the $a_i$ values, you cannot test anymore (this is even unconditional hiding - for uniformly random $a_i$, the value $g^{a_i}$ is a random element and so is $(g^{a_i})^{x_i}$). So your last construction is secure even if the values $x_i$ are known to come from a small set (clearly, assuming that the values $g^{a_i}$ are not available to the adversary).

share|improve this answer
there is a relaxed security definition and the attacker is allowed to reveal the sum but not the individual values. There is no all-or-nothing definition... – curious May 22 '14 at 9:16
@curious, that belongs in your question. Don't ask "chameleon questions", where new requirements get revealed or drip-fed to us only after someone posts a valid answer to the original question. Think through your requirements and all relevant information, and make sure they are present in the question from the start. – D.W. May 22 '14 at 22:39

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