PET Workshop - Day 3 (June 30, 2006)

Day 3, the final day of the workshop (which is really a conference). The final day, and I have the final presentation. The final presentation that happens to begin 30 minutes before the Germany / Argentina World Cup match. What are the chances that I’ll have a relatively small set of people at my talk?

Anyway, on to today’s talks:

Session 5: Private Multiparty Computation

Presentation 1: Private Resource Sharing
- Claims to be an efficient solution to the private matching
problem in both the semi-honest and potentially malicious
scenarios.
- Researchers provide encrypted credentials that they are
on a need-to-know basis via metadata
- Assumption: metadata is static
- Resource then has to prove that they have the requested
data.
- Private Key Generator maintains “master secret” --> Alice
retrieves key for “alice” --> She passes the message that is
assigned with her private key to Bob --> Bob uses the
public key “alice” to verify
- Assume each owner possess a unique master secret for
an IBS private signature scheme

Presentation 2: Honest-Verifier Private Disjointness Testing Without Random Oracles
- New idea “testable and homomorphic commitments”
- Private Disjointness Testing: two parties add their datasets
and they learn if their is an intersection or not (1 or 0)
- Application Examples: 1) No Fly List, 2) Anonymous Login
- Prior solution: secure function evaluation (GMW’87) &
zero-knowledge sets (MRK’03)
- Uses 2 tools
1) Embeds set representations as polynomials
- Roots of polynomial are points in the set
2) Homomorphic encryption:
Addition: E(x) + E(y) = E(x + y)
Constant Mutliplication: E(x)y = E(xy)
- Prior Solution
- Alice will publish encrypted coefficients
- Anoyone can come obviously evaluated polynomial
- But this solution is not private - because people learn f
(b), where b is the coefficient
- FNP extension: multiple everything by random value r. If f
(b) is nonzero (i.e. there’s an intersection) then we learn
random value
- Problem: only works in semi-honest; a malicious party
can just encrypt and evaluate zero
- Today’s solution extension to FNP
- Private Operations: 1) Commitment, 2) Equality Test of
commitments (uses Pederson commitments)
- Open question: security against malicious verifiers?

Presentation 3: A Flexible Framework for Secret Handshakes: Multiparty Anonymous and Unobservable Authentication
- How can people authenticate each other if they are not
permitted to divulge their affiliations
- Prior work uses one-time pseudonyms, but supports only 2
party handshakes
- This research avoids pseudonyms and extends to n-party
handshakes by using reusable group signatures
- Also has the ability for self-distinction: given more than 2
people in a group, it can be determined that everyone in
the system is unique


Session 6: Authentication and Cryptography

Presentation 1: On the Security of the Tor Authentication Protocol
- Uses a customized variation of Diffie-Helman encryption
- Until last year Tor’s authentication model was broken.
- An initial message could be intercepted & ignored
- Then a false response could be sent by the adversary
and the adversary can control Alices Tor route.
- This has been patched and this research proves that the
new authentication protocol is resistant to this problem in
the random oracle model
- Resistance to “reaction attack”
- Alice encrypts and sends message to Bob
- Mallory modifies ciphertext, sends to Bob (sometimes
its meaningful, sometimes its not)
- If meaningful, Bob responds and Mallory can learn
information about Bob


Presentation 2: Optimal Key-Trees for Tree-Based Private Authentication
- Motivation: Mobile user that authenticates himself at each
access point, but an eavesdropper tracks the user and
collects his authentications
- Key-tree based on private authentication
- First authenticates with top key (i.e. root note) and the
server is told which branch of the tree the key resides
- Keys in the next level of the branch are enumerated
until proper key is found
- This repeats recursively until key is found in leaf node
of tree
- Privacy of members, measured in anonymity set size is
increasingly destroyed as more people in the tree are
compromised
- Solution: phrase as an optimization problem and orient the
tree so that it is compromise-level is minimized.


Presentation 3: Simple and Flexible Private Revocation Checking
- Problems with premature revocation of certificates
- Certificates only need to be verified once
- But prior to communication, you should always check the revocation status
- Privacy leaks: third parties can learn
- Source of revocation query
- Target of the query (focus of this talk)
- Problem identified by Kikuchi in “Privacy-preserving
revocation check in PKI”
- Modify certificate revocation trees (CRT) structure
- Range queries
- Instead of querying for a single node, query for a
range of nodes
- My concern - increase in network traffic?
- Permuted Ordering of tree
- Potential problem - near neighbors could be related
and that can reveal “concept” that of query
- Pseudorandom permutation to guarantee uniform
distribution


Session 7: Traffic and Location Analysis

Presentation 1: Breaking the Collusion Detection Mechanism of MorphMix
-Morphmix:
- P2P anonymous networking overlay
- No centralized component
- Nodes only need a local view
- Tunnels are constructed via a witness
- Collusion detection mechanism
- Assumes more difficult to control multiple IPs (16-bit
prefixs)
- Assumes attacks provide all or many malicious nodes
- Assume will provide random selection of malicious
nodes
- Get the list of potential nodes from each node
- Count the number of nodes in common and compute
correlation
- Attacker Goal
- Link connection initiator with outgoing network
- Control at least the first intermediate and last node
- Potential Solutions
- increase the size of potential nodes
- increase length of tunnels (currently set at 5)


Presentation 2: Linking Anonymous Transactions: The Consistent View Attack
- Multiple credentials sent to a user from an organization
- Adversary knows all of the pseudonyms that are issued
to users
- Goal: Partition the set of pseudonyms into equivalence
classes
- Adversary must remove all inconsistent partitions
- partition is inconsistent if issuing of pseudonym occurs
after another pseudonym that has yet to be used
- Enumeration of all groups is NP-complete
- Proof: convert history file into Boolean circuit


Presentation 3: Preserving User Location Privacy in Mobile Data Management Infrastructures
- A data framework that trades location privacy and service
quality
- Introduce a definition of “query quality”
- Cloaked Location Model
- Density over where a query could come from or
correspond to
- Cloaking Agent
- Policy Translator (Sends Privacy Prefs and Cloaked
Location to Service Provider)
- e.g. k-anonymity
- Privacy vs. Accuracy vs. Control with respect to
particular locations or providers
- Service Translator
- Result Translator
- Imprecise location range query --> get probability that
someone / something satisfies range query
- Experimental analysis on IBM City Simulator illustrates a
tradeoff between privacy (in terms of range) and accuracy
or quality of service
- Question asked: How do you communicate “quality” or
probability to a user

Presentation 4: The Effects of Location Access Behavior on Re-identification Risk in a Distributed Environment
- It’s my talk.


And now I’m off to go watch the Germany / Argentina world cup match.