# Seminar 2008-2009

September 17, 2008.Yannis C. Stamatiou. Dynamically reconfigurable block ciphers through parallel substitution box construction
October 8, 2008. Jorge L. Villar. Public Verifiability from Pairings in Secret Sharing Schemes
November 5, 2008. Carles Padró. Algebraic Manipulation Detection Codes
December 3, 2008. Javier Herranz. Restricted Oblivious Transfer and Secret Sharing
December 10, 2008. Oriol Farràs. On the access structure of Algebraic Geometric Schemes
December 17, 2008. Carla Ràfols. The security of all bits using list decoding
January 21, 2009. Jessica Metcalf-Burton. How to get from non-Shannon information inequalities to upper bounds on information rates
April 22, 2009. Javier Herranz. On the characterization of weighted threshold families
April 29, 2009. Frantisek Matus. Secret sharing schemes and entropy functions

Yannis C. Stamatiou. Univ.of Ioannina and Research Academic Computer Technology Institute

Dynamically reconfigurable block ciphers through parallel substitution box construction

Wednesday September 17, 2008, 15.30, Hall 204a, Building C3, Campus Nord

Abstract

The substitution boxes or s-boxes for short, are key elements of any good block cipher design. An n×m s-box takes as input n bits and produces in the output m bits. An s-box can, thus, be represented as an ordered set of m, n-bit Boolean functions, called the columns of the s-box. Over the years, a number of good s-box properties have been proposed so as to strengthen them against known attacks such as the linear and the differential cryptanalysis. One of these characteristics is the high non-linearity of the s-box, i.e. how far from being linear are its columns. One of the methodologies that have been proposed for building highly non-linear s-boxes is that proposed by Mister and Adams for the design of CAST-128, based on the lazy counting algorithm and the maximally non-linear Bent Boolean functions. This methodology essentially generates and checks all possible s-box column subsets so as to have high non-linearity. We have implemented this methodology and, as a rough empirical estimate, a 1600Mhz Pentium machine would need 2 days, on the average, to produce an 8×32 s-box with the specifications set by the method. We observed that columns up to 18 are produced relatively fast and if we assume that the time required to produce all of them is s seconds, then column i > 18 is produced in about 2[(i - 19 + 1)*s] seconds. The conclusion is that constructing s-boxes with this methodology is a computation intensive process that requires many days for a successful completion. However, a desirable characteristic of the process is that it scales well with available processor power. Having more processors, results in the production of a large number of s-box that would require many days to produce on a single machine. These s-boxes can be used to obtain observations about their properties in order to evaluate the whole s-box construction methodology and produce a number of good, dynamically reconfigurable CAST-like variants. The parallelization of the s-box construction method on the MareNostrum supercomputer of BSC is our target.

Jorge L. Villar. Universitat Politècnica de Catalunya

Public Verifiability from Pairings in Secret Sharing Schemes

Wednesday October 8, 2008, 12.00, Hall 204a, Building C3, Campus Nord

Abstract

We propose a new publicly verifiable secret sharing scheme using pairings with close relations to Shoenmakers' scheme. This scheme is efficient, multiplicatively homomorphic and with unconditional verifiability in the standard model. We formalize the notion of Indistinguishability of Secrets and prove that out scheme achieves it under the Decisional Bilinear Square (DBS) Assumption, that is a natural variant of the Decisional Bilinear Diffie Hellman Assumption. Moreover, our scheme tolerates active and adaptive adversaries.
(joint work with Somayeh Heidarvand)

Carles Padró. Universitat Politècnica de Catalunya

Algebraic Manipulation Detection Codes

Wednesday November 5, 2008, 12.00, Hall 204a, Building C3, Campus Nord

Abstract

Some ideas for the construction of asymptotically optimal algebraic manipulation detection codes for arbitrarily long messages are discussed.

Javier Herranz. IIIA - CSIC

Restricted Oblivious Transfer and Secret Sharing

Wednesday December 3, 2008, 12.00, Hall 204a, Building C3, Campus Nord

Abstract

In this talk we will consider the problem of restricted oblivious transfer: on the one hand, the owner of a database wants to restrict the access of users to this data according to some policy, in such a way that a user can only obtain information satisfying the restrictions imposed by the owner. On the other hand, a legitimate user wants to privately retrieve allowed parts of the data, without letting the owner know which part of the data is being obtained.
We will review two solutions that have been proposed to this problem. One is for the non-adaptive case, where the user decides at the same time all the entries of the database that he wants to retrieve (single execution of the query/retrieval phase). The other one is for the adaptive case, where the user can choose the next entries to retrieve depending on the previously obtained values. Both solutions strongly employ the concept of secret sharing schemes.

Oriol Farràs. Universitat Politècnica de Catalunya

On the probability of success of two related queries (I)

Wednesday December 10, 2008, 12.00, Hall 204a, Building C3, Campus Nord

Abstract

Chen and Cramer proposed a new family of linear secret sharing schemes (LSSS), constructed from algebraic geometric Goppa codes, that provide secure multiparty computation (MPC) protocols over small fields. In this talk, we analyze how these algebraic geometric LSSS can be used to obtain secure MPC protocols for general (non-threshold) adversary structures. Specifically, we study the access structures of (strongly) multiplicative LSSS that are constructed from hyperelliptic curves. In particular, we present non-threshold adversary structures for which is not possible to have efficient secure MPC protocols by combining threshold schemes, but it is possible by using algebraic LSSS.

Carla Ràfols.Universitat Politècnica de Catalunya

The security of all bits using list decoding

Wednesday December 17, 2008, 12.00, Hall 204a, Building C3, Campus Nord

Abstract

The relation between list decoding and hard-core predicates due to Akavia, Goldwasser and Safra has provided a clean and easy methodology to prove the hardness of certain predicates. So far this methodology has only been used to prove that the $O(\log \log N)$ least and most significant bits of any function with multiplicative access - which include the most common number theoretic trapdoor permutations- are secure.We will show that the method applies to all bits of any function defined on a cyclic group of order $N$ with multiplicative access for cryptographically interesting $N$. As a result, the security of all bits of RSA, the discrete logarithm in a group of prime order or the Paillier encryption scheme is reproved.
(joint work with Paz Morillo)

Jessica Metcalf-Burton.University of Michigan

How to get from non-Shannon information inequalities to upper bounds on information rates

Wednesday January 21, 2009, 12.00, Hall 204a, Building C3, Campus Nord

Abstract

The Vamos matroid induces two non-isomorphic secret-sharing access structures V_1 and V_6. Beimel, Livne and Padro used the Zhang-Yeung information inequality to prove that the information rates of V_1 and V_6 are bounded above by 10/11 and 9/10 respectively. I will show that by rearranging their argument and using other non-Shannon information inequalities we can improve the upper bounds to 19/21 for V_1 and 17/19 for V_6. In addition, I will explain how to read off an upper bound for the information rate of V_1 or V_6 directly from the coefficients of a non-Shannon information inequality, providing the coefficients of that inequality satisfy certain conditions.

Javier Herranz.Universitat Politècnica de Catalunya

On the characterization of weighted threshold families

Wednesday April 22, 2009, 12.00, Hall 204a, Building C3, Campus Nord

Abstract

One of the main components of a secret sharing scheme is the access structure $\Gamma\subset 2^{\mathcal{P}}$, which is the monotone family of subsets of elements that are authorized to recover the secret. Such structures also appear in other fields such as game theory. It is also well-known that there is a one-to-one relation between (monotone) families of subsets and (monotone) boolean functions. One of the most important examples of access structures are weighted threshold ones: there exist a threshold $t$ and an assignment of weights $\omega: \mathcal{P} \rightarrow \mathbb{Z}^+$ such that a subset $A$ is in $\Gamma$ if and only if $\sum\limits_{i \in A} \omega(i) \geq t$. In this talk we consider the problem of characterizing which monotone families are weighted threshold families. This problem was already studied in the 60's, using the language of boolean functions.
We will explain the main results that were obtained then, translating them into the language of families of subsets (or access structures). Finally, we will discuss a result about the characterization of bipartite weighted threshold families, which (as far as we know) has not been published before.

Frantisek Matus.Inst. Information Th. & Automation, Acad. Sciences Czech Republic

Secret sharing schemes and entropy functions

Wednesday April 29, 2009, 12.00, Hall 204a, Building C3, Campus Nord

Abstract

A secret sharing scheme arises from an access structure and random vector. It can be defined by prescribing linear constraints on Shannon entropies of subvectors of the vector. The entropy function of the random vector assigns Shannon entropy to each of its subvectors. Alternatively, it can be viewed as a point in a Euclidean space. Results on the entropic functions, or points, will be reviewed in terms of polymatroids, and then applied to secret sharing. In particular, the rates of a sss can be expressed via optimization problems over sets of entropic points and their limits.

Back to MAK's main page

Last Update: January 20, 2009