1
$\begingroup$

Let V = $[x_1,\ldots ,x_n]$ be a binary vector of length $n$, and let $E(V)$ be the entrywise encryption of this vector.

Suppose I want to give to another player, $E(V)$, but also let him have the ability to verify that the plain vector contains m values that are equal to 1, and they are consecutive.

For example, n=5,m=2:

Valid V = 0,1,1,0,0; Not valid V = 0,1,0,1,0.

Note that: If the requirement was without the consecutive property, I've just used an homomorphic encryption. (to see if the multiplication of the values are equal to the encryption of $m$).

$\endgroup$
  • $\begingroup$ the requirements with the number of ones is called "having a specific hamming weight", which may or may not be a helpful information... $\endgroup$ – SEJPM Apr 19 '18 at 20:18
  • $\begingroup$ helpful for my general knowledge:) $\endgroup$ – user1387682 Apr 19 '18 at 20:35
  • $\begingroup$ What is your own research? $\endgroup$ – Vadym Fedyukovych Apr 19 '18 at 21:48
  • $\begingroup$ I thought about BGN scheme, where I put 'AND' between ~ N-m expressions that consist of 'OR'. But I want something more practical. $\endgroup$ – user1387682 Apr 19 '18 at 22:26
  • $\begingroup$ @SEJPM I don't think it is true because of the restriction that the ones must be consecutive. Both V given as example on the question have the same Hamming weight. $\endgroup$ – Hilder Vitor Lima Pereira Apr 20 '18 at 8:45
1
$\begingroup$

To capture value/position relations, a "sequence polynomial representation" was suggested, in the context of proving properties of DNA. Self-citing: IACR preprint 2008/357. This technique could apply here in case of ElGamal ciphertext, that could be proven with Schnorr-like responses. The major idea remains to re-state "consecutive" as a property of "characteristic polynomial", that (I believe) is doable. Hamiltonicity test (2008/363) could be another example.

| improve this answer | |
$\endgroup$
  • $\begingroup$ In your discussion section in your article, IACR preprint 2008/357, you state exactly what I'm looking for (which is an extension of the problem that I described above) - matching for 2D and 3D objects. But I find it hard to understand the technique from this article (I get stuck to understand the notation), can you explain it via example? $\endgroup$ – user1387682 Apr 19 '18 at 22:46
  • $\begingroup$ Well, quite a general question. Can you see what is "characteristic polynomial" of sequence, graph or set? $\endgroup$ – Vadym Fedyukovych Apr 19 '18 at 22:51
0
$\begingroup$

An alternative method :

In your case, proving there are $k$ consecutive ones in a binary string $S$ would be similar as proving that the underlying number $\mathcal{X}$ (from $S$) is written as $(2^k-1) \times 2^l$ for some integer $l$. We will denote this property as $\mathcal{P}$.

As an example, if $\vec{X} = (x_1, x_2, x_3, x_4, x_5) = (0,1,1,0,0)$ and $k=2$ then $\mathcal{X} = \sum_{i=1}^5 x_i \times 2^{i-1} = 6 = 2 \times (2^2-1)$.

If you use a homomorphic (public) scheme $E$, I would slightly change it such that $E_j(x) = E(2^{j} \times x)$ where $j \in \{1, \dots, n\}$. In short, substitute $1$ with $2^{j}$ in your vector. For now, we will assume that $E$ is an additive scheme. For instance, we can focus on the Pallier's scheme i.e. it looks like $E(x) = g^m \times r^N \mod N^2$ where $r$ is random. Let us more accurately define $E_j(x)$ as $ g^{2^{j} \times x}\times r_j^N \mod N^2$.

Then, you can evaluate $E_j(x_j)$ for $j \in \{1, \dots, n\}$ and the (component-wise) encrypted vector would be $E(\vec{X}) = (E_1(x_1), \dots, E_n(x_n))$. If the input vector $\vec{X}=(x_1, \dots, x_n)$ lies in $\mathcal{P}$ then $\prod_{j=1}^n E_j(x_j)= E(2^{l} \times(2^k-1))$.

If you don't want to use different encryption scheme $E_j$ for each coordinate, you could only use $E(x)$. Encrypted $\vec{X}$ would then be $(E(x_1), \dots, E(x_n))$. If so, the verifier would virtually be in charge of computing the $E_j$ as $E_j(x) = 2^j \times E(x) = E(2^j \times x)$ based on the $\mathcal{V}_i$ following trick.

If one wants to evaluate $E(2^j \times x)$, one defines $\mathcal{V}_0$ as $E(x)$. Next, one can perform $\mathcal{V}_1 = \mathcal{V}_0 \times \mathcal{V}_0=E(x) \times E(x)=E(2 \times x)$. Iterating, one can compute$\mathcal{V}_{i} \times \mathcal{V}_{i}=\mathcal{V}_{i+1}=E(2^{i+1} \times x)$.

Thus, the verifier would finally obtain the $x_j$ coordinate $g^{2^{j} \times x}\times (r_j^N)^{2^j} \mod N^2$ plus the product $\mathcal{M}=\prod_{j=1}^n E(2^j \times x_j) = g^{2^l \times (2^k-1)} \times (\prod_{j=1}^n (r_j^{2^j}))^N$.

If your $n$ is not too big, you can prove that $\mathcal{M}$ is the cipher of a plain text which belongs to the $\{2^l \times (2^k-1) | l \in \{0, \dots, z \}\}$ set for some integer $z <n$. Of course, this should be carried out without disclosing $2^l \times (2^k-1)$. This can be done based on the following zk-proof : click here. Finally, the prover should also convince the verifier that $E(x_j)$ is the encryption of an element that belongs to $\mathbb{F}_2$.

PS : I'm not sure this is the most efficient method as the generated proof can be quite large (depending on $n$). Nonetheless, it is conceptually quite simple to implement.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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