ISG Research Seminars

The ISG has a regular term-time research seminar on Thursdays in McCrea Room 229 at 1pm. Outside term-time, seminars are arranged on an ad hoc basis. ISG seminars are open to all. Questions regarding these seminars should be emailed to Carlos Cid.

Directions to the campus for attendees and speakers can be found here.

Details of research seminars from previous semesters and academic years can be found here.

Forthcoming seminars:

Thursday 18th March 2010:
Speaker: Ludovic Perret (LIP6-UPMC Univ Paris 6 & INRIA, France)
Title: Algebraic Cryptanalysis of McEliece Variants with Compact Keys
Abstract: In this talk, we will present a new approach to investigate the security of the McEliece cryptosystem. We recall that this cryptosystem relies on the use of error-correcting codes. Since its invention thirty years ago, no efficient attack had been devised that managed to recover the private key. We prove that the private key of the cryptosystem satisfies a system of bi-homogeneous polynomial equations. This property is due to the particular class of codes considered which are alternanting codes. We have used these highly structured algebraic equations to mount an efficient key-recovery attack against two recent variants of the McEliece cryptosystems that aim at reducing public key sizes. These two compact variants of McEliece managed to propose keys with less than 20,000 bits. To do so, they proposed to use quasi-cyclic or dyadic structures. An implementation of our algebraic attack in the computer algebra system Magma allows to find the secret-key in a negligible time (less than one second) for almost all the proposed challenges. For instance, a private key designed for a 256-bit security has been found in 0.06 seconds with about 2^17.8 operations.
(joint work with Jean-Charles Faugere, Ayoub Otmani, and Jean-Pierre Tillich)

Friday 19th March 2010 (special seminar on FRIDAY at 2:30PM, in room 229)
Speaker: Chee Yeow Meng (Nanyang Technological University, Singapore)
Title: Universal Cycles, 2-Radius Sequences, and Fetching Huge Objects into Small Memory
Abstract: A new ordering, extending the notion of universal cycles, is proposed for the blocks of k-uniform set systems. Existence of minimum coverings of pairs by triples that possess such an ordering is established for all orders. This gives rise to 2-radius sequences that are shorter than those currently known, for all orders less than 10^36. Such sequences have application in cache algorithms.

Thursday 25th March 2010:
Speaker: Jon Hart (ISG, RHUL)
Title: Website Credential Storage and Two-factor Web Authentication with a Java SIM
Abstract: In this talk, two mobile authentication schemes are proposed. The first enables authentication credentials (username and password) to be stored and retrieved securely from a mobile handset and requires no changes to existing websites. The second scheme, which may optionally be used with the first, utilises a one-time password and is intended for applications requiring an enhanced level of authentication. Both authentication schemes use a Java SIM for secure storage of credentials and secret keys and the ubiquitous mobile phone; with its familiar and convenient form factor and high user acceptance.

No Seminar on 1st April and 08 April 2010

Thursday 15th April 2010:
Speaker: TBA
Title: TBA
Abstract: TBA

Thursday 22nd April 2010:
Speaker: TBA
Title: TBA
Abstract: TBA

Thursday 29th April 2010:
Speaker: Maura Paterson (Birkbeck, Univ. of London)
Title: Error Decodable Secret Sharing and One-Round Perfectly Secure Message Transmission for General Adversary Structures
Abstract: An error decodable secret-sharing scheme is a secret-sharing scheme with the additional property that the secret can be recovered from the set of all shares, even after a coalition of participants corrupts the shares they possess. In this talk we will consider schemes that can tolerate corruption by sets of participants belonging to a monotone coalition structure, which generalise both a related notion studied by Kurosawa, and the well-known error-correction properties of threshold schemes based on Reed-Solomon codes. In addition, we will explore the connection between one-round perfectly secure message transmission (PSMT) schemes with general adversary structures and secret-sharing schemes, and we will exploit this connection to investigate factors affecting the performance of one-round PSMT schemes.

Thursday 6th May 2010:
Speaker: Simon Blackburn (ISG, RHUL)
Title: TBA
Abstract: TBA

Thursday 13th May 2010:
Speaker: Gerhard Hancke (ISG, RHUL)
Title: TBA
Abstract: TBA

Thursday 20th May 2010:
Speaker: Alex Dent (ISG, RHUL)
Title: TBA
Abstract: TBA

Thursday 27th May 2010:
Speaker: Raphael Phan (Loughborough University, UK)
Title: Evidential Notions of Security
Abstract: TBA

Thursday 3rd June 2010:
Speaker: TBA
Title: TBA
Abstract: TBA

Thursday 10th June 2010:
Speaker: TBA
Title: TBA
Abstract: TBA

Thursday 15th June 2010:
Speaker: TBA
Title: TBA
Abstract: TBA

Previous seminars in 2009/2010 academic year:

Thursday 1st October 2009:
Speaker: Po Yau (ISG, RHUL)
Title: Enhancing Workflow Security using Trusted Computing and Virtualisation
Abstract: Information workflows can involve outsourcing segments to third parties. This is increasingly becoming common because of work into integration technologies, such as Web services, and the emergence of various forms of distributed computing, such as Grid computing and Cloud computing. We use Grid workflows, a set of tasks arranged into a logical order to process a Grid user's dataset, as an example for workflow security requirements addressing the needs of the Grid user. An overview of a secure protocol using Trusted Computing technology will be presented, which is further enhanced with platform virtualisation hardware and software. The proposed scheme allows the selection of trustworthy third parties and gives confidentiality and integrity protection to the workflow, the Grid user's processes and data. The scheme also detects any problems during workflow execution, collecting information that can be potentially used for process provenance.

Thursday 8th October 2009:
Speaker: Jason Crampton (ISG, RHUL)
Title: Trade-Offs in Key Assignment Schemes for Hierarchical and Temporal Access Control
Abstract: A key assignment scheme provides a framework for implementing hierarchical access control policies using encryption. We define several generic key assignment schemes and compare their respective advantages by considering the amount of public storage used and the number of steps required to derive a key. We then examine the specific trade-offs that exist for a particular type of key assignment scheme that has been used to implement temporal access control policies.

Thursday 15th October 2009:
Speaker: Liang Chen (ISG, RHUL)
Title: Set Covering Problems in Role-Based Access Control
Abstract: Interest in role-based access control has generated considerable research activity in recent years. A number of interesting problems related to the well known set cover problem have come to light as a result of this activity. However, the computational complexity of some of these problems is still not known. We explore some variations on the set cover problem and use these variations to establish the computational complexity of these problems. Most significantly, we prove that the minimal cover problem -- a generalization of the set cover problem -- is NP-hard, which is used to determine the complexity of the inter-domain role mapping problem. We also design a number of approximation algorithms for the minimal cover problem, and conduct some experiments to evaluate the quality of those algorithms. Joint work with Jason Crampton.

Thursday 22nd October 2009:
Speaker: Michael Huth (Imperial)
Title: Access Control via Belnap Logic: Intuitive, Expressive, and Analyzable Policy Composition
Abstract: Access control to IT systems is increasingly relying on the composition of policies - accelerated by the need to federate, self-configure or contextualize potentially heterogeneous systems. There is thus benefit in any framework that supports intuitive yet formal (and so ``analyzable'' and ``implementable'') policy compositions, abstracts away irrelevant aspects of application domains, provides a rich and efficiently analyzable set of non-adhoc compositions, and can realize generic and domain-specific extensions of its composition language on top of the framework core.

We here develop such a framework based on Belnap logic: an access-control policy is interpreted as a *four-valued* predicate that maps access requests to either Grant, Deny, Conflict, or Unspecified -- corresponding to the four-valued Belnap bilattice. Our core composition language contains the constant policy Unspecified, base policies that lift specifications of request sets to conflict-free policies, and operators for negation, conjunction, and implication in the truth ordering of the bilattice. These operators are obtained as pointwise extensions of the familiar operators on the Belnap bilattice. In this core language, important and convenient composition operator are derived, which enable the decoupling of conflict resolution from policy composition. We propose a query language for policy refinement checks, show that it can express important analyses (e.g. conflict analysis), and reduce query validity checking to validity checking of propositional logic. Finally, we evaluate our approach through the specification and analysis of firewall policies and RBAC policies and discuss domain-specific and generic extensions of our policy language.

Thursday 29th October 2009:
Speaker: Steve Williams (Bristol)
Title: Secure Two-Party Computation is Practical
Abstract: Secure multi-party computation has been considered by the cryptographic community for a number of years. Until recently it has been a purely theoretical area, with few implementations with which to test various ideas. This has led to a number of optimisations being proposed which are quite restricted in their application. In this paper we describe an implementation of the two-party case, using Yao’s garbled circuits, and present various algorithmic protocol improvements. These optimisations are analysed both theoretically and empirically, using experiments of various adversarial situations. Our experimental data is provided for reasonably large circuits, including one which performs an AES encryption, a problem which we discuss in the context of various possible applications. Joint work with B. Pinkas, T. Schneider and N.P. Smart

Thursday 5th November 2009:
Speaker: Georg Fuchsbauer (ENS, Paris)
Title: Efficient Anonymous Proxy Signatures
Abstract: Consider a set of users each holding a secret signing key and publishing a verification key for digital signatures. "Anonymous proxy signatures" enable a user (delegator) to delegate her signing rights to any other user. The latter can then sign on behalf of the delegator while remaining anonymous. Moreover, received rights can be re-delegated; e.g., Alice delegates to Bob who in turn re-delegates to Carol. Carol can then create a proxy signature that is verifiable under Alice’s public key and that does not reveal the identities of Bob and Carol. As for group signatures, in case of misuse, an authority can open signatures to reveal the chain of delegations and the signer’s identity. Anonymous proxy signatures are a generalisation of both proxy signatures and dynamic group signatures. In order to efficiently instantiate the primitive using the non-interactive witness-indistinguishable proof system by Groth and Sahai (Eurocrypt 2008), we introduce "automorphic signatures" and give an efficient instantiation. A signature scheme in a bilinear group is automorphic if its verification keys lie in the message space, messages and signatures consist of group elements only, and verification amounts to evaluating a set of pairing-product equations. These signatures make a perfect counterpart to Groth-Sahai proofs and turn out to have many more applications.

Thursday 12th November 2009:
Speaker: Cas Cremers (ETH Zurich)
Title: Formalizing and analyzing compromising adversaries
Abstract: We formalize a hierarchy of adversary models for security protocol analysis, ranging from a Dolev-Yao style adversary to more powerful adversaries who can reveal different parts of principals' states during protocol execution. We define our hierarchy by a modular operational semantics describing adversarial capabilities. We use this to formalize various, practically-relevant notions of key and state compromise. Our semantics can be used as a basis for protocol analysis tools. As an example, we extend an existing symbolic protocol-verification tool with our adversary models. The result is the first tool that systematically supports notions such as weak perfect forward secrecy, key compromise impersonation, and adversaries capable of so-called strong corruptions and state-reveal queries. As further applications, we use our model hierarchy to relate different adversarial notions, gaining new insights on their relative strengths, and we use our tool to find new attacks on protocols. Joint work with David Basin.

Thursday 19th November 2009:
Speaker: Christian Cachin (IBM Zurich)
Title: Cryptographic Interfaces: From Hardware-Security Modules to Open Key-Management Systems
Abstract: Cryptographic keys must be stored and managed. In real-world applications, they are often guarded by hardware-security modules (HSMs) with sophisticated physical protection. Several logical attacks through the key-management operations in cryptographic interfaces of HSMs have been reported in the past, which allowed to expose keys merely by exploiting the interface in unexpected ways. We are currently building a key-lifecycle management system accessible through an open protocol. We describe how to secure the system against attacks through its cryptographic interface. Its key-management operations integrate traditional access control with the semantics of cryptographic operations so that they respect the dependencies introduced through the cryptographic operations on keys. Based on joint work with Mathias Björkqvist, Nishanth Chandran, Robert Haas, Xiao-Yu Hu, Anil Kurmus, René Pawlitzek, and Marko Vukolic.

Thursday 26th November 2009:
Speaker: Kostas Markantonakis (ISG, RHUL)
Title: Secure and Efficient Mutual Authentication Protocol for Low-Cost RFID Systems
Abstract: In this work we propose a mutual authentication protocol for RFID (Radio Frequency Identification) systems incorporating low-cost RFID tags. These tags, due to their limited computational capabilities do not incorporate advanced cryptographic primitives. As a result, there are various threats against users’ privacy and against the security of such systems. Our protocol, PMM, utilizes a hash function and a pseudorandom number generator that can be hardware implemented in a low-cost RFID tag. The protocol offers a relatively high level of security by preventing replay attacks, Denial-of-Service attacks, tracking attacks, tag spoofing along with forward security and an enhanced protection of user privacy.

Thursday 3rd December 2009:
Speaker: Charles Morisset (ISG, RHUL)
Title: Comparing Access Control Models
Abstract: Many access control models exist in the literature and choosing one to enforce a security problematics require some tools both to implement it and to compare it with the others. We present here a formal generic definition of an access control model, based on the notion of state-machine, illustrated with well-known models (e.g. BLP or RBAC). We also define a preorder over access control models, mostly based on simulations, and compare formally some models, hence establishing a hierarchy among them. Indeed, we show that the Chinese Wall is strictly more restrictive than Bell & La Padula, which is strictly more restrictive than RBAC, which is equivalent to HRU. Joint work with Mathieu Jaume and Lionel Habib (LIP6)

Thursday 21st January 2010:
Speaker: Manuel Bernardo Barbosa (Universidade do Minho - Portugal)
Title: Deductive Verification of Cryptographic Software
Abstract: We apply state-of-the art deductive verification tools to check security-relevant properties of cryptographic software, including safety, absence of error propagation, and correctness with respect to reference implementations. We also develop techniques to help us in our task, focusing on methods oriented towards increased levels of automation, in scenarios where there are clear obvious limits to such automation. These techniques allow us to integrate automatic proof tools with an interactive proof assistant, where the latter is used off-line to prove once-and-for-all fundamental lemmas about properties of programs. The techniques developed have independent interest for practical deductive verification in general.

Thursday 28th January 2010:
Speaker: Carlos Cid (ISG, RHUL)
Title: Nonlinear Equivalence of Stream Ciphers
Abstract: We investigate (nonlinear) equivalences of LFSR-based stream ciphers using basic properties of Galois fields and certain nonlinear isomorphism maps. By doing this, we attempt to combine the analysis of both the sequence generator and the corresponding Boolean function in the security evaluation of filter generators. Our method can be seen as a way of constructing isomorphic ciphers and the focal point is then to study variance of cryptographic properties with respect to such an equivalence. It is shown that important cryptographic properties used to evaluate the security of filter generators, such as non-linearity and algebraic immunity, are not invariant with respect to such an equivalence. We conclude that cryptanalysis in terms of isolating cipher-components is not sufficient, as a certain cryptographic measurement must hold for all isomorphic ciphers in a class. As a result, analysis of such properties are likely to be very difficult in practice when taking the class of isomorphic ciphers into account.
(joint work with Sondre Roenjom; to be presented at FSE 2010)

Thursday 4th February 2010:
Speaker: Pooya Farshim (ISG, RHUL)
Title: Strong Security Models for Public-Key Encryption Schemes
Abstract: In this talk, we first establish a connection between two strong variants of standard security notions for public-key encryption schemes: indistinguishability under strong chosen-ciphertext attacks and complete non-malleability. Strong chosen-ciphertext attacks model adversaries who can maliciously replace public keys of users and subsequently ask for decryptions under unknown secret keys. Completely non-malleable schemes on the other hand resist attacks which allow an adversary to tamper with both ciphertexts and public keys (which can be used in constructing non-malleable commitment schemes). We give the first precise definition of a strong decryption oracle, pointing out the subtleties in alternative approaches that can be taken. In particular, we specify how to deal with invalid ciphertext and/or public keys and the inherent ambiguity in the message that the oracle should return. We extend indistinguishability of ciphertexts, comparison-based non-malleability and simulation non-malleability under various attack models to allow strong decryption queries. We show that the known relations for the standard versions of these definitions naturally extend to their stronger versions. We end the first part by presenting a practical scheme, which is fully secure against strong chosen-ciphertext attacks, and therefore completely non-malleable, without random oracles.

In the second part of the talk, we introduce two extractor-based properties that allow us to gain insight into the design of completely non-malleable schemes and to go beyond known feasibility results in this area. We formalise strong plaintext awareness and secret key awareness and prove their suitability in realising these goals. Strong plaintext awareness imposes that it is infeasible to construct a ciphertext under any public key without knowing the underlying message. Secret key awareness requires it to be infeasible to output a new public key without knowing a corresponding secret key. We study the relations among these and existing notions in the literature and show that if such properties are realisable (and one admits non-black-box simulators) then the impossibility result established for the construction of completely non-malleable schemes under non-assisted simulators no longer holds. We also look at how such notions can be realised in the standard model and in the random oracle model. More precisely, we propose a generic transformation to construct secret key aware schemes in the random oracle model and give preliminary steps towards building such schemes in the standard model. To this end, we employ a technique used in designing escrow encryption schemes and introduce a new factorisation-based knowledge assumption.

Thursday 11th February 2010:
Speaker: Jan-Erik Ekberg (Nokia Research Center, Finland)
Title: The Mobile Trusted Module
Abstract: The Mobile Trusted Module (MTM) is a specification by the Trusted Computing Group that defines a common API and a set of functionality for embedded devices among other things in the domains of secure boot, secure storage and attestation. It also defines an architecture by which this functionality can be mapped to legacy (processor) security architectures. The talk will briefly outline the use cases for, as well as the features of MTM, and as a case study outline a system adaptation done at the Nokia Research Center.

Thursday 18th February 2010 (This is a joint ISG/pure maths seminar)
Speaker: Mohan Shrikhande (Central Michigan University)
Title: A survey of embedding problems of Quasi-Residual Designs
Abstract: The notion of residual and derived design of a symmetric design goes back to a classic paper of R.C. Bose (1939). A residual design of a symmetric design D is a 2-design obtained from D by removing a block B and replacing every other block A by A\ B. A quasi-residual design is a 2-design which has the parameters of a residual design. A quasi-residual design which is a residual design is called embeddable.
In this survey talk, we begin with some classical results, then discuss some techniques for constructing quasi-residual designs and some different types of non-embeddability conditions. We include some recent results for families of non-embeddable quasi-residual designs. Proofs are provided for some new results and we give some tables of possible parameter sets of non-embeddable quasi-residual designs. This is joint work with T.A. Alraqad (see https://www.ma.rhul.ac.uk/pure_maths_seminars for more information).

Thursday 25th February 2010:
Speaker: Dave Boyd (ISG, RHUL)
Title: E-payments: Cardholder Privacy and Non-Repudiation
Abstract: Card payments tend not to keep the cardholder's details private, which can facilitate fraud, and it can be exceedingly difficult for a cardholder to repudiate a completed payment. This seminar is to outline proposed mechanisms to support cardholders by enhancing their privacy and non-repudiation capabilities.

Mechanisms are proposed that provide enhanced privacy and non-repudiation security services for both card-present and card-not-present payments. Each of these four categories of payment and security service requires its own scheme. Privacy is enhanced by stripping out personally identifiable information and using a different account number for each transaction. Non-repudiation is enhanced by leaving an electronic footprint after each transaction.

Web payments require particular attention. Banks are adept at authenticating clients. The final part of the seminar outlines further proposals to bring together those factors for a single sign-on service to the Web and a mechanism for client authentication in the TLS communications protocol.

Thursday 4th March 2010:
Speaker: Alex W. Dent (ISG, RHUL)
Title: Sufficient Conditions for Intractability over Black-Box Groups: Generic Lower Bounds for Generalized DL and DH Problems
Abstract: The generic (aka. black-box) group model is a valuable methodology for analyzing the computational hardness of number-theoretic problems used in cryptography. Since the properties ensuring generic hardness have not been well-studied and formalized yet, for each newly proposed problem an entire hardness proof has to be done from scratch.

In this work we identify criteria that guarantee the hardness of generalized DL and DH problems in an extended generic group model where algorithms are allowed to perform any operation representable by a polynomial function. Assuming our conditions are satisfied, we are able to provide negligible upper bounds on the success probability of such algorithms. As useful means for the formalization of definitions and conditions we explicitly relate the concepts of generic algorithms and straight-line programs that have only been used independently in cryptography so far.

Friday 12th March 2010 (note change of day/time for this week: the seminar will be on FRIDAY at 2PM, in room 229)
Speaker: Vitaly Shmatikov (The University of Texas at Austin, USA)
Title: New Directions in Privacy-Preserving Data Analysis
Abstract: The new Web economy relies on the collection of personal data on an ever-increasing scale. Information about our tastes, purchases, searches, browsing history, friendships and relationships, health history, genetics, and so forth is shared with advertisers, marketers, and researchers. The aggregated datasets do not exist in isolation; they contain implicit or explicit references to other datasets. Unsurprisingly, this raises a number of interesting privacy issues.

I will discuss the subtle relationship between anonymity and privacy, explain several techniques for de-anonymizing large datasets, and present experimental results which demonstrate how re-identification can be carried out on real-world datasets and social networks.

In the second part of the talk, I will describe the ongoing research on Airavat, a system for large-scale, privacy-preserving computation. Airavat is based on the MapReduce framework and includes a novel integration of mandatory access control and differential privacy. It enables users without security or privacy expertise to carry out computations on sensitive data, while ensuring compliance with the data providers' security policies.