[messaging] Provable (private) conversation while allowing (somewhat) precise redaction

[Tamme Schichler]

Am 07.10.2014 um 02:17 schrieb Robert Ransom:
> On 10/6/14, Tamme Schichler <tammeschichler at googlemail.com> wrote:
>> Hi,
>>
>> normally I just read this list but something just came up in a
>> conversation and I can't find any existing solutions:
>>
>> Let's say A wants to talk with B privately (not necessarily securely,
>> but there can't be witnesses since the content of the conversation may
>> contain private matters). The problem is that B has a history of lying
>> about such conversations, so A wants to be able to prove as much as
>> becomes necessary to deflect allegations, but also little as possible to
>> protect the privacy of either side or third parties (or the other way
>> around, as usual the solution would ideally be symmetric).
>>
>> It's possible to use OpenPGP to get somewhat near the intended
>> behaviour, but the chunks that would become unverifiable would become
>> very large. (If you quote the last message you received and go for a
>> strictly alternating conversation you lose unilateral proof for two
>> messages for any redaction in them.)
>>
>> Ideally it would be possible to redact (but not reorder!) on word
>> boundaries without revealing how much was redacted, while also not
>> publishing signatures for the redacted parts (since they would be short
>> and too easy to brute-force, at least as I understand the topic).
>>
>>
>> I can sort of imagine a scheme that would allow this, but it would have
>> relatively heavy overhead and is far from anything I know in terms of
>> existing programs. (Basically it would create signed versions for all
>> eventualities, at least per message, during the conversation.)
> 
> The obvious approach is as follows:
> 
> * Create a ‘commitment’ to each chunk that you might want to reveal
> independently.  (Probably one for each word and/or line.)
> * Sign a concatenation of the commitments in order.
> * Send that signature and message, together with the ‘opening’ of each
> commitment, to the intended recipient(s).
> 
> You should be able to easily find a better definition of ‘commitment
> scheme’ somewhere online than I can give you right now.  The important
> feature is that, given the commitment alone, one cannot test whether
> it is a commitment to a given value.
> 
> One example of a commitment to a message m is H(r, m), where H is a
> ‘hash function’ and r is a nonce chosen uniformly at random from a
> large set; the opening of that commitment is the pair (r, m).
> 

That's about as far as I'd gotten previously. It would also be important
to include a conversation nonce and message sequence number (with
possibly random starting point) if the commitments are uncompressed.

What is your take on requiring the disclosure of how many messages where
omitted? That _something_ was omitted is important information that
should be impossible to leave out, and I don't think that "this many
messages occurred" is sensitive information by itself, since there would
be no specific meta-data whatsoever.

> 
> One can easily transmit the list of openings of all the commitments in
> a list of chunks, as required for the redactable signature protocol,
> by generating the sequence of nonces using a stream cipher, and then
> transmitting the sequence of messages and the stream cipher key.  Or
> one can generate the nonces in a tree structure, which allows some
> compression of a redacted signature as well.

Hm, that would definitely be useful.

> Unfortunately, someone who learns a fully expanded redacted signature
> under one of those schemes can't re-compress it.  There is a way to
> allow the recipient to merge nonces in a tree structure: given a
> parent-node nonce r with children r_1, r_2, ..., r_n and a hash
> function H (used as a PRF here), compute r_i = H(r, i) for i<n and r_n
> = r + r_1 + r_2 + ... + r_{n-1} (where + denotes addition in some
> commutative group, probably XOR of bitstrings).
> 

I'm not sure how merging the nonces would help, but the stored/replayed
message could just include merge instructions: If the lowest-level
hashes are made by hashing the message chunk together with the nonce, it
would be enough to have a signature of the root node.

It would also provide proof of the message ordering (if the
concatenation _isn't_ commutative) and with random branching the amount
of redacted chunks can be hidden. It would be necessary to insert random
empty chunks though, to avoid creating a lower bound for the number of
redacted messages.

Nodes where only the hash is known would show up as [redacted] during
the verification, since it's unknown how much (if any) content they have.


This is a lot better than my initial idea of automatically signing the
chunks with a sliding window, which is what the OpenPGP approach would
look like with more granularity. Thanks!

> 
>> It would be great if any of you knew a tool that allows a conversation
>> of this kind to take place.
> 
> I've thought of writing one, but I've never actually had an application for it.
> 
> 
> Robert Ransom
> 

I unfortunately don't have the time/motivation to do this in the near
future, so it's another thing for my list of currently suspended projects.


Tamme