Oberseminar über Kryptographie

Wintersemester 2008/2009

Oberseminar
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:

Termin Vortragender Titel
15.10.08 Maike Ritzenhofen DHIES: An encryption scheme based on the Diffie-Hellman Problem
30.10.08 Prof. Dr. Alexander May HMQV: A High-Performance Secure Diffie-Hellman Protocol
05.11.08 Mathias Herrmann Verfahren zur Sicherstellung der Vertraulichkeit einrichtungsübergreifender elektronischer Patientenakten mit Token-basierten Mechanismen zur Zugriffsautorisierung im Behandlungsfall
13.11.08 Emanuele Cesena Pairing with Supersingular Trace Zero Varieties (Revisited)
20.11.08 Thomas Dullien Cube Attacks on Tweakable Black Box Polynomials
27.11.08 Jan Aumann Faster Point Multiplication on elliptic curves with Efficient Endomorphisms
04.12.08 ------------ entfällt
11.12.08 Prof. Dr. Roberto Avanzi Optimizing Double-Base Integer Expansions
18.12.08 Alexander Meurer On the Complexity of Lattice Problems with Polynomial Approximation Factors
08.01.08 Prof. Dr. Alexander May On the Provable Security of an Efficient RSA-Based Pseudorandom Generator
22.01.08 Maike Ritzenhofen Toward a Rigorous Variation of Coppersmith’s Algorithm on Three Variables
29.01.08 Maike Ritzenhofen Toward a Rigorous Variation of Coppersmith’s Algorithm on Three Variables Pt.2
05.03.08 Mathias Herrmann Compact Proofs of Retrievability
12.03.08 Thomas Dullien Review of Truncated and Higher-Order Differentials
26.03.08 Sven Schäge Realizing Hash-and-Sign Signatures under Standard Assumptions

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.