MPC Signing

Transcript

[applause] >> Hi, I'm Yash. Uh I work at Silence Labs and I'll be speaking about some joint work with Naman Kumar, Supreet Varadarajan, and Anant Venegasam. All right. So, this talk is more of a report on a work in progress. All right. So, I'll be speaking about hash-based signatures, um interpreting their their structure from an MPC lens. I think uh large amount of this is previewed in the previous talk. Um so, I'll begin with this sort of simple notion of dealer-assisted threshold signing, then talk about maybe why we don't want to do this in practice, and what it takes to remove the dealer. All right. So, in particular, I'll characterize this notion of black box design paradigms for threshold signing schemes,

and say, you know, sort of do do our due diligence as to why this can't be done over here. Then, I want to give an idea of what it takes to implement a certain scheme um in MPC, like this notion of MPC complexity in some sense, and then talk about, you know, how we would how we would approach this to build our MPC threshold signing system. All right. So, there's going to be a lot of shared uh vocabulary and state from the previous talk. So, maybe I can go through this pretty quickly. So, the the setting is that of MPC, where um each party in the system has some share of the secret key, and the threshold and the threshold signing protocol is essentially a tailored MPC protocol to recon- to um

compute the signature without having to reconstruct this key physically. And this is quite common in practice now, particularly in settings where we want to decentralize risk a little bit, or we want to reduce the risk of an attacker breaking into just one device and um stealing the key. So, the scope of this talk is going to be standard signature schemes, and for this talk is going to be stateful schemes, but uh we can combine this with ideas from the previous one to get uh maybe bootstrap this to stateless schemes as well. So, I specifically want to contrast this with lines of research that go into um designing signature schemes that are specifically designed to be thresholdized. Right, so the focus here is going to be thresholdizing schemes

that are already deployed. And the idea behind this is of course that uh threshold signing is something that a user chooses to do locally and this is something that shouldn't be visible to the outside world. All right, so this is a quick recap of how hash-based signatures are structured at least um what we care about from an MPC perspective. So, we start with the signer who has a secret key and makes a bunch of queries to the hash function and computes a signature string at the end. And there's a verifier who takes the string and then samples some subset of the signer's queries and checks this against a random the hash function itself and then decides whether to accept or reject the signature.

So, there is an optimization that's possible that um at least applies to these stateful schemes. Sorry, these stateful schemes like XMSS and so on. Where one can run a pre-signing algorithm before the message is known. So, all the queries are pre-computed. This is exactly as per the previous talk. So, that once the message becomes available the signing just consists of figuring out which indices of the queries have to be revealed and then revealing those queries and then the verifier when it checks these queries and the signature itself is none the wiser.

And this is um this is a simple pre-signing optimization. So, there is a fairly straightforward way to go from pre-signing to dealer-assisted decentralization. To my knowledge, the first write-up of this idea was by Kelsey Lang and Lux from a couple years ago. Where you know, we have a pre-signing algorithm that makes its queries incrementally and as it makes its queries, it also secret shares each of the queries that it's made amongst a bunch of MPC signing nodes or a bunch of signing nodes.

And the idea now is that once the message is available, we know that all we need is to to compute or to reveal the queries at certain public indices. And so now we just have to reconstruct we have to just reconstruct the queries that uh the public indices demand. All right, so the parties in the MPC system can essentially coordinate so that they're able to reconstruct the queries at these public indices. All right, so in a lot of situations this dealer-assisted mode this works out of the box, but um it's not very satisfying as a general solution because dealers in this situation will be a single point of failure.

And this is very unpalatable in a lot of cases. So, consider for example threshold ECDSA signing. Like threshold ECDSA is already quite widely deployed. And we know for a fact that threshold ECDSA becomes trivial if you have a trusted dealer. All right, this um I guess this maybe folklore, but there's an explicit construction in this Abram et al. paper sort of a building block towards getting full threshold ECDSA. They show that dealer-assisted threshold ECDSA is trivial. But despite this, despite having this option, most deployments today to my knowledge pay the full cost of end-to-end decentralization for threshold ECDSA signing.

All right, so in this talk we're going to apply the same standard of end-to-end decentralization for hash-based signatures. At least we're going to be interested in the settings where we want to remove this trusted dealer. All right, so if you look into the literature on hash-based signing, in particular threshold hash-based signing, you won't find a lot I think. And this might be a bit confusing because you can of course use generic MPC to decentralize any algorithm. There are classic results to uh to this end. And the reason perhaps why this is is that threshold signing becomes interesting only if you're able to construct custom protocols for um distributing the signature scheme.

All right, in particular if you were to use generic MPC machinery and directly apply it to the um signing algorithm, we would have to handle cryptographic algorithm cryptographic algorithms like hash functions and so on inside of MPC or like elliptic curve arithmetic and so on. And then this is typically expensive and if possible we'd like to avoid it. Right? So, this is what I'm referring to as black box uses of cryptography. Right? So, a threshold ECDSA for example also uses MPC machinery but in a very targeted way. Right? So, the there are a lot of practical protocols for threshold ECDSA signing that we have at this point that use MPC but if you look at how they work you'll notice that in all all of

these protocols while they do use MPC they use it specifically for just Zq arithmetic that's integers modulo q. Right? So, all of the elliptic curve operations which entail pretty large circuit representations and so on are treated as black boxes outside of the scope of the MPC itself. And a natural question to ask is if we can get something similar with hash-based signatures. So, this has you know, I think the there has been sort of a folklore understanding in the community that this is not going to be easy to do hash-based signatures with the hash function treated as a black box but just as a sort of due diligence thing for constructing protocols in this paradigm we explored this question

formally and we you know, a couple of years ago showed some co-authors and I showed that for a certain style of hash-based signature based on these so-called like Merkle style signatures they inherently are are resistant to such black box methods of threshold signing and also a very recently we put this preprint up like a few weeks ago that shows that for like one-time signature schemes the kind that we are used to or that are mostly within the scope of discussion now this result extends as well that we can't hope to design schemes that use the hash function as a black box.

Some extremely quick some really quick intuition as to why this is. So, if you consider the Winternitz scheme where you can break down the signing algorithm into the sort of um hash chain evaluations. There are um a number of chains of There are a number of chained or hash queries that result in like sort of discrete public keys. And we can make a couple of simple observations. The first is that you really do have to make the base query of each chain to the random oracle or to the hash function.

Otherwise, there is a noticeable chance that you won't be able to sign certain messages. So, it's necessary for completeness. And then the other claim that I'm going to make that's should be easy to see is that if you take any partitioning of these um base queries, the larger of the two partitions exposing them to an attacker is going to let the attacker break the signature with um substantially improved concrete complexity. Right, so it's going to halve the concrete security level. So, a simple corollary of these two claims is that any two-party protocol that treats the hash function as a black box will permit one of the corrupt parties to um halve the security level of the signature scheme, and this is not acceptable.

All right, so that due diligence out of the way, what are the non-black box techniques we can use? So, to my knowledge, and I'm you know, happy to be corrected on this, it's that symmetric key functions generally don't have any useful structure for MPC. So, AES is a very minor exception to this rule. But by and large, the best that we can hope for is to use generic secure computation tools. Right, so like MPC, FHE, and so on. And there's a vast range of MPC protocols that you could use for this task, but we need to be careful about the choice because unlike previous situations where we've done MPC for threshold signing, the scale of the task is quite different over here.

So, to give an idea of this, the metrics that we usually care about when designing MPC protocols are I mean, there are multiple dimensions, but usually the more the most important ones are how many non-linear gates do you have to handle? That is, in particular, how many multiplications? Like, Boolean AND is just multiplication mod 2. And the other dimension we care about is how deep is the circuit? Like, how how inherently sequential is the computation that we're doing? Because this is going to translate into some complexity metrics down the line. So, as a point of reference in the classical setting, we have Schnorr and ECDSA. Like, ECDSA which is traditionally considered to be one of these you know, difficult to handle things in MPC and you know, has a decade of threshold signing protocol research at this point, has about two multiplication gates to handle and is

fairly low depth as well. Where Whereas for hash functions like SHA-256 or SHA-3 or Keccak, we have on the order of tens of thousands of non-linear gates to handle and the depth for most um symmetric key functions I can think of like SHA and SHA-256 and like Blake as far as I know, is on the order of thousands. Interestingly, Keccak is only 24 rounds or like only has a depth of 24, which makes which is a nice surprise when we're designing MPC tools. Like MPC protocols for this. But yeah, this is just for the hash function by itself.

This doesn't um this doesn't necessarily reflect the full cost of doing a signature because this is going to be a couple of orders of magnitude worse when we actually build a signature from this. All right. So, those are the metrics that we have to think about. And now working towards the deployment, right? So, what signature scheme, what um setting for the MPC do we choose? So, we fix a two out of three configuration as our target. That is, we have three nodes, each of which hold a share of the key. And any two should be able to sign. So, um logically, this is the honest majority setting.

Why do we choose this particular configuration? It has a nice balance between, you know, decentralization and also the ability to recover in the event of a fault and so on. And this is at least anecdotally, this seems to be one of the most common deployment scenarios um that we see in the institutional custody setting. Right? So, three nodes that have shares, but by default, there are just two active signing nodes. And these two nodes can be fixed. So, which signature scheme is target? The Winternitz scheme. So, this can be compiled upwards into XMSS once you generated the public keys. In particular, just as the previous talk said, the sensitive queries that have to be evaluated in MPC are the ones that go into the baseline or into the basic um

signature building block like like winter nets or I guess false or halls or whatever you're using for the underlying signature and then all of the the rest of the hash queries that you need to compile this entire XMSS or as it turns out Sphinx you can do outside of the MPC so that we regard as free operations. Right, and what paradigm do we use to actually construct our scheme? We follow this pre-signing paradigm that I alluded to earlier. So, this comes with a couple of advantages. The first is that signing is just a question of reconstructing the queries. So, this is really cheap or pretty much negligible cost once the you know pre-signatures have been generated. And also this allows us

to use all three nodes to actually generate the pre-signed state. Right, so the advantage of this is that three-party MPC with one corruption is sort of a special case of MPC or rather it's a it's a very useful starting point for MPC protocols. They There are a lot of tricks that are possible in the three choose one case that are a little difficult to generalize but give us you know very good efficiency in the um in this particular niche MPC setting. All right, so pre-signing as a paradigm is not new. This is already quite common or this is already um easy to achieve in the threshold ECDSA

context for example and also threshold Schnorr. So, why hasn't this caught on or at least anecdotally it seems that the fact that you need to keep track of state has been something of a barrier to adoption for pre-signing at least in the threshold ECDSA context or in the classical setting, but things are different now. So, for one the fact that you know we need to support one-time signatures and so on already means that we need to have some sort of state management mechanisms that are reliable and that we can deploy. So, we can you know extrapolate that pre-signing is not much of a jump from there.

And [snorts] the other is that entirely on-the-fly signing is much more expensive when it comes to hash based signatures relative to uh ECDSA or something. Right? So, the benefits of pre-signing really are a lot more extreme in the hash based signature case. All right. So, as a recap, Winternitz, which is the scheme that we target, entails a bunch of these hash these chained hash evaluations. Concretely, for the parameters that we consider, there are there are 35 chains and each chain has 16 sequential lottery evaluations. So, concretely, this results in 20 million gates or so that is spread across 384 layers.

Right? And what MPC protocol do we deem appropriate for this? Right? So, we follow this um I mean, we I'm happy to talk about this, you know, after this during the workshop and so on. But, uh it takes some effort to figure out what the right uh paradigm is. We go with this BGW paradigm where the number of rounds of communication for the protocol is directly proportional to the depth of the circuit that we're computing. So, this is going to be like hundreds of rounds, right? But, because we're doing this in a pre-signing phase, we can sort of absorb this cost and make sure that the you know, the the big downside of the BGW paradigm is this uh depth dependence, but as long as this is done during some time that's uh

you know, relatively cheap to do this computation and not going to filter through to actual online signing latency, this should be tolerable. So, basic three-party computation has this advantage of also being information theoretic, so we don't need to rely on any assumptions beyond um you know, like the secure channels and so on. But, we do optimize it with just PRFs, which again, this is a fairly conservative assumption. And semi-honest computation in the setting takes just one bit per party. Uh this is a classic result from 2016.

Um and to compile this to malicious security, which I should have mentioned, what we target by default is always malicious security. That semi-honest is um you know, a bit too weak as a baseline. So, we use these distributed verifier zero knowledge techniques. I mean, we mostly implement these protocols out of the box. We don't do any like we don't There's not much in the way of customized optimization or anything. So, we're able to get malicious security and amortized cost of less than one bit per gate. Right? So, this is sublinear overhead. So, end-to-end for this parameterization of Wintner's, it takes about 8 MB of communication that's spread across a few hundred rounds to generate a pre-signature. Right? And signing itself is like quite trivial.

So, the slightly non-trivial thing over here, at least with this distributed verifier zero knowledge paradigm, is just checking the computation cost because that it does need some um uh fairly tricky computations to do to verify. And um at the moment, the implementation that we have concretely takes you know, it we're able to do one one or two pre-signatures per second once you've accounted for the fact that we've that we're paying to um send these messages back and forth and so on. So, on average, if we're doing a large number of signatures in a batch, we can get more than one pre-signature per second. But again, with I estimate that this is just, you know, artifacts of our implementation. Probably with a tighter implementation and some better

engineering, I think we can get this to be more than an order of magnitude about an order of magnitude faster, at least in this paradigm. So, what are you working on next? We are, you know, experimenting with deployments. We're also talking to our partners to figure out, you know, is this mode of operation sensible? Does it work for you? Because this is like a little different from what we do for threshold ECDSA because we're using pre-signatures, we're using 3PC, and so on, like honest majority MPC. Um So, again, I'm happy to expand on these things like during the workshop. But um one of the points of difference is that we're using three-party computation instead of two-party computation where only two parties suffice to generate the signatures and so on. So, traditionally

going from 3PC to 2PC has I mean, it's quite expensive because uh depending on the MPC paradigm, for example, in this paradigm, in the BGW GMW sort of paradigm, this is probably an order of magnitude if not more than overhead uh switching from one to the other, but we can take advantage of certain structural um relaxations and that traditionally 2PC protocols and MPC protocols in general are studied for the setting where you really care about the security of every single bit of your input. And but hash-based signatures or cryptographic functions in general have this property that you can tolerate some leakage in the input. So, this helps a lot like the a lot of the overhead of these schemes like in the two parties in

the two party case is going from semi-honest to malicious security and that compiler to go from semi-honest to malicious can be a lot more efficient if you're allowing for leakage, right? So, concretely, one of the paradigms that we're exploring is using garbled circuits and traditionally it's you know um there's some security parameter overhead involved when you want to combine to malicious which you can which we can completely avoid. Something similar that there's something similar we're trying to work out with uh the more traditional OT-based GMW paradigm as well. Hopefully, you'll have some results to share on this soon.

Uh we're also considering alternative alternative modes of operation that prioritize different metrics, right? So, pipelining is one such mode where we have a sort of cache of sec cache of sessions that we that we maintain. So, if you want a signature right away without having to do um pre-signing ahead of time. You can get a signature pretty quickly because you have some session that's about to terminate at any given time. Right? So, again, happy to discuss more about this in the workshop and so on. And beyond this, we're also been sort of been thinking about what it would take to design an MPC-friendly signature like using standard tools, maybe one of the signatures that already exist. How's it going to be amongst the options that we have already for deployment? Which which of these are going to be more friendly to MPC and so

on. Right? So, in summary, we started our journey trying to design custom protocols for hash-based signatures and we showed that in fact there's only so far that you can go. Um this paper's on ePrint as of a couple of weeks ago, that we really have to use generic MPC techniques for this. So, it's well known at this point that uh we can do dealer-assisted threshold signing for a lot of hash-based schemes. And what we want to do is remove the dealer. Like as in the previous talk as well, we have a similar deployment condition, which is two-out-of-the-two-out-of-three setting.

And we can use MPC to replace the trusted dealer with reasonable efficiency. I should have mentioned this earlier, like the throughput that we achieve is actually quite similar to what we get for threshold ECDSA with certain schemes. Like there's like one pre-signature per second thing. And yeah, the I guess at this point we have to figure out what the trade-offs are for different approaches. Um Talk to people who are going to use this in practice to figure out what actually works and yeah, that's sort of where we are now. I'm happy to take questions and discuss more and so on. >> Okay, first question.

>> Yeah, um if you tried to like more like MPC-friendly um hash function the one-way function, say AES, if you tried to test it >> That's a good question. Yeah, so I mean MPC-friendly uh hash functions and so on. No, I mean we didn't consider like Poseidon or anything, but AES specifically I was very interested in this. So that's I'm as I understand it at different points in time in the literature, people have considered using AES to instantiate these signature schemes, but for some reason or the other they seem to have fallen out of use, and I'm trying to understand why.

Right so that aside, the savings what do we achieve relative to SHA-2, let's say AES is maybe about three times smaller, so you can reduce the throughput in the number Sorry, you can increase throughput in the number of gates by a factor of three maybe. Um but in terms of depth, it's actually worse than SHA-3, which I found to be interesting. So, let's say we swap SHA for AES. We can maybe increase our throughput by 3 4x, but maybe not an order of magnitude.

So, is that change or is that improvement in the MPC really worth you know, the rest of the ecosystem adapting to our using a different standard? Right? So, that I'm not so sure about. >> The AES might be only the first step, right? I mean, the we use SHA-256 for very different properties for what is required for signatures. >> Yeah. >> It seemed like overkill that we all pay for nothing that we don't need. >> Yeah, I agree. So, the the correct usage is a one-way function, not a like what it is now. >> you tried like like if you tried like friendly one-way function to to do it with like to do it with friendly one-way functions?

>> So, we can design this ourselves and benchmark it and so on. I but um none of the standards that are available for us to work with, to my knowledge, use AES, which is why we didn't really go down that path, but I would really like to discuss that as an option, like if it's really you know, something that the rest of the ecosystem is willing to use. >> Uh Sorry. Uh can you clarify a bit like your uh definition of black box in the case of the impossibility result? >> Yeah, so essentially we treat the hash function as a random oracle. So, because it's a random oracle, you can't put it inside a functionality to compute. So, it doesn't have a circuit representation is the point. So, there we're able to show like we're able to argue

um by looking at the queries that are made to this random oracle, um we're we're able to reason about um how much of it can be done in the clear versus how much of it, you know, is going to go to the adversary's view if you were to corrupt one of the parties. >> Thank you. If I understand correctly, um Silence Labs is a general purpose MPC shop, and historically you've looked at uh curve-based signatures, uh lattices-based signatures, hash-based signatures. What percentage of your time are you now spending on on the hash-based stuff?

>> Oh, um I don't know if I can assign a number, but a lot. >> A lot, okay. >> So, yeah, this is we are quite seriously looking at productizing this. >> Uh-huh. What would you say is the top priority within Sign a Labs now? >> I would say it's equal to lattice-based signatures at the very least. >> Okay, same roughly the same as lattice-based, okay. Got it. >> Any further questions? If not, thank you so much. Yes. >> [applause]