[freehaven-dev] (FWD) paper comments - 1st impressions

[Roger Dingledine <arma@mit.edu>]

----- Forwarded message from dmolnar@belegost.mit.edu -----

From: dmolnar@belegost.mit.edu
Date: Sat, 24 Feb 2001 00:00:13 -0500 (EST)
To: Roger Dingledine <arma@mit.edu>
cc: freehaven@freehaven.net
Subject: paper comments - 1st impressions

My first impresions on each of the comments. Agree or disagree?

On Fri, 23 Feb 2001, Roger Dingledine wrote:

> before citations to make them easier to read: ~\cite{}. Biblio:
> full citation for refs 11 and 29, please.

OK, this can be fixed. 

> pick a mix. If this was not a bad one, thanIi have a chance of q/(m-1)
> to pick a bad mix for the second time and so on.

I need to sit down with Feller and the paper, but this is probably true. 

> You write:
> the chance of picking no bad MIXes is (1-(q/m))^k, since the sender
> picks k Mixes...
> If there are 5 MIXes and 3 of them are bad an I want to pick 4 MIXes,
> than the chance of picking no bad MIXes is 0 i believe....

Oops. 

> ______________________________________________________
> Reviewer 4: Score 50
> 
> Review summary: Severe practical problems associated with the
> requirement for everybody to read everything all the time.

Yes and no. You could do periodic updates or reads, if you're willing to
accept a risk of being behind. Maybe we can quantify that risk..

> Very strong
> trust assumptions (that are not clearly stated). No clear advance.

OK, we can state the trust assumptions. (We probably need to derive them
first, unfortunately). 

No clear advance - this is a new way to do reliability/robustness. It
works. It doesn't have the nasty overhead in the MIX protocol itself that
the Flash MIX and companion protocols do. So I dispute that there is "no
clear advance." I agree that we haven't formulated it clearly enough. 

> Many meaningless statements about digital cash, weak treatment of the
> related work.

We need to make the distinction between "remailer reliability via
economics" and "remailer reliability via proofs" more clear. This is
currently only briefly covered. They hit us for this in the treatment of
related work below - and justifiably so. 


> Detailed comments: There are two types of mix networks: Synchronous
> and asynchronous. Yours is asynchronous. Many of the other mix
> networks you refer to are synchronous. The comparison is probably not
> always meaningful, but you must point out the differences in trust,
> model, and guarantees.

Good call. We should do this. In general the related work could be fleshed
out. In particular we need to distinguish our way of acheiving reliability
from the distributed MIX method. More on that below. 


> You do not speak of robustness. That is the term normally used to
> describe the reliability of the mixing. You do not have a model that
> describes what you assume, and what can be done. You also do not have
> any claims of what you get. The goals on page 5 are unclear, and
> insufficient without any description of the model.

the model was supposed to be what we did in section 8. the goals on page 5
are informal goals which we try to later make formal. 

So maybe one way to address this would be to move the model earlier.
Oh, and the model needs a hell of a lot of work. But we knew that. 

> Page 1: You say "Since shutting down ... for adversaries." I do not
> understand what you mean and how that lead to the next statement.
> Page 4, section 2.4 "some kind of digital cash". Why only like that?
> Why not accounts? Makes no sense.

We should talk about recompense or payment more generally, without
discussing digital cash unless we really need to do so. The point still
stands that there's no good way to pay MIXes in place.


> Page 4, sect 3. "negligible probability" should be "negligible
> advantage". Define "passive adversary"! Otherwise it is a meaningless
> statement. The part about traffic analysis being in its infancy is not
> convincing. 

This goes back to the model being moved up earlier in the paper. then we
can define a passive adversary. Negligible advantage is correct.


> It is well understood how to perform traffic analysis if
> you have unbounded (but polynomial) resources. That is the kind of
> attack you have to consider!

It is? I mean, it is the attack we have to consider, but I didn't know
that it was well understood. Show me the papers. 


> Page 5: you require that the ledger is fully trusted. This is not made
> clear. Why should I trust the ledger and not the servers? Why will
> the ledger not constitute a bottleneck? Alice would have to read ALL
> information available at the ledger. Otherwise, she reveals what
> messages she is interested in checking the routing of. That means that
> she has to read everything ALL the time -- stopping to be interested
> would also reveal that the message has been delivered! 


Why do we need to check immediately after the message has been delivered?

>This is
> amazingly inefficient. If you read selectively, a lot of information
> can be gleaned. That might be devastating.

First, yes, we need to make the trust requirements for the ledger more
explicit!

This is a major area for future work. Something to alleviate this
partially might be David Hopwood's suggestion.
Private Information Retreival is a possible, but impractical, response.


> p 7. "Unambiguous etc"> You are saying that D(E(m1))=m2 -> m1=m2. This
> is absolutely standard, and it is meaningless to have it any other
> way.

Yeah, I thought so too, until talking to Anna and Chris. We should
probably cook up some example to show how this might not hold for
different public keys, then argue that we only need to worry about the
same public key. But yes, this could be simplified. 

> p 7 Do you need timestamps? By whom? If you trust the ledger anyway,
> it only has to write down the time, no real time stamp.

What do they consider a real time stamp? 


> p 9 "hash cash". Why such a solution? How do you verify the
> correctness of an "access token"? If this has a cost associated with it
> that is not way smaller than that of generating a random string and
> submit that, it can still be abused for attacks. So it won't
> work. This seems to be irrelevant to the remaining paper, and not
> described in sufficient detail.

Mike?

> p 14. If you prove misbehavior, you give out identifying information,
> as you state somewhere. That is a very low degree of robustness. A
> last mix server on the line could always replace the outgoing message
> with what he feels like. Will he be reported? The dummy messages you
> suggest are the only way to do that. You give a feeling that things
> are more secure earlier on. Carefully state what you achieve, early
> on.

the message substitution attack is a good call. 


> p 18 why is commercial remailers originally a cyberpunks idea, and why
> is that relevant? It was Chaum's idea, wasn't it? Why would you need
> to use digital cash? This opinion is not supported at all.

Did Chaum come up with *commerical* remailers or just *remailers*? Mike,
do you know?

I vote to duck the issue by saying that remailers originated with Chaum,
and that the cypherpunks discussed making them commercial for a long time. 

> p 18 Yes, it is known how to make universally verifiable mixes. Many
> of the mixes you quote as related work have that property.

Universally verifiable via the use of ZKPs which prove that all MIXes
worked correctly. Except for the Desmedt-Kurosawa MIX from Eurocrypt 2000
which isn't just ZKPs. 

In any case, these give us assurance that the MIXes behved according to
protocol, but they require much computational overhead on the part of the
MIXes and the users. Plus they're complicated to implement. And sometimes
the protcols aren't right...

We have a lot of overhead as well, but we don't need as much of a chance
to existing MIX practice. (i.e. no ZKPs). Plus we are going after a
different approach than they are for providing reliability. 
 
But yes, we need to address this distinction, because otherwise it makes
us look like we haven't read the related work. 
(the not-so-subtle implication from both of these reviewers). 

> p 18 How would you distribute the ledger? What do you mean?
> Quorum control? Why is a distributed ledger better?

Roger?

> ______________________________________________________
> Reviewer 5:Score 50
> 
> The paper discusses a simple MIX-type network, and a reputation (or
> rating) system for such a network.  It tries to present some details
> formally, but in general it is extremely verbose.  

Guilty.

>Given that there is
> nothing new in Sections 1-4, it could easily be condensed into 1/3 of
> the pages, and I strongly recommend to do this. You should also avoid

OK. We should spend the time instead on distinguishing ourselves from
related work. 

> lengthy presentations of trivial statements, like "Ciphertext
> Collision Free Encryption;" please note that decryption is usually
> deterministic, and in any case correctness requires that almost always
> D(E(m)) = m for correctly chosen keys.

Again, we could probably get away with showing why PK schemes aren't for
multiple keys, then showing that they are for single keys and then that
we're ok with single keys. 

> 
> Regarding Sections 1-4, I disagree with your statement "The
> reliability and efficiency of MIXes have been a secondary concern."
> Reliability is the main motivation for using majority threshold
> decryption for MIXes (your bibliography contains several such articles
> ...).

Actually, I read those papers as trying to acheive anonymity via a process
which can't be compromised unless k out of n MIXes are compromised. as in,
anonymity with better guarantees against traffic analysis. So time to look
at them again. 

The point we should probably look at here is that our protocol requires
less modification to existing MIXes, and that it's a new idea for MIX
reliability. 


>  Ensuring synchronization among mixes and implementing a public
> ledger is probably the most expensive part of most mix schemes, i.e.,
> I don't think your overall design is more realistic than, e.g.,
> threshold mixes a la [6]. Most of the modern scheme implement public
> verifiability.

Public verifiability via ZKPs, usually. Again, we're trying to explore the
"other route." 


> 
> Sections 5-9 are somewhat new, but offer no surprises.  There is no
> discussion on active attacks. For instance, usually a mix network

Yes, this is a good point. We should explicitly say what we can do about
these attacks. Another reason for moving a model earlier. 

> guarantees anonymity as long as one mix is honest. Now assume there is
> only one honest mix. If it is easy to prevent this one honest mix from
> acting quickly senders will complain an happily bridges this mix and
> thus is giving up her anonymity.

This is what dummy messages are for. (we know now)

> Or another example: if users choose
> mixed according to their reputation then an adversary might simply try
> to offer the best and most reliable service on many mixes, so that
> often only his mixes are chosen.

Didn't we say exactly this in the paper? If not, we should...  

> Your calculations in Section 8-9 are too simplistic.

Yes. 

-David


----- End forwarded message -----