Seminars 2007

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.

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.

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.

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

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.

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.