Bitcoin Forum
May 01, 2017, 06:32:09 AM *
News: If the forum does not load normally for you, please send me a traceroute.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: [Crypto] Borromean ringsig: Efficiently proving knowledge for monotone functions  (Read 2629 times)
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2170



View Profile
June 02, 2015, 07:07:36 AM
 #1

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).
1493620329
Hero Member
*
Offline Offline

Posts: 1493620329

View Profile Personal Message (Offline)

Ignore
1493620329
Reply with quote  #2

1493620329
Report to moderator
1493620329
Hero Member
*
Offline Offline

Posts: 1493620329

View Profile Personal Message (Offline)

Ignore
1493620329
Reply with quote  #2

1493620329
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1493620329
Hero Member
*
Offline Offline

Posts: 1493620329

View Profile Personal Message (Offline)

Ignore
1493620329
Reply with quote  #2

1493620329
Report to moderator
1493620329
Hero Member
*
Offline Offline

Posts: 1493620329

View Profile Personal Message (Offline)

Ignore
1493620329
Reply with quote  #2

1493620329
Report to moderator
vokain
Legendary
*
Offline Offline

Activity: 1680


V.V.V.V.V.


View Profile
June 02, 2015, 06:06:05 PM
 #2

Thank you!

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

...مكتوب
Escape the plutocrats’ zanpakutō, Flower in the Mirror, Moon on the Water: brave “the ascent which is rough and steep” (Plato).
wpalczynski
Legendary
*
Offline Offline

Activity: 1050


Twitter: @wpalczynski


View Profile
June 02, 2015, 06:31:54 PM
 #3

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

gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2170



View Profile
June 02, 2015, 11:58:24 PM
 #4

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
Sr. Member
****
Offline Offline

Activity: 336



View Profile
June 03, 2015, 12:41:09 AM
 #5

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

"The nature of Bitcoin is such that once version 0.1 was released, the core design was set in stone for the rest of its lifetime" - Satoshi Nakamoto, June 17, 2010
wpalczynski
Legendary
*
Offline Offline

Activity: 1050


Twitter: @wpalczynski


View Profile
June 03, 2015, 01:29:05 AM
 #6

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
Hero Member
*****
Offline Offline

Activity: 854



View Profile
June 03, 2015, 02:01:34 AM
 #7

How does this relate to Bitcoin/compare to Zerocash Huh

Forgive my petulance and oft-times, I fear, ill-founded criticisms, and forgive me that I have, by this time, made your eyes and head ache with my long letter. But I cannot forgo hastily the pleasure and pride of thus conversing with you.
Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 534


View Profile WWW
June 03, 2015, 11:12:11 PM
 #8

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
Legendary
*
Offline Offline

Activity: 1064


View Profile
June 04, 2015, 08:55:55 AM
 #9

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).

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
andytoshi
Full Member
***
Offline Offline

Activity: 167

-


View Profile
June 04, 2015, 06:10:07 PM
 #10

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
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!