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.
Return to the top of this page
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)
Return to the top of this page
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.
Return to the top of this page
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.
Return to the top of this page
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.
Return to the top of this page
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)
Return to the top of this page
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.
Return to the top of this page
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.
Return to the top of this page
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.
Return to the top of this page
Back to MAK's main page
Last Update:
January 20, 2009