The perfect escrow

Part I. The Nativity Scene.

00011111 Unrelated, picked up an interesting tidbit today at the math lib. It is possible to provably secret-share an RSA prime.
01011011 Oh ?

00011111 (Provably in that each recipient knows that he has k shares of prime P, that prime P really is a key, and that there exists l, l>=k, such that l shares can be reconstituted to P.)
01011011 A, this is already used in multisig btc txn neh ?

00011111 Not as far as I recall.
01011011 But yes. That's how that's implemented I thought.

00011111 There an address is just connected to more than one ECDSA key, like the famous missile launcher consoles with two keyholes.
01011011 Is it ? My understanding of it is vague, i've never deployed the thing

00011111 bitcoin.it/wiki/BIP_0010. No clever math, just a protocol field. Normal secret sharing is easy (Shamir's method, maybe 100 others) but /provable/ sharing is hard.
01011011 Aha yeah. I see.

00011111 Normally a share is indistinguishable from garbage, but for some applications you might want to let the share holder know that he has an actual share of something. The reason I tell you of the 'provable secret-splitting' recipe, is that there is plenty of confusion re: the distinction between 'protocol' - which can be broken or ignored - and actual crypto mechanics, which suffer no such problem.
01011011 Indeed.

00011111 And you're among the few people who appears to know the practical difference.
01011011 It boggles me why should these be few.

00011111 Because nobody wants to lift a finger and do so much as arithmetic.
01011011 I guess.

00011111 Btw, here's the recipe itself. citeseerx.ist.psu.edu/doi=10.1.1.59.6696 wonder if anybody's reduced to practice. Hm, it isn't quite the magic pill I thought it was on first glance. You can probably see what's missing.
01011011 I don't have anythging that can read pdfs here. It'll have to be later.

00011111 What's missing is the part where you can actually prove that it's part of a given private key. All you can prove with their zero-knowledge scheme is that it is a 'safe prime'.
01011011 Lol well that's not proving much.

00011111 Their term for one that doesn't set you up for a Pollard-Rho diddling. Yeah. Damn I hate these wankers.
01011011 I mean basically... this is less than useless.

00011111 Right. Eh, I always bring home a crate of goodies, and then they evaporate on a close read. But my hunch is that this particular conundrum is solvable in the general case. (consider the trivial case of an RSA scheme with p1,p2,...pn instead of the usual 'p, q').
01011011 You could perhaps make a special modulus that is usable both in RSA and this application.

00011111 (Each shareholder can trivially verify that his p divides the private modulus.)
01011011 Something perhaps like Lamport's scheme.

00011111 Right.
01011011 Actually wait. The Lamport scheme is exactly right here. Let us have a rng and a 256 bit hash function. Select 256 pairs of 256 bit integers ; distribute all these pairs to n people where n < 256, by some scheme. Everyone can verify that in fact his pair is the correct pair to match signature bit i, where i is his cardinality. And the proper 256 bits multiplied together give a pretty large prime. "prime".

00011111 Well, an arbitrary set of bits can be wangled into an actual prime. chosen through some one-to-one mapping.
01011011 But see, your large RSA doesn't have to be prime, just a product of primes. So basically, lamport signing + making the 256 bit numbers primes -> multitx RSA.

00011111 Right. I might've gone there when I was on my 'why don't they blockchain MPEx...' kick.
01011011 You wanna write the paper of this ?

00011111 Mebbe. Life's short though.
01011011 If you do by all means. If not I'ma make a blogpost of it.

00011111 Go right ahead. Ideas are cheap.
01011011 You sure ? This'd actually end up a quoted paper, better use it if it can help you any.

00011111 Nah, I've exited the paper mill business.

Part II. Wherein it's all explained.

Asymmetric key cyphers based on the factorisation problem work something like this : pick two large prime numbers, these will be your private key. Multiply these together, this will be your public key. Inasmuch as it's hard for someone to discover the two factors on the basis of the product, but it's easy for you to obtain the product from the factors, you can then both encrypt stuff with your public key and decrypt it back to the clear text with your private key, whereas someone else can encrypt all he wants but can't decrypt at all.

Lamport signatures work something like this : if you have a random number generator and a hashing function which outputs 256 bit hashes, you can create 256 pairs of 256-bit numbers. These will be the private key, allowing you to sign. You then proceed to hash each of the 256 pairs of numbers, obtaining 256 pairs of hashes, each 256 bit long. This list of hashes will be the public key, which may be shared with the world.

To sign a message, you hash the message, then for each bit on the hash : should the bit be 0, you include the first number (not hash!) in the pair at that cardinality ; should the bit be 1, you include the second number in the pair at that cardinality. This creates a list of 256 numbers, which have some interesting properties : 1) anyone can verify they're in fact the numbers which created the original public key, by hashing them ; 2) nobody can use them to sign a different messageⁱ. Obviously should you reuse the same key to sign a different message you'll be leaking key bits and eventually your key can be brokenⁱⁱ.

Now, there's no reason to not use these two together. Consider the case where you generate 256 pairs of 256bit prime numbers and multiply them all together. The result is still a RSA public key, albeit a really large oneⁱⁱⁱ, which we'll call the extended, or full public key. You publish the hashes of all the 256bit pairs along with this large number, then hash it and publish the corresponding 256bit numbers for each cardinality, just like you did in the case of Lamport signing. This trivially allows the reduction of the public key to a half-length reduced, or actual key (by simple division of the long key by each of the 256 published factors).

What's left after this procedure are 256 shards of prime which together constitute a RSA private key (albeit a really large one) and a 65kbit public key, which anyone can independently calculate (by division, from the 128kb published extended public key and the 256 256bit numbers used in the signature). Should you now distribute the 256 original pairs of 256bit numbers to 256 different parties, each individual party can verify that indeed both numbers in its pair were used in the making of the extended key^iv, which in point of fact means they can verify they own 1/256 of the private key corresponding to the public key in question.

Should two of these parties collude, they would be twice as close to bruteforcing the private key. Should a total o 248 such parties collude, they'd have enough data to reduce the public key about to the strength of current keys. Once 255 of the 256 parties collude, the key has been broken (as the last factor can be obtained through simple division). Obviously there is no practical requirement that a max cardinality of 256 be used, you could create 10 or 1024 or any arbitrary number of shards, just as long as you have a hash function that produces that sort of output (which in practice implies you'll be better off making 256 shards and distributing them equally to say 4 people^v, each getting 64, rather than making a 4 bit hash function). There's no similar upper bound however, there's nothing to prevent one from creating billion-pair long keys (outside, of course, of the relative expense of good entropy - which incidentally will be a thing of the future, we'll have entropy farms like today's solar and wind farms).

I won't go into the economic and social implications of this item, but perhaps practical applications for it may be found here and there.

1. For a reason very much reminiscent of Cantor. [↩]
2. Much in the way codebooks work, for that matter. [↩]
3. Standard today seems to be 4kbit, with 8kbit regarded as extravagant and 1kbit unsafe. 256 pairs of 256bit numbers comes to 128kbits. [↩]
4. Or, more practical, that the not-published half of their pair actually divides the reduced public key. [↩]
5. Superficially this scheme may appear to require someone with knowledge of the full key, in order to multiply the numbers together into the extended key. Tis notion lasts up until you consider that the 4 people could each multiply their 256bit primes independently, and then just share the product, to be multiplied into the extended key. This is considerably safer than sharing a common RSA public key, even should there be as many as 64 different parties instead of just 4. This scheme therefore does qualify as zero knowledge. [↩]