## Oberseminar Kryptographie

Sommersemester 2009

Dozent | Zeit | Raum | Erstmals am |
---|---|---|---|

Prof. A. May | donnerstags, 16.00 - 18.00 | NA 5/64 | Do., 16.04.2009 |

### Neue Seite: Perlenseminar

### Nächster Vortrag: 16.04.2009

### Cryptographic hash functions from expander graphs

#### Maike Ritzenhofen

The authors propose constructing provable collision resistant hash functions from expander graphs. As examples, they investigate two specific families of optimal expander graphs for provable hash function constructions: the families of Ramanujan graphs constructed by Lubotzky-Phillips-Sarnak and Pizer respectively. When the hash function is constructed from one of Pizer’s Ramanujan graphs, (the set of supersingular elliptic curves over Fp2 with `-isogenies, ` a prime different from p), then collision resistance follows from hardness of computing isogenies between supersingular elliptic curves.

For the LPS graphs, the underlying hard problem is a representation problem in group theory.

Constructing the hash functions from optimal expander graphs implies that the outputs closely approximate the uniform distribution. This property is useful for arguing that the output is indistinguishable from random sequences of bits.

They estimate the cost per bit to compute these hash functions, implement the hash function for several members of the LPS graph family and give actual timings.

This talk will concentrate on the second example, namely LPS graphs, and give the construction as well as the security analysis.

### Geplante Vorträge:

Termin | Vortragender | Titel |
---|---|---|

06.04.08 | Prof. Dr. Alexander May | Smashing SQUASH-0 |

08.04.08 (MI) | Prof. Dr. Roberto Avanzi | Efficient Divisor Reduction on Hyperelliptic Curves |

16.04.08 | Maike Ritzenhofen | Cryptographic hash functions from expander graphs |

23.04.08 | Mathias Herrmann | Securely Obfuscating Re-Encryption |

### Details:

### Efficient Divisor Reduction on Hyperelliptic Curves

#### Roberto Avanzi

joint work with M. J. Jacobson, Jr. and R. Scheidler

Hyperelliptic curve cryptography makes extensive use of scalar multiplication, which, oftentimes, is performed alternating double add operations. The latter operations constitute the computation of the reduced sum of the two input divisors.

Instead of performing divisor addition with subsequent reduction in each step, it is also possible to first perform more group operations, followed by the entire reduction. In some cases (tripling and quintupling, or merged add-with-double operations) this has proven useful to improve performance, but the

techniques have always been ad-hoc. Therefore, it is desirable to have a highly efficient divisor reduction method. Now, some reduction methods improving on the second part of Cantor's algorithm have been known for a while for quadratic number fields, but have not all been adapted to function fields.

As a consequence, merged operations have not been implemented very efficiently for hyperelliptic curves.

Here, we present such a new fast reduction algorithm for divisors on hyperelliptic curves. The method is based on a technique by R. Sewilla for rapidly reducing ideals in quadratic number fields. This method consists in a simple application of the Euclidean algorithm to the polynomials defining a divisor in Mumford representation - in the form that is known to be hidden

in continued fraction computations. No intermediate divisors are computed throughout this procedure; the Mumford coefficients of the final reduced divisors are recovered via simple formulas at the end.

This is work in progress, but we are confident that it will lead to significant performance improvements.

### Cryptographic hash functions from expander graphs

#### Denis X. Charles, Kristin E. Lauter, Eyal Z. Goren

The authors propose constructing provable collision resistant hash functions from expander graphs. As examples, they investigate two specific families of optimal expander graphs for provable hash function constructions: the families of Ramanujan graphs constructed by Lubotzky-Phillips-Sarnak and Pizer respectively. When the hash function is constructed from one of Pizer’s Ramanujan graphs, (the set of supersingular elliptic curves over Fp2 with `-isogenies, ` a prime different from p), then collision resistance follows from hardness of computing isogenies between supersingular elliptic curves. For the LPS graphs, the underlying hard problem is a representation problem in group theory.

Constructing the hash functions from optimal expander graphs implies that the outputs closely approximate the uniform distribution. This property is useful for arguing that the output is indistinguishable from random sequences of bits.

They estimate the cost per bit to compute these hash functions, implement the hash function for several members of the LPS graph family and give actual timings.

This talk will concentrate on the second example, namely LPS graphs, and give the construction as well as the security analysis.

### Securely Obfuscating Re-encryption

#### Susan Hohenberger, Guy Rothblum, abhi shelat, and Vinod Vaikuntanathan

We present the first positive obfuscation result for a traditional cryptographic functionality. This positive result stands in contrast to well-known negative impossibility results~\cite{betal01} for general obfuscation and recent negative impossibility and improbability~\cite{golkal05} results for obfuscation of many cryptographic functionalities.

Whereas other positive obfuscation results in the standard model apply to very simple point functions, our obfuscation result applies to the significantly more complicated and widely-used re-encryption functionality. This functionality takes a ciphertext for message $m$ encrypted under Alice's public key and transforms it into a ciphertext for the same message $m$ under Bob's public key.