1
$\begingroup$

When using BLS, let's say Alice signs each of the 5 messages ($m_1, m_2, m_3, m_4, m_5$), aggregates the signatures and sends the aggregated signature to Bob. Bob can verify it.

Here's the goal: However, Bob would also like to send the aggregated signature by Alice to Charlie but hide the values of $m_2$ and $m_4$ messages. So, Charlie wouldn't know there are 5 messages in total and he will only know about the 3 messages Bob sent him. Are there ways Bob can send Charlie, such as a proof, so that Charlie can still verify the aggregated signature was signed by Alice and Bob indeed has all 5 messages signed by Alice?

What I'm thinking is, during verification, Charlie will need all the actual values of the messages but $m_2$ and $m4$ will be unknowns since Bob did not send those values to Charlie:

$$ e(G, S_{agg}) = e(Alice_{pub}, H(m_1)) \cdot e(Alice_{pub}, H(?)) \cdot e(Alice_{pub}, H(m_3)) \cdot e(Alice_{pub}, H(?)) \cdot e(Alice_{pub}, H(m_5))) $$

So, for messages $m_2$ and $m_4$, Bob will pre-compute and send the result of the aggregated hash of these 2 messages to Charlie instead: $$ h_{agg(m_1, m_2)} = H(m_2) + H(m_4) $$

So, Bob will eventually send these pieces of info to Charlie:

  • Actual value of $m_1$, $m_3$ and $m_5$
  • Aggregated hash of $m_2$ and $m_4$, $h_{agg(m_2, m_4)} = H(m_2) + H(m_4)$
  • Public key of Alice, $Alice_{pub}$

Then, when Charlie verifies, he will use those information given to him to verify that:

$$ e(G, S_{agg}) = e(Alice_{pub}, H(m_1) + H(m_3) + H(m_5) + h_{agg(m_2, m_4)}) $$ Since $H(m_1) + H(m_3) + H(m_5) + h_{agg(m_2, m_4)} = S_{agg}$, $$ e(G, S_{agg}) = e(Alice_{pub}, H(m_1) + H(m_3) + H(m_5) + h_{agg(m_2, m_4)}) = e(G, S_{agg}) $$

However, my thoughts about my naive idea:

  1. I'm not sure if I'm thinking about the idea correctly with those equations. Would it really work in practice?
  2. I made an assumption that the order of the messages doesn't matter. Can I make such an assumption? What if during the summing of signature, it exceeds the max prime order? Would it result in different results when summed in a different order and hence fail to compute the correct $S_{agg}$?
  3. Is this even a good idea? Are there better ways to achieve my goal? I've read about adding a blinding value but I'm not sure how to combine the signatures with another blinding value.
$\endgroup$

2 Answers 2

1
$\begingroup$

This is exactly the notion of redactable signatures provided by the concept of Locally Verifiable Signatures introduced in https://eprint.iacr.org/2022/179.pdf.

Essentially, Bob has the aggregate signature from Alice for $m1, ..., m5$ and knowledge of the total set of messages. Using this, they can recover signatures (under Alice) for $m1, m3, m5$ and aggregate these to produce a new signature (under Alice) for the subset of messages.

$\endgroup$
1
  • $\begingroup$ Thanks! This scheme looks really cool! Sadly, there aren't any existing implementations in any languages for this scheme yet. And it looks too complicated for me to understand it enough to implement and use it. :'( $\endgroup$
    – xenon
    Nov 2, 2022 at 12:56
1
$\begingroup$

If Charlie is foolish enough as to accept your scheme, and Bob has possession of a single valid signature from Alice, then Bob can pass arbitrary forgeries to Charlie.

For example, in your scenario, suppose that Bob wishes to pass forgeries of messages $f_1$, $f_2$, $f_3$ to Alice. He computes $H(f_1)$, $H(f_2)$, and $H(f_3)$ and then computes the fake aggregate $h_{fagg}:=H(m_1)+ \dots +H(m_5)-H(f_1)-H(f_2)-H(f_3)$. He then passes Charlie the messages $f_1$, $f_2$ and $f_3$ along with $h_{fagg}$ (the fake aggregate) and Alice's signature. Everything will verify and Charlie cannot distinguish this and your legitimate example.

The scheme linked in the other answer will prevent this sort of approach.

$\endgroup$
1
  • $\begingroup$ Thanks for pointing that out! The Locally Verifiable Signature looks cool but is also pretty difficult. I might not understand it enough to use or implement it. I happened to come across another scheme called the BBS+ as I was researching this topic. It seems like it could generate a PoK for such a use case though I don't really understand it enough. Would it work in such a scenario too? $\endgroup$
    – xenon
    Nov 2, 2022 at 12:56

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.