Score:2

Modulus for reduction in BLS Signature Scheme

sk flag

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.

poncho avatar
my flag
"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$)?
empty_stack avatar
sk flag
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.
poncho avatar
my flag
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.
empty_stack avatar
sk flag
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.
poncho avatar
my flag
"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...
empty_stack avatar
sk flag
Would you be kind enough to give me the formulas where you think I should reduce for computing $\mu$ and $\sigma_i$? I tried to implement it as you suggested but the pairing does not work this way.
poncho avatar
my flag
$\mu \leftarrow \sum_{\left(i, \nu_i\right) \in Q} \nu_i m_{i} \bmod p$
empty_stack avatar
sk flag
That is what i tried. I applied mod directly $\mu \bmod p$. And as expected it brings $\mu$ down to the expected bit size. But the pairing breaks in this case. Do i have to apply the modulus to the other calculations of the pairing as well?
empty_stack avatar
sk flag
Okay nevermind I was just an idiot, i choose a random number of the size of $p$ instead of using the order directly. Thanks for your help.
Score:1
my flag

"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]

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.