[HGI-News-de] HGI-Kolloquium: Knapsacks and Index Calculus - Anja Becker und Antoine Joux - Donnerstag, 07. April

[Newsletter des Horst Görtz Instituts]

      HGI






      Sehr geehrte Damen und Herren,



      im Rahmen des HGI-Kolloquiums organisiert vom Lehrstuhl für Netz-
      und Datensicherheit (NDS), werden


              _Anja Becker und Antoine Joux_


      von der


              Universite de Versailles, Frankreich


       am


              nächsten _Donnerstag, den 07. April 2011 _


      über folgende Themen referieren:



  IM­PRO­VED GE­NE­RIC AL­GO­RITH­MS FOR HARD KNAP­SACKS

Anja Be­cker

At Eu­ro­crypt 2010, How­gra­ve-Gra­ham and Joux de­scri­bed an
al­go­rithm for sol­ving hard knap­sacks of den­si­ty close to 1 in time
O^~(2^{0.337n}) and me­mo­ry O^~(2^{0.256n}), the­re­by im­pro­ving a
30-ye­ar old al­go­rithm by Sha­mir and Schro­ep­pel. Our new
tech­ni­que al­lows us to get an al­go­rithm with run­ning time down to
O^~(2^{0.291n}).

The knap­sack in­stan­ce is di­vi­ded in two hal­ves with pos­si­ble
over­lap, as in the How­gra­ve-Gra­ham--Joux al­go­rithm, but the set of
pos­si­ble co­ef­fi­ci­ents is ex­ten­ded from {0,1} to {-1,0,+1}. This
means that a co­ef­fi­ci­ent -1 in the first half can be com­pen­sa­ted
with a co­ef­fi­ci­ent +1 in the se­cond half, re­sul­ting in an
co­ef­fi­ci­ent 0 of the gol­den so­lu­ti­on. To re­veal the gol­den
so­lu­ti­on, we the­re­fo­re se­arch for one de­com­po­si­ti­on (out of
many) of the so­lu­ti­on by sol­ving two knap­sacks. Ad­ding (a few) -1
co­ef­fi­ci­ents brings an ad­di­tio­nal de­gree of free­dom that
enables to again de­crea­se the run­ning time. To ex­plain the idea, we
will have a look at a prac­tical ex­amp­le.


  COVER AND DE­COM­PO­SI­TI­ON INDEX CAL­CU­LUS ON EL­LIP­TIC CUR­VES
  MADE PRAC­TICAL

An­toi­ne Joux

We pre­sent a new va­ri­ant of cover and de­com­po­si­ti­on at­tacks on
the el­lip­tic curve dis­cre­te lo­ga­rithm pro­blem, that com­bi­nes
Weil des­cent and de­com­po­si­ti­on-ba­sed index cal­cu­lus into a
sin­gle dis­cre­te lo­ga­rithm al­go­rithm. This va­ri­ant ap­p­lies, at
least theo­re­ti­cal­ly, to all com­po­si­te de­gree ex­ten­si­on
fields, and is par­ti­cu­lar­ly well-sui­ted for cur­ves de­fined over
$F_{p6}$. We give a re­al-si­ze ex­amp­le of dis­cre­te lo­ga­rithm
com­pu­ta­ti­ons on a see­mingly se­cu­re curve over a $130$-bit de­gree
$6$ ex­ten­si­on field.

------------------------------------------------------------------------


      Der Vortrag beginnt um 11.00 Uhr s.t. im ID 03/445.



      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!



      Weitere Informationen gibt es auf folgender Webseite:


      http://hgi.rub.de/hgi/hgi-seminar/aktuelles/


      Beste Grüße,


      Florian Kohlar




-- 
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
http://www.nds.rub.de

-------------- nächster Teil --------------
Ein Dateianhang mit HTML-Daten wurde abgetrennt...
URL: <http://lists.ruhr-uni-bochum.de/pipermail/hgi-news-deutschland/attachments/20110401/f09254d7/attachment.html>
-------------- nächster Teil --------------
Ein Dateianhang mit Binärdaten wurde abgetrennt...
Dateiname   : hgi_cmyk_RGB.jpg
Dateityp    : image/jpeg
Dateigröße  : 116679 bytes
Beschreibung: nicht verfügbar
URL         : <http://lists.ruhr-uni-bochum.de/pipermail/hgi-news-deutschland/attachments/20110401/f09254d7/attachment.jpg>