Stefan Lucks -- some papers

Last modified: May 30, 1997.
---------------------------------------------------------------------------
Note: Copying files for appeared papers may violate copyrights held by the
publishers! Such files are marked (*) below.
---------------------------------------------------------------------------

Open Key Exchange:
How to Defeat Dictionary Attacks Without Encrypting Public Keys

(47 K of gnu-zipped PostScript)

Classical cryptographic protocols based on shared secret keys often are
vulnerable to key-guessing attacks. For security, the keys must be strong,
difficult to memorize for humans. Bellovin and Merritt (1992) proposed
\equote{encrypted key exchange} (EKE) protocols, to frustrate key-guessing
attacks. EKE requires the use of asymmetric cryptosystems and is based on
encrypting the public key, using a symmetric cipher.

In this paper, a novel way of key exchange is presented, where public keys
are sent openly, not encrypted. In contrast to EKE protocols, the same
public-key/secret-key pair can be used for arbitrary many protocol
executions. The RSA-based protocol variant is found to be quite efficient
and practical.

Compared to previous work on such protocols, a more solid formal treatment
is given, influenced by the work of Bellare and Rogaway (1993) on key
exchange protocols for strong common secrets.

On the Security of Remotely Keyed Encryption

(50 K of gnu-zipped PostScript)

The purpose of remotely keyed encryption is to efficiently realize a
secret-key block cipher by sharing the computational burden between a fast
untrusted device and a slow device trusted with the key. This paper deals
with how to define the security of remotely keyed encryption schemes. Since
the attacker can take over the slow device and actually take part in the
encryption process, common definitions of the security of block ciphers
have to be reconsidered.

Using random mappings, collision resistant hash functions, and stream
ciphers as building blocks, the Random Mapping based Remotely Keyed
(RaMaRK) encryption scheme is proposed. Also GRIFFIN is proposed, a fast
new block cipher for flexible but large blocks. The RaMaRK scheme and
GRIFFIN are provably secure if the underlying building blocks are secure.

BEAST: A fast block cipher for arbitrary blocksizes(*)

(47 K of gnu-zipped PostScript)

This paper describes BEAST, a new blockcipher for arbitrary size blocks. It
is a Luby-Rackoff cipher and fast when the blocks are large. BEAST is
assembled from cryptographic hash functions and stream ciphers. It is
provably secure if these building blocks are secure.

For smartcard applications, a variant BEAST-RK is proposed, where the bulk
operations can be done by the smartcard's host without knowing the key.
Only fast key-dependent operations remain to be done by the smartcard.

Faster Luby-Rackoff Ciphers

(61 K of gnu-zipped PostScript)

This paper deals with a generalization of Luby's and Rackoff's results
(Luby and Rackoff, 1988) on the construction of block ciphers and their
consequences for block cipher implementations. Based on dedicated hash
functions, block ciphers are proposed which are more efficient and operate
on larger blocks than their original Luby-Rackoff counterparts.

How Traveling Salespersons Prove Their Identity

(37 K of gnu-zipped PostScript)

In this paper a new identification protocol is proposed. Its security is
based on the Exact Traveling Salesperson Problem (XTSP). The XTSP is a
close relative of the famous TSP and consists of finding a Hamiltonian
circuit of a given length, given a complete directed graph and the
distances between all vertices. Thus, the set of tools for use in
public-key cryptography is enlarged.

How to Exploit the Intractability of Exact TSP for Cryptography

(34 K of gnu-zipped PostScript)

We outline constructions for both pseudo-random generators and one-way hash
functions. These constructions are based on the exact TSP (XTSP), a special
variant of the well known traveling salesperson problem. We prove that
these constructions are secure if the XTSP is infeasible. Our constructions
are easy to implement, appear to be fast, but require a large amount of
memory.
---------------------------------------------------------------------------
Back to homepage of Stefan Lucks
This Web page is HTML 2.0 Checked and [Lynx Friendly!]