## Oberseminar über Kryptographie

Wintersemester 2008/2009

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

Prof. A. May | mittwochs oder donnerstags, 16:00-18:00 | NA 5/64 | Mi., 15.10 |

### Nächster Vortrag: 26.03.2009

**Realizing Hash-and-Sign Signatures under Standard Assumptions****Sven Schäge**

Currently, there are relatively few instances of ``hash-and-sign'' signatures in the standard model. Moreover, most current instances rely on strong and less studied assumptions such as the Strong RSA and q-Strong Diffie-Hellman assumptions.

In this paper, we present a new approach for realizing hash-and-sign signatures in the standard model. In our approach, a signer associates each signature with an index i that represents how many signatures that signer has issued up to that point. Then, to make use of this association, we create simple and efficient techniques that restrict an adversary which makes q signature requests to forge on an index no greater than 2q. Finally, we develop methods for dealing with this restricted adversary.

Our approach requires that a signer maintains a small amount of state --- a counter of the number of signatures issued. We achieve two new realizations for hash-and-sign signatures respectively based on the RSA assumption and the Computational Diffie-Hellman assumption in bilinear groups.

### Geplante Vorträge:

### Vergangene Vorträge:

## DHIES: An encryption scheme based on the Diffie-Hellman Problem

### Maike Ritzenhofen

This paper describes a Diffie-Hellman based encryption scheme, DHIES (formerly named DHES

and DHAES), which is now in several (draft) standards. The scheme is as efficient as ElGamal encryption,

but has stronger security properties. Furthermore, these security properties are proven to hold

under appropriate assumptions on the underlying primitive. DHIES is a Diffie-Hellman based scheme

that combines a symmetric encryption method, a message authentication code, and a hash function, in

addition to number-theoretic operations, in a way which is intended to provide security against chosen ciphertext

attacks. The proofs of security are based on the assumption that the underlying symmetric

primitives are secure and on appropriate assumptions about the Diffie-Hellman problem. The latter are

interesting variants of the customary assumptions on the Diffie-Hellman problem, and we investigate

relationships among them, and provide security lower bounds. Our proofs are in the standard model; no

random-oracle assumption is required.

## HMQV: A High-Performance Secure Diffie-Hellman Protocol

### Alex May

The MQV protocol of Law, Menezes, Qu, Solinas and Vanstone is possibly the most efficient

of all known authenticated Diffie-Hellman protocols that use public-key authentication. In

addition to great performance, the protocol has been designed to achieve a remarkable list

of security properties. As a result MQV has been widely standardized, and has recently been

chosen by the NSA as the key exchange mechanism underlying “the next generation cryptography

to protect US government information”.

One question that has not been settled so far is whether the protocol can be proven secure

in a rigorous model of key-exchange security. In order to provide an answer to this question we

analyze the MQV protocol in the Canetti-Krawczyk model of key exchange. Unfortunately, we

show that MQV fails to a variety of attacks in this model that invalidate its basic security as

well as many of its stated security goals. On the basis of these findings, we present HMQV, a

carefully designed variant of MQV, that provides the same superb performance and functionality

of the original protocol but for which all the MQV’s security goals can be formally proved to

hold in the random oracle model under the computational Diffie-Hellman assumption.

We base the design and proof of HMQV on a new form of “challenge-response signatures”,

derived from the Schnorr identification scheme, that have the property that both the challenger

and signer can compute the same signature; the former by having chosen the challenge and the

latter by knowing the private signature key.

## Verfahren zur Sicherstellung der Vertraulichkeit einrichtungsübergreifender elektronischer Patientenakten mit Token-basierten Mechanismen zur Zugriffsautorisierung im Behandlungsfall

### Mathias Hermann

Es wird ein Grobkonzept zur Elektronischen-Patienten-Akte (kurz EPA) vorgestellt. Die kryptographische Implementierung basiert auf HMQV und DHIES. Der Vortrag dient der Vorstellung des Konzepts und anschließend wird in der Runde über Schwächen, Nachteile und Verbesserungsvorschläge diskutiert.

## Pairing with Supersingular Trace Zero Varieties (Revisited)

### Emanuele Cesena

### Università degli Studi

RomaTre/Politecnico di Torino

Given a low genus hyperelliptic curve defined over a finite field $\mathbb{F}_q$, a Trace Zero Variety is a specific subgroup of the group of the divisor classes on the curve which are rational over a small degree extension $\mathbb{F}_{q^r}$ of the definition field.

Trace Zero Varieties (TZV) are interesting for cryptographic applications since they enjoy properties that can be exploited to achieve fast arithmetic and group construction.

Rubin and Silverberg have shown that supersingular TZV find interesting applications in pairing-based cryptography and allow to achieve higher MOV security per bit than, for instance, supersingular elliptic curves.

In this talk we survey algorithms in the literature for computing bilinear pairings that apply to TZV and we present a new algorithm for the Tate pairing over supersingular TZV, which exploits the action of the $q$-Frobenius endomorphism. We give explicit examples and provide experimental results for supersingular TZV defined over fields of characteristic 2.

## Cube Attacks on Tweakable Black Box Polynomials

### Thomas Dullien

Abstract. Almost any cryptographic scheme can be described by tweakable polynomials over

GF(2), which contain both secret variables (e.g., key bits) and public variables (e.g., plaintext bits

or IV bits). The cryptanalyst is allowed to tweak the polynomials by choosing arbitrary values for

the public variables, and his goal is to solve the resultant system of polynomial equations in terms

of their common secret variables. In this paper we develop a new technique (called a cube attack)

for solving such tweakable polynomials, which is a major improvement over several previously

published attacks of the same type. For example, on the stream cipher Trivium with a reduced

number of initialization rounds, the best previous attack (due to Fischer, Khazaei, and Meier)

requires a barely practical complexity of 2^55 to attack 672 initialization rounds, whereas a cube

attack can find the complete key of the same variant in 2^19 bit operations (which take less than

a second on a single PC). Trivium with 735 initialization rounds (which could not be attacked

by any previous technique) can now be broken with 2^30 bit operations, and by extrapolating our

experimentally verified complexities for various sizes, we have reasons to believe that cube attacks

will remain faster than exhaustive search even for 1024 initialization rounds. Whereas previous

attacks were heuristic, had to be adapted to each cryptosystem, had no general complexity bounds,

and were not expected to succeed on random looking polynomials, cube attacks are provably

successful when applied to random polynomials of degree d over n secret variables whenever the

number m of public variables exceeds d + log_d(n). Their complexity is 2^{d-1}n + n^2 bit operations,

which is polynomial in n and amazingly low when d is small. Cube attacks can be applied to

any block cipher, stream cipher, or MAC which is provided as a black box (even when nothing

is known about its internal structure) as long as at least one output bit can be represented by

(an unknown) polynomial of relatively low degree in the secret and public variables. In particular,

they can be easily and automatically combined with any type of side channel attack that leaks

some partial information about the early stages of the encryption process (which can typically be

represented by a very low degree polynomial), such as the Hamming weight of a byte written into

a register.

## Faster Point Multiplication on elliptic curves with Efficient Endomorphisms

### Jan Aumann

The fundamental operation in elliptic curve cryptographic schemes is the

multiplication of an elliptic curve point by an integer. This paper

describes a new method for accelerating this operation on classes of

elliptic curves that have efficiently-computable endomorphisms. One

advantage of the new method is that it is applicable to a larger class

of curves than previous such methods. For this special class of curves,

a speedup of up to 50% can be expected over the best general methods for

point multiplication.

## Optimizing Double-Base Integer Expansions

### Roberto Avanzi

We shall make a survey of recent results in DBNS (Double Base Number Systems) and show how we plan to do it better.

## On the Complexity of Lattice Problems with Polynomial Approximation Factors

### Alexander Meurer

Lattice problems are known to be hard to approximate to within sub-polynomial factors.

For larger approximation factors, such as sqrt(n), lattice problems are known to be in complexity

classes such as NP intersect coNP and are hence unlikely to be NP-hard. Here we survey known results

in this area. We also discuss some related zero-knowledge protocols for lattice problems.

## On the Provable Security of an Efficient RSA-Based Pseudorandom Generator

### Alexander May

Pseudorandom Generators (PRGs) based on the RSA inversion (one-wayness) problem have been extensively studied in the literature over the last 25 years. These generators have the attractive feature of provable pseudorandomness security assuming the hardness of the RSA inversion problem. However, despite extensive study, the most efficient provably secure RSA-based generators output asymptotically only at most O(logn) bits per multiply modulo an RSA modulus of bitlength n, and hence are too slow to be used in many practical applications.

To bring theory closer to practice, we present a simple modification to the proof of security by Fischlin and Schnorr of an RSA-based PRG, which shows that one can obtain an RSA-based PRG which outputs Ω(n) bits per multiply and has provable pseudorandomness security assuming the hardness of a well-studied variant of the RSA inversion problem, where a constant fraction of the plaintext bits are given. Our result gives a positive answer to an open question posed by Gennaro (J. of Cryptology, 2005) regarding finding a PRG beating the rate O(logn) bits per multiply at the cost of a reasonable assumption on RSA inversion.

Keywords: Pseudorandom generator, RSA, provable security, lattice attack.

## Toward a Rigorous Variation of Coppersmith’s Algorithm on Three Variables

### Maike Ritzenhofen

In 1996, Coppersmith introduced two lattice reduction based techniques to find small roots in polynomial equations. One technique works for modular univariate polynomials, the other for bivariate polynomials over the integers. Since then, these methods have been used in a huge variety of cryptanalytic applications. Some applications also use extensions of Coppersmith’s techniques on more variables. However, these extensions

are heuristic methods. In the present paper, we present and analyze a new variation of Coppersmith’s algorithm on three variables over the integers. We also study the applicability of our method to short RSA

exponents attacks. In addition to lattice reduction techniques, our method also uses Gröbner bases computations. Moreover, at least in principle, it can be generalized to four or more variables.

## Compact Proofs of Retrievability

### Mathias Herrmann

In a proof-of-retrievability system, a data storage center convinces a verifier that he is actually storing all of a client’s data. The central challenge is to build systems that are both efficient and provably secure—that is, it should be possible to extract the client’s data from any prover that passes a verification check. In this paper, we give the first proof-of-retrievability schemes with full proofs of security against arbitrary adversaries in the strongest model, that of Juels and Kaliski. Our first scheme, built from BLS signatures and secure in the random oracle model, has the shortest query and response of any proof-of-retrievability with public verifiability. Our second scheme, which builds elegantly on pseudorandom functions (PRFs) and is secure in the standard model, has the shortest response of any proof-of-retrievability scheme with private verifiability (but a longer query). Both schemes rely on homomorphic properties to aggregate a proof into one small authenticator value.

## Review of Truncated and Higher-Order Differentials

### Thomas Dullien

Following Lars Knudsens PhD Thesis, truncated and higher-order differentials will be reviewed.

## Realizing Hash-and-Sign Signatures under Standard Assumptions

### Sven Schäge

Currently, there are relatively few instances of ``hash-and-sign'' signatures in the standard model. Moreover, most current instances rely on strong and less studied assumptions such as the Strong RSA and q-Strong Diffie-Hellman assumptions.

In this paper, we present a new approach for realizing hash-and-sign signatures in the standard model. In our approach, a signer associates each signature with an index i that represents how many signatures that signer has issued up to that point. Then, to make use of this association, we create simple and efficient techniques that restrict an adversary which makes q signature requests to forge on an index no greater than 2q. Finally, we develop methods for dealing with this restricted adversary.

Our approach requires that a signer maintains a small amount of state --- a counter of the number of signatures issued. We achieve two new realizations for hash-and-sign signatures respectively based on the RSA assumption and the Computational Diffie-Hellman assumption in bilinear groups.