[Cryptography] ZK meeting scheduling protocol?

[Ray Dillinger]

On 01/14/2017 06:51 AM, Henry Baker wrote:
> As most of you already know, Microsoft Outlook provides some protocols for helping to schedule meetings via email.
> 
> Has anyone developed a zero knowledge protocol for such scheduling?

You mentioned zero-knowledge proofs but I do not see one in your
protocol requirements.  I'm assuming there isn't a ZKP going on
here. If I'm wrong, then who are Peggy and Victor?  What is
Peggy trying to prove and what is Victor trying to verify?

Otherwise this looks like the classic "Byzantine Generals"
problem, with additional security/privacy requirements.  The
additional security/privacy requirements look a lot like multi-
party Diffie-Hellman key exchange, or possibly look like they
might be accomplished using a Dining Cryptographers' Network.

At first blush I'd say something like "multi-party Diffie-
Hellman exchange or Byzantine-Generals protocol, either with
message blinding, or carried out over dining cryptographers'
network," but that's before analyzing the problem carefully,
and the communications overhead for either of those over a
DCN would be pretty cumbersome.

So start by reading up on those classic protocols.  But first
get a firm idea of the requirements in your mind so you can tell
when and how those protocols do and don't match them.

Now.  When attempting protocol design, you start with three
basic questions.


Let's consider.  First, what are your objectives?

1.  Before the protocol, Alice, Bob, Carol .... Xavier,
    Yvette, Zebulon want to schedule something but each
    has constraints on the time slots available during
    which they can schedule it.

2.  After the protocol, either they have determined some
    common time slot that doesn't violate any of their
    constraints (protocol success) or have determined
    that no such time slot exists (protocol failure).

Second, what are your security requirements?

1.  If anyone, including the participants, learns anything
    specific about the schedule constraints of any
    participant, beyond the fact that all have the agreed
    timeslot available or that no such time slot exists,
    then the protocol violates the privacy requirement.

2.  If a nonparticipant can determine what time slot has
    been agreed on, or determine that no such time slot
    exists, then the protocol violates the confidentiality
    requirement.

3.  If a nonparticipant can influence or choose which of
    several possible time slots are chosen, (for example
    by redirecting or resequencing protocol messages
    between participants) then the protocol violates the
    authenticity requirement.

4.  If any two participants can be led to have different
    beliefs about whether a common time slot is available or
    about which that time slot is, then the protocol violates
    the consistency requirement.

Third, what's your threat model?  ie, what are the capabilities
of the attackers trying to cause the above failures?  All the
attackers are assumed to have public keys but no private keys
of all participants.

1.  Eve (eavesdropper) is assumed to be present and will
    monitor the channels hoping to learn things about the
    participants' schedules, including but not limited to
    the event they're trying to schedule in this protocol.

2.  Eve's Big Sister Nessa (traffic and metadata analyst)
    will be monitoring traffic patterns and will learn
    something about schedules violating confidentiality if
    the sequence or direction of messages depends on any
    participant's (or any subset of participants') match
    or mismatch with a proposed schedule.

3.  Mallory (who can also intercept, change, block, redirect,
    or fake messages), is also a fairly constant threat.
    There's really no way to prevent Mallory from performing
    a Denial-of-Service, but that's essentially the same as
    saying you have to be able to communicate at all.

    Mallory must never get the opportunity to present an
    arbitrary string of bits that will get signed by a
    participant's private key, (not even in a protocol that
    will be aborted due to later detection of protocol
    violation) and no message from any participant, including
    messages exchanged in a previous or aborted iteration
    of the protocol, should be meaningful if Mallory
    misdirects it to a different participant or replays it
    to its original recipient.  Either of these conditions
    can lead to virtually any security violation.

4.  Sybil (malefactor pretending to be several participants)
    appears to be excluded because all participants have
    each others' private keys, and if they're scheduling
    meetings and know which private key corresponds to which
    participant they'd notice if the relation isn't 1-to-1.
    This is important because Sibyl can easily mount an
    undetectable denial-of-service in any agreement protocol.

5.  Trent (who normally does something beneficial but can
    screw people over by acting in bad faith) appears to be
    excluded from consideration here because if a Trent were
    tolerable this protocol would be trivial and you wouldn't
    even be thinking about it.

Those are the big five; if there are any other relevant
threat models for this protocol who are they?



-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20170115/5448713a/attachment.sig>