Theoretical Computer Science Forum

Autumn 2005

This is a forum for talks on theoretical computer science organized by the TCS Laboratory at HUT. We meet usually on Fridays at 2 p.m. in room B353 in the Computer Science building. Any exceptions to this rule are reported below.

For further information, please contact Tomi Janhunen.

Program

• 18.10.2005 prof. Gene Tsudik (UC at Irvine, California):

  Oblivious Information Delivery using Oblivious Signature-Based Envelopes

  Note: the talk is at 14:15 in room B353

  Abstract: Secure, anonymous and unobservable communication is becoming increasingly important due to the gradual erosion of privacy in many aspects of everyday life. This prompts the need for various anonymity- and privacy-enhancing techniques, e.g., group signatures, anonymous e-cash and secret handshakes. In this work we investigate an interesting and practical cryptographic construct -- Oblivious Signature-Based Envelopes (OSBEs) recently introduced by Li, et al. (PODC'03). OSBEs are very useful in anonymous communication since they allow a sender to communicate information to a receiver such that the receiver's rights (or roles) are unknown to the sender. At the same time, a receiver can obtain the information only if it is authorized to access it. This makes OSBEs a natural fit for anonymity-oriented and privacy-preserving applications, such as Automated Trust Negotiation and Oblivious Subscriptions. Our work focuses on the ElGamal signature family: we succeed in constructing practical and secure OSBE schemes for several well-known signature schemes. Our schemes are more efficient than previous techniques and are "practical" in the true meaning of the word.

• 17.10.2005 assoc.prof. Marc Denecker (KU Leuven, Belgium):

  Satisfiability checking for PC(ID)

  Note: the talk is at 10:15 in room B353

  Abstract: The logic FO(ID) is an extension of classical first order logic with inductive definitions. This paper studies the satisifiability problem for PC(ID), the propositional fragment of FO(ID). We develop a theoretical framework for model generation in this logic, present an algorithm and prove its correctness. As FO(ID) is an integration of classical logic and logic programming, our algorithm integrates techniques from SAT and ASP. We report on a prototype system, called MidL, experimentally validating our approach.

• 7.10.2005 prof. Pekka Orponen (TKK/TCS, Otaniemi):

  Local Clustering of Large Graphs by Approximate Fiedler Vectors

  Abstract: We address the problem of determining the natural neighbourhood of a given node i in a large nonuniform network G in a way that uses only local computations, i.e. without recourse to the full adjacency matrix of G. We view the problem as that of computing potential values in a diffusive system, where node i is fixed at zero potential, and the potentials at the other nodes are then induced by the adjacency relation of G. This point of view leads to a constrained spectral clustering approach. We observe that a gradient method for computing the respective Fiedler vector values at each node can be implemented in a local manner, leading to our eventual algorithm. The algorithm is evaluated experimentally using three types of nonuniform networks: randomised "caveman graphs", a scientific collaboration network, and a small social interaction network.
  (Joint work with Satu Elisa Schaeffer.)

• 16.9.2005 Nitesh Saxena (Nokia NRC, Helsinki):

  On the Role of Threshold Cryptography Towards Securing Ad Hoc Networks

  Abstract: In this talk, we consider the problem of secure access control or how to bootstrap security in ad hoc networks. This allows every pair of nodes in the network to securely communicate with each other, and forms the basis for other essential security services, such as group communication and secure routing. Due to the distributed nature of an ad hoc network, threshold cryptography is a natural choice towards solving this problem. We classify ad hoc networks into two categories, long-lived and short-lived, based on their lifetime. The former need stronger resistance against the so-called dynamic adversary, while for the latter, protection against the so-called static adversary is sufficient. We first discuss the inapplicability of various known proactive RSA signature schemes in building access control protocols for long-lived networks. We present an attack on a recently proposed proactive RSA scheme, provide a fix to it and discuss related open problems. Finally, we build an efficient access control protocol for short-lived network settings, obviating the need for expensive threshold signing.