Aggregate Signatures for protecting hotwallets (AKA Luke Wallets)

[SantT]

***A friend advised me to post this idea here for public scrutiny from the
cryptographic community, so here it goes:



 I have been thinking about a cryptographic problem I had, and I believe I
have found a solution to it that might be of some use for cryptocurrency developement.
Someone coined the
term "Aggregate Signatures" for what I was trying to achieve.
I hope of some kind of feedback as to the feasibility of this
method, as to the best of my knowledge this is used nowhere else yet and
creating ones own mixture of cryptography comes with a huge risk! However
since below you will find that my method is merely a direct application of
existing cryptography, I strongly believe this would be successful in real
world applications.


Hotwallets are a known and unfortunately necessarily vulnerability in any
deployment of cryptocurrencies, so I wondered how to make them more
secure. Then I wondered if they could be split up into pieces?
Some research suggested this for ECDSA signatures:
https://bitcointalk.org/index.php?topic=81865.msg901491#msg901491
https://bitcoin.stackexchange.com/questions/3853/can-one-safely-buy-vanity-addresses-from-a-third-party-without-risking-ones-coi
The way this works is that 2 keys can be (modulo) added to generate the
final combined key.

The next question for me was to ask if the same application could be
transferred to the signatures themselves? In essence: would it be possibe
that one entity creates a (invalid) signature to the final combined key,
but that it would become only a valid signature after the last (modulo)
multiplication with the second part of the key?
If a*b=c, then Sig(a)*b=Sig(c)

After trying for several weeks to unsuccessfully transform the ECDSA
s= (z+r*x)/k
(where x was a combination of a*b) in order to create a protocol that
would allow this "aggregate-signing" that I envisioned, I learned quite
some things from my mistakes, like letting k leak out or allowing one
entity to learn both parts of the key, defeating my goal of splitting it
up. :-)
It was only when I came across a paper describing "RSA treshold
signatures" (now I know the cryptographic name at last!) and the pallier
cryptosystem, that I realized I had found the missing link: homomorphic
encryption that supports addition AND multiplication.


There are different possible schemes, but basically you need n+1 entities
for n keyparts. (The transmitting/Homomorphic  decrypting entity can be recycled for 3 parts and above.)
Each entity n creates a building block for the signature and
encrypts it with the public key of a chosen common homomorphic encryption
scheme. Then each next entity adds its own encrypted building block to the
signature. Finally the last entity decrypts the (now valid) combined
signature without ever learning the combined key, and broadcasts it to the
network.
Like this:

Enc(z)/Enc(k1)          + Enc(r*a)       /Enc(K1)
Enc(z)/Enc(K1)*Enc(K2)  + Enc(r*a)*Enc(b)/Enc(K1)*Enc(k2)

equals:

Enc(z)/Enc(k1*k2)       + Enc(r*a*b)/Enc(k1*k2)

if k1*k2=k and a*b=x
equals:

Enc((z+r*x)/k)   which decrypts to a valid ECDSA signature by the
broadcasting entity.

Also note that the combined k (ephemeral key is the correct term I
suppose?) renders the Klepto-SETUP described early january 2015 unusable,
unless both of the entities are compromised.
https://www2.informatik.hu-berlin.de/~verbuech/klepto-ecdsa/klepto-ecdsa.pdf
And off course faulty RNG are also similarly thwarted.



Now what about other non-Bitcoin cryptocurrencies like Monero?
Well, I do not know if ECDSA signatures are used as building blocks of
Ring Signatures, but I guess it is possible to modify whatever
signature scheme you have to create this "Luke wallets" (from lukewarm, as
in neither Hot nor Cold. ;-) that vastly better protect users wallets.
Exchanges that employ these Luke Wallets can distribute their
wallets over different operating systems, hardware, physical locations
etc... to better withstand various forms of theft, and as long as certain
safegards in the protocol are in place, no one can gather the needed parts
to re-build the combined secret key that was once generated at a given
place and time in the past.



As I do not have coding ability, a POC cannot be provided, however there are some
Open Source libraries available, like
https://code.google.com/p/thep/
so for somebody who already got his/her feet wet, it should be straightforward to
 implement. Unless offcourse some of the real cryptographers here can immediately
point out weaknesses or errors, but then please consider this as the beginning of an Open Source effort and pool all the comments etc... together for the general benefit.

As I want to remain anonymous, I will sign this with the private key of my adress
- 12ADZcBhHrWpKNoyWTRDEerkz7wJbWeyjK - so I can proveably claim this idea later, if ever.***



Everything between *** is used for signing and verifying this message.
The resulting signature is:

HMgk/qXEc4q2y/MtTp4Mp0nyzjs0mjMY/JNGLkpLCmkHL+7iUy2wX2a5qICer7ZOHiPsf2+ycBSUDsfvCv7f2kI=

Edit: this is rather cumbersome (using preview) to get consistently verifying messages with Bitcoin Core.
Perhaps PGP/GPG-style message format with the --------- could be adopted in the future?

[1714608378]

1714608378

[1714608378]

1714608378

[1714608378]

1714608378

[gmaxwell]

What you're doing is normally called a threshold signature or multiparty signature.  An aggregate signature is usually used to refer to a scheme which takes tuples {message1, pubkey1, sig1}, {message2, pubkey2, sig2} and yields {[message1, message2], [pubkey1, pubkey2], sig12}.

In Bitcoin we have a multisignature scheme which is widely deployed and used by many parties-- any 3xxx address is likely this.  In Bitcoin our digital signature scheme is not ECDSA directly, but Script.   The pubkey people use is either a template for a program or a hash of a program which Bitcoin outputs are marked with,  the multisignature scheme is just to specify a program that includes multiple pubkeys and a OP_CHECKMULTISIG that expects multiple signatures.

There is some efficiency loss in this, but for thresholds less strict than N of N they gain a very useful property of recording in an irrefutable way _which_ of the parties signed.

In the second part of my presentation at https://www.youtube.com/watch?v=TYQ-3VvNCHE  at 19 minutes in I present several useful criteria for candidate multisignature schemes under the mnemonice ACEUP:

Accountable -- authorized parties should be able to tell who signed after the fact and prove it to others.
Composable -- you should be able to take other people's threshold keys and make a threshold of thresholds, so that your own use of threshold security doesn't remove your ability to be a member of a threshold
Efficient -- the size and verification performance should be minimized
Usable -- the scheme should not require excessive round trips or other such burdens
Private -- The scheme should minimize disclosure of the access policy.

The Bitcoin CMS it's Accountable, potentially somewhat composable (though not with current software), not efficient, though usable, but not private.

If something is using schnorr signatures--then s = k - xe and a native multisignature is trivial (and implemented, for example, in libsecp256k1). I am quite confident we will just support that with Bitcoin in the future.
Though the native efficient multisig fails accountability, there is also work on other schnorr based schemes that retain accountability while meeting the other criteria which I mention in that ACEUP presentation.  Pieter recently implement one of them and presented on it: https://www.youtube.com/watch?v=gcQLWeFmpYg

At a first look it you may have reinvented (or be on the road to reinventing) the scheme of http://www.cs.princeton.edu/~stevenag/threshold_sigs.pdf  but it's not clear to me--  in your example you don't make it clear how the decryption works. If you just have a single party (say party 2) that has the pallier decryption key then that party can decrypt a partial then recover the nonce and extract the group private key from the whole signature (or a users partial from the partial).  I think to be secure you must have distributed pallier key generation and distributed decryption which adds much complexity and a(n) additional round-trip(s).

[TooDumbForBitcoin]

I guess it is possible to modify whatever
signature scheme you have to create this "Luke wallets" (from lukewarm, as
in neither Hot nor Cold. ;-)

Just doing my part to raise the NSR (I'm all N, no S) .....

Consider using the term "warm wallets".   "Luke wallets" would carry a highly charged connotation in some circles, obstructing useful discussion (kind of like this post).

[SantT]

...

Thank you Mr. Maxwell for your reply and pointing my attention to the Princeton paper! I'll read trough it and give my remarks as I go:



I would say at first glance that Luke Wallets are not based on Treshold Secret Sharing or Treshold Cryptography as described in 2.3, since ALL the parts are needed to construct a valid signature. This is probably a semantic issue on my part, as I have just described a special case of the above.

In 3.3 they say their homomorphic decryption key is also distributed, while in Mackenzie and Reiters scheme only one of the parties has the decryption key. The latter is like in my proposed scheme: the "transmitting entity".

The usercase why I developed a scheme like mine, was an exchange/owner that wants to automate payments without relying on a hotwallet. This implies that the owner already has an adress/secret key and splits it up into shares on different systems, which then automate the payments in a lineair fashion. i.e.
a (bootstrap+add first share) --> b (add share)--> c (add last share, decrypt and transmit to blockchain)
In the paper this equates to the Trusted Dealer case. A dealerless protocol was not on my mind, but it looks very interesting for those who would need it.

I did not add checks or proofs in my protocol: if the final signature is invalid, it is not transmitted or will be rejected by the network. As I am not a cryptographer or mathematician there is doubt if this would impact security, aldough I don't think so. I would follow the professional team from the paper if there is any doubt, but please elaborate why someone would choose for the extra overhead.

3.4 Par. 1: There is no publication date on the paper, but it appears to be published first on March 8 2015. I found the solution to my problem in Januari but it was not untill April that I made a first limited disclosure to some academics, and a few days ago I followed their advice and made everything here - after months - public.
Given my lack of academic background and thus knowledge of all the previous papers they mentioned on treshold and other cryptography, it would have taken me a very long time to write something even remotely close to the quality of their paper. It is clear they made a breaktrough long befor I did, so for all means and purposes they were first. Just ignore the signature etc... from the first post in this thread. :-(
So for a long and detailed overview of the reasons, threat models, advantages and issues involved with the creation of this type of wallets, I'll refer to their excellent paper. For a very much simplified user case nedding vastly less rounds of interaction, maybe my scheme is still usefull.

I like the treshold determininistic adress derivation!

6.3 Describes the number or the size of shares for each participant in the Princeton scheme. Maybe I misunderstand, but it seems that for larger amounts of participants, the size of each participants share also increases?
In my proposed scheme, the number and size of shares per participant is contant (just one: Xi or more accurately Xi/k, which both have the same size as the final combined private key X = sum(Xi) )
Also in my scheme all the shares are of equal value, so there is no attack vector like an administrator/outside attacker awarding himself extra shares and thus "votes" like described in 6.5 (apart from him stealing the combined private key at the dealing step, which is a universal risk in both schemes.)

Changeing shares or policy would require a complete set of new shares in my scheme. The Princeton scheme is a lot more fine grained.

7.6 Only a few seconds of computing time on a smartphone per signature is very acceptable! One of the remarks I got from the academics who recieved my preview, was that Homomorphic encryption was not fast and efficient enough to be used in cryptocurrency signing. I know they use rather large signatures, but still this seems fast enough for the end user, while professional users like exchanges could probably use more cores or parallellisation to increase the troughput.



That was it.
Regarding your remarks in the post above:
- I do not have time this week to look at the 2 youtube presentations. Next week I'll make an effort.

- (I am typing this as I go.) An s=k-xe Schnorr signature at first glance does not seem compatible with my scheme, as I do not think Pallier supports substraction calculations, but then I realized the cyclic/modulo nature of the cryptography.
If for example A-B mod n cannot be done, the substraction can be calculated separately, like (n-B), and that result can then be added to A, thus: A+(n-B) mod n which would fit into Pallier.
When one looks at the dials on a clock, which is thus mod 12, then 7 - 4 would then be 7+(12-4) = 7+8 = 15 = 3.
So I think my scheme could be adapted in this way to Schnorr Signatures.

- I see now what you mean, as my example was not so well illustrated. Basically each party multiplies the intermediate signature with his own partial, divided with his own ephemeral key ki, like (Xi/ki). This "blinds" the partial against the next party in the chain (and provides Klepto- and faulty RNG protection since the ephemeral key is now also combined.)
To do the above, the message hash "z" must be "bootstrapped" by dividing trough the combined private key. (Which will be stripped away by the next parties as they multiply everything with their Xi/ki)
This raises the pressing issue that:
- the bootstrapper knows the combined private key and you lose the no-hotwallet-advantage
- if you mediate the above by using Pallier, then the second party can just decrypt everything, calculate z and get the inverse of the combined private key
Therefore at least 2n+1 parties are needed (=min 3) as the last party now only has access to the intermediate private key.
The same tought experiment can be done with the partials of the ephemeral key k, with the same 2n+1 result.
Biggest advantage of my scheme would then be that only 3 rounds of Pallier must be done, as from then on the intermediate signature can be multiplied with the Xi/ki blinded partials by each additional party without Homomorphic overhead.
If you write everything out on analog media (paper ;-) it becomes very clear where the issues are.

Greetings!