waxwing on Nostr: After a chance to really dig in - this post was *way* too optimistic! Unfortunately. ...

After a chance to really dig in - this post was *way* too optimistic! Unfortunately. The idea that you could split out the secret(s) for signing and then do IPFE efficiently like that doesn't work as simply as I thought. As per the referenced paper (and the two others in 2015/16) you can do IPFE on standard DL groups (like secp), sure, but the output of the decryption step only gives the curve point, not the scalar (so not the s you need for signing, but sG), and some of the language around that in the papers confused me initially. It works for secrets in restricted ranges because you can just do a DLOG calculation, but not for a 256 bit space. There may be a way round that with Paillier instead of El Gamal (see eprint 2015/608), but it's complicated. Also, my idea of splitting the signature into two parts: vector 1 being [k_1^-1, k_1^-1 * p] ("half of the nonce" is k_1, private key is p), and vector 2 being [k_2^-1 * e * (R_x+1), R_x * k_2^-1] and the dot product of these is equal to the signature, and calculating R_x as k_2 * K_1 - all this so an initial setup could construct ciphertexts of the first vector then ditch the private key ... this line of thinking may still be promising but it's really tricky to create it in a way that is secure.

#cryptography

quoting nevent1q…qe2h

A bit tricky to explain this but let's try:

In the summer Jeremy Rubin proposed "F-ed up covenants" which was the idea of making covenants on bitcoin without an op code, using functional encryption. Basically the idea of FE is "you don't have a key that lets you decrypt encrypted data, you have a key that lets you decrypt the result of a function, F, on encrypted data". And he used that to get a signature on a transaction to be outputt-able by decryption, but the "functional" part restricted it so it would only work if the transaction hash was some value, e. This means that only the covenant-preparer's intended transaction could be signed over, assuming the "root" private key had been permanently deleted on setup. (and this could be repeated indefinitely for different covenants after an initial setup).

Very clever idea and I commented on it here at the time. The problem was, as Jeremy himself well understood, that the function he proposed being complicated (something like "ECDSA-sign(private key + hash, over message which is hash)") is complicated and there is no functional encryption scheme that we know that can do this efficiently. More or less.

So I've spent a couple days writing it out, and I *think* you *can* actually do this using the simplest kind of functional encryption which is inner product functional encryption. There are several twists, though. First, it only works for ECDSA not taproot (I'll explain that to anyone that asks). Second, what we want out of this is different from the toy "calculate student's grade average from encrypted grades" use-case example that's quoted in papers; we want to calculate the ciphertext of the private key, throw it away, then calculate decryption keys separately for each new transaction that we want to covenant. I found a way to do that but with a huge limitation: we need a server to be able to calculate the one-time use decryption keys; we can *still* throw the original private key away, immediately, but we need these "decryption secrets" per use case. However, I think this can be done with a simple blinding, such that a decryption-key-generating server doesn't need to see anything when creating them. Given this, one simply needs to use the El-Gamal encryption scheme "over" the functional encryption (see https://eprint.iacr.org/2015/017.pdf ) to allow anyone to output a valid ECDSA signature from an inner product of the one-time created ciphertext for the private key, combined with the user's individual nonce and transaction data.

fwiw the nastiness of trusted setup one-time privkey creation doesn't bother me so much; it can probably be MPC-ed which is good enough. But the need to do (albeit blinded) calls to some server to create the one time decryption keys is quite nasty. If there were a trick to get round that, AND there was solid enough security analysis to say that this actually works, then I'd call this a huge advance. For now it's a bit pie in the sky. I'll try to make a toy implementation along with a writeup, when I get back to my desk.

Original f-ed up covenants post: https://delvingbitcoin.org/t/fed-up-covenants/929

#cryptography