Coding and Cryptology

Frontmatter

An Infinite Class of Balanced Vectorial Boolean Functions with Optimum Algebraic Immunity and Good Nonlinearity

Abstract

In this paper, we study the cryptographic properties of an infinite class of balanced vectorial Boolean functions recently introduced by Feng, Liao and Yang. These functions provably achieve an optimum algebraic immunity. We give a simpler proof of this fact and we prove that these functions have also an optimum algebraic degree and a non-weak nonlinearity.

Claude Carlet, Keqin Feng

Separation and Witnesses

Abstract

We revisit two notions of difference between codewords, namely separation and the existence of small witnesses, and explore their links.

Gérard Cohen

Binary Covering Arrays and Existentially Closed Graphs

Abstract

Binary covering arrays have been extensively studied in many different contexts, but the explicit construction of small binary covering arrays with strength larger than three remains poorly understood. Connections with existentially closed graphs and Hadamard matrices are examined, particularly those arising from the Paley graphs and tournaments. Computational results on arrays generated by column translation, such as the Paley graphs, lead to substantial improvements on known existence results for binary covering arrays of strengths four and five.

Charles J. Colbourn, Gerzson Kéri

A Class of Three-Weight and Four-Weight Codes

Abstract

In this paper, a class of three-weight linear codes and a class of four-weight linear codes over GF(q) are presented and their weight distributions are determined. These codes are punctured from the irreducible cyclic codes, and contain optimal codes. Their duals contain also optimal codes.

Cunsheng Ding

Equal-Weight Fingerprinting Codes

Abstract

We consider binary fingerprinting codes that trace at least one of t pirates using the marking assumption. Ensembles of binary equal-weight codes are considered along with a new efficient decoding algorithm. The design substantially increases the code rates of the former fingerprinting constructions. In particular, for large t, the new t-fingerprinting codes have code rate of t ^− 2ln 2 and identify a pirate with an error probability that declines exponentially in code length n.

Ilya Dumer

Problems on Two-Dimensional Synchronization Patterns

Abstract

A synchronization pattern is a sequence of dots in which the out-of-phase autocorrelation function takes the values zero or one. These patterns have numerous applications in information theory. Recently, two-dimensional synchronization patterns have found application in key predistribution for wireless sensor networks. This application has raised some new questions. We will discuss some of the old and new questions in this area. We will describe several solution techniques and present some open problems.

Tuvi Etzion

A New Client-to-Client Password-Authenticated Key Agreement Protocol

Abstract

Client-to-client password-authenticated key agreement (C2C-PAKA) protocol deals with the authenticated key agreement process between two clients of different realms, who only share their passwords with their own servers. Recently, Byun et al. [13] proposed an efficient C2C-PAKA protocol and carried a claimed proof of security in a formal model of communication and adversarial capabilities. In this paper, we show that the protocol is insecure against password-compromise impersonation attack and the claim of provable security is seriously incorrect. To draw lessons from these results, we revealed fatal flaws in Byun et al.’s security model and their proof of security. Then, we modify formal security model and corresponding security definitions. In addition, a new cross-realm C2C-PAKA protocol is presented with security proof.

Deng-Guo Feng, Jing Xu

Elliptic Twin Prime Conjecture

Abstract

Motivated by a recent application to hash functions suggested by O. Chevassut, P.-A. Fouque, P. Gaudry and D. Pointcheval, we study the frequency with which both an elliptic curve over a finite field, and its quadratic twist are cryptographically suitable. Here, we obtain heuristic estimates for the number of such curves for which both the curve and its twist have a number of points which is prime. In a work in progress theoretical extimates are obtained wherein the number of such points on both curves has a prescribed arithmetic structure.

John B. Friedlander, Igor E. Shparlinski

Hunting for Curves with Many Points

Abstract

We construct curves with many points over finite fields by using the class group.

Gerard van der Geer

List Decoding of Binary Codes–A Brief Survey of Some Recent Results

Abstract

We briefly survey some recent progress on list decoding algorithms for binary codes. The results discussed include:

• Algorithms to list decode binary Reed-Muller codes of any order up to the minimum distance, generalizing the classical Goldreich-Levin algorithm for RM codes of order 1 (Hadamard codes). These algorithms are “local” and run in time polynomial in the message length.
• Construction of binary codes efficiently list-decodable up to the Zyablov (and Blokh-Zyablov) radius. This gives a factor two improvement over the error-correction radius of traditional “unique decoding” algorithms.
• The existence of binary linear concatenated codes that achieve list decoding capacity, i.e., the optimal trade-off between rate and fraction of worst-case errors one can hope to correct.
• Explicit binary codes mapping k bits to n ≤ poly(k/ε) bits that can be list decoded from a fraction (1/2 − ε) of errors (even for ε= o(1)) in poly(k/ε) time. A construction based on concatenating a variant of the Reed-Solomon code with dual BCH codes achieves the best known (cubic) dependence on 1/ε, whereas the existential bound is n = O(k/ε ²). (The above-mentioned result decoding up to Zyablov radius achieves a rate of Ω(ε ³) for the case of constant ε.)

We will only sketch the high level ideas behind these developments, pointing to the original papers for technical details and precise theorem statements.

Venkatesan Guruswami

Recent Developments in Low-Density Parity-Check Codes

Abstract

In this paper we prove two results related to low-density parity-check (LDPC) codes. The first is to show that the generating function attached to the pseudo-codewords of an LDPC code is a rational function, answering a question raised in [6]. The combinatorial information of its numerator and denominator is also discussed.

The second concerns an infinite family of q-regular bipartite graphs with large girth constructed in [8]. The LDPC codes based on these graphs have attracted much attention. We show that the first few of these graphs are Ramanujan graphs.

Wen-Ching Winnie Li, Min Lu, Chenying Wang

On the Applicability of Combinatorial Designs to Key Predistribution for Wireless Sensor Networks

Abstract

The constraints of lightweight distributed computing environments such as wireless sensor networks lend themselves to the use of symmetric cryptography to provide security services. The lack of central infrastructure after deployment of such networks requires the necessary symmetric keys to be predistributed to participating nodes. The rich mathematical structure of combinatorial designs has resulted in the proposal of several key predistribution schemes for wireless sensor networks based on designs. We review and examine the appropriateness of combinatorial designs as a tool for building key predistribution schemes suitable for such environments.

Keith M. Martin

On Weierstrass Semigroups of Some Triples on Norm-Trace Curves

Abstract

In this paper, we consider the norm-trace curves which are defined by the equation \(y^{q^{r-1}}+y^{q^{r-2}}+ \cdots +y=x^{\frac{q^r-1}{q-1}}\) over where q is a power of a prime number and r ≥ 2 is an integer. We determine the Weierstrass semigroup of the triple of points \(\left(P_{\infty}, P_{00}, P_{0b} \right)\) on this curve.

Gretchen L. Matthews

ERINDALE: A Polynomial Based Hashing Algorithm

Abstract

The aim of this article is to describe a new hash algorithm using polynomials over finite fields. In software, it runs at speeds comparable to SHA-384. Hardware implementation of a slightly modified version of the algorithm presented here runs at significantly faster speeds, namely at 2 Gbits/sec on an FPGA Virtex V of frequency 300 MHz. Modelling suggests that this speed can be increased to 3.4 Gbits/sec. Unlike most other existing hash algorithms, our construction does not follow the Damgard-Merkle philosophy. The hash has several attractive features in terms of its flexibility. In particular, the length of the hash is a parameter that can be set at the outset. Moreover, the estimated degree of collision resistance is measured in terms of another parameter whose value can be varied.

V. Kumar Murty, Nikolajs Volkovs

A Survey of Algebraic Unitary Codes

Abstract

This survey paper gives an overview of algebraic unitary codes. It describes the coding problem involved, and present several algebraic approaches yielding interesting constructions, as well as the latest bounds.

Frédérique Oggier

New Family of Non-Cartesian Perfect Authentication Codes

Abstract

The authentication codes based on the rational normal curves in projective spaces over finite fields were the first construction of the non-Cartesian t-fold perfect authentication codes for arbitrary positive integer t. In this paper it shows that the subfield rational normal curves provide a new family of such codes, its expected probabilities of successful deception for optimal spoofing attacks are less than those probabilities of former constructed codes in most cases.

Dingyi Pei

On the Impossibility of Strong Encryption Over $\aleph_0$

Abstract

We give two impossibility results regarding strong encryption over an infinite enumerable domain. The first one relates to statistically secure one-time encryption. The second one relates to computationally secure encryption resisting adaptive chosen ciphertext attacks in streaming mode with bounded resources: memory, time delay or output length. Curiously, both impossibility results can be achieved with either finite or continuous domains. The latter result explains why known CCA-secure cryptosystem constructions require at least two passes to decrypt a message with bounded resources.

Raphael C. -W. Phan, Serge Vaudenay

Minimum Distance between Bent and Resilient Boolean Functions

Abstract

The minimum distance between bent and resilient functions is studied. This problem is converted into two problems. One is to construct a special matrix, which leads to a combinatorial problem; the other is the existence of bent functions with specified types. Then the relation of these two problems is studied. For the 1-resilient functions, we get a solution to the first combinatorial problem. By using this solution and the relation of the two problems, we present a formula on the lower bound of the minimum distance of bent and 1-resilient functions. For the latter problem, we point out the limitation of the usage of the Maiorana-McFarland type bent functions, and the necessity to study the existence of bent functions with special property which we call partial symmetric. At last, we give some results on the nonexistence of some partial symmetric bent functions.

Longjiang Qu, Chao Li

Unconditionally Secure Approximate Message Authentication

Abstract

Approximate message authentication codes (AMAC) arise naturally in biometric and multimedia applications where plaintexts are fuzzy and a tagged message (x′, t) where t is the calculated tag for a message x that is ‘close’ to x′ should pass the verification test. Fuzziness of plaintexts can be due to a variety of factors including applying acceptable transforms such as compression and decompression to data, or inaccuracy of sensors in reading biometric data.

This paper develops a framework for approximate message authentication systems in unconditionally security setting. We give formal definition of AMAC and analyze two attacks, impersonation attack and substitution attack. We derive lower bounds on an opponent’s deception probability in these attacks under the assumption that all keys are equiprobable. Our bounds generalize known combinatorial bounds in classical authentication theory.

Dongvu Tonien, Reihaneh Safavi-Naini, Peter Nickolas, Yvo Desmedt

Multiplexing Realizations of the Decimation-Hadamard Transform of Two-Level Autocorrelation Sequences

Abstract

In an effort to search for new binary two-level autocorrelation sequences of period 2 ⁿ  − 1, a new method of iterative decimation-Hadamard transform is proposed. It is based on the Hadamard transform of a shift and decimation of a binary two-level autocorrelation sequence, and its multiplexing. The experimental results show that several known binary two-level autocorrelation sequences can be obtained from our method.

Nam Yul Yu, Guang Gong

On Cayley Graphs, Surface Codes, and the Limits of Homological Coding for Quantum Error Correction

Abstract

We review constructions of quantum surface codes and give an alternative, algebraic, construction of the known classes of surface codes that have fixed rate and growing minimum distance. This construction borrows from Margulis’s family of Cayley graphs with large girths, and highlights the analogy between quantum surface codes and cycle codes of graphs in the classical case. We also attempt a brief foray into the class of quantum topological codes arising from higher dimensional manifolds and find these examples to have the same constraint on the rate and minimum distance as in the 2-dimensional case.

Gilles Zémor

Backmatter