A couple weeks ago I made available a short draft write-up describing a simple generalization of the AOS ring signature, which allows it to efficiently prove acceptance of an AND of ORs access policy, rather than OR you get from a basic AOS signature:
https://github.com/Blockstream/borromean_paper/raw/master/borromean_draft_0.01_8c3f9e7.pdf In the write-up Andrew Poelstra and I also describe an alternative framework for thinking about Schnorr signatures (especially when expressed as {e,s}) as an application of chameleon hashes. This description is helpful for understanding this particular construction but may also be useful for gaining other insights into other protocols. I used this primitive to construct a protocol which proves that a blinded value (pedersen commitment) is within a specified range (my upper bounds are only powers of 2 because thats all that I needed.), through an approach isomorphic to the binary decomposition range proofs of Bellare and Goldwasser. Due to the use of the generalized AOS signature and a number of other optimizations my construction requires 2.5 elements per bit proven, which is more efficient than general scheme I could find in the literature using only ECDL+RO assumptions, at least for the number sizes I care about. My implementation also has a number of other cute tricks, like allowing a non-private base-10 exponent. It is also able to use 80% of the proof's size to communicate a private message to a designated receiver (for whom the committed value is not secret). I created a very informal description pedersen commitments, binary decomposition range proofs, and some information about how this scheme is used to construct a cryptocurrency system where the amounts transmitted are private: https://people.xiph.org/~greg/confidential_values.txt I apologize for the informality (and lack of citations) and incompleteness, my primary intended audience is technical persons in the cryptocurrency space whom have strong CS fundamentals but may not know anything about zero-knowledge proof systems. I've received many positive reports about it, so if any of you are only familiar with ECDH and signatures and would like an intuitive and informal overview of range proofs, I'd suggest it as well-- and comments and questions are welcome! I think an essential part of advancing the art and science of cryptography is elevating people's working understanding: I think systems which are pure black boxes to all but a few are unlikely to ever become highly secure. I plan on documenting the system more formally-- along with all details like the use of base-4 encoding-- in the future, certainly before putting it into any production use. (beyond time constraints and the system not being final, I find that more formal descriptions sometimes scare people off, so it's useful to have both). There is an experimental implementation of both the ring-signature and range-proof available at: https://github.com/ElementsProject/secp256k1-zkp This implementation is on top of an also-experimental EC library libsecp256k1-- where I am also a contributor. As the name suggests, it implements secp256k1-- the 256-bit prime order, prime field, SECG specified curve designed to have an efficient endomophism, which is used by Bitcoin. Libsecp256k1 implements many interesting optimizations, including ones not implemented or described elsewhere (e.g. techniques which allow completely inversion free signature verification, or jacobian plus jacobian as fast as jacobian plus affine, under certain conditions). Optimizations where we are aware of heightened potential for patent complications are disabled by default. Currently we view this implementation as a test bed for exploring the limits of performance on top of this curve, as well as s test bed for software quality and verification techniques for use in cryptographic and consensus systems. There are other forks of this library that implement things like batch verified Schnorr signatures, and such. Finally, The range-proof powered private value system is integrated into a cryptocurrency test-bed called Elements Alpha ( https://blockstream.com/developers/ / https://github.com/ElementsProject/elements ). Rather than being a separate cryptocurrency the alpha network is a "pegged side-chain" against Bitcoin testnet, which uses the mechanisms/protocols described in the sidechains whitepaper ( https://blockstream.com/sidechains.pdf ) to allow users to transfer testnet bitcoins into alpha, trade them around, and then transfer them back to Bitcoin testnet. The motivation of this approach is being able to experiment with new constructions and techniques without rebooting the cryptocurrency adoption network effect by creating a separate competing system. So beyond all this being a fun cryptography novelty it can be used right now (though currently only with testnet bitcoin. :) ) I hope some here find some of this of interest. _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
