<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

<html>

<head>

  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">

  <title></title>

</head>

<body bgcolor="#ffffff" text="#000000">

<div align="center">

<div align="left"><br>

</div>

<tt>Prof. Dr. Roberto Avanzi, CITS, RUB<br>

<br>

Montag 3. Juli 2006, 13:15 Uhr IC 4 / 39-41<br>

<br>

On Redundant τ-adic Expansions, the Characterization of Non-Adjacent

Digit Sets and Their Applications<br>

<br>

Joint Work with Clemens Heuberger and Helmut Prodinger<br>

</tt></div>

<tt><br>

We discuss τ-adic expansions of scalars, which are important in the

design of scalar multiplication algorithms for Koblitz Curves, but are

also less understood than their binary counterparts.<br>

<br>

At Crypto '97 Solinas introduced the width-<i>w</i> τ-adic non-adjacent

form for use with Koblitz curves.  It is an expansion of integers <i>z

= <big><big>Σ</big></big><sub>i=0..l</sub> z<sub>i</sub>τ<sup>i</sup></i>,

where τ is a quadratic integer depending on the curve, such that </tt><i><tt>z<sub>i</sub></tt>≠</i><tt><i>0</i>

implies<i> z<sub>w+i-1</sub> = ... = z_{<sub>i+1</sub>} = 0</i>, like

the sliding window binary recodings of integers. We show that the digit

sets described by Solinas, formed by elements of minimal norm in their

residue classes, are uniquely determined. We also show that, unlike for

binary representations, syntactic constraints do not necessarily imply

minimality of weight.<br>

<br>

Digit sets that permit recoding of all inputs are characterized. Two

new digit sets are introduced with useful properties; one set makes

precomputations easier, the second set is suitable for low-memory

applications, generalising an approach started by Avanzi, Ciet, and

Sica at PKC 2004 and continued by several authors since, including

Avanzi, Heuberger and Prodinger, as well as Okeya, Takagi and

Vuillaume. Results by Solinas, and by Blake, Murty, and Xu are

generalized.<br>

<br>

Termination, optimality, and cryptographic applications are considered.

The most important application is the ability to perform arbitrary

windowed scalar multiplication on Koblitz curves without storing any

precomputations first, thus reducing memory storage to just one or two

points and the scalar itself.<br>

<br>

The speaker will also spend a couple of words about the interaction of

these results with those of his previous talk in seminar.<br>

<br>

<br>

</tt>

<div align="left"><tt>_____________________________________________________________________________<br>

Die Webseite des HGI-Seminars mit allen Informationen zu vergangenen und<br>

zukünftigen Vorträgen:

<a class="moz-txt-link-freetext" href="http://www.hgi.rub.de/deutsch/lehrangebot/seminar.html">http://www.hgi.rub.de/deutsch/lehrangebot/seminar.html</a><br>

</tt></div>

<tt><br>

</tt><br>

<br>

<br>

<br>

</body>

</html>