TEST 2007 Accepted Submissions

Abstract:
The notion of key privacy for encryption schemes was defined formally by Bellare, Boldyreva, Desai and Pointcheval in Asiacrypt 2001. This notion seems useful in settings where anonymity is important. In this short note we describe a (very simple) sufficient condition for key privacy. In a nutshell, a scheme that provides data privacy is guaranteed to provide also key privacy if the distribution of a *random encryption of a random message* is independent of the public key that is used for the encryption.

Contact: some-email@address.edu

Category/Keywords: foundations / feedback shift registers, stream ciphers, Markov chains, rapid mixing

Abstract:
The purpose of this note is to show that Markov chains induced by non-singular triangular feedback shift registers and non-degenerate sources are rapidly mixing. The results may directly be applied to the post-processing of random generators and to stream ciphers in CFB mode.

Vincent Rijmen and Elisabeth Oswald

Contact: some-email@address.edu

Category/Keywords: secret-key cryptography / hash functions

Abstract:
We report on the experiments we performed in order to assess the
security of SHA-1 against the attack by Chabaud and Joux. We present some ideas for optimizations of the attack and some properties of the message expansion routine.
Finally, we show that for a reduced version of SHA-1, with 53
rounds instead of 80, it is possible to find collisions in less
than $2^{80}$ operations.

Comments:
This version corrects some errors of the CT-RSA version.

Contact: some-email@address.edu

Category/Keywords: public-key cryptography / elliptic curve cryptosystem, hyperelliptic curve cryptosystem, side-channel attacks, countermeasures

Abstract:
The present survey deals with the recent research in side channel
analysis and related attacks on implementations of cryptographic
primitives. The focus is on software contermeasures for primitives
built around algebraic groups. Many countermeasures are described,
together with their extent of applicability, and their weaknesses.
Some suggestions are made, conclusion are drawn, some directions for
future research are given. An extensive bibliography on recent
developments concludes the survey.

Comments:
This survey was originally written as a final report of the AREHCC project for the European Commission.

Dan Boneh and Craig Gentry and Brent Waters

Contact: some-email@address.edu

Category/Keywords: public-key cryptography / *

Abstract:
We describe two new public key broadcast encryption systems for
stateless receivers. Both systems are fully secure against any number
of colluders. In our first construction both ciphertexts and private
keys are of constant size (only two group elements), for any
subset of receivers. The public key size in this system is
linear in the total number of receivers. Our second system is a
generalization of the first that provides a tradeoff between
ciphertext size and public key size. For example, we achieve a
collusion resistant broadcast system for n users where both
ciphertexts and public keys are of size O(sqrt(n)) for any subset
of receivers. We discuss several applications of these systems.

Masayuki ABE and Rosario Gennaro and Kaoru Kurosawa

Contact: some-email@address.edu

Category/Keywords: public-key cryptography / hybrid encryption

Abstract:
This paper presents a novel framework for generic construction of hybrid encryption schemes which produces more efficient schemes than before. A known framework introduced by Shoup combines a key encapsulation mechanism (KEM) and a data encryption mechanism (DEM). While it is believed that both of the components must be secure against chosen ciphertext attacks, Kurosawa and Desmedt showed a particular example of KEM that might not be CCA but can be securely combined with CCA DEM yielding more efficient hybrid encryption scheme. There are also many efficient hybrid encryption schemes in various settings that do not fit to the framework. These facts serve as motivation to seek another framework that yields more efficient schemes.

In addition to the potential efficiency of the resulting schemes, our
framework will provide insightful explanation about existing schemes
that do not fit to the previous framework. This could result in finding improvements for some schemes. Moreover, it allows immediate conversion from a class of threshold public-key encryption to a hybrid one without considerable overhead, which is not possible in the previous approach.

Giuseppe Ateniese and Kevin Fu and Matthew Green and Susan Hohenberger

Contact: some-email@address.edu

Category/Keywords: * / *

Abstract:
In 1998, Blaze, Bleumer, and Strauss (BBS) proposed an application called
atomic proxy re-encryption, in which a semi-trusted proxy
converts a ciphertext for Alice into a ciphertext for Bob without
seeing the underlying plaintext. We predict that fast and
secure re-encryption will become increasingly popular as a method for
managing encrypted file systems. Although efficiently computable, the
wide-spread adoption of BBS re-encryption has been hindered by
considerable security risks. Following recent work of Ivan and Dodis,
we present new re-encryption schemes that realize a stronger notion of
security and we demonstrate the usefulness of proxy re-encryption as a
method of adding access control to the SFS read-only file system.
Performance measurements of our experimental file system demonstrate
that proxy re-encryption can work effectively in practice.

Boaz Barak and Shai Halevi

Contact: some-email@address.edu

Category/Keywords: * / /dev/random, Entropy, Mixing functions,Pseudo-randomness, Smart-cards, True randomness.

Abstract:
We present a formal model and a simple architecture for robust pseudorandom generation that ensures resilience in the face of an
observer with partial knowledge/control of the generator's entropy source. Our model and architecture have the following properties:

1 Resilience: The generator's output looks random to an observer with no knowledge of the internal state. This holds even if that observer has complete control over data that is used to refresh the internal state.

2 Forward security: Past output of the generator looks random to an observer, even if the observer learns the internal state at a later time.

3 Backward security/Break-in recovery: Future output of the generator looks random, even to an observer with knowledge of the current state, provided that the generator is refreshed with data of sufficient entropy.

Architectures such as above were suggested before. This work differs
from previous attempts in that we present a formal model for robust
pseudo-random generation, and provide a formal proof within this model
for the security of our architecture. To our knowledge, this is the
first attempt at a rigorous model for this problem.

Our formal modeling advocates the separation of the *entropy extraction* phase from the *output generation* phase. We argue that the former is information-theoretic in nature, and could therefore rely on combinatorial and statistical tools rather than on cryptography. On the other hand, we show that the latter can be implemented using any standard (non-robust) cryptographic PRG.

We also discuss the applicability of our architecture for applications such as /dev/(u)random in Linux and pseudorandom generation on smartcards.

Comments:
Minor revision

A. A. Kalele and V. R. Sule

Contact: some-email@address.edu

Category/Keywords: public-key cryptography / Bilinear Diffie-Hellman problem, Triparty key exchange

Abstract:
This paper develops a cryptanalysis of the pairing based Diffie
Hellman (DH) key exchange schemes an instance of which is the
triparty single round key exchange proposed in cite{joux}. The
analysis of emph{weak sessions} of the standard DH scheme
proposed in cite{kasu} is applied to show existence of weak
sessions for such schemes over supersingular curves. It is shown
that for such sessions the associated Bilinear Diffie Hellman
Problem is solvable in polynomial time, without computing the
private keys i.e. without solving the discrete logarithms. Other
applications of the analysis to Decisional Diffie Hellman Problem
and the identitiy based DH scheme are also shown to hold. The
triparty key exchange scheme is analyzed for illustration and it
is shown that the number of weak keys increases in this scheme as
compared to the standard two party DH scheme. It is shown that the
random choice of private keys by the users independent of each
other's knowledge is insecure in these schemes. Algorithms are
suggested for checking weakness of private keys based on an order
of selection.

Comments:
Submitting the revised copy as we found a mistake in references.

Iwan Duursma and Negar Kiyavash

Contact: some-email@address.edu

Category/Keywords: public-key cryptography / Elliptic curve cryptography, Curves of genus two

Abstract:
The group of m-torsion points on an elliptic curve, for a prime
number m, forms a two-dimensional vector space. It was suggested
and proven by Yoshida that under certain conditions the vector
decomposition problem (VDP) on a two-dimensional vector space is
at least as hard as the computational Diffie-Hellman problem
(CDHP) on a one-dimensional subspace. In this work we show that
even though this assessment is true, it applies to the VDP for
m-torsion points on an elliptic curve only if the curve is
supersingular. But in that case the CDHP on the one-dimensional
subspace has a known sub-exponential solution. Furthermore, we
present a family of hyperelliptic curves of genus two that are
suitable for the VDP.

Qiang Tang and Chris J. Mitchell

Contact: some-email@address.edu

Category/Keywords: cryptographic protocols / identification scheme Identity-based cryptosystem

Abstract:
Two identification schemes based on the Maurer-Yacobi ID-based
cryptosystem are analysed and shown to suffer from serious
security problems.

Contact: some-email@address.edu

Category/Keywords: * / RFID, Adversarial Model, Privacy, Untraceability, Cryptanalysis

Abstract:
Radio Frequency Identification (RFID) systems aim to identify objects in open environments with neither physical nor visual contact. They consist of transponders inserted into objects, of readers, and usually of a database which contains information about the objects. The key point is that authorised readers must be able to identify tags without an adversary being able to trace them. Traceability is often underestimated by advocates of the technology and sometimes exaggerated by its detractors. Whatever the true picture, this problem is a reality when it blocks the deployment of this technology and some companies, faced with being boycotted, have already abandoned its use. Using cryptographic primitives to thwart the traceability issues is an approach which has been explored for several years. However, the research carried out up to now has not provided satisfactory results as no universal formalism has been defined.
In this paper, we propose an adversarial model suitable for RFID environments. We define the notions of existential and universal untraceability and we model the access to the communication channels from a set of oracles. We show that our formalisation fits the problem being considered and allows a formal analysis of the protocols in terms of traceability. We use our model on several well-known RFID protocols and we show that most of them have weaknesses and are vulnerable to traceability.