CoSi protocol extension

[masomel]

From the CoSi paper abstract:

To protect authorities and their clients proactively from undetected exploits and misuse, we introduce CoSi, a scalable witness cosigning protocol ensuring that every authoritative statement is validated and publicly logged by a diverse group of witnesses before any client will accept it. A statement S collectively signed by W witnesses assures clients that S has been seen, and not immediately found erroneous, by those W observers. Even if S is compromised in a fashion not readily detectable by the witnesses, CoSi still guarantees S’s exposure to public scrutiny, forcing secrecy-minded attackers to risk that the compromise will soon be detected by one of the W witnesses. Because clients can verify collective signatures efficiently without communication, CoSi protects clients’ privacy, and offers the first transparency mechanism effective against persistent man-in-the-middle attackers who control a victim’s Internet access, the authority’s secret key, and several witnesses’ secret keys.

We would like to implement CoSi as a protocol extension for CONIKS; here are some benefits we've discussed via email so far:

• you can have multiple participants/parties signing off (a tree-root for instance) and get a single signature at the end. Someone who wants to verify this signature can do so as if it was a single signature, too.
• equivocation could be detected proactively (even before the tree-roots are signed)
• to forge such a signature you would need to control all co-signers instead of a single server (which would be a single point of failure).
• It would simplify the auditing protocol: for clients to be sure that they received the right “world view” they wouldn’t need to contact several auditors as all (or a threshold t of n) auditors have witnessed the same view.
• users in repressive regimes can’t be forced to used state controlled auditors (the regime might censor access to honest ones).

What would the integration look like:

The next STR would be signed by CoSi. The TBs could be a little tricky (but would need to be signed, too). Starting with a threshold of zero could mean that end-clients could ignore CoSi at the beginning.

cc @bford @liamsi @arlolra @c633

[masomel]

One question I would like to discuss is the role of auditors with CONIKS+CoSi. So far, we've discussed CoSi as a possible replacement for the CONIKS auditing protocol. But the CoSi paper also makes an argument for using proactive and retroactive consistency checking in combination as a way of reducing vulnerabilities to Sybil attacks; I'm wondering if auditors could help improve the chances of detecting such attacks, or really any collusion between co-signers and the authority?

[liamsi]

equivocation could be detected proactively (even before the tree-roots are signed)

In the current cosi implementation the "exception mechanism" is still lacking, which would be necessary for the pro-active detection. Also it would be ideal if the to-be-signed statement would be already validated in the announcement which currently isn't the case, too.

This will be implemented soon (dedis/cosi#10, dedis/cosi#11, dedis/cosi#58)

[vqhuy]

Alternatively, we can use the multisig construction based on BLS signature described in https://eprint.iacr.org/2018/483.pdf

AFAIK, this ASM (Accountable-Subgroup Multi-signatures) scheme provides all the aforementioned benefits. Furthermore, it also requires only 1 round of communication between "witnesses" (the subset S out of N signers) before the signing process (the offline phase). The signing phase can be done quite efficiently by the combiner (the directory in the CONIKS case). And it has a built-in "exception mechanism" in the construction, which they call "t-of-n multisig" in the paper. It takes 4 rounds in the case of CoSi, and the whole process needs to be restarted if there were unavailable witnesses. In this ASM scheme, the set S does not have to be fixed at the beginning of the protocol, so witnesses don't need to be as highly available as CoSi's ones. The downside is that the verification needs perform 3 pairing operations (which costs more than standard Schnorr signature verification in CoSi).