Storing messages in the Bitcoin network - a steganographic scheme

[Ryo]

Hello everyone.

I'm a computer scientist with some knowledge in cryptography. I wrote a paper describing a way to implement steganography inside the Bitcoin network: that is, storing hidden messages inside the network, that would be available only to those who knew where (and how) to look.

I tried to write it in a simple language, so that it could be understood by anyone. The only part that's a little bit technical is the security analysis. I would be happy to receive comments and provide explanations if needed.

The paper can be downloaded here for 1 BTC
http://www.bitcoinservice.co.uk/files/86

There is no implementation, as it is only a proof of concept. An actual implementation would be relatively easy to build from the official client, and I might do it if there was some demand for it (and maybe a bounty ).

Here is the abstract from the paper:
    The Bitcoin peer-to-peer network creates a dis-
    tributed, anonymous virtual currency. We claim
    that this network can be used to store informa-
    tion in a secure way. We propose a very sim-
    ple steganographic scheme as a proof of concept.
    That scheme is related a difficult graph theory
    problem (finding a maximal clique of a graph)
    and as such, provides good guaranties if prop-
    erly implemented. We give pointers as to what
    a proper implementation would be, and the con-
    clude by giving some thought to the impact on
    the network that such a scheme would cause if
    it became widespread.

[Hal]

Your name (in the paper) is Nakamoto? Are you any relation to Satoshi?

[Ryo]

Answering positively that question would give information regarding Satoshi's identity. Since he may not want that, I hope you'll forgive me if I don't answer either positively or negatively

[mico]

I doubt that Ryo is Satoshi =) Satoshi wouldn't ask 1 BTC for this paper =)

[Ryo]

I'm not pretending to be Satoshi. A simple statisical analysis of the paper would show that it was written by a different person.

[davout]

So everyone who'd like to join the discussion and debate on your paper has to pay 1 BTC ?
Meh.

[Ryo]

I'm not working for free - what a surprise. I'm not going to explain my reasons, they don't matter at all. I'm sure the ideas will leak at some point, and if I make a few bit-bucks out of this I'll consider myself paid.

<edit>Here's an offer: someone buys the same article for 25 BTC here http://www.bitcoinservice.co.uk/files/94 and I'll release it for free under a CC BY-SA licence.</edit>

I'm also currently studying how an egoistical miner could abuse cooperative mining operations to maximize his profit, and I expect to post the result of that study in a few days. If there are other areas someone would want me to take a look at, feel free to ask.

[Gavin Andresen]

I paid for the download; nice little paper.  And interesting choice of pseudonym.

Are you submitting it somewhere to get it peer reviewed?

And do you mind me asking what you mean by "I'm a computer scientist with some knowledge in cryptography" -- are you a professor, grad student, postdoc, graduated-with-a-degree-in-computer-science-and-now-working-in-industry ?

[davout]

I'm also currently studying how an egoistical miner could abuse cooperative mining operations to maximize his profit, and I expect to post the result of that study in a few days. If there are other areas someone would want me to take a look at, feel free to ask.

Have a look at the what-if-a-mining-cartel-colludes-for-its-own-advantage threads if you haven't already.

[Ryo]

I paid for the download; nice little paper.  And interesting choice of pseudonym.

Thank you.

Are you submitting it somewhere to get it peer reviewed?

Not yet. I'm not academically active in the field of steganography, so if I ever want to submit it to a journal, I'll have to brush up a little. The paper lacks comparisons with other graph-based steganographic schemes. Providing an implementation would help, too. I might do it, but I have funnier things to do and other papers to finish. Papers I'm paid to work on Let's see if it gathers interest first.

And do you mind me asking what you mean by "I'm a computer scientist with some knowledge in cryptography" -- are you a professor, grad student, postdoc, graduated-with-a-degree-in-computer-science-and-now-working-in-industry ?

I used to work in industry, but I got bored. Now I'm back in academia.

Have a look at the what-if-a-mining-cartel-colludes-for-its-own-advantage threads if you haven't already.

I read that a while back, and I had forgotten that it was still somewhat undecided whether cartels were dangerous or not, thank you for remining me of that thread. Maybe I will try to work this out later. For now, I'm focusing on another way to strategically use mining pools. I'll start with simple ways, conforming with the rules, before searching for ways to cheat. I'm currently trying to find whether some miners are already using those tactics.

[Anonymous]

An interesting paper. Does adding extra information into the block chain punish everyone by increasing block sizes and transaction fees ?

We are starting a mining investment club and your input would be valuable. is it beneficial to have many people running the pool for transparency reasons?  One person by themselves could cheat imo. Many eyeballs and all that . 
http://bitcointalk.org/index.php?topic=2884.0 

[Ryo]

An interesting paper. Does adding extra information into the block chain punish everyone by increasing block sizes and transaction fees ?

Thanks. Adding extra information does punish every user a little, but not more than adding a few users to the network. I don't see this become widespread or being used to store large amounts of data, so it shouldn't be a problem. But it might be used to pass secret messages, Twitter-style, with no real effect on the network.

We are starting a mining investment club and your input would be valuable. is it beneficial to have many people running the pool for transparency reasons?  One person by themselves could cheat imo. Many eyeballs and all that . 

I will have a look at that after finishing the paper on "abusing" mining pools. I guess this article will be of interest if you plan on creating your own pool anyway.