<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-15">
</head>
<body bgcolor="#ffffff" text="#000000">
<span class="Apple-style-span" style="border-collapse: separate;
color: rgb(0, 0, 0); font-family: 'Times New Roman'; font-size:
16px; font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal; orphans: 2;
text-indent: 0px; text-transform: none; white-space: normal;
widows: 2; word-spacing: 0px;"><span class="Apple-style-span"
style="color: rgb(0, 53, 96); font-family: 'Helvetica
Neue',Arial,Helvetica,sans-serif; font-size: 12px; line-height:
18px;">
<div class="section"
id="improved-generic-algorithms-for-hard-knapsacks"
style="margin: 0px 16px 0px 0px; padding: 0px 0px 1.5em;
border-width: 0px; font-weight: inherit; font-style: inherit;
font-size: 12px; font-family: inherit; vertical-align:
baseline; display: inline; width: 572px; float: left;">
<h3><span class="Apple-style-span" style="border-collapse:
separate; color: rgb(0, 0, 0); font-family: 'Times New
Roman'; font-size: 16px; font-style: normal; font-variant:
normal; font-weight: normal; letter-spacing: normal;
line-height: normal; orphans: 2; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px;"><span class="Apple-style-span"
style="color: rgb(0, 53, 96); font-family: 'Helvetica
Neue',Arial,Helvetica,sans-serif; font-size: 12px;
line-height: 18px;">
<h3><img
src="cid:part1.04080108.03040908@ruhr-uni-bochum.de"
alt="HGI" align="left" height="136" width="150"><br>
</h3>
</span></span></h3>
<h3><br>
</h3>
<h3><br>
</h3>
<h3><br>
</h3>
<h3><br>
</h3>
<h3>Sehr geehrte Damen und Herren,</h3>
<h3><br>
im Rahmen des HGI-Kolloquiums organisiert vom Lehrstuhl für
Netz- und Datensicherheit (NDS), werden</h3>
<h3> <big><u>Anja Becker und Antoine Joux</u></big><br>
</h3>
<h3>von der <br>
</h3>
<h3> Universite de Versailles, Frankreich<br>
</h3>
<h3> am <br>
</h3>
<h3> nächsten <u>Donnerstag, den 07. April 2011 </u><br>
</h3>
<h3>über folgende Themen referieren:<br>
</h3>
<br>
<br>
<h1 style="margin: 0px; padding: 0.25em 0px 0.75em;
border-width: 0.125em 0px 0px; font-weight: bold;
font-style: inherit; font-size: 1.333em; font-family:
inherit; vertical-align: baseline; color: rgb(0, 53, 96);
line-height: 1.125em; text-transform: uppercase; border-top:
0.125em solid rgb(0, 53, 96); max-width: 572px;">IMPROVED
GENERIC ALGORITHMS FOR HARD KNAPSACKS</h1>
<p style="margin: 0px 0px 1.5em; padding: 0px; border-width:
0px; font-weight: inherit; font-style: inherit; font-size:
12px; font-family: inherit; vertical-align: baseline;
text-align: justify;">Anja Becker</p>
<p style="margin: 0px 0px 1.5em; padding: 0px; border-width:
0px; font-weight: inherit; font-style: inherit; font-size:
12px; font-family: inherit; vertical-align: baseline;
text-align: justify;">At Eurocrypt 2010,
Howgrave-Graham and Joux described an algorithm for
solving hard knapsacks of density close to 1 in time
O^~(2^{0.337n}) and memory O^~(2^{0.256n}), thereby
improving a 30-year old algorithm by Shamir and
Schroeppel. Our new technique allows us to get an
algorithm with running time down to O^~(2^{0.291n}).</p>
<p style="margin: 0px 0px 1.5em; padding: 0px; border-width:
0px; font-weight: inherit; font-style: inherit; font-size:
12px; font-family: inherit; vertical-align: baseline;
text-align: justify;">The knapsack instance is divided
in two halves with possible overlap, as in the
Howgrave-Graham--Joux algorithm, but the set of
possible coefficients is extended from {0,1} to
{-1,0,+1}. This means that a coefficient -1 in the first
half can be compensated with a coefficient +1 in the
second half, resulting in an coefficient 0 of the
golden solution. To reveal the golden solution, we
therefore search for one decomposition (out of
many) of the solution by solving two knapsacks. Adding
(a few) -1 coefficients brings an additional degree
of freedom that enables to again decrease the running
time. To explain the idea, we will have a look at a
practical example.</p>
</div>
<div class="section"
id="cover-and-decomposition-index-calculus-on-elliptic-curves-made-practical"
style="margin: 0px 16px 0px 0px; padding: 0px 0px 1.5em;
border-width: 0px; font-weight: inherit; font-style: inherit;
font-size: 12px; font-family: inherit; vertical-align:
baseline; display: inline; width: 572px; float: left;">
<h1 style="margin: 0px; padding: 0.25em 0px 0.75em;
border-width: 0.125em 0px 0px; font-weight: bold;
font-style: inherit; font-size: 1.333em; font-family:
inherit; vertical-align: baseline; color: rgb(0, 53, 96);
line-height: 1.125em; text-transform: uppercase; border-top:
0.125em solid rgb(0, 53, 96); max-width: 572px;">COVER AND
DECOMPOSITION INDEX CALCULUS ON ELLIPTIC CURVES
MADE PRACTICAL</h1>
<p style="margin: 0px 0px 1.5em; padding: 0px; border-width:
0px; font-weight: inherit; font-style: inherit; font-size:
12px; font-family: inherit; vertical-align: baseline;
text-align: justify;">Antoine Joux</p>
<p style="margin: 0px 0px 1.5em; padding: 0px; border-width:
0px; font-weight: inherit; font-style: inherit; font-size:
12px; font-family: inherit; vertical-align: baseline;
text-align: justify;">We present a new variant of cover
and decomposition attacks on the elliptic curve
discrete logarithm problem, that combines Weil
descent and decomposition-based index calculus into
a single discrete logarithm algorithm. This variant
applies, at least theoretically, to all composite
degree extension fields, and is particularly
well-suited for curves defined over $F_{p6}$. We give a
real-size example of discrete logarithm
computations on a seemingly secure curve over a
$130$-bit degree $6$ extension field.<br>
</p>
<hr width="100%" size="2">
<p style="margin: 0px 0px 1.5em; padding: 0px; border-width:
0px; font-weight: inherit; font-style: inherit; font-size:
12px; font-family: inherit; vertical-align: baseline;
text-align: justify;"><br>
</p>
<p style="margin: 0px 0px 1.5em; padding: 0px; border-width:
0px; font-weight: inherit; font-style: inherit; font-size:
12px; font-family: inherit; vertical-align: baseline;
text-align: justify;"><span class="Apple-style-span"
style="border-collapse: separate; color: rgb(0, 0, 0);
font-family: 'Times New Roman'; font-size: 16px;
font-style: normal; font-variant: normal; font-weight:
normal; letter-spacing: normal; line-height: normal;
orphans: 2; text-indent: 0px; text-transform: none;
white-space: normal; widows: 2; word-spacing: 0px;"><span
class="Apple-style-span" style="color: rgb(0, 53, 96);
font-family: 'Helvetica
Neue',Arial,Helvetica,sans-serif; font-size: 12px;
line-height: 18px;">
<h3>Der Vortrag beginnt um 11.00 Uhr s.t. im ID 03/445.
<br>
</h3>
<h3><br>
</h3>
<h3>Zu diesem und sämtlichen weiteren Vorträgen im
Rahmen des HGI-Kolloquiums sind alle Studierenden und
Interessierten herzlich eingeladen! Eine Voranmeldung
ist nicht erforderlich!</h3>
<h3><br>
Weitere Informationen gibt es auf folgender Webseite:</h3>
<h3><a class="moz-txt-link-freetext" href="http://hgi.rub.de/hgi/hgi-seminar/aktuelles/">http://hgi.rub.de/hgi/hgi-seminar/aktuelles/</a></h3>
<br>
</span></span></p>
<span class="Apple-style-span" style="border-collapse:
separate; color: rgb(0, 0, 0); font-family: 'Times New
Roman'; font-size: 16px; font-style: normal; font-variant:
normal; font-weight: normal; letter-spacing: normal;
line-height: normal; orphans: 2; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px;"><span class="Apple-style-span"
style="color: rgb(0, 53, 96); font-family: 'Helvetica
Neue',Arial,Helvetica,sans-serif; font-size: 12px;
line-height: 18px;"></span></span><span
class="Apple-style-span" style="border-collapse: separate;
color: rgb(0, 0, 0); font-family: 'Times New Roman';
font-size: 16px; font-style: normal; font-variant: normal;
font-weight: normal; letter-spacing: normal; line-height:
normal; orphans: 2; text-indent: 0px; text-transform: none;
white-space: normal; widows: 2; word-spacing: 0px;"><span
class="Apple-style-span" style="color: rgb(0, 53, 96);
font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;
font-size: 12px; line-height: 18px;"><span
class="Apple-style-span" style="border-collapse:
separate; color: rgb(0, 0, 0); font-family: 'Times New
Roman'; font-size: 16px; font-style: normal;
font-variant: normal; font-weight: normal;
letter-spacing: normal; line-height: normal; orphans: 2;
text-indent: 0px; text-transform: none; white-space:
normal; widows: 2; word-spacing: 0px;"><span
class="Apple-style-span" style="color: rgb(0, 53, 96);
font-family: 'Helvetica
Neue',Arial,Helvetica,sans-serif; font-size: 12px;
line-height: 18px;"></span></span></span></span>
<h3>Beste Grüße,</h3>
<h3>Florian Kohlar</h3>
<br>
</div>
</span></span><br>
<br>
<pre class="moz-signature" cols="72">--
Dipl.-Ing. Florian Kohlar
Lehrstuhl für Netz- und Datensicherheit
Ruhr Universität Bochum
-----------------------------------
Universitätsstr. 150, Geb. ID 2/457
D-44780 Bochum
Telefon: +49 (0) 234 / 32-26798
Fax: +49 (0) 234 / 32-14347
<a class="moz-txt-link-freetext" href="http://www.nds.rub.de">http://www.nds.rub.de</a>
</pre>
</body>
</html>