[vgb2k11]

>Assuming that I can exchange keys of some sort (physical, digital) with the other contact.

Each contact has an identical table of data (pure-random, 1 terabyte, ASCII 256 or choose your own encoding); this is your "Key of some sort". Messages sent between contacts are encoded character-by-character as offsets from the start of the table. No offset can be used more than once. After offset 1099511627776 (for a 1 terabyte files) has been used for encode, a new key file is generated and exchanged.

Example:

tables contains a terabyte of random data such as "ahx Ui D 7gu3a7NrdMr 9y&S )iM AAt 8'9s 98m..e kj j uhbd f..."

1,5,6,9,12,15,18,20,23,25,30,33,35,36,39,41 = hi garry it's me

[y7]

If you're gonna go through the trouble of exchanging 1TB of one time key, use a standard one time pad. This method is either insecure (when offsets are not strictly ascending), or unnecessarily wasteful.

[vgb2k11]

After searching the definition of one-time-pad, I'm pretty sure post is redundant and shall be deleted (in T-minus 2 minutes). [edit] No delete option. Mod please delete.

[MatthewWilkes]

There's a subtle flaw in your design here. You're selectively discarding data with meaning and those decisions can be seen and you are not being strict enough with your rules about reuse of data. Although the user doesn't have to use the first possible index according to this scheme, chances are they would (and you did in your example)

The short form of the problem is where you say "No offset can be used more than once." where you actually want "No offset can be used unless it is higher than all previously used offsets".

Consider an assassin and their controller using this scheme for designating targets. Garry is first, the controller sends

  10, 13, 16, 19, 22 = garry

The security services intercept this and notice that garry is killed.

They now know that 0-9 != g, 11-12 != a, 14-15 != r, 17-18 != r, 19-21 != y

They suspect that either andi or rory is the next target, the controller orders Andy killed and sends:

  0, 15, 17, 27 = andi

The security services can then infer that the person to be killed is matched by the regex:

  ^[^g][^r][^r].$

andi matches, rory doesn't.

It's much better to treat your random characters as numbers to add to the your data mod 256 (in your ASCII 256 example), and also set rules like fixed message length and scheduled messages that can be 'no-op'.