CC #3: PKI 🎃

Welcome to the third issue of Ciphertext Compression, meant to be a quick digest of what happened on ePrint last week. If you are wondering why I am doing this, I am wondering that too, see the this post for what I was thinking.

Range considered. new ePrints posted between Sun, 17 Oct 2021 12:02AM GMT and Sun, 24 Oct 2021 12:02AM GMT!

Crypto Protocols

Practical Non-Interactive Publicly Verifiable Secret Sharing with Thousands of Parties — Recall that secret sharing allows a user to split a secret $S$ into shares say $(S_1, S_2, S_3)$ and distribute them to Alice, Robert, and Charlie such that if one wanted to recover the secret $S$, they need more than $2$ shares. However, notice that there is implicit trust in the user to be honest, because there is nothing stopping them from creating shares such that $S_1 + S_2 = S$ but $S_2 + S_3 = S’ \neq S$. Publicly verifiable secret sharing works around this limitation by asking the user to (1) commit to the shares (this is usually publishing an encryption of the shares to say Alice, Robert, and Charlie’s public keys¹) and (2) be able to prove to any interested party that has these public commitments that they are consistent (typically via an interactive proof). This paper proposes a non-interactive publicly verifiable secret sharing scheme that is practical for 1000s of parties.

Universally Composable Almost-Everywhere Secure Computation — PKI is hard—so much that my current resume includes the line “am scared of PKI”.² But have you noticed that almost every crypto paper and construction unquestioningly assumes the existence of PKI, it is typically in the form of an “authenticated channel” between all users. This paper is an outlier, it looks at the MPC setting where the participants are connected through a more structured network where there may be many “wires” connecting two participants and some of those wires may be compromised. It gives a universally composable definition of what security means in this setting and gives a protocol for achieving this.

Efficient Adaptively-Secure Byzantine Agreement for Long Messages — Recall that Byzantine agreement is a protocol for $n$ participants to agree on a shared value, even in the presence of malicious participants (as long as they are below some threshold). Classic Byzantine agreement protocols require each participant to communicate with every other participant, incurring an $O(n^2)$ communication cost. This cost is untenable in large-scale distributed systems, where we ideally want a communication cost that scales almost linearly in the number of participants. Indeed, prior work has achieved this, by splitting participants into committees of size $\kappa$ and doing consensus-by-committee, achieving $O(n \cdot \poly(\kappa))$ communication. This papers points out that this figure hides a multiplicative factor of the input length $\ell$, in other words, it is really $O(\ell n \cdot \poly(\kappa))$ and for large inputs $\ell \gg n$, this is bad. Then it gives a protocol that achieves $O(n\ell + n\cdot\poly(\kappa))$ communication.

Blockchains

HIDE & SEEK: Privacy-Preserving Rebalancing on Payment Channel Networks — Last issue, I mentioned a dirty secret of traditional blockchains, I have another one, they are so fucking slow, bitcoin has a throughput of <7 transactions per second with a latency of ~5-10 minutes.³ One solution that is frequently floated is “payment channels” which is a fancy term for a pre-paid tab. You have tab with everyone you transact with, you fund the tab by doing an on-chain transaction, you keep track of your tab via a “Layer 2” application like the lightning network, and if you need money, you close out the tab with another on-chain transaction. I am shoving a lot of complexity under the rug here, for instance, there is a lot of cool cryptography involved in Layer 2 which removes trust in the counterparty as long as you (or someone you trust) is always online, but you get the general idea. But as with tabs, you can’t use money Alice owes you to pay Bob unless you close out the tab with Alice and use that to fund the tab with Bob which requires 2 on-chain transactions. The solution to this is “rebalancing” where you rebalance your tab with Alice and Bob, and use that to pay Bob. This paper provides a privacy-preserving rebalancing solution that eventually achieves the global optimum.

Foundations

Non-Interactive Distributional Indistinguishability (NIDI) and Non-Malleable Commitments — So, you know how non-interactive zero-knowledge proofs aren’t really non-interactive and require some setup like a common reference string (like a small amount of public randomness), and how without any such setup there do not exist non-interactive zero-knowledge proofs for non-trivial statements. So, there has recently been some interest in weaker notions of zero-knowledge that can be proved non-interactively without any setup. This paper constructions the strongest such notion so far from sub-exponential indistinguishability obfuscation.

Closing Words

Thanks for sticking till the end. 🎃

You can subscribe to this hooey via Buttondown (using email or rss) and find it on Twitter.

Obvious Disclaimer. Views are mine and not serious. All mistakes are mine. If you’d like to point them out, shoot me an email. If I get more than 10 emails, I’ll create a discord and post the invite link here.