Paderborn University

Tight security is increasingly gaining importance in real-world
cryptography, as it allows to choose cryptographic parameters in a way
that is supported by a security proof, without the need to sacrifice
efficiency by compensating the security loss of a reduction with larger
parameters. However, for many important cryptographic primitives,
including digital signatures and authenticated key exchange (AKE), we
are still lacking constructions that are suitable for real-world deployment.

This talk will present the first first practical AKE protocol with tight
security. It allows the establishment of a key within 1 RTT in a
practical client-server setting, provides forward security, is simple
and easy to implement, and thus very suitable for practical deployment.
It is essentially the "signed Diffie-Hellman" protocol, but with an
additional message, which is crucial to achieve tight security. This
message is used to overcome a technical difficulty in constructing
tightly-secure AKE protocols.

The second important building block is a practical signature scheme with
tight security in a real-world multi-user setting with adaptive
corruptions. The scheme is based on a new way of applying the
Fiat-Shamir approach to construct tightly-secure signatures from certain
identification schemes.

For a theoretically-sound choice of parameters and a moderate number of
users and sessions, our protocol has comparable computational efficiency
to the simple signed Diffie-Hellman protocol with EC-DSA, while for
large-scale settings our protocol has even better computational per-
formance, at moderately increased communication complexity.