Contact:
Marcus Greferath
School of Math. Sciences
University College Dublin
Belfield, Dublin 4, Ireland
Phone:
+353-1-716-2588 (UCD)
+353-85-153-0951 (mobile)

Joachim Rosenthal
Institut of Mathematics
University of Zurich
Winterthurerstrasse 190
8057 Zurich, Switzerland
Phone:
+41-44-63 55884 (office)

ITW 2010 Dublin
IEEE Information Theory Workshop
Dublin, August 30 - September 3, 2010

Coding and information-theoretic methods in cryptography

Mon 30 Aug, 09.55-12.45, Room 1

Invited session
Organizer: Gérard Cohen

Sihem Mesnager Recent Results on Bent and Hyper-bent Functions and Their Link With Some Exponential Sums

Abstract: Bent functions are maximally nonlinear Boolean functions with an even number of variables. They were introduced by Rothaus in 1976. For their own sake as interesting combinatorial objects, but also because of their relations to coding theory (Reed-Muller codes) and applications in cryptography (design of stream ciphers), they have attracted a lot of research, specially in the last 15 years. The class of bent functions contains a subclass of functions, introduced by Youssef and Gong in 2001, the so-called hyper-bent functions whose properties are still stronger and whose elements are still rarer than bent functions. Bent and hyper-bent functions are not classified. A complete classification of these functions is elusive and looks hopeless. So, it is important to design constructions in order to know as many of (hyper)-bent functions as possible. This paper is devoted to the constructions of bent and hyper-bent Boolean functions in polynomial forms. We survey and present an overview of the constructions discovered recently. We extensively investigate the link between the bentness property of such functions and some exponential sums (involving Dickson polynomials). Mon 30 Aug, 09.55-10.20, Room 1

Constanza Riera and Matthew G. Parker Boolean Functions Whose Restrictions are Highly Nonlinear

Abstract: We construct Boolean functions whose non-trivial restrictions are either highly nonlinear with respect to the Walsh-Hadamard or the negahadamard transform. We generalise these properties, identify group actions that preserve them, and obtain complementary sets from our functions. Mon 30 Aug, 10.20-10.45, Room 1

Hugues Randriam Hecke operators with odd determinant and binary frameproof codes beyond the probabilistic bound?

Abstract: We give a slight improvement on Xing's lower bound for frameproof codes constructed from algebraic curves. Combined with some additional number-theoretic assumptions (still conjectural) and a concatenation process, this should lead to the existence of a family of binary 2-frameproof codes of asymptotic rate going beyond the up to now best known (non-constructive) lower bound. Mon 30 Aug, 10.45-11.10, Room 1

Alexander Barg, G. Robert Blakley, Grigory Kabatiansky, and Cedric Tavernier Robust parent-identifying codes

Abstract: Codes with the identifiable parent property (IPP codes) are used in traitor tracing schemes that protect data broadcast by the publisher from unauthorized access or distribution. An n-word y over a finite alphabet is called a descendant of a set of t words x1,...,xt if yi ∈ {x1i,...,xti} for all i=1,...,n. A code C={x1,...,xM} is said to have the t-IPP property if for any n-word y that is a descendant of at most t parents belonging to the code it is possible to identify at least one of them. The existence of good t-IPP codes is known from earlier works. We introduce a robust version of IPP codes which allows unconditional identification of parents even if some of the coordinates in y can break away from the descent rule, i.e., can take arbitrary values from the alphabet, or become completely unreadable. By linking this problem to perfect hash functions and, more generally, to hash distances of a code, we prove initial results on the proportion of such coordinates that can be tolerated under the unconditional recovery requirement. Mon 30 Aug, 11.30-11.55, Room 1

Davide Schipani and Joachim Rosenthal Coding Solutions for the Secure Biometric Storage Problem

Abstract: The paper studies the problem of securely storing biometric passwords, such as fingerprints and irises. With the help of coding theory Juels and Wattenberg derived in 1999 a scheme where similar input strings will be accepted as the same biometric. In the same time nothing could be learned from the stored data. They called their scheme a fuzzy commitment scheme. In this paper we will revisit the solution of Juels and Wattenberg and we will provide answers to two important questions: what type of error-correcting codes should be used and what happens if biometric templates are not uniformly distributed, i.e. the biometric data come with redundancy. Answering the first question will lead us to the search for low-rate large-minimum distance error-correcting codes which come with efficient decoding algorithms up to the designed distance. In order to answer the second question we relate the rate required with a quantity connected to the "entropy" of the string, trying to estimate a sort of "capacity", if we want to see a flavor of the converse of Shannon's noisy coding theorem. Finally we deal with side-problems arising in a practical implementation and we propose a possible solution to the main one that seems to have so far prevented in many situations real life applications of the fuzzy scheme. Mon 30 Aug, 11.55-12.20, Room 1

Julien Bringer, Hervé Chabanne, Gérard Cohen, and Bruno Kindarji Identification codes in cryptographic protocols

Abstract: Identification codes were introduced by Ahlswede and Dueck more than twenty years ago. There is today a lot of studies to identify objects such as contactless devices (for instance RFID tags) but, surprisingly, no one has considered the use of this kind of codes in the literature for that purpose until the recent work of Bringer et al. at Indocrypt '09. We here show how the security of these new identification protocols is related to some well-known problems in coding theory. We also extend the original proposal to a new problem. Mon 30 Aug, 12.20-12.45, Room 1

Back to previous page

Return to conference mainpage

SPONSORS