DSpace Collection:
http://hdl.handle.net/2307/30
20180526T14:03:56ZModel and Domain Independence : an Experience in Model Management and Information Extraction
http://hdl.handle.net/2307/4567
<Title>Model and Domain Independence : an Experience in Model Management and Information Extraction</Title>
<Authors>Toti, Daniele</Authors>
<Issue Date>20120419</Issue Date>
<Abstract>Information systems play a crucial role in handling the
ow of informa
tion generated, exchanged, acquired and stored nowadays. The strife to pursue
model and domainindependent approaches by prescinding from the speci city
of their respective instances is a natural way to keep advancing towards more
scalable and interoperable information systems, and therefore contributing to
the creation of a more cohesive and productive world. In this regard, this dis
sertation addresses the problem of model and domain independence applied
to two critical elements of the whole lifecycle of information management: the
modeling and design phase, and the acquisition and storage phase, respectively
exempli ed here by the areas of Model Management and Information Extrac
tion. Speci cally, in this Thesis we rst focus on the topic of modelindependent
schema and data translations, where we show an extension of a model manage
ment operator at both the conceptual and the operative level, by introducing
the concepts of inheritance and polymorphism within its underlying data dic
tionary and the rules used to perform the actual translations. Subsequently, we
shift our attention towards the automatic discovery of abbreviations from full
text scienti c papers, where we propose a domainindependent methodology to
identify and resolve acronyms and abbreviations and match them with entities
of a given domain, all within a suitable implementing framework. Eventually,
we discuss potential future directions of this research, by introducing the con
cept of semantic similarity among ontologies and the challenge of automatically
build them and align them, in order to both extend the proposed methodology
and tackle wider areas of knowledge discovery.</Abstract>20120418T22:00:00ZAmalgamation of algebras and the ultrafilter topology on the Zariski space of valuation overrings of an integral domain
http://hdl.handle.net/2307/4074
<Title>Amalgamation of algebras and the ultrafilter topology on the Zariski space of valuation overrings of an integral domain</Title>
<Authors>Finocchiaro, Carmelo Antonio</Authors>
<Issue Date>20110224</Issue Date>20110223T23:00:00ZRole mining techniques to improve RBAC administration
http://hdl.handle.net/2307/3996
<Title>Role mining techniques to improve RBAC administration</Title>
<Authors>Colantonio, Alessandro</Authors>
<Issue Date>20110510</Issue Date>
<Abstract>Access control is currently one of the most important topics in ICT security. The main areas of research related to access control concern the identification of methodologies and models to efficiently administer user entitlements. With the everincreasing number of users and IT systems, organizations have to manage large numbers users’ permissions in an efficient manner. Rolebased access control (RBAC) is the most widespread access control model. Yet, companies still find it difficult to adopt RBAC because of the complexity of identifying a suitable set of roles. Roles must accurately reflect functions and responsibilities of users in the organization. When hundreds or thousands of users have individual access permissions, adopting the best approach to engineer roles saves time and money, and protects data and systems. Among all role engineering approaches, searching legacy access control systems to find de facto roles embedded in existing permissions is attracting an increasing interest. Data mining techniques can be used to automatically propose candidate roles, leading to a class of tools and methodologies referred to as role mining.
This thesis is devoted to role mining techniques that help security analysts and administrators maximize the benefits of adopting RBAC. To this aim, we consider the role mining problem from several viewpoints. First, we propose a costdriven approach to identify candidate roles. This approach measures and evaluates cost advantages during the entire roleset definition process. This allows to easily integrate existing bottomup approaches to role engineering with topdown information. Second, we provide a new formal framework to optimize role mining algorithms. Applying this framework to real data sets consistently reduces running time and often improves output quality. Another key problem that has not previously been adequately addressed is how to automatically propose roles that have business meaning. To do this, we provide a formal framework that leverages business information, such as business processes and organization structure, to implement role mining algorithms. Furthermore, we address the problem of reducing the role mining complexity in RBAC systems by removing “noise” from data; i.e., permissions exceptionally or accidentally granted or denied. We propose a new methodology to elicit stable candidate roles, by contextually simplifying the role selection task. Finally, we address the problem of effectively managing the risk associated with granting access to resources. We propose a new divideandconquer approach to role mining that facilitates attributing business meaning to automatically elicited roles and reduces the problem complexity.
Each of the above results is rooted on a sound theoretical framework and supported by extensive experiments on real data.</Abstract>20110509T22:00:00ZKazhdanLusztig combinatorics in the moment graph setting
http://hdl.handle.net/2307/3936
<Title>KazhdanLusztig combinatorics in the moment graph setting</Title>
<Authors>Lanini, Martina</Authors>
<Issue Date>20120316</Issue Date>20120315T23:00:00ZRole mining over big and noisy data theory and some applications
http://hdl.handle.net/2307/3923
<Title>Role mining over big and noisy data theory and some applications</Title>
<Authors>Verde, Nino Vincenzo</Authors>
<Issue Date>20120402</Issue Date>
<Abstract>RBAC (RoleBased Access Control [2]) is a widely adopted access control model.
According to this model, roles are created for various job functions within the
organization. The permissions required to perform certain operations are assigned
to specific roles. System users, in turn, are assigned to appropriate
roles based on their responsibilities and qualifications. Through role assignments
they acquire the permissions to perform particular system functions. By
deploying RBAC systems, organizations obtain several benefits such as simplified
access control administration, improved organizational productivity, and
security policy enforcement.
Companies that plan to use RBAC model are usually large or medium organizations
that are currently using other access control models and/or legacy
systems. Despite the benefits related to RBAC, it is sometimes hard for these
organizations to adopt such a model. Indeed, there is an important issue that
needs to be addressed: the model must be customized to capture the needs
and functions of the company. For this purpose, the role engineering discipline
[21] has been introduced. Various approaches to role engineering have
been proposed, which are usually classified as: topdown and bottomup. The
former requires a deep analysis of business processes to identify which access
permissions are necessary to carry out specific tasks. The latter seeks to
identify de facto roles embedded in existing access control information. Since
bottomup approaches usually resort to data mining techniques, the term role
mining is often used as a synonym for bottomup.
This thesis is devoted to role mining techniques, and their applications
to large scale datasets. Several works prove that the role mining problem is
reducible to many other wellknown NPhard problems, such as binary matrices
factorization [56, 72] and tiling database [38] to cite a few. Therefore,
most of the existing theoretical approaches cannot be directly applied to large
datasets. Indeed, such algorithms have a complexity that is not linear com
pared to the number of users or permissions to analyze [6, 29, 78]. In this
thesis, the main drawbacks of traditional role mining tasks that are based on
minimality measures are highlighted. Indeed, a minimal set of roles is generally
not useful to the system administrators. We point out that in order to
provide a good candidate roleset, role mining algorithms have to take into
account business information as well.
We address the problem of reducing the role mining complexity in RBAC
systems by making it practical and usable. The first approach that we propose
is to elicit stable candidate roles, by contextually simplifying the role selection
task. Furthermore, we introduce two methodologies that can be combined
together in order to elicit meaningful roles, while reducing the role mining
complexity. The first is a divide et impera strategy that is driven by one or
more business attributes. The second methodology, overcomes the main limitation
of the divide et impera approach by reducing the problem size without
sacrificing on utility and accuracy. The original access control dataset is compressed
and then analyzed in order to identify interesting portions, which are
then reconstructed. Any existing role mining algorithm can be used to analyze
the reconstructed portions—that are orders of magnitude smaller than
the original dataset.
We point out that to effectively elicit a deployable roleset, role engineers
have to handle the noise that is always present within access control datasets.
It is important to figure out if there are assignments that have been not granted,
but that, if they would be granted, they could help the management of the
role set. Also, it is important to figure out if there are permissions that have
been accidentally granted, but that could hinder the role management. We
introduce two algorithms that are able to find missing and abnormal userpermission
assignments. Furthermore, we introduce a fast update operation
that quickly reevaluate the dataset when a modification occurs during the
normal life cycle of the roles.
Further, we introduce a new approach to the role mining, referred to as
visual role mining. It offers a graphical way to effectively navigate the result of
any existing role mining algorithm, showing at glance what it would take a lot
of data to expound. Moreover, we allow to visually identify meaningful roles
within access control data without resorting to traditional role mining tools.
Finally, some final remarks as well as future research directions are highlighted.</Abstract>20120401T22:00:00ZOn the Kolmogorov Set for many body problems
http://hdl.handle.net/2307/3732
<Title>On the Kolmogorov Set for many body problems</Title>
<Authors>Pinzari, Gabriella</Authors>
<Issue Date>20090423</Issue Date>
<Abstract>We study existence and estimate the measure of the invariant set of the Hamiltonian
system, known as manybody problem, governed by
Hplt(µ y, x) =
1
iN

yi2
2 ~mi

~mi ^mi
xi
+
µ
1
i<jN
y
i yj
¯m0

¯mi ¯mj
xi  xj
,
(0.1)
where y, x (R3
)N
and
^mi := ¯m0 + µ ¯mi , ~mi :=
¯m0 ¯mi
¯m0 + µ ¯mi
which correspons to the gravitational interaction of the 1 + N masses ¯m0, µ ¯m1, , µ ¯mN ,
from the point of view of Arnol'd's Fundamental Theorem for properly degenerate system,
which we refine as
theorem 1. Assume that
(ft0) H(I, , p, q) = h(I) + f(I, , p, q) is realanalytic on I x T¯n x B2^n
r (0), with I an
open, bounded, connected subset of R¯n
;
(ft1) h is a diffeomorphism of an open neighborhood of I, with non degenerate Jacobian
= 2
h on such neighborhood;
(ft2) the mean perturbation ¯f(I, p, q) := 1
(2)¯n
T
¯n f(I, , p, q)d has the form
¯f = ¯f = f0(I) +
1
im
i(I)Ji +
1
2
1
i, jN
Aij(I)JiJj + o4
+ o6
with Ji :=
p2
i + q2
i
2
and o4/(p, q)4
0;
(ft3) = (1, , ^n) is 4non resonant, i.e. ,
(I) k = 0 for any I ¯I, k = (k1, , km) Zm
:
1
im
ki 4 (0.2)
(ft4) A is non singular on I, i.e. ,
detA(I) = 0 for any I ¯I .
1
Then, for any sufficiently large b > 0, there exist r, 0 < c <1 < C such that, for any
0 < r < r and 0 < < c(log r1
)2b
(0.3)
a set V (, r) I x T¯n x B2^n
¯r (0) of the same measure of I x T¯n x B2^n
r (0) and an invariant
set K(, r) V (, r) ("Kolmogorov set") with measure
meas
K
(, r)
1
 C1/2
(log r1
b
 Cr1/2
m
eas
V
(, r)
(0.4)
consisting of n = ¯n + ^ndimensional invariant tori where the motion is analytically conju
gated to Tn
+ t. The tori frequencies may be chosen ( r5/2
, )Diophantine.
We apply th1 to the plane Problem and, using the set of BoigeyDeprit variables, to the
spatial problem.
Using only a partial reduction, we prove (inductively) that, for N 3, the many body
problem verifies the assuptions of theorem 1 allowing to find KAM tori with 3N  1
Diophantine frequencies and estimating the measure of the invariant set as prescribed by
equation (0.4), where represents the masses and r eccentricities and coinclinations. We
also prove that, reducing furtherly the system, in the range of small eccentricities and
inclinations, the secular perturbation can be put into the form
¯fplt = ^f0
plt(, G) +
1
iN
si(, G)
2
i + 2
i
2
+
1
iN2
zi(, G)
p2
i + q2
i
2
+ O(3)
where the first Birkhoff invariants (s1, , sN ), (z1, , zN2)do not satisfy any linear
relation. This allows us to apply an analytic first order properly KAM Theory such as the
one developed in Chierchia Pusateri 2008 without any modification of the Hamiltonian,
hence gaining some information on the motion of the system (on the KAM of the tori and
their amount of irrationality).</Abstract>20090422T22:00:00ZSemiclassical analysis of loop quantum gravity
http://hdl.handle.net/2307/603
<Title>Semiclassical analysis of loop quantum gravity</Title>
<Authors>Perini, Claudio</Authors>
<Issue Date>20100430</Issue Date>
<Abstract>In this PhD thesis I discuss various aspects of the semiclassical dynamics of Loop Quantum Gravity (LQG) as defined by Spin Foam models (the covariant version of canonical LQG). In particular I consider the ”new spin foam models” as candidates for the LQG vertex amplitude. I introduce a technique for testing the semiclassical behaviour which is the study of the propagation of semiclassical wavepackets, obtaining some preliminary good indications. Then I study the asymptotics of a building block of the spin foam amplitude which are the fusion coefficients; these
are combinatorial symbols that realize the equivalence between the LQG and the SF kinematical state space. Their asymptotics shows nice properties in the semiclassical sector. One of the most important test is the comparison of the npoint functions computed in LQG with the ones of standard perturbative quantum gravity. I compute the connected 2point function of metric operators, and compare it with the graviton propagator of standard QFT, finding a complete agreement (scaling and tensorial structure) for a suitable choice of the few free parameters. This is an important test for the ”new SF models” since the previous major model, the BarrettCrane model, failed to yield the correct graviton propagator. The computation of the propagator is based on a rather particular choice of the boundary state (the one representing the semiclassical geometry over which the gravitons propagate), which is dictated by geometrical intuition. The robustness of this formalism is strengthened in my recent work ”Coherent spinnetworks”. Here I define coherent states for full LQG from a heatkernel over phasespace (like in ordinary QM) and find that in the semiclassical limit their asymptotics reproduce exactly the states used in SF models.
The importance of coherent spinnetworks, defined over a threedimensional hypersurface, is that we have a clear geometrical interpretation of the classical geometry (intrinsic and extrinsic) they are peaked on; hence we can in principle construct quantum states having minimal uncertainty in conjugate quantities that represent a given (e.g. Minkowski or deSitter) classical spacetime.</Abstract>20100429T22:00:00ZDegenerations and applications : polynomial interpolation and secant degree
http://hdl.handle.net/2307/602
<Title>Degenerations and applications : polynomial interpolation and secant degree</Title>
<Authors>Postinghel, Elisa</Authors>
<Issue Date>20100407</Issue Date>
<Abstract>The polynomial interpolation problem in several variables and higher multiplicities is a
subject that has been widely studied, but there is only a little understanding about the
question. What is known, so far, is essentially concentrated in the AlexanderHirschowitz
Theorem which says that a general collection of double points in Pr gives independent conditions on the linear system L of the hypersurfaces of degree d, with a well known list of
exceptions. In the ﬁrst part of this thesis we present a new proof of this theorem which consists in performing degenerations of Pr and analyzing how L degenerates. Our construction
gives hope for further extensions to greater multiplicities.
There is a long tradition within algebraic geometry that studies the dimension and the
degree of k secant varieties. These are problems that are unsolved in general. In the second
part of the thesis, we consider any projective toric surface XP associated to a polytope
P ⊆ R2 and we perform planar toric degenerations D of XP in order to study the k secant
varieties of XP . In particular we give a lower bound to the secant degree and to the 2secant
degree of XP , taking into account the singularities of the conﬁguration D of nondelightful
planar toric degenerations.
1</Abstract>20100406T22:00:00ZGeometry and combinatorics of toric arrangements
http://hdl.handle.net/2307/601
<Title>Geometry and combinatorics of toric arrangements</Title>
<Authors>Moci, Luca</Authors>
<Issue Date>20100326</Issue Date>
<Abstract>A toric arrangement is a finite set of hypersurfaces in a complex torus, each hypersurface being the kernel of a character.
In the first chapter we focus on the case of toric arrangements defined by root systems: by describing the action of the Weyl group, we get precise counting formulae for the layers (connected components of intersections) of the arrangement, and then we compute the Euler characteristic of its complement.
In the second chapter we introduce a multiplicity Tutte polynomial M(x,y), which generalizes the ordinary one and has
applications to zonotopes, multigraphs and toric arragements. We prove that M(x,y) satisfies a deletionrestriction formula and has positive coefficients. The characteristic polynomial and the Poincaré polynomial of a toric arrangement are shown to be specializations of the associated polynomial M(x,y). Furthermore, M(x,1) counts integral points in the faces of a zonotope, while M(1,y) is the graded dimension of the related discrete DahmenMicchelli space.
In the third chapter we build wonderful models for toric arrangements. We develop the "toric analogue" of the combinatorics of nested sets, which allows to prove that the model is smooth, and to give a precise description of the normal crossing divisor.</Abstract>20100325T23:00:00ZAsymptotic analysis for a singularly perturbed Dirichlet problem
http://hdl.handle.net/2307/600
<Title>Asymptotic analysis for a singularly perturbed Dirichlet problem</Title>
<Authors>Petralla, Maristella</Authors>
<Issue Date>20100510</Issue Date>
<Abstract>Let us consider the problem −∆u + λV (x)u = up in Ω, u = 0 on ∂ Ω, where Ω is a smooth
bounded domain, p > 1, V is a positive potential and λ > 0. We are interested in the regime λ → +∞, which is equivalent to a singularly perturbed Dirichlet problem. It is known that
solutions u must blow up as λ → +∞, and we address here the asymptotic description of such
a blow up behavior. When the ”energy” is uniformly bounded, the behavior is well understood
and the solutions can develop just a ﬁnite number of sharp peaks. When V is not constant, the
blow up points must be c.p.’s of the potential V. The situation is more involved when V = 1,
and the crucial role is played by the mutual distances between the blowup points as well as the
boundary distances. The construction of these blowingup solutions has also been addressed.
The ﬁrst part in the thesis is devoted to strengthen such an analysis when just a Morse index
information is available. A posteriori, we obtain an equivalence in the form of a doubleside
bound between Morse index and ”energy” with essentially optimal constants. This result can be
seen as a sort of RozenblyumLiebCwikel inequality, where the number of negative eigenvalues
of a Schrodinger operator −∆ + V can be estimated in terms of a suitable Lebesgue norm of the
negative part V− . Thanks to the speciﬁcity of our problem, we improve it by getting the correct
Lebesgue exponent (in view of the doubleside bound) as well as the sharp constants. We then
turn to the question of concentration on manifolds of positive dimensions. The problem is well
understood by a constructive approach but the asymptotic analysis is in general missing. Let
us notice that on the annulus the radial ground state solution has Morse index and ”energy”
which blow up as λ → +∞. Nonetheless, the radial Morse index is one which has allowed
EspositoManciniSantraSrikanth to develop a ﬁne asymptotic analysis to localize the limiting
concentration radii. They are c.p.’s of a modiﬁed potential, whose role had been already
clariﬁed by the constructive results. The second part part of the thesis is devoted to develop an
asymptotic analyis for solutions on the annulus which have partial symmetries. In particular,
we consider the threedimensional annulus and solutions which are invariant under rotations
around the zaxis. Assuming an uniform bound on the reduced invariant Morse index, we obtain
a localization of the limiting concentration circles in terms of a suitable modiﬁed potential. The
main difficulty here is related to the presence of ﬁxed points w.r.t. the group action (the zaxis)
and the aim is to exhibit potentials V for which the concentration circles (for example, for the
ground state solution) do not degenerate to points on the zaxis.</Abstract>20100509T22:00:00ZKronecker function rings of domains and projective models
http://hdl.handle.net/2307/598
<Title>Kronecker function rings of domains and projective models</Title>
<Authors>Fabbri, Alice</Authors>
<Issue Date>20100216</Issue Date>
<Abstract>In questa tesi vengono aﬀrontati due argomenti entrambi riguardanti
l’anello delle funzioni di Kronecker. Nella prima parte si aﬀronta il problema di
caratterizzare e dare nuovi esempi di quei domini integralmente chiusi aventi
un unico anello di funzioni di Kronecker. Nella seconda parte si considera la
generalizzazione degli anelli di funzioni di Kronecker introdotta da HalterKoch,
ovvero gli anelli di F funzioni, con F campo. Per particolari estensioni di campi
si fornisce una costruzione d’ispirazione geometrica, in cui anche gli anelli di
F funzioni si possono dedurre da operazioni di tipo star come nel caso classico.</Abstract>20100215T23:00:00ZTrace zero varietes in pairingbased cryptography
http://hdl.handle.net/2307/597
<Title>Trace zero varietes in pairingbased cryptography</Title>
<Authors>Cesena, Emanuele</Authors>
<Issue Date>20100326</Issue Date>
<Abstract>The term cryptography, by etymology or simply by association of ideas, suggests its
connection with secret messages and this is made clear from the deﬁnition that we ﬁnd
in Wikipedia: “The practice and study of hiding information”.
In light of the results of the fundamental article of Diﬃe and Hellman New Directions in Cryptography [DH76] this simple deﬁnition of cryptography seems to require
a supplement: nowadays states, public organizations and private individuals can not
only exchange information in secrecy, but also sign electronic documents so that the
digital signature is easily veriﬁable, but not falsiﬁable. To make this possible, Diﬃe
and Hellman introduced the concept of publickey cryptosystems : the use of public keys
allows us to exchange secret keys without having to meet in person (for instance, using
channels in clear on the network) or generate/verify digital signatures.
The ﬁrst example of a public key cryptosystem was proposed in 1978 by Rivest,
Shamir and Adleman [RSA78]. Diﬃe and Hellman also advanced the idea of establishing
a cryptographic system on the discrete logarithm problem (DLP) in a ﬁnite ﬁeld, an idea
which they attributed to Prof. Gill of Stanford University, and carried out for the ﬁrst
time in 1985 by ElGamal [ElG85].
In the same year Miller and Koblitz [Mil86, Kob87] proposed to use the group of
rational points of an elliptic curve over a ﬁnite ﬁeld. Compared to those already mentioned, elliptic curves allow greater ﬂexibility in building the group and the use of smaller
keys at the same level of security. Four years later Koblitz [Kob89] indicated the Jacobian variety of hyperelliptic curves as another possible candidate for the construction of
cryptosystems.
In 1998 Frey [Fre98, Fre01] suggested to use Trace Zero Varieties (TZV) for cryptosystems based on the DLP. The starting point of Frey’s construction is, in the simplest
case, an elliptic curve E deﬁned over a ﬁnite ﬁeld Fq . Let Fqr /Fq be a ﬁnite extension.
The group E (Fqr ) contains E (Fq ) and the Frobenius automorphism Fqr /Fq extends to
E (Fqr ) in a natural way. The TZV is a subgroup of E (Fqr ) (more precisely, a subvariety
of the Weil restriction of scalars of E (Fqr ) from Fqr to Fq ) which is globally invariant
under the action of the Frobenius and isomorphic to the quotient E (Fqr )/E (Fq ). It is
exactly the action of the Frobenius that makes the computation of scalar multiplication
on TZV particularly eﬃcient.
Several authors addressed the study of TZV: Naumann [Nau99] and Blady [Bla02]
considered TZV of elliptic curves over extension ﬁelds of degree 3 (r = 3); Weimerskirch [Wei01] analyzed the case for extension ﬁelds of degree 5; ﬁnally Lange [Lan01,
Lan04] built TZV from the Jacobian variety of hyperelliptic curves of genus two, over extension ﬁelds of degree 3. Avanzi and Lange [AL04] compared the performance of these
three kinds of TZV over ﬁelds of odd characteristic. Avanzi and Cesena [Ces04, AC08]
compared the same three types of TZV deﬁned over binary ﬁelds, highlighting similarities and main diﬀerences between TZV deﬁned over ﬁelds of even and odd characteristic.
1
The performance of an elliptic curve cryptosystem depends mainly on two aspects
that one needs to consider when implementing the scalar multiplication: the ﬁrst is
the choice of the coordinate system used to represent points, such as classical aﬃne
coordinates where a point is represented by the pair (x, y ), and the second is the use or
not of precomputation.
In this work we extend the results of [AC08] over binary ﬁelds, by taking into account diﬀerent types of coordinate systems and evaluating the eﬀect of using or not
precomputation (the latter has already been considered in literature).
For elliptic curves several coordinate systems are available. The basic idea is to avoid
inversions in the ﬁeld (typically expensive) and to speed up the operation of doubling a
point on the curve, which is the one with the major impact on scalar multiplication, especially when using precomputation. Among the proposed coordinate systems for binary
elliptic curves, we mention projective coordinates in which a point is represented by the
tuple (X, Y, Z ) that corresponds to (x, y ) = (X/Z, Y /Z ) and L´pezDahab coordinates
o
where (X, Y, Z ) corresponds to (x, y ) = (X/Z, Y /Z 2 ).
The main result of our analysis is that TZV of elliptic curves over extensions of
degree 5 are the most eﬃcient groups suitable to build cryptographic systems based
on the DLP. On our Intel platform (32bit), at 80bit security they are about 10%
faster (20% using precomputation) and at 96bit security they are about 22% faster
(30% using precomputation) than elliptic curves with L´pezDahab coordinates (to be
o
precise, we considered the fastest extended L´pezDahab coordinates). For TZV, the
o
aﬃne coordinates appear to be the most eﬃcient. This is because we work in extension
ﬁelds, where the bad impact of inversions is reduced (an inversion in a extension ﬁeld
Fqr only requires a single inversion in the ground ﬁeld Fq ).
Nowadays it is easy to be blinded by the incredible amount of memory and computational power which is available in laptops and personal computers. However, it is
important to stress that there are countless applications – where cryptography is important and often overlooked – that are or need to be deployed on devices with limited
resources, like mobile phones or wireless sensors.
In such cases using aﬃne coordinates and avoiding precomputation can be the only
way to cope with the constrains imposed by the scenario and TZV turn out to be an
excellent solution to improve performance. Indeed, if we limit ourselves to consider aﬃne
coordinates, we conﬁrm the results in [AC08] that TZV of elliptic curves are always much
more eﬃcient than elliptic curves themselves (by factors about 1.5 for extension of degree
3 and more than 2 for degree 5).
To further assess the validity of our results, we perform experiments also on a PowerPC machine, still a relatively powerful server, but the idea is to have a comparison
also with an architecture more similar to what can be found in many embedded devices.
Here the advantage of TZV is even more accentuated.
Finally, following an idea of [HKA06], we develop for TZV a new coordinate system,
the compressed L´pezDahab coordinates, in which a Fqr rational point is represented
o
by the tuple (X, Y, z ) ∈ Fqr × Fqr × Fq that corresponds to (x, y ) = (X/z, Y /z 2 ). The
difference with L´pezDahab coordinates is therefore that the coordinate z is in Fq , thus
o
smaller. Arithmetic in this representation is made possible by a particular operation
available in extension ﬁelds, called pseudoinversion, that does not involve inversions in
the ground ﬁeld.
This new coordinate system turns out to be on average 8 − 10% faster than L´pezo
Dahab coordinates, and generally presents similar performance to aﬃne coordinates. We
2
want to remark that, since they do not require inversions in the ground ﬁeld, compressed
coordinates become more eﬀective the worse the inversion is, thus they are attractive
for devices with constrained resources.
Returning to the history of publickey cryptography, a big step forward has been
made with the introduction of pairingbased cryptography. A pairing, from the mathematical point of view, is a nondegenerate, bilinear map and to use it in practical
applications, we additionally require that it is eﬃciently computable. Algebraic geometry gives us two examples of pairings that meet the above deﬁnition: the Weil pairing
and the LichtenbaumTate pairing, that we shall simply call Tate pairing. The latter is particularly interesting for cryptography because it has better qualities from a
computational point of view, at least for moderate security levels.
The ﬁrst use of pairings in cryptography dates back to the 1990’s, when they are
exploited by Menezes, Okamoto and Vanstone [MOV93] and by Frey and R¨ck [FR94] to
u
attack cryptosystems by reducing the DLP in the group of rational points of an elliptic
curve to the DLP in a ﬁnite ﬁeld.
We have to wait until 2000 to see authors rediscover pairings and use it “for good”,
starting to develop cryptographic protocols and schemes based on pairings: Sakai,
Ohgishi and Kasahara [SOK00] introduced the ﬁrst pairingbased keyagreement and
signature schemes, and Joux [Jou00] extended the DiﬃeHellman key agreement protocol to a threeparty, oneround protocol.
Another fundamental construction is the ﬁrst IdentiyBased Encryption (IBE) scheme
realized in 2001 by Boneh and Franklin [BF01]. In IBE, the user’s public key is derived
from some known aspects of her identity, such as her name or email address and this
eliminates the key distribution or certiﬁcation problems. The construction of a workable
and provably secure scheme was an open problem posed by Shamir in 1984 [Sha85].
These key contributions have been the trigger for an actual explosion of interest in
pairingbased cryptography, which led in recent years the deﬁnition of many protocols
and schemes and motivated the research for ever more eﬃcient implementations.
Pairings met TZV in 2002, when Rubin and Silverberg [RS02] proposed to use
supersingular abelian varieties of dimension greater than one to improve the security
of pairingbased cryptosystems. Besides Jacobian varieties of hyperelliptic curves, the
other signiﬁcant example was the class of TZV (called primitive subgroups in that paper), which can be constructed from elliptic curves.
The original work of Rubin and Silverberg and their more recent results presented
in [RS09] constitute the motivation of our research. Notably, supersingular TZV of
elliptic curves allow to achieve higher “security per bit” than supersingular elliptic curves
themselves: in characteristic 3 (r = 5) TZV represent the ﬁrst example of supersingular
abelian varieties with security parameter greater than 6 (in fact 7.5); in characteristic
2 (r = 3) TZV present an alternative to supersingular elliptic curves over F3m which is
more eﬃcient, simpler to implement and with equivalent security properties.
The computation of pairings over TZV has already been taken into account by Barreto et al. [BK+ 02, BG+ 07], who deﬁned the η and ηT pairings on supersingular abelian
varieties. Other pairings, such as the (twisted) Ate pairing [HSV06] and its extended
versions [MK+ 07, LLP09, Ver08] can be naturally deﬁned on TZV too. However no work
in literature considered using the q th power Frobenius available in TZV to speedup the
computation of pairings.
The focus of the present work is exactly that: develop a new algorithm to compute
3
the Tate pairing on TZV exploiting the action of the q th power Frobenius. Our result
applies to supersingular TZV in characteristic 2, 3 and p > 3.
ˆ
In our main theorem we derive a new formula for the Tate pairing t(P, Q):
M a q a−1
r
r−1
q i(r+1)
fq,P (Qσi )
ˆ
t(P, Q) =
,
i=0
where fq,P is the Miller function, σi is proper power of the q th power Frobenius endomorphism, and a and M are constants depending on the curve.
The previous formula yields a new algorithm to compute the Tate pairing over supersingular TZV. We evaluate fq,P at the r points Qσi (raising each evaluation to the
proper power q i(r+1) ). At the end we compute the ﬁnal exponentiation to M a q a−1 .
r
The algorithm is suitable for a parallel implementation, requiring r processors and
achieving a Miller loop of “length” q . Moreover, both in a parallel and in a sequential
model, an implementation with precomputation of the multiples of P requires the storage
of only log2 q points. Together with implementation details, we also propose a variant
of the point compression algorithm of Rubin and Silverberg [RS02] in characteristic 2
which is more eﬃcient and requires no inversion in the ﬁeld.
Experimental results show that the parallel version of our new algorithm is on average
25 − 30% faster than any previous pairing algorithm – notably the ηT pairing described
in [BG+ 07].
Besides the computation of pairings, we also analyze the performance of scalar multiplication on supersingular elliptic curves and TZV. Supersingular TZV are much faster
than the corresponding elliptic curves and, as we already mentioned, they also allow
to achieve higher security per bit. For instance, on our Intel platform (32bit), scalar
multiplication on the supersingular TZV over F2103 (r = 3) is 4 times faster than on the
corresponding elliptic curve deﬁned over F2307 , pairing can be up to 30% faster exploiting the parallel version of the new algorithm and ﬁnally points can be compressed to
208 bits, allowing a reduction of storage or bandwidth by a factor about 3/2.
In conclusion we have seen that TZV, ordinary and supersingular, have many interesting features that make them attractive for building cryptosystems based on the DLP
as well as pairingbased cryptosystems. They are also well suited for implementations
on devices with constrained resources at moderate security levels.
Foundation
The following publications and preprints form the foundation of this thesis:
• R. M. Avanzi and E. Cesena. Pairing on Supersingular Trace Zero Varieties.
Cryptology ePrint Archive, Report 2008/404, 2008.
http://eprint.iacr.org/2008/404
A preliminary version of this work was presented at Eurocrypt 2009 poster session.
• R. M. Avanzi and E. Cesena. Trace Zero Varieties over Fields of Characteristic 2 for Cryptographic Applications. In J. Hirschfeld, J. Chaumine, and
R. Rolland, editors, Algebraic geometry and its applications, volume 5 of Number
Theory and Its Applications, pp. 188–215. World Scientiﬁc, 2008. Proceedings of
the ﬁrst SAGA conference, Papeete, 711 May 2007.
4
• E. Cesena, H. L¨hr, G. Ramunno, A.R. Sadeghi, and D. Vernizzi. Anonymous
o
Authentication with TLS and DAA. Submitted to TRUST 2010.
• E. Cesena, G. Ramunno, and D. Vernizzi. Towards Trusted Broadcast Encryption. TrustCom 2008: The 2008 International Symposium on Trusted Computing. Zhang Jia Jie (Hunan, China), 1820 November 2008, pp. 2125–2130.
Organization
The dissertation is organized as follows.
Chapter 1 introduces pairingbased cryptography with a few relevant cryptographic
schemes taken from the literature; this serves as a practical motivation and we will
return to the schemes during the course of the dissertation.
In Chapter 2 we arrange the mathematical background with particular focus on
the LichtenbaumTate pairing. Most of this chapter is taken from two presentations of
Prof. Frey at the ﬁrst Symposium on Algebraic Geometry and its Applications (SAGA
2007) and at the GTEM Workshop on Pairings (Essen, 2009). We adapt the theory to
better ﬁt the case of TZV.
Chapter 3 is the core of this dissertation. We take a more computationally oriented
approach: we discuss the arithmetic in the ideal class group of a TZV, we review techniques for pairing computation taken from the literature and we develop a new algorithm
for the computation of the Tate pairing over supersingular TZV which exploits the action of the q th power Frobenius endomorphism. In the end of the chapter we discuss
the security of TZV and we provide explicit examples of curves that are used in the
experiments.
In Chapter 4 we deal with the implementation details and we provide experimental
results. For emotional reasons most of this chapter is devoted to the implementation
in characteristic two. Notably, in this chapter we deﬁne new compressed L´pezDahab
o
coordinates for ordinary TZV of elliptic curves, we analyze the performance of scalar
multiplication both on ordinary and supersingular TZV, we detail the parallel and the
sequential versions of the new algorithm for the Tate pairing, including experimental
results.
Finally, Chapter 5 is devoted to realworld applications and notably to the Trusted
Computing technology: due to my personal and somehow atypical research experience
at Politecnico di Torino, I have gotten to know a more applied way to do research and
I wish to include in the dissertation some results obtained in this area. Pairing here is
used as a blackbox toolkit and actually these topics originated my interest in pairing
computation. Unfortunately, due to technical details that will be clariﬁed at proper
time, the algorithm for pairing computation developed in this dissertation is probably
not the best candidate for such applications, but the hope is to continue my research
and let these two routes converge.
References
[AC08]
R. M. Avanzi and E. Cesena. Trace Zero Varieties over Fields of Characteristic
2 for Cryptographic Applications. In J. Hirschfeld, J. Chaumine, and R. Rolland, editors, Algebraic geometry and its applications, volume 5 of Number
5
Theory and Its Applications, pages 188–215. World Scientiﬁc, 2008. Proceedings of the ﬁrst SAGA conference, 2007, Papeete.
[AL04]
R. M. Avanzi and T. Lange. Cryptographic Applications of Trace Zero Varieties. Unpublished manuscript., 2004.
[BF01]
D. Boneh and M. Franklin. Identitybased encryption from the Weil pairing.
LNCS, 2139:213–??, 2001.
´
[BG+ 07] P. S. Barreto, S. D. Galbraith, C. O’ H´igeartaigh, and M. Scott. Eﬃcient
e
pairing computation on supersingular Abelian varieties. Des. Codes Cryptography, 42(3):239–271, 2007.
[BK+ 02] P. S. L. M. Barreto, H. Y. Kim, B. Lynn, and M. Scott. Eﬃcient algorithms
for pairingbased cryptosystems. In Advances in Cryptology  CRYPTO 2002,
22nd Annual International Cryptology Conference, Santa Barbara, California,
USA, August 1822, 2002, Proceedings, volume 2442 of LNCS, pages 354–368.
Springer, 2002.
[Bla02]
G. Blady. Die WeilRestriktion elliptischer Kurven in der Kryptographie.
Master’s thesis, Universit¨tGesamthochschule Essen, 2002.
a
[Ces04]
E. Cesena. Variet` a traccia zero su campi binari – applicazioni crittograﬁche.
a
Master’s thesis, Universit` degli Studi di Milano, 2004.
a
[DH76]
W. Diffe and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976.
[ElG85]
T. ElGamal. A public key cryptosystem and signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, pages 473–481,
1985.
[FR94]
G. Frey and H.G. R¨ck. A remark concerning mdivisibility and the discrete
u
logarithm in the divisor class group of curves. Mathematics of Computation,
62(206):865–874, 1994.
[Fre98]
G. Frey. How to disguise an elliptic curve. Talk at Waterloo workshop on the
ECDLP, 1998. http://www.cacr.math.uwaterloo.ca/conferences/1998/
ecc98/slides.html.
[Fre01]
G. Frey. Applications of arithmetical geometry to cryptographic constructions.
In Finite ﬁelds and applications (Augsburg, 1999), pages 128–161. Springer,
Berlin, 2001.
[HKA06] F. Hoshino, T. Kobayashi, and K. Aoki. Compressed jacobian coordinates for
OEF. In Progress in Cryptology  VIETCRYPT 2006, volume 4341 of LNCS,
pages 147–156. Springer, 2006.
[HSV06] F. Hess, N. P. Smart, and F. Vercauteren. The Eta Pairing Revisited. IEEE
Trans. Inform. Theory, 52:4595–4602, 2006.
[Jou00]
A. Joux. A one round protocol for tripartite Diﬃe–Hellman. In Algorithmic
Number Theory, ANTSIV, volume 1838 of LNCS, pages 385–394. Springer,
2000.
6
[Kob87]
N. Koblitz. Elliptic curve cryptosystems. Math. Comp., 48(177):203–209,
1987.
[Kob89]
N. Koblitz. Hyperelliptic cryptosystems. Journal of Cryptology, 1:139–150,
1989.
[Lan01]
T. Lange. Eﬃcient arithmetic on hyperelliptic curves. PhD thesis, University
Essen, 2001.
[Lan04]
T. Lange. Trace zero subvarieties of genus 2 curves for cryptosystems. J.
Ramanujan. Math. Soc., 19:15–33, 2004.
[LLP09] E. Lee, H.S. Lee, and C.M. Park. Eﬃcient and generalized pairing computation on abelian varieties. IEEE Transactions on Information Theory,
55(4):1793–1803, 2009.
[Mil86]
V. S. Miller. Use of elliptic curves in cryptography. In Advances in cryptology
– crypto ’85, volume 218 of LNCS, pages 417–426. Springer, Berlin, 1986.
[MK+ 07] S. Matsuda, N. Kanayama, F. Hess, and E. Okamoto. Optimised versions of
the Ate and Twisted Ate Pairings. In The 11th IMA International Conference
on Cryptography and Coding, volume 4887 of LNCS, pages 302–312. Springer,
2007.
[MOV93] A. J. Menezes, T. Okamoto, and S. Vanstone. Reducing elliptic curve logarithms to a ﬁnite ﬁeld. IEEE Trans. on Inform. Theory, 39:1639–1646, 1993.
[Nau99]
N. Naumann. WeilRestriktion abelscher Variet¨ten. Master’s thesis, Univera
sity Essen, 1999.
[RS02]
K. Rubin and A. Silverberg. Supersingular abelian varieties in cryptology.
In CRYPTO ’02: Proceedings of the 22nd Annual International Cryptology
Conference on Advances in Cryptology, pages 336–353, London, UK, 2002.
Springer.
[RS09]
K. Rubin and A. Silverberg. Using abelian varieties to improve pairingbased
cryptography. Journal of Cryptology, 22(3):330–364, 2009.
[RSA78] R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital
signature and public key cryptosystems. Comm. ACM, 21:120–126, 1978.
[Sha85]
A. Shamir. Identitybased cryptosystems and signature schemes. In Proceedings of CRYPTO 84 on Advances in cryptology, pages 47–53. Springer, 1985.
[SOK00] R. Sakai, K. Ohgishi, and M. Kasahara. Cryptosystems based on pairing. In
The 2000 Symposium on Cryptography and Information Security (SCIS2000),
pages 26–28, Okinawa, Japan, 2000.
[Ver08]
F. Vercauteren. Optimal Pairings. Cryptology ePrint Archive, Report
2008/096, 2008. http://eprint.iacr.org/2008/096.
[Wei01]
A. Weimerskirch. The application of the Mordell–Weil group to cryptographic
systems. Master’s thesis, Worchester Polytechnic Institute, 2001.</Abstract>20100325T23:00:00ZQuantum lattice Boltzmann methods for the linearand nonlinear Schrödinger equation in several dimensions
http://hdl.handle.net/2307/587
<Title>Quantum lattice Boltzmann methods for the linearand nonlinear Schrödinger equation in several dimensions</Title>
<Authors>Palpacelli, Silvia</Authors>
<Issue Date>20090527</Issue Date>
<Abstract>In the last decade the lattice kinetic approach to fluid dynamics, and notably the Lattice Boltzmann (LB) method, has consolidated into a powerful
alternative to the discretization of the NavierStokes equations for the numerical simulation of a wide range of complex fluid flows. However, to date,
the overwhelming majority of LB work has been directed to the investigation
of classical (non quantum) fluids. Nonetheless a small group of authors have
also investigated lattice kinetic formulations of quantum mechanics which
led to the definition of the socalled quantum lattice gas methods for solving
linear and nonlinear Schrodinger equations.
The earliest LB model for quantum motion was proposed by Succi and Benzi
in 1993 and it built upon a formal analogy between the Dirac equations and
a Boltzmann equation satisfied by a complex distribution function. This
first quantum lattice Boltzmann (qLB) scheme was formulated in multi
dimensions but it was numerically validated only in one space dimension.
Indeed, the first result of this thesis is the effective numerical extension
and validation of the multidimensional qLB scheme.
In particular, we present a numerical study of the two and three dimensional qLB model, based on an operator splitting approach. Our results show
a satisfactory agreement with the analytical solutions, thereby demonstrating the validity of the threestep streamcolliderotate theoretical structure
of the multidimensional qLB scheme.
Moreover, we extend the qLB model by developing an imaginarytime
version of the scheme in order to compute the ground state solution of the
GrossPitaevskii equation (GPE). The GPE is commonly used to describe
the dynamics of zerotemperature BoseEinstein condensates (BEC) and it
is a nonlinear Schrodinger equation with a cubic nonlinearity. The ground state solution of the GPE is the eigenstate which corresponds to the minimum energy level. Typically, this minimizer is found by applying to the
GPE a transformation, known as Wick rotation, which consists on "rotating"
the time axis on the complex plane so that time becomes purely imaginary.
With this rotation of the time axis, the GPE becomes a diffusion equation
with an absorption/emission term given by the nonlinear potential.
Thus, the basic idea behind the imaginarytime qLB model is to apply the
Wick rotation to the realtime qLB scheme. The imaginarytime qLB scheme
is also extended to multidimensions by using the same splitting operator
approach already applied to the realtime qLB model.
In addition, we apply the qLB scheme to the study of the dynamics of
a BEC in a random potential, which is a very active topic in present time
research on condensed matter and atomic physics research. In particular,
we investigate the conditions under which an expanding BEC in a random
speckle potential can exhibit Anderson localization.
Indeed, it is well known that disorder can profoundly affect the behavior of
quantum systems, Anderson localization being one of the most fascinating
phenomena in point.
Here, we explore the use of qLB for the case of nonlinear interactions with
random potentials and, in particular, we investigate the mechanism by which
the localized state of the BEC is modified by the residual selfinteraction in
the (very) longtime term evolution of the condensate.
These studies have demonstrated the viability of the qLB model as numerical algorithm for solving linear and nonlinear Schrodinger equations for
both the timedependent and ground state solutions, even in external random potentials.
Such lattice kinetic methods for quantum mechanics represent interesting
numerical schemes, which can be easily implemented and retain the usual
attractive features of LB methods: simplicity, computational speed, straight
forward parallel implementation.</Abstract>20090526T22:00:00ZCompactified Picard stacks over the moduli space of curves with marked points
http://hdl.handle.net/2307/426
<Title>Compactified Picard stacks over the moduli space of curves with marked points</Title>
<Authors>Mascarenhas Melo, Ana Margarida</Authors>
<Issue Date>20090528</Issue Date>
<Abstract>For any d Z and g, n 0 such that 2g  2 + n > 0, denote by Picd, g, n
the stack whose sections over a scheme S consist of flat and proper families
: C S of smooth curves of genus g, with n distinct sections si : S C
and a line bundle L of relative degree d over C. Morphisms between two
such objects are given by cartesian diagrams
C
2
// C
S 1
//
si
II
S s
iU
U
such that si 1 = 2 si, 1 i n, together with an isomorphism
3 : L
2(L ).
Picd, g, n is endowed with a natural forgetful map onto Mg, n and it is, of
course, not complete.
The present thesis consists of the construction of an algebraic stack Pd, g, n
with a map d, g, n onto Mg, n with the following properties.
(1) Pd, g, n and d, g, n fit in the following diagram;
Picd, g, n
// Pd, g, n
d, g, n
Mg, n
// Mg, n
(2) d, g, n is universally closed;
(3) Pd, g, n has a geometrically meaningful modular description.
For n = 0 (and g 2), our compactification consists of a stack theoretical
interpretation of Lucia Caporaso's compactification of the universal Picard
variety over Mg. Then, for n > 0 and 2g2+n > 1, we proceed by induction
in the number of points following the guidelines of Knudsen's construction
of Mg, n.
1</Abstract>20090527T22:00:00ZCollisions of fat points
http://hdl.handle.net/2307/423
<Title>Collisions of fat points</Title>
<Authors>Nesci, Michele</Authors>
<Issue Date>20090330</Issue Date>20090329T22:00:00ZGroup schemes of order p^2 and extension of Z/p^2Ztorsors
http://hdl.handle.net/2307/135
<Title>Group schemes of order p^2 and extension of Z/p^2Ztorsors</Title>
<Authors>Tossici, Dajano</Authors>
<Issue Date>20080303</Issue Date>20080302T23:00:00ZMinimal surfaces derived from the CostaHoffmanMeeks examples
http://hdl.handle.net/2307/111
<Title>Minimal surfaces derived from the CostaHoffmanMeeks examples</Title>
<Authors>Morabito, Filippo</Authors>
<Issue Date>20080528</Issue Date>20080527T22:00:00Z