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.