M.Sc Thesis

M.Sc StudentCohen Tzafrir
SubjectResponsive Round Complexity and Concurrent Zero-Knowledge
DepartmentDepartment of Computer Science
Supervisor PROF. Erez Petrank


The number of communication rounds is a classic complexity measure for protocols; reducing round complexity is a major goal in protocol design.  However, when the communication time is varies between different rounds, and in particular, when one of the parties intentionally delays its messages, the round complexity measure may become meaningless.  For example, if one of the rounds takes longer than the rest of the protocol, then it does not matter if the round complexity is bounded by a constant or by a polynomial.

In this paper, we propose a complexity measure called responsive round complexity.  Loosely speaking, a protocol has responsive round complexity m with respect to Party A, if it makes the following guarantee:

If A's longest delay in responding to a message in a run of the protocol is t, then, in that run, the overall communication time is at most m·t 

This guarantees a quicker response to a party that replies faster whereas a party with a slow connection (or that delays its answer) has a worse guarantee.

We demonstrate the significance of responsive round complexity by presenting a new protocol for concurrent zero-knowledge. The new protocol is a black-box concurrent zero knowledge proof for all languages in NP with round-complexity  but with responsive round-complexity . While the round complexity of the new protocol is similar to what is known from previous works, its responsive round complexity is a significant improvement: 

All known concurrent zero-knowledge protocols require  rounds.  Furthermore, in light of the known lower bounds for black-box concurrent zero-knowledge protocols, the responsive round complexity of this protocol is basically optimal.