Title : Analysis of the Random-Surfer Web-Graph model
Speaker : Pall Melsted
When : 4:30-5:30pm, April 12th
Where : Physical Plant Building(PPB) Room #300
Abstract:
We analyze the Random-Surfer Web-Graph Model introduced by Blum et al. In this model a new vertex picks a random vertex, performs a short random walk and connects to the end of the walk. We give the expected degree of a vertex and show that it follows a power law for early vertices thus showing a First Mover Advantage in the graph. We also show that for certain values of the parameters the first vertex will be connected to a considerable fraction of the vertices and give evidence of a phase transition for this behavior.
This is joint work with Prasad Chebolu.
SPEAKER: Elaine Shi
TIME: Wednesday 12-1pm, April 11, 2007
PLACE: NSH 1507
TITLE: Multi-Dimensional Range Query over Encrypted Data
ABSTRACT:
We design an encryption scheme called Multi-dimensional Range Query over Encrypted Data (MRQED), to address the privacy concerns related to the sharing of network audit logs and various other applications. Our scheme allows a network gateway to encrypt summaries of network flows before submitting them to an untrusted repository. When network intrusions are suspected, an authority can release a key to an auditor, allowing the auditor to decrypt flows whose attributes (e.g., source and destination addresses, port numbers, etc.) fall within specific ranges. However, the privacy of all irrelevant flows are still preserved. We formally define the security for MRQED and prove the security of our construction under the decision bilinear Diffie-Hellman and decision linear assumptions in certain bilinear groups. We study the practical performance of our construction in the context of network audit logs. Apart from network audit logs, our scheme also has interesting applications for financial audit logs, medical privacy, untrusted remote storage, etc. In particular, we show that MRQED implies a solution to its dual problem, which enables investors to trade stocks through a broker in a privacy-preserving manner.
Joint work with John Bethencourt, T-H. Hubert Chan, Dawn Song, and Adrian Perrig.
