## Seminars 2007

 Title: How to Strengthen any Weakly Unforgeable Signature into a Strongly Unforgeable Signature Speaker: Ron Steinfeld Date: 17 December 2007 Venue: NIE Journal Room (NIE5-01-TR45) 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 Speaker: Masayuki AbeNTT Date: 29 November 2007 Time: 10.30am - 11.30am Venue: NIE5-01-TR45 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 Speaker: Christian Rechberger Date: 28 November 2007 Venue: NIE Journal Room, NIE5-03-04 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 Speaker: Etienne de Klerk Date: 20 November 2007 Time: 10.30am - 11.30am Venue: NIE5-01-TR45 Abstract: 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.

 Title: Pairing Based Threshold Cryptography  Improving on Libert-Quisquater and Baek-Zheng Speaker: Professor Yvo Desmedt Date: 9 November 2007 Time: 4.00pm - 6.00pm Venue: New MAS Computational Lab at SBS-B2n-02 Abstract: 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.

 Title: Mathematics and Economics Speaker: Dr John Lane Date: 31 October 2007 Time: 4.30pm - 5.30pm Venue: NTU LT3 Abstract: 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.

 Title: When does a problem have a solution: A computability-theorists view Speaker: Rod Downey Date: 26 October 2007 Time: 4.00pm - 6.00pm Venue: New MAS Computational Lab at SBS-B2n-02 Abstract: 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 Speaker: Fred Ezerman Date: 19 October 2007 Time: 4.00pm - 5.00pm Venue: New MAS Computational Lab at SBS-B2n-02 Abstract: The talk will cover two major primality testings1. The Miller-Rabin Algorithm2. The Agrawal-Kayal-Saxena Algorithm "Primes is in P"A brief discussion on the proof and complexity analysis of each will be presented

 Title: Cryptanalysis of LASH Speaker: Dr Scott Contini Date: 12 October 2007 Time: 4.00pm - 6.00pm Venue: New MAS Computational Lab at SBS-B2n-02 Abstract: he 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.

 Title: Simplifying Complexity for Mathematics Speaker: Mr Frankie Tiong Date: 9 October 2007 Time: 1.30pm - 3.00pm Venue: Computational Chemistry Lab (LT19A-B4-01) Abstract: 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.

 Title: Introduction to cryptographic hash functions Speaker: Dr Krystian Matusiewicz Date: 5 October 2007 Time: 4.00pm - 5.00pm Venue: New MAS Computational Lab at SBS-B2n-02 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 ofcryptography. 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" Speaker: Niranjan Balachandran Date: 26 September 2007 Time: 4.00pm - 5.00pm Venue: NIE Journal room (NIE 5-03-04) 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 Speaker: Dr Khoongming Khoo Date: 14 September 2007 Time: 3pm - 4pm Venue: New MAS Computational Lab at SBS-B2n-02 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.

 Title: Implementing gradient descent decoding Speaker: Robert A. Liebler Date: 7 September 2007 Time: 4.00pm - 5.00pm 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".

 Title: Deletion-Correcting Codes Achieving Both Perfectness and Optimality Speaker: Dr Alan Ling Date: 31 August 2007 Time: 4.00pm - 5.00pm Venue: New MAS Computational Lab at SBS-B2n-02 Abstract: One peculiarity with deletion-correcting codes is that perfect deletion-correcting codes are not always optimal, because the balls of radius $t$ with respect to Levenshte{\u\i}n distance may be of different sizes. There is interest, therefore, in determining when deletion-correcting codes exist that are both perfect and optimal.Bours has constructed perfect $q$-ary 2-deletion-correcting codes of length four and perfect $q$-ary 3-deletion-correcting codes of length five for certain congruence classes of $q$, but his codes are not always optimal. In this talk, we give constructions for $q$-ary 2-deletion-correcting codes of length four and $q$-ary 3-deletion-correcting codes of length five that are perfect and optimal for almost all $q$, leaving only a small finite number of cases in doubt. We also determine completely the spectrum of possible sizes for perfect $q$-ary 1-deletion-correcting codes of length three and perfect $q$-ary 2-deletion-correcting codes of length four, for all $q$.

 Title: Secure Multi -Party Computation Party Computation in Black in Black-Box Groups Box Groups Speaker: Associate Professor Wang Huaxiong Date: 24 August 2007 Time: 4.00pm - 6.00pm Venue: MAS Computational Lab (SBS-B2n-02) Abstract: Groups form a natural mathematical structure for cryptography. In particular, the most popular public-key encryption schemes today (RSA and Diffie-Hellman) both operate in abelian groups. However, the discovery of efficient quantum algorithms for breaking these cryptosystems gives increased importance to the construction of alternative cryptosystems in non-abelian abelian groups, where quantum algorithms seem to be less effective. Motivated by such emerging cryptographic applications of non-abelian abelian groups, we study the natural problem of secure multi-party computation (in the passive, computationally unbounded attack model) of functions of products in an arbitrary finite group.We reduce the problem of constructing such multi-party computation protocols to a party combinatorial colouring problem in planar graphs.We give two constructions for such graph colourings. The first colouring construction gives a protocol with optimal collusion resistance, but has exponential communication complexity.The second probabilistic colouring construction gives a protocol with suboptimal collusion resistance, and has polynomial communication complexity. We believe that our results can be improved by further study of the associated combinatorial problems.This is joint work with Yvo Desmedt, Josef Pieprzyk and Ron Steinfeld Steinfeld.

 Title: A random construction for Title: A random construction for permutation codes and covering radius Speaker: Dr Cheng Yeaw Ku Date: 17 August 2007 Time: 4.00pm - 6.00pm Venue: MAS Computational Lab (SBS-B2n-02) Abstract: Very recently, an operator channel was defined by r channel was defined by Koetter and Kschischang when they studied random network coding. They also introduced constant dimension codes and demonstrated that these codes can be employed to correct errors and/or erasures over the operator channel. Constant dimension codes are equivalent to the so-called linear authentication codes introduced by Wang, Xing and Safavi-Naini when constructing distributed authentication systems in 2003. In this paper, a relationship between constant dimension codes and binary constant weight codes is observed, and two Johnson type upper bounds, say I and II, on constant dimension codes are derived. It is shown that the Wang derived. It is shown that the Wang-Xing-Safavi-Naini bound is always better than the Singleton type bound derived by Koetter and Kschischang, and the Johnson type bound II slightly improves the Wang-Xing-Safavi-Naini bound. Furthermore, a necessary and sufficient condition for achieving the Wang-Xing-Safavi-Naini bound is obtained and it is shown that if a Steiner structure exists, there exists a corresponding constant dimension code which achieves the Wang-Xing-Safavi-Nainibound. Finally, a family of optimal bound constant dimension codes which achieves the Johnson type bounds I and II is obtained.

 Title: 10 Years of the Efficient BD-II Group Key Exchange Protocol Speaker: Dr Yvo G. Desmedt Date: 3 May 2007 Time: 3.00pm - 4.00pm Venue: NIE Psychomotor lab (NIE5-02-01), (NIE, Block 5, Level 2, Room 1) Abstract: While the work by Burmester-Desmedt (I) at Eurocrypt 1994 is well known, their work published in 1997 (BD-II) (presented at the Protocols Workshop, Cambridge in 1996) is unknown to most researchers. Some variants were reinvented, e.g. by Wong-GoudaLam, a paper heavily cited in the literature. The advantages of BD-II compared to BD-I are: (1) works in a broadcast/serial communication model, (2) BD-II is a compiler that can use any two party key exchange and transform it into a group key exchange protocol, (3) BD-II's computational and communication complexities are significantly lower. The security proof against a passive adversary is rather trivial. The work on guaranteeing the authenticity in group key exchange protocols is the root of new research. However, the Katz-Yung compiler results in an inefficient variant of BD-II. Recently a variant has been presented of this compiler that does not affect the efficiency of BD-II. In this presentation we survey some of the work published in these 10 years, compare BD-I and BD-II and explain how to deal with active attacks by outsiders. The last part is based on joint work with Tanja Lange and Mike Burmester and was presented at Financial Cryptography 2007.

 Title: Complex Double Bases applied to Scalar Multiplication on Algebraic Curves Speaker: Dr Fancesco Sica Date: 3 May 2007 Time: 1.00pm - 2.00pm Venue: NIE Psychomotor Lab(NIE5-02-01), (NIE, Block 5, Level 2, Room 1) Abstract: In elliptic curve based cryptography, the costliest operation is the computation of $nP=P+\cdots+P$, that is $n$ times a point $P$, called scalar multiplication. It is acknowledged that the existence of fast endomorphisms (such as the Frobenius on Koblitz curves) results in a clear performance speedup. I will expose how the use of a double base expansion of $n$ gives way to a new class of scalar multiplication algorithms capable of beating the fastest known implementations on Koblitz curves, with negligible additional memory.

 Title: “Unconditionally Secure Authentication Systems in Query Model” Speaker: Dr Rei Safavi-Naini Date: 19 March 2007 Time: 2.00pm - 3.00pm Venue: NIE Journal Room (NIE5-03-04), (NIE, Block 5, Level 3, Room 4) Abstract: Unconditionally secure authentication codes (A-codes) provide information theoretic security against spoofing. Traditional study if A-codes assume the adversary ‘observes’ the channel and then makes a fraudulent message. We consider an adversary who has ‘oracle access’ to authentication and versification algorithms and then spoofs. We show how to analyse the game and obtain the best strategy of the spoofer. This is used to derive information theoretic bound on the success probability of the adversary and obtain codes that satisfy the bound with equality.

 Title: “VSH: A Practical and Provable Collision Resistant Hash Function” Speaker: Dr Scott Contini Date: 14 February 2007 Time: 2.30pm - 3.30pm Venue: MME Journal Room (NIE7-03-16),  (NIE, Block 7, Level 3, Room 16) Abstract: Due to the recent work of Chinese researchers lead by Xiaoyun Wang, the most widely used hash functions are known to be insecure (MD4, MD5, SHA-0) or are on the brink of being broken (SHA-1). What did we do wrong? In this talk, we start by looking at the gap between the theory and the practice of cryptographic hashing. Historically, we see that due to the lack of a practical design that agreed with the theory, the research community has taken a heuristic approach to hashing. Furthermore, there have been attempts to build a theory justifying the heuristic approach (such as random oracles), but these attempts have several shortcomings. This introduction will motivate our new design, VSH, which is a practical solution to what theoreticians have asked for from as early as 1987. VSH can be combined with Cramer-Shoup signatures to provide an entirely provable and practical real-world solution

 Title: “ID-Based Cryptography Using Symmetric Primitives” Speaker: Professor Peter Wild Date: 26 January 2007 Time: 2.00pm - 3.00pm Venue: MME Journal Room (NIE7-03-16),  (NIE, Block 7, Level 3, Room 16) Abstract: Prof Peter Wild received his Ph.D. degree in Mathematics in 1980 from the University of London. He has worked at the Ohio State University, Columbus, Ohio; the University of Adelaide; and with the CSIRO, Australia. In 1984, he joined Royal Holloway where he is currently employed as a Professor in Mathematics. His research interests are in combinatorics, design theory, cryptography and coding theory. He has acted as a data security consultant for a number of companies offering advice in algorithm analysis, key management and user identification protocols.