Lucia Moura:

Title: Variable Strength Covering Arrays and Software Testing Applications

Abstract:

In this talk, I will discuss Variable Strength Covering Arrays.
Covering arrays are generalizations of orthogonal arrays that 
have been well studied and have applications in software and 
network testing. A covering array of strength t with n rows 
and k columns on v symbols is an n by k array such 
that in every set of t columns, every possible t-tuple of 
symbols occur in at least one row. We wish to minimize n for 
fixed t, k and v. Applications in software and network
testing identify the components/parameters of the system with 
the columns of the array, each component/parameter having v 
possible configurations/values. The set of rows of the array 
prescribe a test suite with the smallest possible number of 
tests, such that every t-way interaction of parameter values 
is tested in at least one of the tests. In summary, covering 
arrays are the combinatorial structures that yield the so-called 
Combinatorial Testing (see ACTS research at NIST).

Variable strength covering arrays (VCAs) are a  
generalizations of covering arrays that uses a hypergraph on 
the columns of the array, with hyperedges of arbitrary size 
specifying which sets of columns must have coverage. These 
objects are  interesting not only for being nice combinatorial 
designs but also because they address more complex testing 
models where different levels of interaction need to be tested 
among different sets of components. In this talk, I will survey 
joint work with Raaphorst and Stevens on VCAs and show two 
upper bounds on their number of rows. The first bound comes 
from a greedy algorithm that generalizes the density method 
of Bryce, Cohen  and Colbourn (2004, 2007) yielding an upper 
bound on the number of rows that is logarithmic on the number 
of columns. The second upper bound uses the probabilistic 
method and the Lov\'asz Local Lemma.

====================================================================

Thais Bardini Idalino:

Title: Using Combinatorial Group Testing to Solve Security Issues

Abstract:

We consider the problem of detecting and locating modifications in signed
data to ensure partial data integrity. We assume two scenarios, the first is
related to locating modifications in a signed document, where we divide it
into n blocks and assume a threshold d for the maximum amount of modified
blocks that the scheme can locate. We propose efficient algorithms for
signature and verification steps which provide a reasonably compact
signature size. The second scenario aims to locate invalid signatures in a
set of individually signed tuples stored in an outsourced database. We
introduce the concept of levels of signature aggregation, that allows the
querier to distinguish the valid tuples from the invalid ones while
decreasing the number of signatures transmitted, in contrast to traditional
aggregation, where even a single invalid tuple would invalidate the whole
query. Both schemes are based on nonadaptive combinatorial group testing and
cover-free families.

====================================================================

Lucas Perin:

Title: Low Complexity Cube Root Computation over F_3^m using Polynomial Basis

Abstract:

Barreto and Ahmadi's previous works shows us that it is possible to
significantly reduce the cost of Cube Root computations over F3m by
carefully selecting the irreducible polynomial definining the
extension. The impact of this is directly related to the performance
of some pairing-based cryptographic algorithms. To achieve better
performance, the number of nonzero coefficients (Hamming Weight) in
the polynomial representation of x^(1/3) should be low. We extend 
Ahmadi and Rodriguez-Henriquez's work and present a a generic 
construction of "Cube Root Friendly Polynomials". Furthermore, we
provide new extensions over F_3^m using irreducible heptanomials that
produce Hamming Weights equal to 1. 

====================================================================

Juliano Bandeira Lima:

Title: Trigonometry over Finite Fields: Theoretical Aspects 
and Application Scenarios

Abstract:

The first concepts related to trigonometry over finite fields were
proposed in the late 1990¹s, as a requirement for introducing the finite
field Hartley transform. Over the past few years, such concepts have
provided several developments, constituting the basis for defining other
transforms and describing Chebyshev polynomials, for instance. In this
presentation, besides reviewing theoretical aspects related to the
mentioned context, we intend to illustrate their applicability in
cryptography, signal processing, communications and error-correcting codes.

===================================================================

Daniel Panario:

Title: Open Problems for Polynomials over Finite Fields and Applications

Abstract:

We survey open problems for univariate polynomials over a finite field.

We first comment in some detail on the existence and number of several 
classes of polynomials. The open problems here are of a more theoretical 
nature.

Then, we center in classes of low-weight (irreducible) polynomials. 
The conjectures here are more practically oriented.

Finally, we give brief descriptions of a selection of open problems 
from several areas including factorization of polynomials, special 
polynomials (APN functions, permutation), and relations between 
integer numbers and polynomials.

===================================================================

Rodrigo dos Santos Veloso Martins:

Title: On the Heuristic of Approximating Polynomials over a 
Finite Field by Random Mappings

Abstract:

The study of iterations of functions over a finite field and the 
corresponding functional graphs is a growing area of research
with connections to cryptography. The behavior of such iterations 
is frequently approximated by what is know as the Brent-Pollard
heuristic, where one treats functions as random mappings. We aim 
at understanding this heuristic and focus on the expected rho 
length of a node of the functional graph of a polynomial over a 
finite field. Since the distribution of indegrees (preimage sizes) 
of a class of functions appears to play a central role in its 
average rho length, we survey the known results for polynomials 
over finite fields giving new proofs and improving one of the 
cases for quartic polynomials. We discuss the effectiveness of 
the heuristic for many classes of polynomials by comparing our 
experimental results with the known estimates for random mapping 
models defined by different restrictions on their distribution 
of indegrees. We prove that the distribution of indegrees of 
general polynomials and mappings have similar asymptotic 
properties, including the same asymptotic average coalescence. 
The combination of these results and our experiments suggests 
that these polynomials behave like random mappings, extending 
a heuristic that was known only for degree 2. We show numerically 
that the behaviour of Chebyshev polynomials of degree d > 1 over 
finite fields present a sharp contrast when compared to other 
polynomials in their respective classes.

===================================================================

Claudio Qureshi:

Title: Redei Actions on Finite Fields

Abstract: The dynamics of iterations of polynomials and rational functions
over finite fields have attracted much attention in recent years, in part
due to their applications to cryptography. In this talk we focus our
attention to certain family of functions called Rédei functions, we describe
its functional graph and we study its relation with certain class of
endomorphism over cyclic groups. We also discuss an algorithm to generate
Redei functions with prescribed length cycles.

===================================================================

Alfredo Viola:

Title: Correlation - Immune Boolean Functions and Applications to Cryptography

Abstract:

Boolean functions are very important cryptographic
primitives in stream or block ciphers. In order to be useful for
cryptographic applications, these functions should satisfy some
properties like high algebraic degree, high non linearity or being
correlation immune.

This talk presents a complete characterization of the first
order correlation immune Boolean functions that includes the
functions that are 1-resilient. Our approach consists in defining
an equivalence relation on the full set of Boolean functions
with a fixed number of variables. An equivalence class in this
relation, called a first-order correlation class, provides a measure
of the distance between the Boolean functions it contains and
the correlation-immune Boolean functions. The key idea consists
on manipulating only the equivalence classes instead of the
set of Boolean functions. To achieve this goal we introduce a
class operator to construct a class with n variables from two
classes of n − 1 variables.

In the second part of the talk we generalize these ideas for k-order
correlation immune functions, and the relation with covering arrays. 
At the end we present some problems we are woking on.

This is joint work with Jean-Marie Le Bars, Nicolás Carrasco, 
María Cecilia García y Sebastián Fonseca.

===================================================================