Cryptographic
`
`Protocol
`
`for
`
`Trustable
`
`Match
`
`Making
`
`Robert W. Baldwin
`
`and Wayne
`
`C. Gramlich
`
`of Technology
`Institute
`Massachusetts
`Cambridge,
`MA 02139
`
`Abstract
`
`goals of anonymity
`conflicting
`with
`A problem
`and
`a cryptograpKlc
`is defined
`authentication
`and
`is presented.
`The
`the
`problem
`protocol
`that
`solves
`scheme
`that
`provides
`protocol
`uses an authentication
`and
`authentication.
`the
`desired
`degree
`of anonymity
`Fake
`transactions
`are used to detect
`active
`attackers,
`and to camouflage
`information
`that
`cannot
`be Kldden
`cryptographically.
`
`1.
`
`that
`
`Introduction
`the
`privacy,
`personal
`values
`In
`a society
`services must
`carefully
`balance
`designers
`of computer
`anonymity
`and accountability.
`the trade-offs
`between
`If
`a service,
`such
`as a community
`bulletin
`board,
`provides
`total
`anonymity,
`people
`are likely
`to abuse
`it. On the other
`hand,
`a service,
`such as an electronic
`library,
`that
`keeps
`strictly
`authenticated
`records
`for
`accountability
`purposes
`presents
`a major
`opportunity
`for
`the
`invasion
`of
`privacy.
`The
`problem
`is
`that
`authentication
`is the basis for accountability.
`
`by Chaum in [3], a system designer
`As argued
`have
`tools
`that
`allow
`some
`measure
`of
`should
`without
`loosing
`the ability
`to control
`who
`anonymity
`is
`authorized
`to
`use
`the
`system
`and
`who
`is
`Some
`tools
`have
`for
`accountable
`unusual
`activities.
`already
`been developed.
`The
`problem
`of anonymous
`electronic
`voting
`(only
`authorized
`people
`can
`vote,
`and each person ~votes
`at most
`once)
`is solved
`in [2].
`The
`tool
`developed
`to solve
`the voting
`problem
`is a
`protocol
`that
`allows
`a user who trusts
`the behavior
`of
`a single
`computer
`to trust
`the cooperative
`behavior
`of
`several
`computers.
`The problem
`of oblivious
`transfer
`information
`to
`an
`unauthenticated
`(transferring
`destination
`without
`revealing
`to all
`listeners)
`has
`been
`solved
`using
`commutative
`encryption
`functions
`[1].
`
`it
`
`CH2150-l185iooOOloo92$Ol
`
`.0001985
`
`IEEE
`
`92
`
`tools,
`of additional
`In search
`at
`problems
`that
`explore
`anonymity
`and authentication.
`
`it
`the
`
`is interesting
`relationship
`
`to look
`between
`
`has
`and
`a
`
`poses and solves a problem that
`paper
`This
`requirements
`conflicting
`for
`anonymity
`authentication.
`design
`The
`problem
`is
`to
`protocol
`that
`can be used to implement
`cryptographic
`matchmakhg
`server
`in a ciktributed
`a computerized
`computing
`environment.
`a
`Such
`server
`receives
`wishes
`from its users (e.g., person A wants
`to be hired
`a
`by
`company
`B),
`and
`notifies
`them
`whenever
`matching
`wish is found
`(e.g., company
`B wants
`to hire
`A).
`person
`For
`the
`users
`to trust
`the
`system,
`they
`need to use it anonymously.
`However,
`what
`a match
`occurs,
`they
`need to authenticate
`the
`identity
`of
`the
`other
`party.
`That
`is, users want
`to be authenticated
`to each other,
`but not
`to the matchmaker.
`
`and
`two
`clarify
`Sections
`three
`of
`goals
`the
`by
`defining
`problem
`matchmaking
`To illustrate
`system and the goals of an attacker.
`section
`resources
`and
`goals
`of
`the
`attacker,
`describe
`a simple
`solution
`and
`its weaknesses.
`full
`solution
`is
`presented
`in
`section
`five
`correctness
`argument
`is given
`in section
`six.
`
`and
`
`the
`the
`the
`four
`The
`a
`
`for
`
`Risk
`
`Free
`
`2. Requirements
`Matchmaking
`The
`matchmaking
`by
`considering
`managers.
`Imagine
`new vice-president
`vice-presidents
`does not want
`person
`currently
`want
`to
`announce
`Neither
`party wants
`wishes
`unless
`they
`matcK]ng
`wish.
`
`goals
`of
`requirements
`the
`and
`system (see figure
`2-1) can be motivated
`the
`problem
`of
`hiring
`high-level
`that
`a corporation
`wants
`to hire a
`from among
`one
`of
`the
`current
`its
`competitors.
`of
`The
`corporation
`a
`job
`announce
`the
`opening
`and
`to
`employed
`by a competitor
`does not
`F& or
`her willingness
`to
`leave.
`to reveal
`information
`about
`their
`know
`that
`the other
`party
`has a
`
`

`
`a
`
`by introducing
`can be resolved
`impasse
`This
`the
`corporations
`that
`is trusted
`by both
`party
`thkd
`employees.
`the
`and
`an
`electronic
`Unfortunately
`a distributed
`In
`easy
`is not
`to trust.
`matchmaker
`their
`own
`local
`environment,
`users
`trust
`computing
`the behavior
`of
`of
`but
`they
`are suspicious
`computer,
`service
`to be
`other
`computers.
`For
`the matchmaking
`trustable,
`the
`privacy
`of a user’s wish must
`depend
`primarily
`on the behavior
`of
`the user’s
`computer
`and
`not
`on the
`behavior
`of
`the matchmaker.
`To reduce
`their
`dependence
`on the matchmaker’s
`behavior,
`users
`do not
`reveal
`their
`identities
`to the matchmaker.
`It
`must
`be possible
`to use the service
`anonymously.
`
`does happen,
`a match
`When
`the match
`is real
`and
`that
`be sure
`to
`a corporation
`could
`try
`example,
`its employees
`by pretending
`of
`wishes
`makhg
`offers.
`corporation
`To
`avoid
`the
`users must
`be able
`fake match,
`the other
`party
`involved
`in the match.
`anonymity
`requirement,
`the authentication
`of
`based on the behavior
`the user’s
`computer
`on the behavior
`of
`the matchmaker.
`
`to
`the users want
`For
`not
`faked.
`the
`figure
`out
`to be another
`the
`risk
`of
`to authenticate
`As with
`the
`should
`be
`and not
`
`a
`
`to benefit
`is intended
`service
`The matchmaking
`notification
`a joint
`its users,
`so it must
`have
`all of
`occurs
`both
`requirement.
`That
`is, when
`a match
`parties
`are notified.
`It would
`not
`be reasonable
`to
`notify
`an
`employee
`about
`a match
`without
`also
`notifying
`the corporation
`(and vice-versa).
`
`should
`
`degrade
`wishes
`of
`privacy
`The
`a small
`If
`compromised.
`are
`keys
`as
`gracefully
`number
`of
`expose
`a large
`could
`keys
`of
`number
`amount
`of
`would
`focus
`a large
`attackers
`then
`wishes,
`when
`the
`on those keys expecting
`a high
`return
`effort
`trusting
`keys are compromised.
`Users would
`not
`risk
`such
`a system.
`Graceful
`degradation
`of privacy
`can
`as
`be
`viewed
`the
`equivalent
`the
`common
`to
`that
`requirement
`large systems
`be resilient
`to failures.
`Failures
`in the security
`mechanism
`that
`reveal
`secret
`keys
`are
`bound
`to
`happen,
`so the
`system must
`be
`designed
`to limit
`the amount
`information
`exposed
`by
`More
`generally,
`the
`amount
`of
`such
`a
`failure.
`information
`available
`to an attacker
`or
`the amount
`of
`damage
`an attacker
`can do should
`grow slowly
`with
`the number
`of keys the attacker
`knows.
`
`goals of
`The main
`summarized
`in figure
`2-I.
`common
`goals
`of database
`
`system are
`the matchmaking
`The system also meets
`two
`transactions
`are
`servem
`
`change
`and
`the
`
`the state
`bandwidth
`number
`
`of
`
`(repeating
`idempotent
`of
`the
`database),
`and
`requirements
`increase
`users.
`
`them does not
`space,
`time,
`linearly
`with
`
`1. Anonymity
`
`of Users
`
`2. Authentication
`
`of Matches
`
`3. Joint Notification
`
`of Matches
`
`4. Graceful
`
`Degradation
`
`of Privacy
`
`Figure
`
`2-1:
`
`Goals of
`
`the matchmaking
`
`system.
`
`of
`
`3. Goals
`Attacker
`the
`Resources
`and
`this
`solved,
`being
`the
`problem
`clarify
`To
`people
`of
`resources
`the
`goals
`and
`describes
`section
`who might
`try
`to attack
`the system.
`The general
`aim
`of an attacker
`of
`the matchmaking
`system is to find
`out
`other
`people’s
`wishes without
`participating
`in a
`match.
`A list of an attacker’s
`goals
`is given
`in figure
`3-1.
`
`who
`1. Learn
`participating
`
`the
`is using
`in a match.
`
`system without
`
`2. Find
`it.
`
`out
`
`a user’s wish without
`
`matching
`
`3. Determine
`matching
`
`whether
`interests.
`
`a
`
`two
`
`users
`
`have
`
`the attacker
`notification.
`joint
`4. Prevent
`in the wish,
`the parties
`involved
`is one of
`to finding
`out
`goal
`is equivalent
`then
`this
`a user’s wish without
`matching
`it.
`
`If
`
`5. Make
`match
`
`user
`a
`occurred.
`
`incorrectly
`
`think
`
`that
`
`a
`
`Figure
`
`3-1:
`
`Goals of an attacker.
`
`does
`
`problem
`The matchmaking
`is available.
`that
`the
`service
`access
`to
`the
`to
`deny
`users
`extract
`information
`is
`trying
`to
`trying
`to manipulate
`a user’s
`or
`false matches.
`
`insuring
`not
`try
`attacker
`service
`causing
`
`include
`not
`Attackers
`do
`service.
`An
`from the
`behavior
`by
`
`range
`A wide
`to an attacker.
`
`of
`
`to
`is assumed
`resources
`All
`transmitted
`information
`
`be
`
`available
`
`93
`
`

`
`by
`the
`
`local
`their
`important
`
`A
`is trusted.
`which
`computer,
`non-resources
`is given
`in figure
`
`stored
`list
`of
`3-3.
`
`4. Matchmaking
`To illustrate
`guard
`against,
`must
`matchmaking
`protocol
`
`in an Ideal World
`solution
`the attacks
`that
`a correct
`a simple
`this
`section
`describes
`and points
`out
`its weaknesses.
`
`a human
`after
`is modeled
`solution
`simple
`The
`4-1.
`See figure
`begins
`protocol
`The
`matchmaker.
`their
`about
`the matchmaker
`telling
`user
`with
`each
`records
`the names
`of users
`wishes.
`The matchmaker
`and
`their
`wishes
`in a database
`which
`is indexed
`by
`the wishes.
`Whenever
`two
`people
`are interested
`in
`the
`same
`wish,
`a match
`has
`occurred,
`so
`the
`matchmaker
`notifies
`both
`parties.
`
`two users,
`of
`in terms
`is expressed
`The protocol
`server
`hf. A wish
`such
`A and B, and a matchmaking
`both
`users,
`and
`it
`is
`as “A hkes B“
`is the same for
`represented
`by W. Sending
`a message, X,
`from A to B
`is denoted
`by A–>B: X.
`
`1.
`
`A->M:
`M stores:
`
`W, A
`W,
`
`{A)
`
`2. M->A:
`
`ok
`
`3. B->M:
`M stores:
`
`W, B
`W,
`
`{A,
`
`B3
`
`4. M->B :
`
`ok
`
`5. M->A:
`
`Match
`
`for W
`
`6. M->B :
`
`Match
`
`for W
`
`Figure
`
`4-1:
`
`A Protocol
`would work
`
`that
`for matchmaker
`if all parties were trusted.
`
`If
`
`simple
`the
`used
`service
`a matchmaking
`could
`attacker
`an
`4-I,
`shown
`in
`figure
`protocol
`list
`of
`3.
`The
`in section
`all
`the
`goals
`listed
`achieve
`be determined
`either
`by
`the
`service
`could
`of
`users
`the matchmaker,
`or
`by
`messages
`sent
`to
`watching
`the matchmaker’s
`storage.
`In both
`cases,
`the
`readkg
`of
`users
`appear
`unencrypted.
`Reading
`the
`names
`mat chmaker’s
`storage
`is
`particularly
`attractive,
`because
`the wishes
`of ail users
`could
`be determined.
`The
`privacy
`of
`all wishes
`is
`compromised
`if
`attacker
`can read the matchmaker’s
`storage.
`
`an
`
`available.
`is
`the
`by
`stored
`information
`Any
`attacker.
`to
`the
`is available
`program
`matchmal&g
`receive messages
`can send
`and
`attacker
`the
`Further,
`to any host and can perform
`all
`the publicly
`available
`cryptographic
`transforms.
`A list of
`these resources
`given
`in figure
`3-2.
`
`is
`
`1. Record messages.
`
`2. Send messages.
`
`3. Block messages
`
`from being
`
`received.
`
`4. Read the matchmaker’s
`
`storage.
`
`5. Perform
`
`public
`
`transformations.
`
`6. Subpoena
`matchmaker.
`
`any
`
`secrets
`
`known
`
`to
`
`the
`
`Figure
`
`3-2:
`
`Resources
`
`of an attacker.
`
`The
`attention.
`special
`deserves
`resource
`One
`The
`secrets.
`the matchmaker’s
`can subpoena
`attacker
`problem
`difficulty
`in solving
`the matchmakhg
`main
`used to
`discussed
`in thk
`paper
`is that
`the
`computer
`run
`the service
`is not
`under
`the
`control
`of a trusted
`the
`administrators
`of
`the
`party.
`In
`particular,
`matchmaker’s
`computer
`can
`find
`out
`static
`secrets
`known
`to the matchmaker
`program
`keys
`compiled
`into
`the program).
`
`any
`(e.g.,
`
`1. Determine
`
`the source of messages.
`
`2. Read
`or
`computer.
`
`write
`
`storage
`
`on
`
`a
`
`user’s
`
`3. Write
`
`the matchmaker’s
`
`storage.
`
`4. Observe
`
`computations
`
`inside
`
`a program.
`
`5. Modify
`
`the matchmakhg
`
`program.
`
`Figure
`
`3-3:
`
`not available
`Resources
`an attacker.
`
`to
`
`is traffic
`list
`on this
`not
`resource
`The major
`can
`be
`traffic
`tracing
`on
`based
`Attacks
`message
`forwarding
`anonymous
`by
`an
`one
`described
`in [2].
`Another
`such
`se the
`in the list
`is the ability
`to read
`not
`included
`Any
`in
`a user’s
`computer.
`the
`storage
`that
`the users need to remember
`can be
`
`tracing.
`thwarted
`service
`resource
`or write
`information
`
`94
`
`

`
`is to cause fake
`of an attacker
`goal
`Another
`mat ches.
`that
`goal
`is to
`way
`to
`achieve
`A direct
`pretend
`to be the matchmaker
`and send a message to
`the
`user announcing
`a match.
`The
`direct
`approach
`works
`because
`the protocol
`does not
`authenticate
`the
`An
`indirect
`method
`to
`to
`matchmaker
`the
`users.
`cause a fake match
`is to pretend
`to be the other
`user
`involved
`in
`the match.
`For
`example,
`when
`the
`attacker
`sees that A has sent a wish to M,
`the attacker
`could
`pretend
`to be B and submit
`a matching
`wish.
`The
`problem
`is that
`the
`users are not
`authenticated
`to the matchmaker.
`
`his
`that
`is to learn
`goal
`attacker’s
`The
`users).
`the
`to
`the matchmaker
`without
`allowing
`wish matched
`in
`the wish.
`notify
`the
`other
`user
`involved
`The
`the
`his
`wish
`until
`attacker
`delays
`submitting
`all old wishes.
`matchmaker
`is about
`to delete
`If
`a
`blocks
`the notitlcation
`match
`does occur,
`the attacker
`sent
`from the matchmaker
`to the
`other
`user.
`The
`matchmaker
`might
`retransmit
`the
`notification,
`but
`only
`that will
`happen
`a small
`number
`of
`times
`before
`entry
`the wish
`is deleted
`and an attacker
`could
`block
`all
`those retransmissions.
`
`The
`to
`
`ability
`correctly
`network
`faking
`
`to
`
`and the
`a match
`fake
`to indirectly
`user’s
`wishes
`by
`a
`determine
`ability
`complementary.
`recording
`are
`messages
`not
`users
`are
`works
`because
`Indirect
`also
`but
`that
`the matchmaker,
`authenticated
`attacker
`cannot
`authenticate
`wishes.
`the
`means
`that
`attacker
`cannot
`tell
`if
`a wish
`was
`an
`That
`is,
`the
`person who
`claimed
`to submit
`it.
`by
`submitted
`hand,
`if users where
`authenticated
`to
`other
`On
`the
`indirect
`faking
`would
`not work,
`but
`the matchmaker,
`tell which
`wishes were
`real.
`An
`could
`the
`attacker
`the protocol
`presented
`in the next
`aspect of
`important
`is the
`amount
`of authentication
`information
`section
`accompanies
`each message.
`There
`is enough
`that
`information
`for
`users
`to
`authenticate
`their
`own
`but
`matches,
`not
`enough
`information
`for
`a third
`(including
`party
`the matchmaker)
`authenticate
`users involved
`in a match.
`
`to
`
`ion
`authenticate
`lacking
`to
`ad~ltion
`In
`also
`protocol
`in the simple
`the messages
`information,
`could
`An
`attacker
`information.
`lack
`integrity
`the
`and
`then
`it,
`intercept
`a message, modify
`The
`recipient.
`intended
`modNied
`message
`to
`the
`the
`not
`detect
`receiver
`of
`such
`a message
`could
`that
`the
`sender
`tampering.
`A further
`problem
`is
`intact.
`In the
`cannot
`tell
`that
`the message
`arrived
`returns
`an
`simple
`the
`matchmaker
`protocol,
`acknowledgment
`to the user, but
`the acknowledgment
`does not
`tell
`the user what wish was
`received
`by the
`matchmaker.
`
`send
`
`simple
`The
`notification,
`joint
`of
`notification.
`joint
`assumption
`that
`delete
`old wishes
`prevent
`the
`delivery
`(persistently
`blocking
`
`the goal
`to meet
`appears
`protocol
`can avoid
`attacker
`a clever
`but
`on
`the
`is
`based
`attack
`The
`eventually
`must
`the matchmaker
`to
`ability
`attacker’s
`and
`on
`the
`of messages
`number
`of a small
`delivery
`would
`be detectable
`by
`
`5. Risk
`
`Our
`tools
`several
`these
`First
`will
`protocol
`protocol meets
`
`Matchmaking
`Free
`uses
`problem
`solution
`to the matchmaking
`that
`could
`be applied
`to other
`problems.
`tools
`will
`be
`described,
`and
`then
`the
`be explained.
`Section
`6 argues
`that
`the
`the system goals described
`in section
`2.
`
`solve
`
`tool
`
`used
`
`5.1. Tools
`the
`to
`essential
`An
`introducing
`problem
`matchmaking
`fake
`is
`is hard
`to
`information
`that
`to camouflage
`transactions
`Thus,
`the matchmaking
`cryptography.
`hide
`using
`both
`sincere
`users
`and
`by
`carried
`out
`protocol
`is
`jokers.
`automated
`jokers
`generate
`fake
`The
`a third
`party
`cannot
`distinguished
`which
`transactions
`transactions.
`Fake
`transactions
`are similar
`from real
`to the
`fake messages wKlch
`are sometimes
`added
`to
`communication
`channels
`to
`thwart
`traffic
`analysis.
`Fake messages
`are intended
`to reduce
`the amount
`of
`information
`that
`a traffic
`analyst
`can deduce from the
`source
`and destination
`fields
`of a message.
`Similarly,
`fake
`transactions
`reduce
`the
`amount
`of
`information
`that
`an
`attacker
`of
`the matchmaking
`service
`can
`deduce
`from
`the wish
`field
`in
`the matchmaker’s
`database.
`
`the
`
`because
`possible
`are
`transactions
`Fake
`authentication
`service
`uses a very weak
`matchmaldng
`one
`of
`the protocol
`that
`authenticates
`tool.
`The part
`enough
`to the other
`party
`is strong
`party
`of a match
`to avoid
`fake matches,
`but
`it
`is not strong
`enough
`for
`a third
`party
`to tell whether
`either
`end of
`the match
`was authentic.
`This
`tool
`allows
`a joker
`to play
`both
`sides of
`the
`authentication
`protocol
`and
`thus
`create
`fake
`transactions.
`The
`authentication
`scheme
`uses a
`The
`basic
`idea
`is that
`the
`public-key
`cryptosystem.
`first
`party
`challenges
`the second
`party
`to demonstrate
`that
`the
`second
`party
`knows
`the
`secret
`key
`of
`the
`
`95
`
`

`
`The
`that
`
`is to decrypt
`challenge
`claim to be.
`they
`person
`has
`been
`encrypted
`chosen
`value
`a randomly
`Thk
`challenge-
`key.
`recipient’s
`public
`under
`the
`used
`build
`a
`fully
`scheme
`can
`be
`response
`connection
`as shown
`in [6].
`However,
`authenticated
`the challenge-response
`in one direction
`by not
`linking
`the
`party
`authenticates
`second)
`to the
`(i.e.
`the
`first
`other
`the
`challenge-response
`in
`the
`dhection,
`the
`protocol
`stays weak enough
`to allow fake transactions.
`
`to
`
`the matchmaking
`in solving
`difficulty
`Another
`w~lch
`“is a program,
`the matchmaker,
`is that
`problem
`administrators
`of
`its
`keep
`secrets
`from the
`cannot
`in
`information
`the
`Some
`of
`the
`computer.
`be kept
`secret even from
`database must
`matchmaker’s
`the matchmaker’s
`keys.
`that
`knows
`all of
`an attacker
`problem
`is a one-way
`to
`use
`solve
`this
`The
`tool
`Basically,
`all
`the users trust
`some person
`to
`function.
`key-pair
`for
`a
`public-key
`a
`random
`generate
`is
`and to destroy
`the secret
`key. What
`cryptosystem
`can
`left
`is a one-way
`function
`that
`the matchmaker
`The matchmaker
`compute,
`but
`no one
`can invert.
`uses
`thk
`function
`when
`it
`needs
`to
`store
`a user’s
`scrambled
`wish.
`[The scrambling
`of wishes
`is part
`of
`the authentication
`scheme,
`though
`it also adds
`to the
`security
`of
`the one-way
`function.
`If wishes were
`not
`scrambled,
`an attacker
`could
`construct
`a dictionary
`of
`all possible wishes
`and the corresponding
`value
`of
`the
`one-way
`function.
`The dictionary
`could
`then
`be used
`The
`one-way
`to
`invert
`the
`one-way
`function.]
`but
`function
`hides
`the scrambled
`wish
`still
`allows
`the
`matchmaker
`to
`test
`for
`equality
`between
`two
`scrambled
`wishes
`that
`have
`been transformed
`the
`one-way
`function.
`
`by
`
`the matchmaking
`used to solve
`tool
`final
`The
`extension
`of Gifford’s
`cryptographic
`is an
`for obtaining
`privacy
`and authentication
`computing
`environments
`[5].
`Section
`functions,
`Queryl
`and Response~,
`
`two
`
`problem
`primitives
`distributed
`defines
`
`in
`5.2
`for
`
`generating
`matchmaker.
`
`messages
`The
`
`a user and the
`to be sent between
`functions
`are indexed
`to indicate
`
`is
`
`to
`
`ith
`the
`linked
`message
`ith Query
`the
`that
`of
`these
`properties
`The main
`message.
`Response
`can
`be
`the Query
`sender
`of
`the
`are that
`functions
`read
`the
`desired
`recipient
`can
`only
`the
`sure
`that
`the
`sender
`can
`tell whether
`the
`and
`that
`message,
`message came from the desired
`recipient
`of
`response
`A list of
`the properties
`of
`these functions
`the query.
`is given
`in figure
`5-1.
`
`the
`‘ Both
`1,
`messages
`for
`their
`
`query
`.-
`contains
`recipients
`
`the
`and
`sufficient
`to detect
`
`response
`redundancy
`tampering.
`
`2.
`
`Knowing
`
`X and Kg (M’s public
`
`key)
`
`it
`
`is
`
`possible
`not
`generated
`
`to tell
`by Query
`
`that
`
`a message Y was
`
`i, K~ (xl
`
`without
`
`also
`
`knowing
`
`K;
`
`(M’s secret
`
`key).
`
`That
`
`is,
`
`the
`
`query
`
`function
`
`is randomized.
`
`3.
`
`Knowing
`recognize
`
`X does
`Response~
`
`not
`(X).
`
`help
`
`an
`
`attacker
`
`4.
`
`A query
`
`does not authenticate
`
`its source.
`
`5.
`
`A valid
`
`Response~
`
`(X) message
`
`can only
`
`be generate
`
`by
`
`someone
`
`who
`
`knows
`
`the
`
`decryption
`the response
`
`the ith query.
`for
`key
`is partially
`authenticated.
`
`That
`
`is,
`
`Figure
`
`Properties
`5-1:
`query-response
`
`the
`of
`messages.
`
`5.2. Notation
`the
`defines
`section
`This
`the matchmaking
`protocol
`express
`implementation
`for
`Query
`functions.
`
`the
`
`to
`used
`notation
`one
`and
`describes
`and
`Response
`
`is expreesed
`The protocol
`A and B, and a matchmaking
`as “A hires B”
`is the same
`represented
`by W. Sending
`is denoted
`by A->B:
`X.
`
`two users,
`of
`in terms
`server M. A wish
`such
`both
`users,
`and
`it
`is
`for
`a message, X,
`from A to B
`
`D
`and
`encryption
`denotes
`E
`symbol
`The
`a message
`Both
`E and D map
`decryption.
`denotes
`These
`symbols
`are used for
`both
`onto
`itself.
`space
`public-key
`and conventional
`cryptosystems.
`The two
`cases are dkitinguished
`by a superscript
`on the
`key.
`For
`example,
`~c
`denotes
`conventional
`encryption
`
`q
`the conventional
`
`using
`
`key K:.
`
`Public-key
`
`encryption
`
`using A’s public
`
`key is represented
`
`by ~p.
`
`Similarly,
`
`decryption
`
`using A’s secret
`
`key is written
`
`‘w D s.
`‘A
`
`An
`Response
`time Query
`
`Query
`the
`implementation
`5-2.
`in figure
`functions
`is shown
`is invoke,
`two
`random
`message
`
`of
`
`and
`Each
`keys, K:
`
`96
`
`

`
`and
`
`K;,
`
`are
`
`generated.
`
`These
`
`are
`
`keys
`
`for
`
`a
`
`conventional
`generate
`given
`
`cryptosystem,
`a true
`random
`
`so
`
`they
`number
`
`easy
`are
`source.
`
`to
`The
`
`key K:
`
`is used to encrypt
`
`the query message, while K:
`
`is passed
`message.
`recipient’s
`
`to
`
`the
`Both
`public
`
`to
`
`recipient
`are
`keys
`key and sent
`
`response
`the
`encrypt
`under
`the
`encrypted
`in the query message.
`
`Notice
`
`that
`
`the ith response
`
`cannot
`
`be computed
`
`until
`
`the ith query
`
`haa been received.
`
`random
`two
`1. Pick
`cryptosystem.
`Call
`
`a conventional
`for
`keys
`them K; and K;.
`
`2. Query~
`
`~P (X)
`‘A
`
`yields
`
`a 3 part message:
`
`3. Response~
`
`(Y)
`
`yields
`
`the message:
`
`~c(Y
`r
`
`plus
`
`checksum).
`
`Registration
`so
`cryptography,
`uses public-key
`protocol
`The
`keys.
`The server
`server
`to hand out
`it needs a trusted
`need not
`be implemented
`by the matchmaker,
`but
`it
`is included
`here for
`completeness.
`
`to which
`degree
`The
`identity
`is limited
`other’s
`public-keys
`are
`when
`registration
`might
`require
`or
`could
`be as simple
`electronic
`mailbox.
`
`users can be sure of each
`by the authentication
`done
`registered.
`For
`example,
`showing
`a physical
`ID card,
`as sen&lng
`the
`name
`of
`an
`
`1.
`
`A registers
`
`a public
`
`remembers
`Kjo
`
`the
`
`key K~ with M and
`corresponding
`secret
`key
`
`2.
`
`B registers
`
`a public
`
`remembers
`K:.
`
`the
`
`key Kg with M and
`correspondhg
`secret
`key
`
`Figure
`
`5-2:
`
`An Implementation
`Query
`and Response
`
`the
`of
`functions.
`
`5.3.
`
`Protocol
`The Matchmaking
`several
`involves
`system
`The
`matchmaking
`depends
`solution
`of our
`databases
`and the correctness
`the operation
`of
`those
`databases.
`The users maintain
`a database
`the wishes
`they
`have
`submitted.
`For
`of
`each wish,
`a user must
`record,
`and
`keep secret,
`two
`values
`that
`are
`used
`by
`the
`protocol.
`The
`matchmaker
`maintains
`a
`database
`of
`prospective
`wishes
`and a database
`of scrambled
`wishes.
`For
`each
`kind
`of wish
`the matchmaker
`keeps
`track
`of a set of
`notes which
`are received with
`the wishes.
`The
`notes
`roughly
`correspond
`to
`the
`identities
`of
`the
`people
`interested
`in each wish.
`
`a two-phase
`using
`are operated
`databases
`All
`the
`firat
`phase
`of a wish-cycle,
`During
`wish-cycle.
`is,
`are accepted
`and can be checked.
`That
`new wishes
`the databases
`can be read and written
`during
`the first
`the
`phase.
`During
`the
`second
`phase,
`databases
`are
`Users
`can
`check
`for matches,
`but
`they
`read
`only.
`cannot
`submit
`new wishes.
`Thhi
`two
`phase operation
`a
`insures
`that
`users have plenty
`of
`time
`to notice
`that
`match
`occurred
`before
`the matchmaker
`deletes
`a wish
`from its database.
`
`protocol
`The
`stage
`registration
`system is initialized.
`
`four
`of
`consists
`that
`is executed
`
`including
`stages
`once when
`
`a
`the
`
`3. M registers
`or more servers
`selects
`a public
`
`its own public
`
`key K; with
`..
`M
`the the users trust.
`that
`one-way
`function
`OM (see
`
`one
`
`section
`
`5.1), and keeps it secret.
`
`Bid
`
`the Bld
`of
`effect
`The
`A and B to
`exchange
`two
`K: ~, without
`
`revealing
`
`stages
`and Lookup
`one-time
`keys, K:
`
`is for
`* and
`
`them to M or anyone
`
`else.
`
`1. A->M:
`
`Queryl,%
`
`(B)
`
`2. M->A:
`
`Responsel
`
`(B,
`
`Kg)
`
`A now knows B’s public
`
`key.
`
`3. A picks
`
`a random
`
`conventional
`
`key K; A,
`
`and
`
`an random
`
`number,
`
`N;,
`
`that will
`
`be
`
`during
`pseudonym
`as A’s
`used
`a
`The
`value
`transaction.
`send K; A to B via M.
`secretly
`
`thk
`used
`
`wish
`to
`
`is
`
`A computes:
`
`a = ~g
`
`(Kj,A)
`
`A stores:
`
`W, N],
`
`a
`
`A->M :
`
`Query2,~
`
`(W,
`
`a)
`
`M stores:
`
`W,
`
`{al
`
`

`
`fake
`added
`of
`part
`As
`stores
`a random number
`along with
`the value
`a.
`
`M
`transactions,
`random values
`
`of
`
`4.
`
`M->A :
`
`Response2(W,
`
`d
`
`This message
`wish.
`
`confirms
`
`that M received
`
`A’s
`
`A computes:
`
`K$ ~ from
`
`A recalls:
`
`A compu%es;
`
`K; A from
`6”= E&A(y
`
`D s (~)
`‘A
`storage
`,(W))
`
`,
`
`3. B performs
`
`a similar
`
`step.
`
`B->M :
`
`Query6,%
`
`(W)
`
`5.
`
`B performs
`
`a similar
`
`set of steps.
`
`4. M->B:
`
`Response6(W,
`
`{a,
`
`B})
`
`B->M:
`
`Query3,%
`
`(A)
`
`6.
`
`M->B :
`
`Response3
`
`(A,
`
`K:)
`
`B now knows A’s public
`
`key.
`
`7.
`
`B picks
`
`a random
`
`conventional
`
`key K; ~,
`
`and
`
`an random
`
`number,
`
`N:,
`
`that will
`
`be
`
`during
`pseudonym
`as+ B’s
`used
`The
`value @ is
`transaction.
`secretly
`send K; ~ to A via M.
`,
`
`thk
`used
`
`wish
`to
`
`B computes:
`
`9 = ~~(K~,J
`
`W, N:, @
`
`B computes:
`
`K: ~ from
`
`D s(a)
`‘B
`
`B ‘ecalls:
`B computes:
`
`‘;,B
`6 =
`
`‘rem
`
`‘torage
`
`%,A(%,B(W))
`
`Check
`
`is now
`There
`the wish W.
`is submitted
`
`identifies
`pseudonym
`
`6,
`a value,
`value
`This
`to M to check
`
`anonymously
`that
`each
`user’s
`and
`for a match.
`
`1.
`
`A recalls:
`
`N~
`
`A->M:
`
`Query7,K~(6,
`
`N])
`
`2. M leeks
`
`up 6 in its database
`
`of scrambled
`
`B stores:
`
`B->M : Query4,K;
`
`(W, @
`
`M stores:
`
`W,
`
`{a,
`
`j3)
`
`8. M->B :
`
`Response4
`
`(W,
`
`8)
`
`wishes.
`
`The
`
`value
`
`N;
`
`is added
`
`to
`
`the
`
`one element
`is only
`there
`If
`set.
`associated
`in the set, M returns
`the message NoMatch.
`
`M stores:
`
`OM(6)
`
`, <N:}
`
`M->B:
`
`Response7(6,
`
`N:,
`
`NoMatch)
`
`This message
`wish.
`
`confirms
`
`that M received
`
`B’s
`
`3. B performs
`
`a similar
`
`step.
`
`Lookup
`
`By
`
`the end of
`
`the Lookup
`
`stage, A and B have
`
`exchanged
`
`the secret
`
`keys K; ~ and K; ~.
`
`These t-+:c
`
`wish
`z &ambled’
`keys are used to construct
`I! ~? keeps 6 secret,
`that
`only A and B know.
`oth
`knows
`that B is the only
`i user who could
`the value
`of 6 to the matchmaker.
`
`t,
`value,
`then A
`prescn:
`
`1.
`
`A->M:
`
`Query5,K~(W)
`
`iti
`bp M ifi
`2. M kds
`and Teturxla
`w“k+h~
`asaociatedwith
`*.
`
`-ui w _gec&ive
`ua.au-
`the set or secretaotea
`
`*-M:
`
`4t*SpOTiS*#.
`
`Xa.
`
`/573
`
`B recalls:
`
`N;
`
`B->M:
`
`Query8,K~(6.
`
`N:)
`
`4.M looks
`wishes.
`
`up 6 in its database
`
`of scrambled
`
`The
`
`value
`
`N;
`
`is added
`
`to
`
`the
`
`aeeociated
`elements
`Match.
`
`or more
`are two
`there
`If
`set.
`in the set, M returns
`the message
`
`M stores:
`
`OM(J),
`
`{N:,
`
`N~}
`
`M->B:
`
`Responsee(6,
`
`N~, Match)
`
`5. Some
`maker
`positive
`
`time.
`;f
`
`zmks the match
`A again
`later
`amatch has ocmwred,
`nd
`getsa
`response.
`
`98
`
`

`
`A recalls:
`
`N;
`
`A->M : Query9,K;
`
`(6, N:)
`
`6.M looks
`wishes.
`
`up 6 in its database
`
`of scrambled
`
`The
`
`value
`
`N]
`
`is already
`
`in
`
`the
`
`is added.
`set, so nothing
`associated
`in the set, SOM returns
`are two values
`meesage Match.
`
`There
`the
`
`M->B :
`
`Response9(6,
`
`N], Match)
`
`2.
`
`6. Correctness
`Argument
`presented
`the protocol
`argues
`that
`This
`section
`the
`system
`goals
`presented
`in
`section
`5 meets
`in
`section
`correctness
`argument
`is made
`The
`the
`proof
`techniques
`for multi-
`informally
`because
`party
`protocols
`are not well
`developed,
`and
`because
`the system goals are hard
`to express
`formally.
`Notice
`that
`the matchmaking
`protocol
`involves
`four
`parties:
`A, B, M, and M’s storage.
`Even
`and Goldreich
`[4] have
`shown
`that
`the
`general
`problem
`of
`proving
`the
`security
`(privacy
`of messages)
`of a protocol
`like
`ours
`is undecidable.
`Security
`properties
`such as anonymity
`have not been considered
`formally.
`
`is
`goal
`authentication
`the
`that
`confirm
`To
`could
`decide whether
`an attacker
`one must
`achieved,
`in fact
`that
`a match
`occurred
`when
`make
`a user
`think
`it dld
`not.
`A user, A,
`thinks
`that
`a match
`occurred
`when
`the matchmaker,
`M,
`response
`positively
`to A’s
`query
`about
`some wish, W. Due
`to the properties
`of
`the Query
`and Response
`functions
`(see figure
`5-l),
`an attacker
`cannot
`generate
`a fake message from M to
`A. The attacker must
`use an indirect
`approach.
`
`to
`
`to cause a fake match
`method
`indirect
`The
`the
`appropriate
`scrambled
`send
`the wish, W,
`is
`The
`value
`6 is
`matchmaker.
`wish,
`6,
`to
`the
`by
`the
`check
`stage,
`and
`the
`transmitted
`during
`only
`properties
`the Query
`function,
`it
`can
`be
`of
`deduced
`by a person who
`knows K;.
`The case where
`
`of
`
`the
`
`attacker
`
`knows
`
`K~ is discussed
`
`under
`
`the goal of
`
`so let us assume that
`of privacy,
`degradation
`graceful
`from the messages
`sent
`during
`be deduced
`6 cannot
`stage.
`Another
`way
`to determine
`8 is to
`the
`check
`However,
`that
`approach
`is
`look
`at M’s
`storage.
`blocked
`by the one-way
`function
`OM. The only
`other
`
`way
`
`to deduce
`
`6 is to compute
`
`it
`
`from K;
`
`* and K; ~,
`
`but
`
`those values
`
`are only
`
`stored
`
`or
`
`transmitted
`
`wh’en
`
`key.,
`under A’s or B’s secret
`have been encrypted
`they
`the
`of
`those
`encryptions,
`insure
`the
`security
`To
`to
`the attacker
`with
`a way
`protocol
`avoids
`providing
`get a user
`to apply
`his secret
`key
`to a chosen
`value.
`Thus,
`except
`for
`the
`case where
`the
`attacker
`knows
`
`Ks
`u,
`
`there
`
`is no way
`
`to fake a match.
`
`is anonymity.
`to consider
`system goal
`The next
`of a user of
`the
`identity
`determine
`an attacker
`Can
`system without
`matching
`a wish?
`the matchmaking
`to verify
`the
`identity
`of a user
`is to
`The
`only way
`chal kmge
`hlm to decipher
`a random
`value
`that
`has
`been encrypted
`under
`someone’s
`public
`key.
`It
`is not
`enough
`to
`see
`that
`someone
`can
`produce
`a
`corresponding
`pair
`of ciphertext
`and cleartext
`values.
`Jokers
`produce
`such
`pairi
`to
`generate
`fake
`transactions.
`The
`only way
`to offer
`a challenge
`and
`to see the response
`is to submit
`a wish
`to the match
`maker
`and wait
`for a match
`notification
`or
`to use K;
`
`to directly
`
`read the response.
`
`the
`
`achieving
`notification
`The
`
`joint
`for
`strategy
`The
`the
`be
`to make
`goal
`is
`notification
`users.
`of
`the
`responsibility
`matchmaker
`keep
`intact
`is
`information
`match
`that
`guarantees
`is
`and
`it
`during
`the read-only
`phase of a wish-cycle,
`about
`up
`to
`the
`users
`query
`to matchmaker
`to
`possible matches.
`advantage
`of
`this
`approach
`is
`The
`that
`a
`user
`can
`detect
`an
`active
`attacker
`that
`persistently
`blocks
`the
`user’s
`queries.
`The
`other
`of
`benefit
`making
`notification
`be
`the
`user’s
`responsibility
`is that
`the matchmaker
`does not
`need
`to record
`the network
`addresses
`of
`the users involved
`with
`a match.
`The
`only
`information
`that
`the
`matchmaker
`must
`keep secret
`can be transformed
`by
`a one-way
`function.
`It
`is not
`necessary
`to recall
`the
`original
`values
`as it would
`be with
`network
`addresses.
`
`graceful
`the
`is
`discuss
`to
`goal
`final
`The
`is that
`property
`desired
`The
`of privacy.
`degradation
`learn
`an
`attacker
`can
`of
`information
`the
`amount
`the
`of
`keys
`known
`as the
`number
`grows
`slowly
`can
`what
`an attacker
`attacker
`increases.
`Consider
`learn
`if he knows
`the matchmaker’s
`secret
`key, K~.
`
`to
`
`can read all messages sent
`the attacker
`key,
`that
`With
`to the matchmaker
`and can generate
`a valid
`response
`to any
`query.
`Fortunately,
`neither
`of
`these
`abilities
`make
`it possible
`for
`the match maker
`to authenticate
`users.
`Such an attacker
`is in no better
`shape than
`the
`matchmaker
`when
`it
`comes
`to
`dktinguishlng
`fake
`wishes
`from real ones.
`
`99
`
`

`
`An
`
`attacker
`
`that
`
`knows
`
`K;
`
`can
`
`cause
`
`fake
`
`by
`matches
`wishes.
`about
`unless
`useful
`ones.
`real
`matches,
`their
`fake
`get matched,
`
`queries
`to
`responses
`positive
`generating
`is not
`very
`ability
`Fortunately,
`this
`fake wishes
`from
`the
`attacker
`can tell
`If
`an
`attacker
`started
`causing
`fake
`users would
`detect
`it
`because
`some
`of
`the
`transactions,
`which
`they
`know should
`not
`end up getting matched.
`
`An
`key
`secret
`recognize
`member
`of graceful
`
`of
`
`that
`attacker
`and
`the secret
`and
`authenticate
`that
`set of users.
`degradation.
`
`the matchmaker’s
`knows
`keys of a set of users,
`can
`wishes
`that
`involve
`a
`This
`fits
`the definition
`
`7. Summary
`can be used to ac~leve
`that
`tools
`of
`In search
`and
`accountability
`this
`paper
`has
`anonymity
`both
`a problem
`with
`conflicting
`goals of
`and solved
`posed
`Authentication
`is
`and
`anonymity.
`authentication
`usually
`the basis for accountability,
`so this problem
`is
`relevant
`to
`the
`trade-off
`between
`anonymity
`and
`accountability
`in the design of
`information
`systems.
`
`this
`solve
`to
`developed
`were
`tools
`Several
`active
`were used to detect
`Fake transactions
`problem.
`could
`information
`that
`and
`to camouflage
`attackers
`public-key
`hidden
`cryptograptilcally.
`not
`be
`authentication
`scheme was used to meet
`the system’s
`authentication
`goal
`without
`conflicting
`with
`the
`anonymity
`Finally,
`two
`functions,
`Query
`and
`goal.
`to
`Response,
`defined
`and
`shown
`have
`useful
`were
`properties
`of privacy
`and partial
`authentication.
`
`A
`
`References
`
`1. Manuel
`Proceedings
`Computing,
`
`How to Exchange
`Blum.
`of
`the 15th Symposium
`ACM,
`1983.
`
`(Secret) Keys.
`on Theory
`of
`
`2. David
`
`L. Chaum.
`
`!!Untraceable
`
`Electronic
`
`Mail,
`
`Address,
`Return
`Communications
`84-88.
`
`Pseudonyms”.
`and Digital
`the ACM 24, 2 (February
`oj
`
`1981),
`
`3. David
`Individuals
`Security
`
`for
`A New Paradigm
`L. Chaum.
`in the Information
`Age.
`Symposium
`and Privacy,
`IEEE,
`1984.
`
`on
`
`and O. Goldreich.
`4. S. Even
`Ping-Pong
`Protocols.
`Multi-Party
`25th Symposium
`on the Foundations
`Science,
`IEEE,
`1984.
`
`of
`On the Security
`of
`Proceedings
`of Computer
`
`the
`
`K. Gifford.
`5. David
`Secrecy
`Information
`Communications
`of
`274-286.
`
`11Cryptograp~lc
`and Authentication”.
`the ACM 25, 4 (April
`
`Sealing
`
`fOr
`
`1982),
`
`6. R.M. Needham and M.D. Schroeder.
`“Using
`of
`Encryption
`for Authentication
`in Large Networks
`the ACM 21, 12
`Computers”.
`Communications
`oj
`(December
`1978), 993-999.
`
`100