2
$\begingroup$

I'm currently working with BLS Signature Schemes in the field of publicly verifiable Compact Proofs of Retrievability by Shacham and Waters.

So for creating the Sigmas the following function is defined: $$ \sigma_i \leftarrow\left(H(\text { name } \| i) \cdot u^{m_{i}}\right)^\alpha . $$ $\left\{m_{i}\right\}_{\substack{1 \leq i \leq n}}$ are bytes derived from a File $M$ which is devided into $n$ blocks. $u$ is a generator of $G_1$. $\alpha$ is the private key with $\alpha \stackrel{\mathrm{R}}{\leftarrow} \mathbb{Z}_p$. The hash function is defined as $H:\{0,1\}^* \rightarrow G_1$

The Proofs are generated by: $$\mu \leftarrow \sum_{\left(i, \nu_i\right) \in Q} \nu_i m_{i} \in \mathbb{Z}_p$$

and

$$\quad \sigma \leftarrow \prod_{\left(i, \nu_i\right) \in Q} \sigma_i^{\nu_i} \in G_1 $$

where $\nu_i \stackrel{\mathrm{R}}{\leftarrow} \mathbb{Z}_p$.

Finally the verification is done by the following pairing: $$ e(\sigma, g_2) \stackrel{?}{=} e\left(\prod_{\left(i, \nu_i\right) \in Q} H(\text { name } \| i)^{\nu_i} \cdot u^{\mu}, v\right) ; $$

Where $v$ is the public key computed by $v \leftarrow g^\alpha$ and $g_2$ is a generator of $G_2$

The problem:

As $\mu$ in the proof generation becomes a big number, my idea was to apply a modulus on $m_i$. I would choose a random prime $c \stackrel{\mathrm{R}}{\leftarrow} \mathbb{Z}_p$ and reduce $m_i$ in the sigma generation and the proof generation.

So the new construction of $\sigma_i$ and $\mu$ would look like this:

$$ \sigma_i \leftarrow\left(H(\text { name } \| i) \cdot u^{(m_{i} \bmod c)}\right)^\alpha . $$

$$\mu \leftarrow \sum_{\left(i, \nu_i\right) \in Q} \nu_i \cdot (m_{i} \bmod c) \in \mathbb{Z}_p$$

The question:

Does applying the modulus like this lower the security of the authenticators (sigmas) in a bad way?

A solution: As @poncho pointed out, I can just apply $\mu \bmod p$ where $p$ is the prime order of $G_1$ in order to bring the size of $\mu$ down and still have a valid pairing. So I do not need to fiddle around with the bytes I'm reading as i wrote in my idea.

Thanks and best regards.

$\endgroup$
9
  • $\begingroup$ "my idea was to apply a modulus on $m_i$. I would choose a random prime..."; wouldn't the obvious idea be to reduce things modulo $p$ (the order of $G_1$)? $\endgroup$
    – poncho
    Jan 9, 2023 at 13:47
  • $\begingroup$ That would be obvious, but that does not reduce it enough. $p$ is of bit size 254 as I'm using alt_bn128 curves. When using modulo $p$ the order of $G_1$) $\mu$ results in 341 bit. But as i need to fit $\mu$ into a 32byte integer this is not suitable. So my thoughts where to choose a $p$ of 128 bit size for $c$ as this results in $\mu$ being 215 bits. $\endgroup$ Jan 9, 2023 at 14:49
  • $\begingroup$ Huh? If you reduce things modulo $p$, you should never get anything larger than $p$ - if $p$ is 254 bits, the value you get should always fit in 32 bytes. $\endgroup$
    – poncho
    Jan 9, 2023 at 14:56
  • $\begingroup$ But $\mu$ as described above is the sum of some amount of $m_i$, and building the sum can result in a number being bigger than 32 bytes. If you mean i could just apply modulo to $\mu$ itself, from my understanding this is not possible as it does break the pairing. $\endgroup$ Jan 9, 2023 at 15:06
  • $\begingroup$ "from my understanding ... it does break the pairing" - no, why would it? After all, the pairing works on groups of order $p$ - hence reducing things modulo $p$ doesn't change anything... $\endgroup$
    – poncho
    Jan 9, 2023 at 15:13

1 Answer 1

1
$\begingroup$

"my idea was to apply a modulus on $m_i$. I would choose a random prime...";

Wouldn't the obvious idea be to reduce things modulo $p$ (the order of $G_1$)? After all, the pairing works on groups of order $p$ - hence reducing things modulo $p$ doesn't change anything..

[This added to give you an answer you can accept]

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