## All papers in 2002 (195 results)

An addition to the paper: A polarisation based visual crypto system and its secret sharing schemes

An (n,k) pair is a pair of binary nxm matrices (A,B), such that the weight of the modulo-two sum of any i rows, 1\leq i \leq k, from A or B is equal to a_i or b_i, respectively, and moreover, a_i=b_i, for 1\leq i < k, while a_k \neq b_k. In this note we first show how to construct an (n,k) Threshold Visual Secret Sharing Scheme from an (n,k) pair. Then, we explicitly construct an (n,k)-pair for all n and k with 1 \leq k <n.

A polarisation based Visual Crypto System and its Secret Sharing Schemes

In this paper, we present a new visual crypto system based on the polarisation of light and investigate the existence and structure of the associated threshold visual secret sharing schemes. It is shown that very efficient $(n,n)$ schemes exist and that $(2,n)$ schemes are equivalent to binary codes. The existence of $(k,n)$ schemes is shown in general by two explicit constructions. Finally, bounds on the physical properties as contrast and resolution are derived.

A Note on Ideal Tripartite Access Structures

Uncategorized

Uncategorized

Padró and Sáez introduced the concept of a
$k$-partite access structure for secret sharing, and gave a complete
characterization of ideal bipartite structures. We derive a necessary
condition for ideal tripartite structures, which we conjecture is
necessary for all $k$.

Security Proofs for an Efficient Password-Based Key Exchange

Password-based key exchange schemes are designed to provide
entities communicating over a public network, and sharing a
(short) password only, with a session key (e.g, the key is used
for data integrity and/or confidentiality). The focus of the
present paper is on the analysis of very efficient schemes that
have been proposed to the IEEE P1363 Standard working group on
password-based authenticated key-exchange methods, but for which
actual security was an open problem. We analyze the AuthA key
exchange scheme and give a complete proof of its security. Our
analysis shows that the AuthA protocol and its multiple modes
of operation are provably secure under the computational
Diffie-Hellman intractability assumption, in both the
random-oracle and the ideal-cipher models.

A Linearization Attack on the Bluetooth Key Stream Generator

In this paper we propose an attack on the key stream generator underlying the encryption system $E_0$ used in the Bluetooth specification.
We show that the initial value can be recovered by solving
a system of nonlinear equations of degree 4 over the finite field GF(2).
This system of equations can be transformed by linearization into a system
of linear equations with at most $2^{24.056}$ unknowns. To our knowledge, this is the best attack on the key stream generator
underlying the $\mbox{E}_0$ yet.

Parallelizable Authentication Trees

Uncategorized

Uncategorized

We define a new authentication tree in the symmetric key setting,
which has the same computational time, storage
and security parameters as the well
known Merkle authentication tree, but which unlike the latter, allows
for all the cryptographic operations required for an update to be performed
in parallel. The cryptographic operations required for verification can
also be parallelized. In particular, we show a provably secure scheme for
incremental MAC with partial authentication secure against substitution and
replay attacks, which on total data of size $2^n$ blocks,
and given $n$ cryptographic engines,
can compute incremental macs and perform
individual block authentication with
a critical path of only one cryptographic operation

Bit-Slice Auction Circuit

In this paper, we introduce a bit-slice approach for auctions and present a more efficient circuit than the normal approach for the highest-price auction. Our circuit can be combined with any auction protocol based on general circuit evaluation. Especially, if we combine with the mix and match technique, then we can obtain a highest-price auction protocol which is at least seven times faster. A second-price auction protocol is also easily constructed from our circuit.

Key recovery attacks on NTRU without ciphertext validation routine

NTRU is an efficient public-key cryptosystem proposed by
Hoffstein, Pipher, and Silverman.
Assuming access to a decryption oracle,
we show ways to recover the private key of NTRU systems
that do not include a ciphertext validating procedure.
The strongest of our methods will employ just a single call to the
oracle, and in all cases, the number of calls needed will be small
enough to be realistic.

Entity Authentication Schemes Using Braid Word Reduction

Artin's braid groups currently provide a promising background
for cryptographical applications, since the first
cryptosystems using braids were introduced in
\cite{SCY,AAF, AAG, KLC}. A variety of key agreement
protocols based on braids have been described, but few
authentication or signature schemes have been
proposed so far. We introduce three authentication
schemes based on braids, two of them being
zero-knowledge interactive proofs of knowledge. Then
we discuss their possible implementations,
involving normal forms or an alternative braid algorithm,
called handle reduction, which can achieve
good efficiency under specific requirements.

Zero-Knowledge twenty years after its invention

Zero-knowledge proofs are proofs that are both convincing and yet
yield nothing beyond the validity of the assertion being proven.
Since their introduction about twenty years ago,
zero-knowledge proofs have attracted a lot of attention
and have, in turn, contributed to the development of other
areas of cryptography and complexity theory.
We survey the main definitions and results regarding
zero-knowledge proofs.
Specifically, we present the basic definitional approach
and its variants, results regarding the power of zero-knowledge proofs
as well as recent results regarding questions such as
the composeability of zero-knowledge proofs
and the use of the adversary's program
within the proof of security (i.e., non-black-box simulation).

Turing, a fast stream cipher

This paper proposes the Turing stream cipher. Turing offers up to 256-bit key strength, and is designed for extremely efficient software implementation. It combines an LFSR generator based on that of SOBER with a keyed mixing function reminiscent of a block cipher round. Aspects of the block mixer round have been derived from Rijndael, Twofish, tc24 and SAFER.

Identity Based Authenticated Key Agreement Protocols from Pairings

Uncategorized

Uncategorized

We investigate a number of issues related to identity based
authenticated key agreement protocols using the Weil or Tate
pairings. These issues include how to make protocols efficient;
how to avoid key escrow by a Trust Authority (TA) who issues
identity based private keys for users, and how to allow users to
use different Trusted Authorities. We describe a few authenticated
key agreement (AK) protocols and AK with key confirmation (AKC)
protocols which are modified from Smart's AK protocol.
We study the security of these protocols heuristically and using
provable security methods. In addition, we prove that our AK
protocol is immune to key compromise impersonation attacks, and we
also show that our second protocol has the TA forward secrecy
property (which we define to mean that the compromise of the TA's
private key will not compromise previously established session
keys). We also show that this TA forward secrecy property implies
that the protocol has the perfect forward secrecy property.

Simple backdoors to RSA key generation

We present extremely simple ways of embedding a backdoor in the key
generation scheme of RSA. Three of our schemes generate two
genuinely random primes $p$ and $q$ of a given size, to obtain their
public product $n=pq$. However they generate private/public
exponents pairs $(d,e)$ in such a way that appears very random while
allowing the author of the scheme to easily factor $n$ given only
the public information $(n,e)$. Our last scheme, similar to the PAP
method of Young and Yung, but more secure, works for any public
exponent $e$ such as $3,17,65537$ by revealing the factorization of
$n$ in its own representation. This suggests that nobody should
rely on RSA key generation schemes provided by a third party.

Oblivious Keyword Search

In this paper,
we introduce a notion of Oblivious Keyword Search ($OKS$).
Let $W$ be the set of possible keywords.
In the commit phase, a database supplier $T$ commits $n$ data.
In each transfer subphase,
a user $U$ can choose a keyword $w \in W$ adaptively
and find $Search(w)$ without revealing $w$ to $T$,
where $Search(w)$ is the set of all data which includes $w$ as a keyword.
We then show two efficient protocols
such that the size of the commitments is only $(nB)$
regardless of the size of $W$, where $B$ is the size of each data.
It is formally proved that $U$ learns nothing more and
$T$ gains no information on the keywords which $U$ searched.
We further present a more efficient adaptive $OT_k^n$ protocol
than the previous one as an application of our first $OKS$ protocol.

Counting Points for Hyperelliptic Curves of type $y^2=x^5+ax$ over Finite Prime Fields

Counting rational points on Jacobian varieties of hyperelliptic curves
over finite fields is very important for constructing
hyperelliptic curve cryptosystems (HCC),
but known algorithms for general curves over given large prime
fields need very long running times.
In this article, we propose an extremely fast point counting algorithm for
hyperelliptic curves of type $y^2=x^5+ax$ over given large
prime fields $\Fp$, e.g. 80-bit fields.
For these curves, we also determine the necessary condition
to be suitable for HCC, that is, to satisfy that the order
of the Jacobian group is of the form $l\cdot c$ where $l$
is a prime number greater than about $2^{160}$ and
$c$ is a very small integer.
We show some examples of suitable curves for HCC obtained by
using our algorithm.
We also treat curves of type $y^2=x^5+a$ where $a$ is not
square in $\Fp$.

OMAC: One-Key CBC MAC

In this paper, we present One-key CBC MAC (OMAC) and prove its security for arbitrary length messages. OMAC takes only one key, $K$ ($k$ bits) of a block cipher $E$. Previously, XCBC requires three keys, $(k+2n)$ bits in total, and TMAC requires two keys, $(k+n)$ bits in total, where $n$ denotes the block length of $E$.
The saving of the key length makes the security proof of OMAC substantially harder than those of XCBC and TMAC.

Parallel Algorithm for Multiplication on Elliptic Curves

Given a positive integer $n$ and a point $P$ on an elliptic curve $E$, the computation of
$nP$, that is, the result of adding $n$ times the point $P$ to itself, called the
\emph{scalar multiplication}, is the central operation of elliptic curve cryptosystems.
We present an algorithm that, using $p$
processors, can compute $nP$ in time $O(\log n+H(n)/p+\log p)$, where $H(n)$ is
the Hamming weight of $n$. Furthermore, if this algorithm is applied to Koblitz curves,
the running time can be reduced to $O(H(n)/p+\log p)$.

Attack on A New Public Key Cryptosystem from ISC'02 (LNCS 2433)

Uncategorized

Uncategorized

In ISC 2002, J. Zheng proposed a new public key
cryptosystem whose security is based upon the algebraic problem of
reducing a high degree matrix to its canonical form by similarity
transformations. In this paper, we show that factoring a
polynomial over a finite field can be used to break down Zheng's
public key cryptosystem. The complexity of our attack is
polynomial time. In other word, the underlying problem of Zheng's
public key cryptosystem is not a ``hard'' problem.

two attacks on xia-you Group Signature

Uncategorized

Uncategorized

Group signature is very important primitive in cryptography. A group signature scheme allows any group member to sign on behalf of the group in an anonymous and unlinkable fashion .In case of dispute, group manager can reveal the identity of the signer. Recently, S.Xia and J.You proposed a group signature scheme based on identity with strong separability in which the revocation manager can work without the involvement of the membership manger. In this paper, we analyze the security of Xia-You group signature and indicate that two or more group members can collude to construct a valid signature and any group member can forge a valid membership certification.

Theoretical Analysis of ``Correlations in RC6''

In this paper, we give the theoretical analysis of Chi-square attack proposed by Knudsen and Meier on the RC6 block cipher. To this end, we propose the novel method of security evaluation against Chi-square attack precisely including key dependency by introducing a technique ``Transition Matrix Computing.'' On the other hand, the way of security evaluation against Chi-square attack has not been known except the computer experiment. We should note that it is the first results the way of security evaluation against Chi-square attack is shown theoretically. Using this method, we can obtain the ``weakest keys'' against the attack.

Aggregate and Verifiably Encrypted Signatures from Bilinear Maps

An aggregate signature scheme is a digital signature that supports
aggregation: Given $n$ signatures on $n$ distinct messages from
$n$ distinct users, it is possible to aggregate all these
signatures into a single short signature. This single signature
(and the $n$ original messages) will convince the verifier that
the $n$ users did indeed sign the $n$ original messages (i.e.,
user $i$ signed message $M_i$ for $i=1,\ldots,n$). In this paper
we introduce the concept of an aggregate signature scheme, present
security models for such signatures, and give several applications
for aggregate signatures. We construct an efficient aggregate
signature from a recent short signature scheme based on bilinear
maps due to Boneh, Lynn, and Shacham. Aggregate signatures are
useful for reducing the size of certificate chains (by aggregating
all signatures in the chain) and for reducing message size in
secure routing protocols such as SBGP. We also show that
aggregate signatures give rise to verifiably encrypted signatures.
Such signatures enable the verifier to test that a given
ciphertext $C$ is the encryption of a signature on a given message
$M$. Verifiably encrypted signatures are used in contract-signing
protocols. Finally, we show that similar ideas can be used to
extend the short signature scheme to give simple ring signatures.

A Designer's Guide to KEMs

A generic or KEM-DEM hybrid construction is a formal method of
combining a asymmetric and symmetric encryption techniques to give
an efficient, provably secure public-key encryption scheme. This
method combines an asymmetric KEM with a symmetric DEM, and each
of these components must satisfy their own security conditions. In
this paper we describe generic constructions for provably secure
KEMs based on lower level primitives such as one-way trapdoor
functions and weak key-agreement protocols.

Efficient Group Signatures without Trapdoors

Group signature schemes enable unlinkably anonymous
authentication, in the same fashion that digital signatures provide the basis for
strong authentication protocols. This paper introduces the first group signature scheme
with constant-size parameters that does not require any group member, including group
managers, to know trapdoor secrets. This novel type of group signature scheme allows
public parameters to be shared among organizations, and are useful when
several distinct groups must interact and exchange information about
individuals while protecting their privacy.

PECDSA. How to build a DL-based digital signature scheme with the best proven security

Many variants of the ElGamal signature scheme have been proposed. The most famous is the DSA standard.
If computing discrete logarithms is hard, then some of these schemes have been proven secure in an idealized model,
either the random oracle or the generic group. We propose a generic but simple presentation of signature schemes with
security based on the discrete logarithm. We show how they can be proven secure in idealized model,
under which conditions. We conclude that none of the previously proposed digital signature
schemes has optimal properties and we propose a scheme named PECDSA.

Statistical weaknesses in the alleged RC4 keystream generator

A large number of stream cipher were proposed and implemented over the last twenty years. In 1987 Rivest designed the RC4 stream cipher, which was based on a different and more software friendly paradigm. It was integrated into Microsoft Windows, Lotus Notes, Apple AOCE, Oracle Secure SQL, and many other applications, and has thus become the most widely used a software-based stream cipher. In this paper we describe some properties of an output sequence of RC4. It is proved that the distribution of first, second output values of RC4 and digraphs are not uniform, which makes RC4 trivial to distinguish between short outputs of RC4 and random strings by analyzing their first, or second output values of RC4 or digraphs.

An Analysis of RMAC

A recent trend in message authentication is the use of a randomizing parameter, such that the authentication tag is based not only on the message and the key, but a public nonce which is changed for every authenticated message. This generally affords a better security proof. However, several new classes of attacks are made available by these techniques. We examine these attacks, and apply some of them to RMAC, a recently published MAC mechanism.

Theoretical Use of Cache Memory as a Cryptanalytic Side-Channel

Uncategorized

Uncategorized

We expand on the idea, proposed by Kelsey et al, of cache memory being
used as a side-channel which leaks information during the run of a
cryptographic algorithm. By using this side-channel, an attacker may
be able to reveal or narrow the possible values of secret information
held on the target device. We describe an attack which encrypts
$2^{10}$ chosen plaintexts on the target processor in order to collect
cache profiles and then performs around $2^{32}$ computational steps
to recover the key. As well as describing and simulating the
theoretical attack, we discuss how hardware and algorithmic
alterations can be used to defend against such techniques.

New Signature Scheme Using Conjugacy Problem

We propose a new digital signature scheme based on a
non-commutative group where the conjugacy search problem is hard
and the conjugacy decision problem is feasible. We implement our
signature scheme in the braid groups and prove that an existential
forgery of the implementation under no message attack
gives a solution to a variation of conjugacy search problem. Then
we discuss performance of our scheme under suggested parameters.

Cryptanalysis of Two New Signature Schemes

Uncategorized

Uncategorized

Group signature and blind signature are very important primitives
in cryptography. A group signature scheme allows a group member to
sign messages anonymously on behalf of the group and a blind
signature scheme can ensure anonymity of the sender of a message.
Recently, S. Xia and J. You proposed a group
signature scheme with strong separability in which the revocation
manager can work without the involvement of the membership manager
and J.J-R. Chen and A.P. Chen proposed a blind
signature scheme based on dual complexities (which combines
factorization and discrete logarithm problem). In this paper, we
give a universal forgery attack on Xia-You's group signature
scheme which any one (not necessarily a group member) can produce
a valid group signature on an arbitrary message, and it is
untraceable by the group revocation manager. For Chen-Chen's blind
signature scheme, we show that it could not meet the
untraceability property of a blind signature, $i.e.$, it could not
ensure anonymity of the user.

Multi-Party Authenticated Key Agreement Protocols from Multilinear Forms

A. Joux presented a one round protocol for tripartitie key agreement and Al-Riyami et.al. developed a number of tripartitie, one round, authenticated protocols related to MTI and MQV protocols. Recently,
Boneh and Silverleg studied multilinear forms, which provides a one round multi-party key agreement protocol. In this paper, we propose $(n+1)$ types of one round authenticated multi-party key agreement protocols from multilinear forms based on the application of MTI and MQV protocols.

Coercion-Resistant Electronic Elections

Uncategorized

Uncategorized

We introduce a model for electronic election schemes that involves
a more powerful adversary than in previous work. In particular, we allow the adversary to demand of coerced voters that they vote in a particular manner, abstain from voting, or even disclose their secret keys. We define a scheme to be _coercion-resistant_
if it is infeasible for the adversary to determine whether
a coerced voter complies with the demands.
A first contribution of this paper is to describe and characterize a
new and strengthened adversary for coercion in elections. (In doing
so, we additionally present what we believe to be the first formal
security definitions for electronic elections of _any_ type.) A
second contribution is to demonstrate a protocol that is secure
against this adversary. While it is clear that a strengthening of
attack models is of theoretical relevance, it is important to note
that our results lie close to practicality. This is true both in that
we model real-life threats (such as vote-buying and vote-cancelling),
and in that our proposed protocol combines a fair degree of efficiency
with an unusual lack of structural complexity. Furthermore, while
previous schemes have required use of an untappable channel, ours only
carries the much more practical requirement of an anonymous channel.

Authenticated ID-based Key Exchange and remote log-in with simple token and PIN number

Authenticated Key exchange algorithms tend to be either token-based
or password based. Token-based schemes are often based on expensive
(and irreplaceable) smart-card tokens, while password-only schemes
require that a unique password is shared with every correspondent.
The magnetic strip swipe card and associated PIN number is a
familiar and convenient format that motivates a combined approach.
Finally we suggest an extension of the scheme for use in a
client-server scenario.

Man-in-the-Middle in Tunnelled Authentication Protocols

Uncategorized

Uncategorized

Recently new protocols have been proposed in IETF for protecting
remote client authentication protocols by running them within a
secure tunnel. Examples of such protocols are PIC, PEAP and EAP-TTLS.
One goal of these new protocols is to enable the migration from legacy
client authentication protocols to more secure protocols, e.g., from
plain EAP type to, say, PEAP. In the new drafts, the security of
the subsequent session credentials are based only on keys derived
during the unilateral authentication where the network server is
authenticated to the client. Client authentication is mentioned as an
option in PEAP and EAP-TTLS, but is not mandated. Naturally, the PIC
protocol does not even offer this option, because the goal of PIC is
to obtain credentials that can be used for client authentication.
In addition to running the authentication protocols within such tunnel
it should also be possible to use them in legacy mode without any
tunnelling so as to leverage the legacy advantages such as widespread
use. In this paper we show that in practical situations, such a mixed
mode usage opens up the possibility to run a man-in-the-middle attack
for impersonating the legitimate client. For those well-designed
client authentication protocols that already have a sufficient level
of security, the use of tunnelling in the proposed form is a step
backwards because they introduce a new vulnerability.
The problem is due to the fact that the legacy client authentication
protocol is not aware if it is run in protected or unprotected mode.
We propose to solve the discovered problem by using a cryptographic
binding between the client authentication protocol and the protection
protocol.

On Constructing Locally Computable Extractors and Cryptosystems in the Bounded Storage Model

We consider the problem of constructing randomness extractors
which are {\em locally computable}, i.e. only read a small number
of bits from their input. As recently shown by Lu (CRYPTO `02), locally computable extractors directly yield secure private-key cryptosystems in Maurer's bounded storage model (J. Cryptology, 1992).
In this note, we observe that a fundamental lemma of Nisan and
Zuckerman (J. Computer and System Sciences, 1996) yields a general technique for constructing locally computable extractors. Specifically, we obtain a locally computable extractor by combining any extractor with any randomness-efficient (averaging) sampler. Plugging in known extractor and sampler constructions, we obtain locally computable extractors, and hence cryptosystems in the bounded storage model, whose parameters improve upon previous constructions and come quite close to the lower bounds.
Along the way, we also present a refinement of the Nisan--Zuckerman lemma, showing that random sampling bits from a weak random source preserves the min-entropy rate up to an arbitrarily small additive loss (whereas the original lemma loses a logarithmic factor).

Practical Verifiable Encryption and Decryption of Discrete Logarithms

This paper presents a variant of the new public key encryption of Cramer and Shoup based on Paillier's decision composite residuosity assumption, along with an efficient protocol for verifiable encryption of discrete logarithms. This is the first verifiable encryption system that provides chosen ciphertext security and avoids inefficient cut-and-choose proofs. This has numerous applications, including fair exchange and key escrow. We also present efficient protocols for verifiable decryption, which has applications to, e.g., confirmer signatures. The latter protocols build on a new protocol for proving whether or not two discrete logarithms are equal that is of independent interest. Prior such protocols were either inefficient or not zero-knowledge.

Cryptology and Physical Security: Rights Amplification in Master-Keyed Mechanical Locks

This paper examines mechanical lock security from the perspective of
computer science and cryptology. We focus on new and practical
attacks for amplifying rights in mechanical pin tumbler locks. Given
access to a single master-keyed lock and its associated key, a
procedure is given that allows discovery and creation of a working
master key for the system. No special skill or equipment, beyond a
small number of blank keys and a metal file, is required, and the
attacker need engage in no suspicious behavior at the lock's location.
Countermeasures are also described that may provide limited protection
under certain circumstances. We conclude with directions for research
in this area and the suggestion that mechanical locks are worthy
objects for study and scrutiny.

Related-Key and Key-Collision Attacks Against RMAC

In [JJV02] Jaulmes, Joux, and Valette propose a new randomized
message authentication scheme, called RMAC, which NIST is currently
in the process of standardizing [NIS02]. In this work we
present several attacks against RMAC. The attacks are based on a
new protocol-level related-key attack against RMAC and can be
considered variants of Biham's key-collision attack [Bih02].
These attacks provide insights into the RMAC design. We believe
that the protocol-level related-key attack is of independent
interest.

The Book of Rijndaels

This paper is the full book of the 240 dual ciphers of Rijndael,
in which only the constants differ from Rijndael. See: ``In
How Many Ways Can You Write Rijndael?'', http://eprint.iacr.org.

In How Many Ways Can You Write Rijndael?

In this paper we ask the question what happens if we replace all
the constants in Rijndael, including the replacement of the
irreducible polynomial, the coefficients of the MixColumn
operation, the affine transformation in the S box, etc. We show
that such replacements can create new dual ciphers, which
are equivalent to the original in all aspects. We present
several such dual ciphers of Rijndael, such as the square of
Rijndael, and dual ciphers with the irreducible polynomial
replaced by primitive polynomials. We also describe another family
of dual ciphers consisting of the logarithms of Rijndael. We then
discuss self-dual ciphers, and extend our results to other
ciphers.

Last updated: 2002-12-02

Validating Digital Signatures without Time-Stamping and Certificate Revocation

Uncategorized

Uncategorized

In non-repudiation services where digital signatures usually serve as
irrefutable cryptographic evidence for dispute resolution, trusted time-stamping and certificate revocation services, although very costly in practice, must be available, to prevent big loss due to compromising of the signing key. In [IR02], a new concept called intrusion-resilient signature} was proposed to get rid of trusted time-stamping and certificate revocation services and a concrete scheme was presented. In this paper, we put forward a new scheme that can achieve the same effect in a much more efficient way. In our scheme, forward-secure signature serves as a building block that enables signature validation without trusted time-stamping, and a one-way hash chain is employed to control the validity of public-key certificates without the CA's involvement for certificate revocation. We adopt a model similar to the intrusion-resilient signature in [IR02], where time is divided into predefined short periods and a user has two modules, signer and home base. The signer generates forward-secure signatures on his own while
the home base manages the validity of the signer's public-key certificate with a one-way hash chain. The signature verifier can check the validity of signatures without retrieving the certificate revocation information from the CA. Our scheme is more robust in the sense that loss of synchronization between the signer and the home base could be recovered in the next time period while it is unrecoverable in [IR02]. To facilitate the implementation of our signature validation scheme, we further present a new forward-secure signature scheme which is more efficient than all of the existing forward-secure signature schemes.

Secure Bilinear Diffie-Hellman Bits

The Weil and Tate pairings are a popular new
gadget in cryptography and have found many applications,
including identity-based cryptography.
In particular, the pairings have been used for key exchange
protocols.
This paper studies the bit security of keys obtained
using protocols based on pairings (that is,
we show that obtaining certain bits of the common key
is as hard as computing the entire key).
These results are valuable as they give insight into
how many ``hard-core'' bits can be obtained from
key exchange using pairings.

On multi-exponentiation in cryptography

We describe and analyze new combinations of multi-exponentiation
algorithms with representations of the exponents. We deal mainly but
not exclusively with the case where the inversion of group elements is fast: These methods are most attractive with exponents in the range from 80
to 256 bits, and can also be used for computing single
exponentiations in groups which admit an automorphism satisfying
a monic equation of small degree over the integers.
The choice of suitable exponent representations allows us to match or
improve the running time of the best multi-exponentiation techniques
in the aforementioned range, while keeping the memory
requirements as small as possible. Hence some of the methods
presented here are particularly attractive for deployment in
memory constrained environments such as smart cards.
By construction, such methods provide good resistance
against side channel attacks.
We also describe some applications of these algorithms.

Weighted Coordinates on Genus 2 Hyperelliptic Curves

This paper is the third in a line considering the arithmetic in the ideal class group of hyperelliptic genus two curves. The previous two papers deal with generalizations of affine and projective coordinates. Now we investigate how one can obtain inversion free formulae that are faster than projective by considering weighted coordinates. To that end we make an extensive case study to deal with different characteristic, equation of the curve, space requirement and situation of appliance.

A note on Weak Keys of PES, IDEA and some Extended Variants

This paper presents an analysis of the PES cipher in a similar setting as
done by Daemen et al. at Crypto'93 for IDEA. The following results were
obtained for 8.5 round PES: a linear weak-key class of size
$2^{48}$; two distinct differential weak-key classes of size $2^{41}$; two
differential-linear weak-key classes of size $2^{62}$. For 17-round PES
(double-PES): a linear weak-key class of size $2^7$, and a differential
weak-key class of size $2^7$ were found. Daemen suggested a modified key
schedule for IDEA in order to avoid weak keys. We found a differential
weak-key class of size $2^{83}$ for 2.5-round IDEA under his redesigned
key schedule, and differential-linear relations for 3.5-round IDEA.

Selective disclosure credential sets

We describe a credential system similar to the electronic cash system
described by Chaum, Fiat and Naor. Our system uses bit commitments to
create selective disclosure credentials which limit what portions of a
credential the holder must reveal. We show how credentials from
separate issuers can be linked to the same person in order to prevent
users from pooling credentials to obtain services no one user could
obtain alone. We also describe how to use a blinding technique
described by Laurie which may not violate the patents on blind
signatures.

Cryptanalysis of the Lee-Hwang Group-Oriented Undeniable Signature Schemes

Undeniable signature is an intriguing concept introduced by Chaum and Antwerpen at Crypto'89. In 1999, Lee and Hwang presented two group-oriented undeniable signature schemes with a trusted center. Their schemes are natural generalizations of Chaum's zero-knowledge undeniable signature scheme proposed in 1990. However, we find that the Lee-Hwang schemes are insecure. In this paper, we demonstrate five attacks on their schemes: four of them are universal forgery, in which one dishonest member (maybe collude with a verifier) can get a valid signature on any chosen massage, and another attack allows a dishonest member to prevent honest members from generating valid signatures but his cheating behavior is undetected. We also suggest heuristic improvements to overcome some of the problems involved in these attacks.

About Filliol's Observations on DES, AES and Hash Functions (draft)

Recently Filiol proposed to test cryptographic algorithms
by making statistics on the number of low degree terms in the boolean functions.
The paper has been published on eprint on 23th of July 2002.
In this paper we reproduce some of Filiol's simulations.
We did not confirm his results:
our results suggest that DES, AES, and major hash functions
have no significative bias and their output bits behave just like random boolean functions.

The EMD Mode of Operation (A Tweaked, Wide-Blocksize, Strong PRP)

We describe a block-cipher mode of operation, EMD,
that builds a strong pseudorandom permutation (PRP)
on $nm$ bits ($m\ge2$) out of
a strong PRP on $n$ bits (i.e., a block cipher).
The constructed PRP is also tweaked
(in the sense of [LRW02]):
to determine the $nm$-bit ciphertext block $C=\E_K^T(P)$
one provides, besides the key $K$ and the $nm$-bit plaintext block $P$, an $n$-bit tweak $T$.
The mode uses $2m$ block-cipher calls and
no other complex or computationally expensive steps
(such as universal hashing).
Encryption and decryption are identical except that encryption uses the
forward direction of the underlying block cipher and decryption uses the backwards
direction.
We suggest that EMD provides an attractive solution to the
disk-sector encryption problem, where one wants to encipher
the contents of an $nm$-bit disk sector in a way that
depends on the sector index and is secure against
chosen-plaintext/chosen-ciphertext attack.

Inversion-Free Arithmetic on Genus 2 Hyperelliptic Curves

We investigate formulae to double and add in the ideal class group
of a hyperelliptic genus 2 curve avoiding inversions. To that aim
we introduce a further coordinate in the representation of a class
in which we collect the common denominator of the usual 4 coordinates.
The analysis shows that this is practical and advantageous whenever
inversions are expensive compared to multiplications like for example
on smart cards.

Bauer-Berson-Feiertag attack revisited

We show that Shoup and Rubin's protocols are not secure against the BBF attack proposed by Bauer, Berson, and Feiertag, and propose an amendment. Furthermore, our results indicate that both Bellare and Rogaway's security and Paulson's security do not imply the security against the BBF attack.

Cryptanalysis of MQV with partially known nonces

In this paper we present the first lattice attack on an authenticated
key agreement protocol, which does not use a digital signature algorithm
to produce the authentication.
We present a two stage attack on MQV in which one party may recover
the other party's static private key from partial knowledge of the nonces
from several runs of the protocol.
The first stage reduces the attack to a hidden number problem which
is partially solved by considering a closest vector problem and using
Babai's algorithm.
This stage is closely related to the attack of Nguyen and Shparlinski
on DSA but is complicated by a non-uniform distribution
of multipliers.
The second stage recovers the rest of the key using the baby-step/giant-step
algorithm or Pollard's Lambda algorithm and runs in time $O(q^{1/4})$.
The attack has been proven to work with high probability and validated
experimentally.
We have thus reduced the security from $O(q^{1/2})$ down to $O(q^{1/4})$
when partial knowledge of the nonces is given.

On Some Algebraic Structures in the AES Round Function

In this paper, we show that all the coordinate functions of the
Advanced Encryption Standard (AES) round function are equivalent under an affi
ne transformation of the input to the round function. In other words, let $f_i$
and $f_j$ be any two distinct output coordinates of the AES round function, then
there exists a nonsingular matrix $A_{ji}$ over $GF(2)$ such that
$f_j(A_{ji} x) + b_{ji}= f_i(x), b_{ji} \in GF(2)$.
We also show that such linear relations will always exist if the Rijndael s-b
ox is replaced by any bijective monomial over $GF(2^8)$.
%We also show that replacing the s-box by any bijective monomial will not change
this property.

An Attack on the Isomorphisms of Polynomials Problem with One Secret

At EUROCRYPT '96 J. Patarin introduced the "Isomorphisms of
Polynomials (IP)" problem as a basis of authentication and signature
schemes. We describe an attack on the secret key of "IP with one
secret" and demonstrate its efficiency through examples with realistic
parameter sizes. To prevent our attack, additional restrictions on the
suggested parameters should be imposed.

On the Applicability of Distinguishing Attacks Against Stream Ciphers

We demonstrate that the existence of distinguishing attacks against stream ciphers is unrelated to their security in practical use, and in particular that the amount of data required to perform a distinguishing attack is unrelated to the key length of the cipher. The implication for the NESSIE Project is that no submitted symmetric cipher would be accepted under the unpublished rules for distinguishing attacks, not even the block ciphers in Counter Mode or Output Feedback Mode.

Applying General Access Structure to Proactive Secret Sharing Schemes

Verifiable secret sharing schemes (VSS) are secret sharing schemes (SSS) dealing with possible cheating by participants. In this paper we use the VSS proposed by Cramer, Damgard and Maurer \cite{CDM99,CDM00,Cra00}.
They introduced a purely linear algebraic method to transform monotone span program (MSP) based secret sharing schemes into VSS. In fact, the
monotone span program model of Karchmer and Wigderson \cite{KW93} deals with arbitrary monotone access structures and not just threshold ones. Stinson and Wei \cite{SW99} proposed a proactive SSS based on threshold (polynomial) VSS. The purpose of this paper is to build unconditionally secure proactive SSS over any access structure, as long as it admits a linear secret sharing scheme (LSSS).

Universally Composable Two-Party and Multi-Party Secure Computation

We show how to securely realize any two-party and multi-party functionality in a {\em universally composable} way, regardless of the number of corrupted participants. That is, we consider an asynchronous multi-party network with open communication and an
adversary that can adaptively corrupt as many parties as it wishes. In this setting, our protocols allow any subset of the parties (with pairs of parties being a special case) to securely realize any desired functionality of their local inputs, and be guaranteed that security is preserved regardless of the activity in the rest of the network. This implies that security is preserved under concurrent composition of an unbounded number of protocol executions, it implies non-malleability with respect to arbitrary protocols, and more. Our constructions are in the common reference string model and rely on standard intractability assumptions.

Reaction Attacks on Public Key Cryptosystems Based on the Word Problem

Wagner and Magyarik outlined a general construction for public key
cryptosystems based on the hardness of the word problem for
finitely presented groups. At the same time, they gave a specific
example of such a system. We prove that their approach is
vulnerable to so-called reaction attacks, namely, it is possible
to retrieve the private key just by watching the performance of a
legitimate recipient.

On the Security of HFE, HFEv- and Quartz

Quartz is a signature scheme based on an HFEv- trapdoor function published at Eurocrypt 1996. In this paper we study "inversion" attacks for Quartz, i.e. attacks that solve the system of multivariate equations used in Quartz. We do not cover some special attacks that forge signatures without inversion.
We are interested in methods to invert the HFEv- trapdoor function or at least to distinguish it from a random system of the same size. There are 4 types of attacks known on HFE: Shamir-Kipnis, Shamir-Kipnis-Courtois, Courtois, and attacks related to Gröbner bases such as the F5/2 attack by Jean Charles Faugère.
No attack has been published so far on HFEv- and it was believed to be more secure than HFE. In this paper we show that even modified HFE systems can be successfully attacked. It seems that the complexity of the attack increases by at least a factor of $q^{tot}$ with $tot$ being the total number of perturbations in HFE. From this and all the other known attacks we will estimate what is the complexity of the best "inversion" attack for Quartz.

Provably Secure Steganography

Informally, steganography is the process of sending a secret message from Alice to Bob in such a way that an eavesdropper (who listens to all communications) cannot even tell that a secret message is being sent. In this work, we initiate the study of steganography from a complexity-theoretic point of view. We introduce definitions based on computational indistinguishability and we prove that the existence of one-way functions implies the existence of secure steganographic protocols.
NOTE: An extended abstract of this paper appeared in CRYPTO 2002. Here we present a full version, including a correction to a small error in Construction 1.

Practical Non-Interactive Key Distribution Based on Pairings

We propose a practical non-interactive key distribution protocol based
on pairings and define a notion of security for such a scheme. We prove
the security of the system in this setting under the GDBH
assumption, and present some possible realisations using Weil or Tate
pairings on supersingular and ordinary elliptic curves.

Folklore, Practice and Theory of Robust Combiners

Uncategorized

Uncategorized

Cryptographic schemes are often designed as a combination of multiple
component cryptographic modules. Such a combiner design is {\em robust}
for a (security) specification if it meets the specification,
provided that a sufficient subset of the components meet
their specifications. A folklore combiner for encryption is {\em cascade}, i.e. $c={\cal E}''_{e''}({\cal E}'_{e'}(m))$. We show that cascade is a robust combiner for cryptosystems, under three important indistinguishability specifications: chosen plaintext attack (IND-CPA),
non-adaptive chosen ciphertext attack (IND-CCA1), and replayable chosen ciphertext attack (IND-rCCA). We also show that cascade is not robust for the important specifications adaptive CCA (IND-CCA2) and generalized CCA (IND-gCCA). The IND-rCCA and IND-gCCA specifications are closely related, and this is an interesting difference between them. All specifications are defined within.
We also analyze few other basic and folklore combiners. In particular, we show that the following are robust combiners: the {\em parallel combiner} $f(x)=f''(x)||f'(x)$ for one-way functions , the {\em XOR-Input combiner} $c=\left({\cal E}''_{e''}(m\oplus r),{\cal E}'_{e'}(r)\right)$ for cryptosystems, and the {\em copy combiner} $f_{k'',k'}(m)=f''_{k''}(m)||f'_{k'}(m)$ for integrity tasks such as Message Authentication Codes (MAC) and signature schemes. Cascade is also robust for the hiding property of commitment schemes, and the copy combiner is robust for the binding property, but neither is a robust combiner for both properties.
We present (new) robust combiners for
commitment schemes; these new combiners can be viewed as a composition of the cascade and the copy combiners. Our combiners are simple, efficient and practical.

Asynchronous Verifiable Secret Sharing and Proactive Cryptosystems

Verifiable secret sharing is an important primitive in
distributed cryptography. With the growing interest in the
deployment of threshold cryptosystems in practice, the
traditional assumption of a synchronous network has to be
reconsidered and generalized to an asynchronous model.
This paper proposes the first \emph{practical} verifiable secret
sharing protocol for asynchronous networks. The protocol creates
a discrete logarithm-based sharing and uses only a quadratic
number of messages in the number of participating servers. It
yields the first asynchronous Byzantine agreement protocol in
the standard model whose efficiency makes it suitable
for use in practice. Proactive cryptosystems are another
important application of verifiable secret sharing. The second part of this paper introduces proactive cryptosystems in
asynchronous networks and presents an efficient protocol for
refreshing the shares of a secret key for discrete
logarithm-based sharings.

Efficient Construction of (Distributed) Verifiable Random Functions

We give the first simple and efficient construction of {\em verifiable
random functions} (VRFs). VRFs, introduced by Micali et al. [MRV99],
combine the properties of regular pseudorandom functions (PRFs)
[GGM86] (i.e., indistinguishability from a random function) and
digital signatures [GMR88] (i.e., one can provide an unforgeable proof
that the VRF\ value is correctly computed). The efficiency of our VRF
construction is only slightly worse than that of a regular PRF
construction of Naor and Reingold [NR97]. In contrast to ours, the
previous VRF constructions [MRV99,Lys02] all involved an expensive
generic transformation from verifiable unpredictable functions (VUFs),
while our construction is simple and direct.
We also provide the first construction of {\em distributed} VRFs. Our
construction is more efficient than the only known construction of
distributed (non-verifiable) PRFs [Nie02], but has more applications
than the latter. For example, it can be used to distributively
implement the random oracle model in a {\em publicly verifiable}
manner, which by itself has many applications (e.g., constructing
threshold signature schemes).
Our main construction is based on a new variant of decisional
Diffie-Hellman (DDH) assumption on certain groups where the regular
DDH assumption does {\em not} hold. We do not make any claims about
the validity of our assumption (which we call {\em sum-free} DDH, or
sf-DDH). However, this assumption seems to be plausible based on our
{\em current} understanding of certain candidate elliptic and
hyper-elliptic groups which were recently proposed for use in
cryptography [JN01,Jou00]. We hope that the demonstrated power of our
sf-DDH assumption will serve as a motivation for its closer study.

Tight Lower Bound on Linear Authenticated Encryption

We show that any scheme
to encrypt m blocks of size n bits while assuring
message integrity,
that
apart from using m+k invocations of
random functions (from n bits
to n bits) and vn bits of randomness, is linear in (GF2)^n,
must have k+v at least Omega(log m).
This lower bound is proved in a very general model which rules
out many promising linear modes of operations for encryption
with message integrity.
This lower bound is
tight as linear
schemes to encrypt m blocks while
assuring message integrity by using only m+2+log m invocations
are known.
of random permutations.

An Improved Pseudorandom Generator Based on Hardness of Factoring

We present a simple to implement and efficient pseudorandom generator based on the factoring assumption. It outputs more than pn/2 pseudorandom bits per p exponentiations, each with the same base and an exponent shorter than n/2 bits. Our generator is based on results by Hastad, Schrift and Shamir [HSS93], but unlike their generator and its improvement by Goldreich and Rosen [GR00], it does not use hashing or extractors, and is thus simpler and somewhat more efficient.
In addition, we present a general technique that can be used to speed up pseudorandom generators based on iterating one-way permutations. We construct our generator by applying this technique to results of [HSS93]. We also show how the generator given by Gennaro [Gen00] can be simply derived from results of Patel and Sundaram [PS98] using our technique.

OAEP++ : A Very Simple Way to Apply OAEP to Deterministic OW-CPA Primitives

We prove in the random oracle model that OAEP++,
which was proposed by us at the rump session of Asiacrypt
2000, can generate IND-CCA2 ciphers
using deterministic
OW-CPA cryptographic primitives.
Note that
OAEP++ differs from OAEP$^{++}$ proposed by
Jonsson in \cite{Jon02}.
While OAEP$^{++}$
requires a non-malleable block cipher,
OAEP++ does not require
such additional functions.
The security reduction of OAEP++ is as tight as that of
OAEP$^{++}$.

Key-collisions in (EC)DSA: Attacking Non-repudiation

Uncategorized

Uncategorized

A new kind of attack on the non-repudiation property of digital signature schemes is presented. We introduce a notion of key-collisions, which may allow an attacker to claim that the message (presented to a judge) has been signed by someone else. We show how to compute key-collisions for the DSA and ECDSA signature schemes effectively. The main idea of these attacks has been inspired by the well-known notion of message-collisions, where an attacker claims that the signature presented at the court belongs to a different message. Both of these collision-based attacks significantly weaken the non-repudiation property of signature schemes. Moreover, they weaken the non-repudiation of protocols based on these schemes. It is shown that key-collision resistance of the (EC)DSA schemes requires the incorporation of a mechanism ensuring honest generation of (EC)DSA instances. The usage of such a mechanism shall be verifiable by an independent third party without revealing any secret information. We propose and discuss basic general countermeasures against key-collision attacks on the (EC)DSA schemes.

Perfectly Secure Message Transmission Revisited

Achieving secure communications in networks has been one
of the most important problems in information technology.
Dolev, Dwork, Waarts, and Yung have studied secure
message transmission in one-way or two-way channels.
They only consider the case when all channels are two-way or
all channels are one-way. Goldreich, Goldwasser, and Linial,
Franklin and Yung, Franklin and Wright, and Wang and
Desmedt have studied secure communication and
secure computation in multi-recipient (multicast)
models. In a ``multicast channel'' (such as Ethernet), one processor
can send the same message---simultaneously and privately---to
a fixed subset of processors. In this paper, we shall
study necessary and sufficient conditions for achieving
secure communications against active adversaries in mixed
one-way and two-way channels. We also discuss
multicast channels and neighbor network channels.

Power of a Public Random Permutation and its Application to Authenticated-Encryption

In this paper,
we first show that many independent pseudorandom permutations
over $\{0,1\}^n$
can be obtained
from a single public random permutation
and secret $n$ bits.
We next prove that a slightly modified IAPM is secure even if
the underlying block cipher $F$
is publicly accessible (as a blackbox).
We derive a similar result for OCB mode, too.
We finally prove that
our security bound is tight within a constant factor.

Assumptions Related to Discrete Logarithms: Why Subtleties Make a Real Difference

The security of many cryptographic constructions relies on
assumptions related to Discrete Logarithms (DL), e.g., the
Diffie-Hellman, Square Exponent, Inverse Exponent or Representation
Problem assumptions. In the concrete formalizations of these
assumptions one has some degrees of freedom offered by parameters such
as computational model, problem type (computational, decisional) or
success probability of adversary. However, these parameters and their
impact are often not properly considered or are simply overlooked in
the existing literature.
In this paper we identify parameters relevant to cryptographic
applications and describe a formal framework for defining DL-related
assumptions. This enables us to precisely and systematically classify
these assumptions.
In particular, we identify a parameter, termed granularity, which
describes the underlying probability space in an assumption. Varying
granularity we discover the following surprising result: We prove that
two DL-related assumptions can be reduced to each other for medium
granularity but we also show that they are provably not reducible with
generic algorithms for high granularity. Further we show that
reductions for medium granularity can achieve much better concrete
security than equivalent high-granularity reductions.

The Jacobi Model of an Elliptic Curve and Side-Channel Analysis

A way for preventing SPA-like attacks on elliptic curve systems is to
use the same formula for the doubling and the general addition of
points on the curve. Various proposals have been made in this
direction with different results. This paper re-investigates the
Jacobi form suggested by Liardet and Smart (CHES 2001). Rather than
considering the Jacobi form as the intersection of two quadrics, the
addition law is directly derived from the underlying quartic. As a
result, this leads to substantial memory savings and produces the
fastest unified addition formula for curves of order a multiple of 2.

On Optimal Hash Tree Traversal for Interval Time-Stamping

Skewed trees constitute a two-parameter family of recursively constructed trees. Recently, Willemson proved that suitably picked skewed trees are space-optimal for interval time-stamping. At the same time, Willemson proposed a practical but suboptimal algorithm for nonrecursive traversal of skewed trees. We describe an alternative, extremely efficient traversal algorithm for skewed trees. The new algorithm is surprisingly simple and arguably close to optimal in every imaginable sense. We provide a detailed analysis of the average-case storage (and communication) complexity of our algorithm, by using the Laplace's method for estimating the asymptotic behavior of integrals. Since the skewed trees can be seen as a natural generalization of Fibonacci trees, our results might also be interesting in other fields of computer science.

New covering radius of Reed-Muller codes for $t$-resilient functions

From a view point of cryptography,
we define a new covering radius
of Reed-Muller codes as the maximum distance between
$t$-{\it resilient} functions
and the $r$-th order Reed-Muller code $RM(r,n)$.
We next derive its lower and upper bounds.
We also present a table of numerical data
of our bounds.

ID-Based One Round Authenticated Tripartite Key Agreement Protocol with Pairings

With positive applications of Weil pairing (Tate pairing) to
cryptography, ID-based encryption schemes, digital signature
schemes, blind signature scheme, two-party authenticated key
agreement schemes, and tripartite key agreement scheme were
proposed recently, all of them using bilinear pairing (Weil or
Tate pairing). In this paper, we propose an ID-based one round
authenticated tripartite key agreement protocol. The authenticity
of the protocol is assured by a special signature scheme, so that
messages carrying the information of two ephemeral keys can be
broadcasted authentically by an entity. Consequently, one instance
of our protocol results in eight session keys for the three
entities. Security attributes of our protocol are presented,
and the computational overhead and bandwidth of the broadcast messages are analyzed as well.

Efficient Arithmetic on Genus 2 Hyperelliptic Curves over Finite Fields via Explicit Formulae

We extend the explicit formulae for arithmetic on genus two curves of Takahashi and Miyamoto,Doi,Matsuo,Chao,and Tsuji to fields of even characteristic and to arbitrary equation of the curve and slightly improve them. These formulae can be evaluated faster than the more general Cantor algorithm and allow to obtain faster arithmetic on a hyperelliptic genus 2 curve than on elliptic curves. We give timings for implementations using various libraries for the field arithmetic.

Security Analysis of IKE's Signature-based Key-Exchange Protocol

We present a security analysis of the Diffie-Hellman
key-exchange protocols authenticated with digital signatures
used by the Internet Key Exchange (IKE) standard, and of the more
comprehensive SIGMA family of key exchange protocols.
The analysis is based on an adaptation of the key-exchange security
model from [Canetti and Krawczyk, Eurocrypt'01] to the setting
where peer identities are not necessarily known or disclosed
from the start of the protocol. This is a common practical setting,
which includes the case of IKE and other protocols that provide
confidentiality of identities over the network. The rigorous study
of this ``post-specified peer" model is a further contribution of
this paper.

Provably Secure Public-Key Encryption for Length-Preserving Chaumian Mixes

Mix chains as proposed by Chaum allow sending untraceable electronic
e-mail without requiring trust in a single authority: messages are
recursively public-key encrypted to multiple intermediates (mixes),
each of which forwards the message after removing one layer of
encryption. To conceal as much information as possible when using
variable (source routed) chains, all messages passed to mixes should
be of the same length; thus, message length should not decrease when
a mix transforms an input message into the corresponding output
message directed at the next mix in the chain. Chaum described an
implementation for such length-preserving mixes, but it is not secure
against active attacks. We show how to build practical
cryptographically secure length-preserving mixes. The conventional
definition of security against chosen ciphertext attacks is not
applicable to length-preserving mixes; we give an appropriate
definition and show that our construction achieves provable security.

Efficient threshold signature, multisignature and blind signature schemes based on the Gap-Diffie-Hellman-group signature scheme

We propose a robust proactive threshold signature scheme, a multisignature scheme and a blind signature scheme which work in any Gap Diffie-Hellman (GDH) group (where the Computational Diffie-Hellman problem is hard but the Decisional Diffie-Hellman problem is easy). Our constructions are based on the recently
proposed GDH signature scheme of Boneh et al. \cite{bls}. Due to the instrumental structure of GDH groups and of the base scheme, it turns out that most of our constructions are simpler, more efficient and have more useful
properties than similar
existing constructions. We support all the proposed schemes with proofs under the appropriate computational assumptions, using the corresponding notions of security.

Diffie-Hellman Problems and Bilinear Maps

We investigate relations among the discrete logarithm (DL)
problem, the Diffie-Hellman (DH) problem and the bilinear
Diffie-Hellman (BDH) problem when we have an efficient computable
non-degenerate bilinear map $e:G\times G \rightarrow H$. Under a
certain assumption on the order of $G$, we show that the DH
problem on $H$ implies the DH problem on $G$, and both of them are
equivalent to the BDH problem when $e$ is {\it weak-invertible}.
Moreover, we show that given the bilinear map $e$ an injective
homomorphism $f:H\rightarrow G$ enables us to solve the DH problem
on $G$ efficiently, which implies the non-existence a {\it
self-bilinear} map $e:G\times G \rightarrow G$ when the DH problem
on $G$ is hard. Finally we introduce a sequence of bilinear maps
and its applications.

How to convert any ID-based Signature Schemes

This paper describes how any Identity Based Signature schemes
can be used to implement a Group Signature scheme.
The performance of the generated Group Signature scheme is similar to
the performance of the underlying ID-based Signature scheme.
This makes our proposal very attractive since
most of existing group signature schemes that have been proposed so far
are grossly inefficient. In contrast, ID-based signature schemes can be
very efficient especially if they use elliptic curves and pairing.

Universal Padding Schemes for RSA

A common practice to encrypt with RSA is to first apply a padding scheme to the message and then to exponentiate the result with the public exponent; an example of this is OAEP. Similarly, the usual way of signing with RSA is to apply some padding scheme and then to exponentiate the result with the private exponent, as for example in PSS. Usually, the RSA modulus used for encrypting is different from the one used for signing. The goal of this paper is to simplify this common setting. First, we show that PSS can also be used for encryption, and gives an encryption scheme semantically secure against adaptive chosen-ciphertext attacks, in the random oracle model. As a result, PSS can be used indifferently for encryption or signature. Moreover, we show that PSS allows to safely use the same RSA key-pairs for both encryption and signature, in a concurrent manner. More generally, we show that using PSS the same set of keys can be used for both encryption and signature for any trapdoor partial-domain one-way permutation. The practical consequences of our result are important: PKIs and public-key implementations can be significantly simplified.

Point Multiplication on Ordinary Elliptic Curves over Fields of Characteristic Three

In this paper we investigate the efficiency of cryptosystems based on
ordinary elliptic curves over fields of characteristic three.
We look at different representations for curves and consider some of
the algorithms necessary to perform efficient point multiplication.
We give example timings for our operations and compare them with
timings for curves in characteristic two of a similar level of security.
We show that using the Hessian form in characteristic three
produces a point multiplication algorithm under $50$ percent slower
than the equivalent system in characteristic two.
Thus it is conceivable that curves in characteristic three, could
offer greater performance than currently perceived by the community.

A Note on the Bilinear Diffie-Hellman Assumption

Uncategorized

Uncategorized

Abstract. The Bi-linear Diffie-Hellman (BDH) intractability assumption is required to establish the security of new Weil-pairing based cryptosystems. BDH is reducible to most of the older believed-to-be-hard discrete-log problems and DH problems, but there is no known reduction from any of those problems to BDH. Let the bilinear mapping be e:G1 X G1->G2, where G1 and G2 are cyclic groups. We show that a many-one reduction from any of the relevant problems to BDH has to include an efficient mapping \phi:G2 ->G1 where \phi(g^{x})=f(x)P. Here g, and P are generators of the corresponding cyclic groups. The function \phi must be used in the reduction either before or after the call to oracle BDH. We show that if f(x)=ax^n+b for any constants a,b,n, then \phi could be used as an oracle for a probabilistic polynomial time solution for Decision Diffie-Hellman in G2. Thus such a reduction is unlikely.

An Efficient Procedure to Double and Add Points on an Elliptic Curve

We present an algorithm that speeds exponentiation on a
general elliptic curve by an estimated 3.8% to 8.5% over the best
known general exponentiation methods when using affine coordinates.
This is achieved by eliminating a field multiplication when we compute 2P + Q from given points P, Q on the curve. We give
applications to simultaneous multiple exponentiation and to the
Elliptic Curve Method of factorization. We show how this
improvement together with another idea can speed the
computation of the Weil and Tate pairings by up to 7.8%.

On Linear Redundancy in the AES S-Box

Uncategorized

Uncategorized

We show the existence of a previously unknown linear redundancy
property of the only nonlinear component of the AES block cipher.
It is demonstrated that the outputs of the 8*8 Rijndael s-box
(based on inversion in a finite field) are all equivalent under
affine transformation. The method used to discover these affine
relations is novel and exploits a new fundamental result on the
invariance properties of local connection structure of affine
equivalence classes. As well as increasing existing concerns about
the security of the AES, these results may also have serious
consequences for many other ciphers recently proposed for
standardisation.

The GGM Construction does NOT yield Correlation Intractable Function Ensembles

We consider the function ensembles emerging from the
construction of Goldreich, Goldwasser and Micali (GGM),
when applied to an arbitrary pseudoramdon generator.
We show that, in general, such functions
fail to yield correlation intractable ensembles.
Specifically, it may happen that, given a description of such a function,
one can easily find an input that is mapped to zero under this function.

A New Class of Unsafe Primes

In this paper,
a new special-purpose factorization algorithm is presented,
which finds a prime factor $p$ of an integer $n $
in polynomial time, if $4p-1$ has the form
$d b^2$ where $d \in \{3, 11, 19, 43, 67, 163\}$
and $b$ is an integer.
Hence such primes should be avoided when we select the
RSA secret keys. Some generalizations of the algorithm are
discussed in the paper as well.

Last updated: 2003-02-05

Clock-Controlled Alternating Step Generator

A new construction of a pseudorandom generator based on a simple combination of three feedback shift registers (FSRs) is introduced. The main characteristic of its structure is that the output of one of the three FSRs controls the clocking of the other two FSRs.
This construction allows users to generate a large family of sequences using the same initial states and the same feedback functions of the three combined FSRs. The construction is related to the Alternating Step Generator that is a special case of this construction.
The period, and the lower and upper bound of the linear complexity of the output sequences of the construction whose control FSR generates a de Bruijn sequence and the other two FSRs generate m-sequences are established. Furthermore, it is established that the distribution of short patterns in these output sequences occur equally likely and that they are secure against correlation attacks. All these properties make it a suitable crypto-generator for stream cipher applications.

Efficient Arithmetic on Hyperelliptic Curves

Using the Frobenius endomorphism the operation of computing
scalar-mulitples in the Jacobian of a hyperelliptic curve is sped-up
considerably. The kind of curves considered are Kobiltz i.e. subfield
curves, defined over a small finite field which are then considered
over a large extension field. We deal with computation of
the group order over various extension fields, algorithms to obtain
the mentioned speed-up, and experimental results concerning both
issues. Additionally an alternative set-up is treated which uses arihtmetic in the finite field only and allows shorter code for similar security.
Furthermore explicit formulae to perform the arithmetic in the ideal class group explicitely are derived and can thus be used for implementation in hardware; in software they are also faster than the generic Cantor algorithm. As a second group suitable for cryptographic applications the trace-zero-variety is considered. Here we investigate the group operation and deal with security issues.

Secret sharing schemes on access structures with intersection number equal to one

The characterization of ideal access structures and
the search for bounds on the optimal information rate
are two important problems in secret sharing.
These problems are studied in this paper for access structures
with intersection number equal to one, that is, access structures
such that there is at most one participant in the intersection
of any two different minimal qualified subsets.
The main result in this work is the complete characterization
of the ideal access structures with intersection number equal to one.
Besides, bounds on the optimal information rate
are provided for the non-ideal case.

An Extension of Kedlaya's Algorithm to Hyperelliptic Curves in Characteristic 2

We present an algorithm for computing the zeta function of an arbitrary hyperelliptic curve
over a finite field $\FF_q$ of characteristic 2, thereby extending the algorithm of Kedlaya
for odd characteristic.
For a genus $g$ hyperelliptic curve defined over $\FF_{2^n}$,
the average-case time complexity is $O(g^{4 + \varepsilon} n^{3 + \varepsilon})$
and the average-case space complexity is $O(g^{3} n^{3})$, whereas the worst-case time and space
complexities are $O(g^{5 + \varepsilon} n^{3 + \varepsilon})$ and $O(g^{4} n^{3})$ respectively.

Forward-Secure Signatures with Fast Key Update

In regular digital signatures, once the secret key is compromised, all signatures, even those that were issued by the honest signer before the compromise, will not be trustworthy any more. Forward-secure signatures have been proposed to address this major shortcoming.
We present a new forward-secure signature scheme, called KREUS, with several advantages. It has the most efficient Key Update of all known schemes, requiring just a single modular squaring. Our scheme thus enables more frequent Key Update and hence allows shorter time periods, enhancing security: fewer signatures might become invalid as a result of key compromise. In addition, the on-line component of signing is also very efficient, consisting of a single multiplication. We precisely analyze the total signer costs and show that they are lower when the number of signatures per time period is small; the advantage of our scheme increases considerably as the number of time periods grows.
Our scheme's security relies on the Strong-RSA assumption and the random-oracle-based Fiat-Shamir transform.

On the Power of Claw-Free Permutations

Probabilistic Signature Scheme (PSS), Full Domain Hash (FDH) and
several of their variants are widely used signature schemes, which can
be formally analyzed in the random oracle model. These schemes output
a signature of the form (f^{-1}(y),pub), where y somehow depends
on the message signed (and pub) and f is some public trapdoor
permutation (typically RSA). Interestingly, all these signature
schemes can be proven {\em asymptotically} secure for an {\em
arbitrary} trapdoor permutation f, but their {\em exact} security
seems to be significantly better for {\em special} trapdoor
permutations like RSA. This leads to two natural questions:
(1) can the asymptotic security analysis be improved with general
trapdoor permutations?; and, if not, (2) what {\em general
cryptographic assumption} on f --- enjoyed by specific functions
like RSA --- is ``responsible'' for the improved security?
We answer both these questions. First, we show that if f is a
``black-box'' trapdoor permutation, then the poor exact security is
unavoidable. More specifically, the ``security loss'' for general
trapdoor permutations is \Omega(q_hash), where q_hash is the
number of random oracle queries made by the adversary (which could be
quite large). On the other hand, we show that all the security
benefits of the RSA-based variants come into effect once f comes
from a family of {\em claw-free permutation} pairs. Our results
significantly narrow the current ``gap'' between general trapdoor
permutations and RSA to the ``gap'' between trapdoor permutations and
claw-free permutations. Additionally, they can be viewed as the first
{\em security/efficiency} separation between these basic cryptographic
primitives. In other words, while it was already believed that certain
cryptographic objects {\em can} be build from claw-free permutations
but {\em not} from general trapdoor permutations, we show that certain
important schemes (like FDH and PSS) provably work with {\em either},
but enjoy a much better tradeoff between security and efficiency when
deployed with claw-free permutations.

Applying General Access Structure to Metering Schemes

Uncategorized

Uncategorized

In order to decide on advertisement fees for web servers, Naor and Pinkas introduced metering schemes secure against coalition of corrupt servers and clients. In their schemes any server is able to construct a proof to be sent to an audit agency if and only if it has been
visited by at least a certain number of clients. Several researchers have generalized the idea of Naor and Pinkas: first metering scheme with pricing and dynamic multi-threshold metering schemes have been proposed; later the solution has been extended to allow for
general access structures and an approach on linear algebra has been introduced. In this paper we are interested in the efficiency of applying general access structures and linear algebra techniques to metering schemes. We propose a new model considering general access structures for clients, corrupted clients and servers. Then we bind the
access structures for clients and corrupted clients into one. We propose a new metering scheme, which is more efficient w.r.t.\ communication complexity and memory requirements than the scheme of Blundo \textit{et al.}

An Upper Bound on the Size of a Code with the $k$-Identifiable Parent Property

Uncategorized

Uncategorized

The paper gives an upper bound on the size of a $q$-ary code of length
$n$ that has the $k$-identifiable parent property. One consequence of
this bound is that the optimal rate of such a code is determined in
many cases when $q\rightarrow\infty$ with $k$ and $n$ fixed.

Encryption-Scheme Security in the Presence of Key-Dependent Messages

Encryption that is only semantically secure should not be used on messages that depend on the underlying secret key; all bets are off when, for example,one encrypts using a shared key K the value K.
Here we introduce a new notion of security, KDM security, appropriate for key-dependent messages. The notion makes sense in both the public-key and shared-key settings. For the latter we show that KDM security is easily achievable within the random-oracle model.
By developing and achieving stronger notions of encryption-scheme security it is hoped that protocols which are proven secure under ``formal'' models of security can, in time, be safely realized by generically instantiating their primitives.

A New Statistical Testing for Symmetric Ciphers and Hash Functions

This paper presents a new, powerful statistical testing of symmetric
ciphers and hash functions which allowed us to detect biases in both
of these systems where previously known tests failed. We first give a
complete characterization of the Algebraic Normal Form (ANF) of
random Boolean functions by means of the Möbius transform. Then we
built a new testing based on the comparison between the structure of
the different Boolean functions Algebraic Normal Forms characterizing
symmetric ciphers and hash functions and those of purely random
Boolean functions. Detailed testing results on several cryptosystems
are presented. As a main result we show that AES, DES Snow and
Lili-128 fail all or part of the tests and thus present strong biases.

Identity-Based Signcryption

Uncategorized

Uncategorized

A signcryption scheme is a scheme that provides private and authenticated delivery of messages between two parties.
It does this in a more efficient manner than a straightforward composition of an encryption scheme with a signature scheme.
An identity-based cryptosystem is one in which the public key may be any string (or may be derived from any string).
In this paper we propose an identity-based signcryption scheme.
We give a security model for such a scheme and sketch the details of how our scheme may be proved secure in this model.

Last updated: 2003-08-11

A new public key encryption scheme provably secure against adaptive chosen cipher-text attack

Uncategorized

Uncategorized

We present a new public key cryptosystem based on
the notion called square decisional Diffie-Hellman problem. The
scheme is provably secure against adaptive chosen cipher-text
attack under the hardness assumption of the square decisional
Diffie-Hellman problem. Compared with Cramer and Shoup's notable
public key scheme, our scheme enjoys several nice features:
(1)Both schemes are provably secure against adaptive chosen
cipher-text attack under the intractability paradigm (the security
of Cramer-Shoup's scheme is based on the standard decisional
Diffie-Hellman problem while ours based on the square decisional
Diffie-Hellman problem; (2)The computational and communication
complexity of our scheme is equivalent to the Cramer and Shoup's
scheme however, the test function of Cramer-shoup's scheme is
linear while our scheme is non-linear, therefore our reduction is
more efficient.

Generating Large Non-Singular Matrices over an Arbitrary Field with Blocks of Full Rank

This note describes a technique for generating
large non-singular matrices with blocks of full rank.
While this may be of independent interest, our motivation
arises in the white-box implementation of cryptographic algorithms with S-boxes.