[Crypto] Borromean ringsig: Efficiently proving knowledge for monotone functions

[gmaxwell]

Some here may be interested in a new cryptosystem I've been working on which efficiently and privately proves the knowledge of secrets according to an policy defined by an AND/OR network:

https://github.com/Blockstream/borromean_paper/raw/master/borromean_draft_0.01_34241bb.pdf

This new ring-signature is asymptotically 2x more efficient than the one used in Monero/Bytecoin: It needs n_pubkeys+1 field elements in the signature instead of 2 * n_pubkeys. In particular, it retains this 2x efficiency gain when doing an AND of many smaller rings, because the +1 term is amortized across all of them.

The paper also describes a new way to think about ring signatures; which might be helpful to anyone who has looked at them before and found them confusing. (If we were successful, you'll think the new construction was so simple that it was completely obvious; I can assure you it was not... fortunately Andrew Poelstra came up with an especially good way to explain it.)

While the connection to Bitcoin may not be immediately obvious, I've used this as a building block in a much larger and more applicable cryptosystem which I'll be publishing, complete with implementation, shortly  (I'm trying to not flood people with too many new ideas built on new ideas all at once, and I'm still working on the description of the other constructions). I think this construction is interesting in its own right, and I'd be happy to learn if someone knows of this being previously published (though I was unable to find anything prior).

[vokain]

Thank you!

Some additional commentary: http://www.reddit.com/r/Bitcoin/comments/386vh0/borromean_ring_signatures_new_research_by_greg/

[wpalczynski]

If this innovation in ring signature efficiency proves mathematically sound is it something that could be applied to the ring signatures in Monero?

[gmaxwell]

Yes, it could replace the construct used in Monero (though I am pretty sure it would have to be a hard fork there) for an efficiency gain (or a privacy gain at a given efficiency). Though I've not implemented the tracability required for that particular application.

[celestio]

Very interesting, 2x improvement in efficiency is a huge boost. Also looking forward to the "larger cryptosystem" in Bitcoin. Core has my vote.

[wpalczynski]

Yes, it could replace the construct used in Monero (though I am pretty sure it would have to be a hard fork there) for an efficiency gain (or a privacy gain at a given efficiency). Though I've not implemented the tracability required for that particular application.

Do you ever see anonymity, stealth addressing, transactional privacy in general being implemented into Bitcoin?

I'm curious as to your opinion on the matter.  I feel that the whole premise under which all the VC money was invested into Bitcoin recently is that it is a Public ledger and because it's a Public ledger various governments have let it breathe enough to make these people think it's safe to invest.  Although some Bitcoin users suggest otherwise I just don't think this would ever be possible.

[BlindMayorBitcorn]

How does this relate to Bitcoin/compare to Zerocash

[Sergio_Demian_Lerner]

Some here may be interested in a new cryptosystem I've been working on which efficiently and privately proves the knowledge of secrets according to an policy defined by an AND/OR network:

https://github.com/Blockstream/borromean_paper/raw/master/borromean_draft_0.01_34241bb.pdf

Very interesting! I have several ideas on how to improve it, but I must think more.

One possibility to extend one level depth of logic operations is to create signatures for additions of keys (P1+P2). Then, as long as keys are linearly independent there is no way to cheat (I think this would be the Representation Problem in the EC). User 2 may cheat by choosing his pubkey as (-P1+Q) as to allow proving the signature of both (and not having a private key for any of them). One way to prevent this cheating would be that each public key must be accompanied by a non-interactive ZPN of the secret key. Of course, if two users collude to create two keys so that one is a multiple of the other, then there is a hidden key (the difference) that is neither one nor the other that can be used to build the signature, but this seems not to be a practical concern.

So you can achieve circuits like  ( (P1 AND P2 AND P3) OR (P4 AND P5 AND P6) ) AND ( ....  ) with 3 levels of gates: AND-OR-AND

PS: using a edge-to-vertex dual graph where signatures are represented as nodes and edges are time implications seems easier to reason about.

Regards

[TierNolan]

So you can achieve circuits like  ( (P1 AND P2 AND P3) OR (P4 AND P5 AND P6) ) AND ( ....  ) with 3 levels of gates: AND-OR-AND

I think that is already covered? 

AND means 2 paths in parallel but OR means in series.

For example, this achieves your circuit:

Code:

    +----->[ .... ] -----------------------+
    |                                      |
S --+                                      |
    |     +-->[P1]----+   +-->[P4]----+    |
    |     |           |   |           |    |    
    |     |           V   |           V    V
    +-----+-->[P2]--->H---+-->[P5]--->H--->H---> [to S]
          |           ^   |           ^
          |           |   |           |
          +-->[P3]----+   +-->[P6]----+

The paper suggests that the P4, P5 and P6 nodes would have to accept 3 edges input each.

Multiple incoming edges could be combined with a standard non-trapdoor hash function (H).

[andytoshi]

PS: using a edge-to-vertex dual graph where signatures are represented as nodes and edges are time implications seems easier to reason about.

I had this initially, but it seemed to require I use a hypergraph (edges with more than two vertices) and I felt it was actually easier to reason about the way that it's written.

Andrew