Date: 18 June 08 (Wed)
Time: 4pm

Venue: SS2-01-17, TR100

Title: Network FRESCO: A Framework for Experimental Screening, Control, and Optimization

Seminar Abstract: FRESCO is an interdisciplinary project driven by the challenging long-standing problem of optimizing performance of wireless networks under changing operating conditions. A new experimental design called a locating array is introduced to efficiently identify significant factors and low-order interactions of factors when the number of factors is massive.  Profile-driven regression is a new hybrid regression methodology to address the issues in non-linear modelling through the use of profiling. The methodology is applied to derive models from a stochastic simulation of a mobile ad hoc network. Novel self-tuning techniques are developed to decide when and what localized measurements are needed in the network to drive the real-time statistical monitoring, model evolution, and adaptive control to optimize network performance as conditions change.

About the Speaker: Violet R. Syrotiuk earned her Ph.D. in Computer Science from the University of Waterloo (Canada) in 1992. She joined Arizona State University in 2002 and is currently an Associate Professor of Computer Science and Engineering. Dr. Syrotiuk's research has been supported by the U.S. National Science Foundation, Los Alamos National Laboratory,  Defence Science and Technology Organisation (Australia), Architecture Technology Corp., Raytheon Co., and General Dynamics.  She serves on the Editorial Board of Computer Networks and the International Journal of Communication Systems, and on the Technical Program Committee of several major conferences including Mobicom, Mobihoc, and Infocom. Her research interests include medium access control (MAC) and higher layer protocols for multi-hop wireless networks.

VENUE : Block N2, Level 4, Section A, Room no. 2

SEMINAR TITLE : Externalities in Algorithmic Game Theory

SEMINAR EXTRACT : In recent years, there has been a great deal of interests in research at the boundaries between algorithms, game theory and economics. This is because many important artifacts, such as the Internet and the web, are deeply affected by cooperation and competition among parties with different economic interests, and logarithms and protocols, e.g. for routing, resource allocation and electronic commerce, need to be rethought in light of these economic effects.

We consider one particular effect, externalities (or network effects), that links the value of a good to a consumer to the set of other consumers having that good. We will review recent studies on externalities in different areas (including mechanism design, viral marketing and social networks, online dating systems, and envy-free pricing) in algorithmic game theory, and discuss directions for future study.

ABOUT THE SPEAKER : Ning Chen is a Ph.D. candidate in the department of Computer Science & Engineering at the University of Washington, Seattle. He obtained his B.S and M.S. degree both from Fudan University, Shanghai, 2001 and 2004. His research interests include Algorithmic Game Theory, Computational Economics, and Algorithmic and Economic aspects of the Internet.

Title: Coset Stabilized Quantum Codes: New quantum codes from Goethals and Preparata codes

Lecturer: Markus Grassl (Institute for Quantum Optics and Quantum Information Austrian Academia of Sciences Innsbruck, Austria).

Venue: NIE Blk 5 Level 1 – TR45

Seminar Abstract :
Most of the quantum error-correcting codes (QECCs) are based on the stabilizer formalism which relates quantum codes to certain additive codes over GF(4). However, it is known that non-additive QECCs can have a higher dimension compared to additive QECCs with the same length and minimum distance. The most prominent example is the code
((5,6,2)) of Rains et al. More recently, some improved one-error-correcting codes of length 9 and 10 have been found. All these codes can be described as codeword stabilized (CWS) quantum codes.
The class of CWS QECCs is very rich, it includes e.g. all stabilizer codes. The prize we have to pay for this generality is that with increasing length it is getting more difficult to find good codes.

Based on the classical non-linear binary Goethals and Preparata codes, we obtain a new family of non-additive quantum codes with parameters ((2^m,2^{2^m-5m+1},8)). The dimension of these codes is eight times higher than the dimension of the best known additive quantum codes of equal length and minimum distance.

Title: Sequences with good correlation properties
Speaker: Professor K.T. Arasu Wright State University)
Venue: NIE Journal Room (NIE5-03-04)

Abstract: See Attached

Venue: NIE Blk 5 Level 1 – TR45

Title: Mean Values of Cubic Character Sums

Speaker:
Dr. Stephan Baier completed his Ph.D. at the Free University in Berlin, Germany. He has held postdoctoral position in Harish-Chandra Research Institute, the University of Cambridge and Queen’s University in Canada. His research area is in analytic number theory. Currently, he is working as a lecturer in Jacobs University in Bremen.

Seminar:
This is joint work with Matthew Young. Our main result is the following: There exist infinitely many primitive Dirichlet characters $\chi$ of order 3 such that $L(s,\chi)$ does not vanish at the central point, i.e. $L(1/2,\chi)\not=0$. More precisely, the number of such characters with conductor $\le Q$ is $\gg Q^{4/5}$. This result will be deduced from a new asymptotic estimate for the average of $L(1/2,\chi)$ and a new bound for the first moment of $L(1/2,\chi)$ for cubic characters $\chi$. As tools we use the approximate functional equation and certain recursive estimates on cubic character sums.

Venue: NIE Journal Room (NIE, blk. 5 lev. 3)

Title: Amalgams and representations

Speaker: Prof. A.A.Ivanov, Imperial College (London)

Abstract: See Attached

Venue: NIE Blk 7 Level 1 – TR53

Title: Non Vanishing of L functions

Speaker:
Jeff Hoffstein does research in number theory, automorphic forms and multiple Dirichlet series. In 1996 he, Jill Pipher, Joe Silverman created the NTRU public key cryptosystem and founded the company NTRU.

Abstract :
It is well known that given an elliptic curve, whose L-series has a positive sign in its functional equation, there must exist a quadratic twist of the L-series that does not vanish at the center of the critical strip. Suppose one is given two such elliptic curves. Must there exist a quadratic twist such that both L-series simultaneously do not vanish at the center of the critical strip? I'll show that the answer to this question is yes.

Venue: NIE Blk 7 Level 1 – TR53

Title : Public Key Crypto Systems and NTRU

Speaker:
Jeff Hoffstein does research in number theory, automorphic forms and multiple Dirichlet series. In 1996 he, Jill Pipher, Joe Silverman created the NTRU public key cryptosystem and founded the company NTRU.

Abstract :
I'll describe a public key cryptosystem called NTRU. Depending on how one wants to look at it, NTRU is based on convolution rings of polynomials, or on lattices over the integers. It differs from other public key cryptosystems in that the fundamental hard problem it is based on is the difficulty of finding short vectors in lattices of high dimension. It is not based on integer factorization, as in RSA, or the discrete logarithm problem, as in Diffie-Hellman and elliptic curve based cryptosystems. As a result, it is considerably faster and more efficient, and better suited for low powered devices such as cell phones. I will assume no previous knowledge of cryptography or lattices, and the lecture should be entirely self contained.

Abstract: Quantum groups appeared aproximately 25 years ago as a tool
to solve the so-called Yang-Baxter equation. They appeared in form of basic examples and these examples wererelated to simple complex finite dimensional Lie algebras, polynomial Lie algebras, and loop algebras

In the talk I will explain the notion of quantum group and its classical limit, Lie bialgebra.Surprisingly, it turned out to be possible to classify quantum groups,which have  simple complex finite dimensional Lie algebras and
polynomial Lie algebras as the classical limit. 

Venue: NIE Journal Room

Title: Pairing friendly elliptic curves and fields.

Speaker: Professor Igor Shparlinski

Abstract: We present some theoretic and heuristic estimates for the number of elliptic curves with low embedding which is essential for their applicability in pairing based cryptography. We also give estimates for the number of fields over which such curves may exist. The main ideas behind the proofs will be explained as well. Finally, we give a heuristic analysis of the so-called MNT algorithm and show that it produces a rather "thin" sequence of curves.

About the Speaker: Professor Igor Shparlinski
from Macquarie University, Australia
Website: http://www.comp.mq.edu.au/~igor/

Venue:  NIE5-01-TR44

Title: Feebly trapdoor functions

Speaker: Edward A. Hirsch; S.I.Nikolenko

Abstract: One-way functions are the basic primitive of private-key cryptography. However, no provably one-way functions (the ones that can be computed more than polynomially faster than inverted) are known. A natural question is to construct a function that would be at least a little bit (provably!) harder to compute than to invert (call it feebly secure one-way function). Alain Hiltgen (1992) answered this question affirmatively by constructing a function that can be computed by n+O(1)-size circuits but can be inverted only by 2n-size circuits. However, similar constructions of other cryptographic primitives remained unknown.

Trapdoor functions are the basic primitive of public-key cryptography. In this work we construct a family of feebly secure trapdoor functions. This is joint work with Sergey Nikolenko.

About the speaker: Dr. Edward Hirsch is a staff member of the Steklov Institute of Mathematics at St. Petersburg, his research concerns computational complexity and proof theory. More information, including recent publications etc, can be found on his homepage: http://logic.pdmi.ras.ru/~hirsch/

Venue: NIE Journal Room, NIE5-03-04

Title: Fast family of Stream Ciphers: TPY

Speaker: Prof Jennifer Seberry
University of Wollongong, Australia

Abstract: We use software rolling arrays to make a new very fast stream cipher family. This is joint work with Eli Biham

About the speaker: Dr Seberry graduated PhD in Computation Mathematics from La Trobe University in 1971. She has subsequently held positions at the Australian National University, The University of Sydney and University College, The Australian Defence Force Academy, The University of New South Wales. She has published extensively in Discrete Mathematics and is world renown for her new disco

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

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

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.

Venue: NIE5-01-TR45

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

Speaker: Masayuki Abe
               NTT, 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.

Venue: NIE Journal Room, NIE5-03-04

Title: Security of SHA-1

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: http://boinc.iaik.tugraz.at>SHA-1 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.

Venue: NIE5-01-TR45

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

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.

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

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

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.

Venue: NTU LT3

Title: Mathematics and Economics

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.

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

Title: When does a problem have a solution: A computability-theorists view

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.

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

Title: Primality Testing

Speaker: Fred Ezerman 

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

Talk 1: Cryptanalysis of LASH

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

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"

Venue of this talk : 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

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

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".

A random construction for permutation codes and covering radius
Dr Cheng Yeaw Ku (California Institute of Technology)

-------------------------------------------------------------------------------

Constant Dimension Codes and the Wang-Xing-Safavi-Naini Bound
Dr Fangwei Fu (Naikai University)