nopara73
commented
4 years ago More complicated building blocks allow simplification at the higher levels of the protocol
This isn't necessarily true. See BLS Blind Signature scheme vs Blind Pedersen Commitment Scheme, where the former requires an additional communication round to acquire the accummulator and anonymity networks of today are unreliable, thus this may delegate more complexity for higher level protocol, than the Blind Pedersen Commitment Scheme would. I suspect the same is true for ringCT/e-cash, etc approaches, they will require more interactivity.
nothingmuch
For construction of coinjoin transactions with a coordinator we require some sort of tokens issued at input registration and redeemed at output registration.
This issue is for systematically comparing the various alternatives, with separate issues.
Possible Approaches
There are 4 approaches we've considered for issuing tokens representing amounts at input registration, presented in order of strictly increasing flexibility/capability (but also complexity)
High Level Comparison
More complicated building blocks allow simplification of the privacy considerations at the higher levels of the protocol (specifically how clients use tokens to combine/split amounts, see below).
Both the fixed denomination and the overkill approaches are solved already, so can be considered fallbacks. They represent extreme ends of the tradeoff spectrum, simplicity on the one hand vs. optimal unlinkability on the other.
The fixed denomination approach presents the smallest change from the current protocol, but also presents more difficulties with regards to improving the resulting transaction structure and adding flexibility (e.g. payments).
Arbitrary splitting or merging requires some novel construction, since our use case is a bit unusual than what is typically found in the e-cash literature: our tokens are short lived, the interaction is online, the issuer is also the verifier, and there is no risk of theft, only denial of service (since that is secured by the final signature phase).
Merging would simplify certain aspects, but with very marginal benefits compared to the advantage that arbitrary splitting into blinded amounts provides over fixed denominations. However, homomorphism signatures also presents some challenges to double spending prevention, so it may turn out to be significantly more complex.
Consequentially at least for now we will focus on option 2, arbitrary splitting into blinded amounts, which is a more modest goal, and sufficient for our needs, but still pursue client side merging as a nice to have stretch goal if we can realize.
Evaluation Criteria
Privacy
First, we consider 3 levels of potential privacy leaks:
Cryptographic unlinkability is a hard requirement, necessary but not sufficient, but depending on how it is instantiated does not guarantee privacy at the higher levels.
Secondary Criteria
Privacy is the most important property, but the following evaluation criteria also apply:
Potential Building Blocks for Splitting Approach
This section attempts to organize the different constructions we've considered for review. Individual approaches that have been studied in more detail have their own issues referenced here.
For the most part we've discussed different blind signature schemes where the messages are amounts. The e-cash literature contains several constructions, with divisible and compact e-cash being the closest to what we need, but typically address the offline setting. Single use anonymous credentials also apply.
Blinded Signatures on Pedersen Commitments #10
Requires bilinear groups.
Uses a randomizable, partially blind signature scheme: http://www.cs.pwr.edu.pl/hanzlik/preludium/wyniki/paper2.pdf
Camenisch-Lysyanskaya signatures #12
Requires bilinear groups. Supports double spending prevention.
Anonymous Credentials Light #16
Anonymous credential system that supports single use credentials and does not require pairing: https://cs.brown.edu/people/fbaldimt/papers/CCS13.pdf
See also Wasabi Research Club meeting about this paper: https://www.youtube.com/watch?v=pgErjQSQQsg
Notably, this seems to be the simplest anonymous credential scheme that can be used "off the shelf" for this case, albeit inefficiently (a single attribute credential per amount), and it only requires standard cryptographic assumptions (no pairing).
Malleable signatures
Generalization of previous redactable signature schemes that permits restricted transformations on signed values: https://www.microsoft.com/en-us/research/wp-content/uploads/2014/07/CSF-CKLM14-.pdf
Double spending prevention unclear.
Mercurial signatures
Similar to malleable signatures, but also randomizes the keys. Has been used to construct delegatable anonymous credentials: https://eprint.iacr.org/2018/923.pdf
Double spending prevention unclear.
Algebraic MACs #17
Simpler construction based on standard groups specifically designed for the issuer-is-verifier setting: http://www0.cs.ucl.ac.uk/staff/S.Meiklejohn/files/ccs14.pdf
A more recent construction also allows MACs over group elements, similar to the ACL scheme: https://signal.org/blog/pdfs/signal_private_group_system.pdf
Since these schemes support unlinkable multi-show, double spending prevention would likely require some serial number based approach.
Fuchsbaurer
https://eprint.iacr.org/2015/626.pdf
@seresistvanandras - can you provide an overview?
RSA
@seresistvanandras suggested we may be able to recover some of the attractive properties of the BLS based signature scheme described in #5 without the overspending issues arising from signature homomorphism.
See also https://crypto.stackexchange.com/questions/80011/the-security-of-blind-rsa-signatures-with-modular-exponentiation-as-padding
Lelantus #14
Blinded amounts with splitting/merging using Groth-Kohlweiss proofs
Divisible e-cash inspired
Several related approaches described in the divisible e-cash literature.
There are some non-trivial limitations and complexity in most schemes, but perhaps building blocks can be factored out and simplified for our needs, since divisible e-cash generally implies offline setting, and usually only support dividing some fixed denomination to arbitrary sub-amounts.
Typically these build a tree of commitments to serial numbers on fixed denominations, where spending a single node on the tree invalidates its children and parents but not its siblings or their descendants.