Seminars

Title: How to Strengthen any Weakly Unforgeable Signature into a Strongly Unforgeable Signature

Date: 17-Dec-2007, (Monday)

Venue: NIE Journal Room (NIE5-01-TR45)

Speaker: Ron Steinfeld, Macquarie University, Australia

Abstract: Standard signature schemes are usually designed only to achieve weak unforgeability, preventing forgery of signatures on new messages not previously signed. However, some applications require strong unforgeability, preventing also forgery of new signatures on previously signed messages. Motivated by such applications, we present a general transform for strengthening a given weakly unforgeable signature into a strongly unforgeable signature using a trapdoor hash function. We also review other such transforms proposed in the literature.

Title: Compact CCA-Secure Encryption for Messages of Arbitrary Length

Date: 29-Nov-2007 (Thursday) 10:30 – 11:30am 

Venue: NIE5-01-TR45

Speaker: Masayuki AbeNTT, Japan

Abstract: This talk presents two new chosen-ciphertext secure public-key encryption schemes with minimal ciphertext expansion when encrypting plaintext messages of arbitrary length.

I'll however mainly forcus on its background and our first construction that is a Diffie-Hellman based scheme.  In terms of key-size and computational cost for encryption and decryption it is nearly as efficient as a plain ElGamal encryption.  The ciphertext overhead of our scheme is one group element which amounts to $2 \sep$ bits in elliptic curve groups with $\sep$-bit security. Here the novelty is the scheme's versatility: the optimal overhead is obtained for short and long messages alike, which is not possible for known schemes such as DHIES.  The security is proven based on the gap Diffie-Hellman assumption in the random oracle model.  Handling both long and short plaintext causes a technical difficulty in the proof.
I'll present an overview of our security proof. If time allows, an RSA-based scheme will be presented, too.

These properties are obtained by incorporating the idea of redundancy-free design and the feedback structure from the symmetric-part to the asymmetric-part, which eliminates the use of chosen-ciphertext secure symmetric encryption for encrypting arbitrary messages.

This is a joint work with Eike Kiltz and Tatsuaki Okamoto.

Title: Security of SHA-1

Date: 28-Nov-2007

Venue: NIE Journal Room, NIE5-03-04

Speaker: Christian Rechberger, Craz University of Technology, Austria

Abstract: After the spectacular results on collisions for popular hash functions like MD4 and MD5 in 2004, also the security of SHA-1 is called into question. SHA-1 is ubiquitously used throughout a wide range of applications, and hence deserves special attention from the cryptanalyst community.

Even for finding random looking collisions, the published attacks remain theoretical since they require a too high workfactor. After developing a new shortcut attack which is estimated to be around a million times faster than generic attacks, we started a distributed computing project to find the first SHA-1 collision: Collision Search Graz.

Some applications of SHA-1 do not require collision resistance but only rely on preimage or second preimage resistance, a property that is generally assumed to be much harder to violate. Nevertheless, some of our very recent results indicate that we might see a development similar to collision attacks.

Title: Exploiting algebraic symmetry in semidefinite programming relaxations of the quadratic assignment problem

Date: 20th-Nov-2007 (Tuesday) 10.30am

Venue: NIE5-01-TR45

Speaker: Etienne de Klerk

We consider semidefinite programming (SDP) relaxations of the quadratic assignment problem (QAP), and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem

library:
[R.E. Burkard, S.E. Karisch, F. Rendl. QAPLIB --- a quadratic assignment problem library. Journal on Global Optimization, 10: 291-403, 1997].

An important special case of the QAP is the traveling salesman problem (TSP). We show that the symmetry reduction technique may be used here to obtain an interesting new SDP relaxation of TSP.

This is joint work with Renata Sotirov at Tilburg University.

About the speaker: Etienne de Klerk is an Associate Professor at Tilburg University (Netherlands). His main research area is optimisation, in particular semidefinite programming and its applications. More can be found on his homepage at http://stuwww.uvt.nl/~edeklerk/

Prof. de Klerk is visiting MAS/SPMS/NTU until 24th Nov.

Talk 1: Pairing Based Threshold Cryptography  Improving on Libert-Quisquater and Baek-Zheng

Date: 9-Nov-2007 (Friday) 4pm - 6pm 

Venue: New MAS Computational Lab at SBS-B2n-02

Speaker: Prof Yvo Desmedt, University College of London, UK

We apply techniques from secret sharing and threshold decryption to show how to properly design an ID-based threshold system in which one assumes no  trust in any party. In our scheme:

  *) We avoid that any single machine ever knew the master secret s of the trusted authority (TA). Instead  only shares of it will be known by parties of the distributed TA and it can be seen as a virtual key.

  *) The threshold t_{TA} and the number of shareholders n_{TA} used by the distributed TA do not need to be identical to the ones used by user ID. Moreover, each user ID can use its own values for the threshold t_{i} and the number of parties n_{i} that will acquire shares.

  *) No single machine will ever know the secret key of the user -- this means no single machine in the distributed TA and no shareholder of the user ID. Like Baek and Zheng suggest, such a scheme can be turned into a mediate system.

Talk 2: Privacy-Preserving Techniques for Distributed Data Mining

Speaker: Chunhua Su, Kyushu University, Japan.

Data Mining is a analyzing technology which can get the automated extraction of hidden predictive information from databases. In today's information age, data collection is ubiquitous.  and data mining is becoming increasingly common in both the private and public sectors.However, it also brings the problem of sensitive information leakage. Both individual and enterprise may suffer from the massive data collection and the information retrieval by the distrusted parties. For meeting the privacy concern, Privacy preserving data mining (PPDM) technique is becoming a more and more important issue nowadays, particularly in the security and defense area. In this talk, I will give a introduction of our research on privacy-preserving techniques in distributed data mining.

Title: Mathematics and Economics

Date: 31-Oct-2007, (Wednesday) 4.30pm - 5.30pm 

Venue: NTU LT3

Speaker: Dr John Lane (London School of Economics)

In this talk, Dr. John Lane will talk about the sort of mathematical techniques that are used in economics and what areas of economics these techniques are applied to. Dr. Lane will also emphasize that to be a good economist, one needs strong modelling skills, which overide both discursive economics and math techniques.

Date: 26th-Oct-2007 (Friday), 4pm - 6pm

Venue: New MAS Computational Lab at SBS-B2n-02

Speaker: Rod Downey

This talk will give a broad brush account of the development of computability theory as a possible solution to the question above from intuitive ideas dating back to Euclid, culminating in some recent uses of computability theory to show that certain classification problems don't have any reasonable set of invariants.
Time permitting, I will also look at somne recent developments in complexity theory.

This talk is aimed at advanced undergraduates and is meant for a completely general audience.

Title: Primality Testing

Date: 19-Oct-2007 (Friday), 4pm - 5pm 

Venue: New MAS Computational Lab at SBS-B2n-02

Speaker: Fred Ezerman

The talk will cover two major primality testings
1. The Miller-Rabin Algorithm
2. The Agrawal-Kayal-Saxena Algorithm "Primes is in P"

A brief discussion on the proof and complexity analysis of each will be presented

Talk 1: Cryptanalysis of LASH

Date: 12th-Oct-2007 (Friday) 4pm - 6pm

Venue: New MAS Computational Lab at SBS-B2n-02

Speaker: Dr. Scott Contini

The LASH-x cryptographic hash function was introduced at NIST's second hash function workshop.  The design is an attempt to transform a provable hash by Goldreich, Goldwasser, and Halevi into something practical.  In this talk, we show that LASH falls far short of the designers' security goals since it is vulnerable to a  2^(4x/11)  collision attack and a  2^(4x/7) preimage attack, where  x  is the size of the LASH output.  Consequently, the smallest variant, LASH-160 (x = 160), is within reach of being broken in practice using a large computing effort.

Since our attacks exploit the designers' unwise choice of an all zero initial vector (IV), we then consider whether the function can be patched simply by changing this IV.  In this case we show that for any IV, LASH is vulnerable to a  2^(7x/8) preimage attack.  Moreover, we also show that LASH is easily distinguished from a PRF when the IV (or any other inputs) is replaced with a secret key.

Joint work with Krystian Matusiewicz, Josef Pieprzyk and Ron Steinfeld from Macquarie University, and Guo Jian, Ling San, and Wang Huaxiong from NTU.

Talk 2: Doing research (in cryptography) -- tools of the trade

Speakers: Dr. Scott Contini and Dr Krystian Matusiewicz

In this talk we try to address the question of what is necessary for successful research, focusing on research in cryptography. We try to analyse the research process and give our opinions on what are the important factors that contribute to the final success. We list some of the tools and skills that proved particularly useful for us. We believe this talk may benefit some people just starting their research experience like PhD and Masters students.

Engineers, scientists and educators around the world use the power of Maple for performing everyday calculations, developing advanced mathematical models and creating user-friendly technical applications.
Come join us in our seminar to find out how you can solve the most complex technical problems today!

Simplifying Complexity for Mathematics
9th October 2007, Tuesday
1330hrs – 1500hrs
Computational Chemistry Lab (LT19A-B4-01)

Seminar Highlights
This seminar aims to share innovative techniques on how Mathematics learning and teaching can be of ease. It will also showcase various applications on how to solve complex mathematics problems.

Presenter
Mr. Frankie Tiong, Programmer, i-Math Pte Ltd, graduated with a Master of Science in Informatics and Control from Coventry University, United Kingdom. He is currently in charge of the application support for Maple's products. He will showcase on how Maple 11 and Toolboxes help in Mathematics fields.

Who Should Attend
Familiarity with the products is not required.
This free technical seminar is intended for anyone involved in mathematics.

Title: Introduction to cryptographic hash functions

Date: 5-Oct-2007 (Friday), 4pm – 5pm

Venue: New MAS Computational Lab at SBS-B2n-02

Speaker:  Dr. Krystian Matusiewicz

Abstract: Cryptographic hash functions constitute an important class of
cryptographic primitives and are ubiquitous in modern cryptography. In
this talk we present an overview of this interesting area of
cryptography. After motivating the interest in cryptographic hash
functions we discuss various security requirements and explain three
main design strategies: hash functions based on block ciphers, functions
based on intractable problems and dedicated heuristic designs. We
briefly summarize the current situation in the world of hash functions
and outline the future challenges, especially in the context of the
coming Advanced Hash Standard competition.

TITLE: "PSL(2,q) and Simple 3-designs, q congruent to 1 modulo 4"

Date: 26-Sep-2007 (Wednesday) 4pm – 5pm

Venue: NIE Journal room (NIE 5-03-04)

SPEAKER: Niranjan Balachandran

(A paper of the same title will appear in the September, 2007 special issue of Designs, Codes, and Cryptography celebrating Dan Hughes' 80th
birthday)

ABSTRACT: The action of PSL(2,q) on the projective line $\mathbb{F}_q\cup\{infty\}$ is $3$-homogenous if and only if q is congruent to 3 modulo 4. In the case of q being 1 modulo 4, the action is never $3$-homogenous. Nonetheless we seek to construct simple 3-designs by taking unions of orbits. We obtain infinite families of such simple 3 designs which are also minimal and also prove a general asymptotic existence theorem where one can always obtain such 3-designs for all possible block sizes.

Title: On an Improved Correlation Analysis of Stream Ciphers Using Muti-Output Boolean functions and the Related Generalized Notion of Nonlinearity

Date: 14-Sep-2007 (Friday), 3pm - 4pm

Venue: New MAS Computational Lab at SBS-B2n-02

Speaker: Dr Khoongming Khoo

Abstract: We investigate the security of $n$-bit to $m$-bit vectorial Boolean functions in stream ciphers. Such stream ciphers have higher throughput than those using single-bit output Boolean functions. However, as shown by Zhang and Chan at Crypto 2000, linear approximations based on composing the vector output with any Boolean functions have higher bias than those based on the usual correlation attack. In this paper, we introduce a new approach for analyzing vector Boolean functions called generalized correlation analysis. It is based on approximate equations which are linear in the input $x$ but of free degree in the output $z=F(x)$. The complexity for computing the generalized nonlinearity for this new attack is reduced from $2^{2^m \times n+n}$ to $2^{2n}$. Based on experimental results, we show that the new generalized correlation attack gives linear approximation with much higher bias than the Zhang-Chan and usual correlation attack. We confirm this with a theoretical upper bound for generalized nonlinearity, which is much lower than for the unrestricted nonlinearity (for Zhang-Chan's attack) and {\em a fortiori} for usual nonlinearity. We also prove a lower bound for generalized nonlinearity which allows us to construct vector Boolean functions with high generalized nonlinearity from bent and almost bent functions. We derive the generalized nonlinearity of some known secondary constructions for secure vector Boolean functions. Finally, we prove that if a vector Boolean function has high nonlinearity or even a high unrestricted nonlinearity, it cannot ensure that it will have high generalized nonlinearity.

This is a joint work with Claude Carlet, Chu-Wee Lim and Chuan_wen Loe.

Coding and Crypto Seminar

Title: Implementing gradient descent decoding

Date: 07-Sep-2007 (Friday), 4pm – 5pm

Speaker: Robert A. Liebler

Venue: New MAS Computational Lab at SBS-B2n-02

Abstract: Recently there has been substantial interest in iterative decoding. Working with a binary symmetric channel and your favorite code, I show how to find a (highly redundant) parity check matrix for which a simple gradient function, that I call "syndrome misery", gives provably accurate, efficient, optimal decoding. A variety of examples are presented.The effect of this work is to show that almost all of the decoding problem's difficulty can be shifted away from "implementation cost" to "design complexity".