Wednesday, January 24, 2018

NP problem-based signatures - scaling signable data

For fun, I proposed a crossword puzzle-based signature scheme. It suffers a rather serious limitation. I expect one can securely sign a single bit of data in a one-time fashion with it, but security falls apart as you go above a few bits. Even a single bit likely requires two puzzles, one solved to indicate a 1 and the other solved to indicate a 0 (as partial solutions to the whole key degrade the key massively).

The attraction of NP complete problems is the idea that the difference in complexity of signing, versus complexity of forging, can be made arbitrarily large, and that we have very high assurance this is true. That by itself does not guarantee the system is practically secure with today's technology, nor does it (by itself) say what signing complexity must be chosen for the complexity of attack to exceed some target threshold, but it seems like a good first step. Any such problem can be used to sign one bit, but can any such problem be scaled to much more than that? For any given number of bits x, one can make a composite key out of 2x smaller keys, so if we fix X in advance (at any value!) the answer is yes. But again, simply being NP complete does not guarantee security in practical applications on today's hardware. It seems improbable that crosswords would be a good way to secure terabytes under this scheme.

Sunday, December 24, 2017

Intrinsic uses of bitcoin

One often sees the false assertion that bitcoin has no intrinsic use in the sense that one can use gold to make jewelry (although such use a counts for a tiny percent of overall market cap in gold.)

Bitcoin does have intrinsic uses. For example, one can encode a hash value of arbitrary data in a transaction for purpose of depositing that hash on the blockchain, which is an immutable record. Thus, it is like a trustless spin on a public notary. There are other intrinsic uses which leverage the double spend protections to implement trustless mechanisms for tracking transfers and exchanges of physical or other virtual assets, via rigorous analogy to bitcoin - by encoding representations in literal bitcoin.

When seeing the assertion that there are no intrinsic uses, it may be worth asking how well researched the piece as a whole is likely to be. These uses have been recognized for some years now.

Thursday, December 21, 2017

How do you authenticate this blog? Why not use Tesla / DCKR?

If I used HTTPS, then you might decide to trust each and every one of the zillion CAs selected by your operating system and/or browser, to not vouch for this site unless someone paid them money for a certificate and if that person also had control of this domain, and then you might hope that person furthermore happens to be me. This seems to be a popular choice.

Or... you can view a summary of the site, current as of 12/21/2017, here:

You could also download and record this signature for safe keeping (quickly - it expires Monday!)

You could then come back a week (or more) later to see if I have signed anything else. If I have, you could download that signature as well, then check the three inputs (signature, data, newer signature) with this python 3 script:

That program would use the more recent signature for the purpose of extracting the key used to sign the first signature, so it can then check that signature for validity. It would then go on to confirm that this key relates to my public key. Of course, encoded in that script is my public key, and maybe someone tampered with it or else with the algorithm itself? So as a one-time exercise, you would want to confirm that you truly have the correct script. This would have to be done out-of-band, for example you could call me and ask me to confirm the sha1sum checksum (which happens to be 28867e62adb0271779f75509cc91f76acdb9afca, not that you should trust this post on that last point.)

This script is of course a prototype, but why not give it a spin? Later, I might implement a crossword puzzle signature as well.

Monday, December 18, 2017


For 78.4% of American history, money was understood to derive its value from one or more precious metals.