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$).

• the requirements with the number of ones is called "having a specific hamming weight", which may or may not be a helpful information... – SEJPM Apr 19 '18 at 20:18
• helpful for my general knowledge:) – user1387682 Apr 19 '18 at 20:35
• What is your own research? – Vadym Fedyukovych Apr 19 '18 at 21:48
• I thought about BGN scheme, where I put 'AND' between ~ N-m expressions that consist of 'OR'. But I want something more practical. – user1387682 Apr 19 '18 at 22:26
• @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. – Hilder Vitor Lima Pereira Apr 20 '18 at 8:45

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.

• 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? – user1387682 Apr 19 '18 at 22:46
• Well, quite a general question. Can you see what is "characteristic polynomial" of sequence, graph or set? – Vadym Fedyukovych Apr 19 '18 at 22:51

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.