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$
5
  • $\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
    Commented Apr 19, 2018 at 20:18
  • $\begingroup$ helpful for my general knowledge:) $\endgroup$ Commented Apr 19, 2018 at 20:35
  • $\begingroup$ What is your own research? $\endgroup$ Commented Apr 19, 2018 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$ Commented Apr 19, 2018 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$ Commented Apr 20, 2018 at 8:45

2 Answers 2

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.

$\endgroup$
2
  • $\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$ Commented Apr 19, 2018 at 22:46
  • $\begingroup$ Well, quite a general question. Can you see what is "characteristic polynomial" of sequence, graph or set? $\endgroup$ Commented Apr 19, 2018 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.

$\endgroup$

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.