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

[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).


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.

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).


> 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