# 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^{i}. 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^{ii}.

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^{iii}, 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.

———- For a reason very much reminiscent of Cantor. [↩]
- Much in the way codebooks work, for that matter. [↩]
- Standard today seems to be 4kbit, with 8kbit regarded as extravagant and 1kbit unsafe. 256 pairs of 256bit numbers comes to 128kbits. [↩]
- Or, more practical, that the not-published half of their pair actually divides the reduced public key. [↩]
- 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. [↩]