## All papers (Page 188 of 19185 results)

Cryptographic Randomized Response Techniques

Uncategorized

Uncategorized

We develop cryptographically secure techniques to guarantee unconditional privacy for respondents to polls. Our constructions are efficient and practical, and are shown not to allow cheating respondents to affect the ``tally'' by more than their own vote --- which will be given the exact same weight as that of other respondents. We demonstrate solutions to this problem based on both traditional cryptographic techniques and quantum cryptography.

Hyperelliptic Curve Cryptosystems: Closing the Performance Gap to Elliptic Curves (Update)

For most of the time since they were proposed, it was widely
believed that hyperelliptic curve cryptosystems (HECC) carry a
substantial performance penalty compared to elliptic curve
cryptosystems (ECC) and are, thus, not too attractive for
practical applications. Only quite recently improvements have been
made, mainly restricted to curves of genus 2. The work at hand
advances the state-of-the-art considerably in several aspects.
First, we generalize and improve the closed formulae for the group
operation of genus 3 for HEC defined over fields of characteristic
two. For certain curves we achieve over 50% complexity improvement
compared to the best previously published results. Second, we
introduce a new complexity metric for ECC and HECC defined over
characteristic two fields which allow performance comparisons of
practical relevance. It can be shown that the HECC performance is
in the range of the performance of an ECC; for specific
parameters HECC can even possess a lower complexity than an ECC at
the same security level. Third, we describe the first
implementation of a HEC cryptosystem on an embedded (ARM7)
processor. Since HEC are particularly attractive for constrained
environments, such a case study should be of relevance.

Homomorphic public-key cryptosystems and encrypting boolean circuits

Homomorphic cryptosystems are designed for the first time over any
finite group. Applying Barrington's construction we produce for any
boolean circuit of the logarithmic depth its encrypted simulation of
a polynomial size over an appropriate finitely generated group.

On Modeling IND-CCA Security in Cryptographic Protocols

Two common notions of security for public key encryption schemes are shown to be equivalent: we prove that indistinguishability against chosen-ciphertext attacks (IND-CCA) is in fact polynomially equivalent to (yet "slightly" weaker than) securely realizing the ideal functionality F_PKE in the general modeling of cryptographic protocols of [http://eprint.iacr.org/2000/067]. This disproves in particular the claim that security in the sense of IND-CCA strictly implies security in the sense of realizing F_PKE (see [http://eprint.iacr.org/2000/067]). Moreover, we give concrete reductions among such security notions and show that these relations hold for both uniform and non-uniform adversarial entities.

New identity based signcryption schemes from pairings

We present a new identity based scheme based on pairings
over elliptic curves. It combines the functionalities of
signature and encryption and is provably secure in the random
oracle model. We compare it with Malone-Lee's one from security
and efficiency points of view. We give a formal proof of
semantical security under the Decisional Bilinear Diffie-Hellman
assumption for this new scheme and we show how to devise other
provably secure schemes that produce even shorter ciphertexts.

Did Filiol Break AES ?

On January 8th 2003, Eric Filiol published on the eprint a paper (eprint.iacr.org/2003/003/) in which he claims that AES can be broken by a very simple and very fast ciphertext-only attack. If such an attack existed, it would be the biggest discovery in code-breaking since some 10 or more years.
Unfortunately the result is very hard to believe.
In this paper we present the results of computer simulations done by
several independent people, with independently written code.
Nobody has confirmed a single anomaly in AES,
even for much weaker versions of the bias claimed by the author.
We also studied the source code provided by the author to realize that the first version had various issues and bugs, and the latest version still does not confirm the claimed result on AES.

Interleaving Cryptography and Mechanism Design: The Case of Online Auctions

Uncategorized

Uncategorized

We propose a new cryptographically protected multi-round auction mechanism for online auctions. This auction mechanism is designed to provide (in this order) security, cognitive convenience, and round-effectiveness. One can vary internal parameters of the mechanism to trade off bid privacy and cognitive costs, or cognitive costs and the number of rounds. We are aware of no previous work that interleaves cryptography explicitly with the mechanism design.

Attacks based on Conditional Correlations against the Nonlinear Filter Generator

In this paper we extend the conditional correlation attack ([LCPP96])
against the nonlinear filter generator (NLFG) by introducing
new conditions and generalisations and present two known-plaintext attacks, called hybrid correlation attack and concentration attack.
The NLFG is a well known LFSR-based keystream generator which could be used as a basic building block in a synchronous stream cipher system.
Both new attacks use methods from the conditional correlation attack and additional
from fast correlation attacks to derive the unknown initial
state of the LFSR of the NLFG.
The basic principle of iteratively cumulating and updating conditional
correlations for the NLFG was proposed in [Loh01]
and for general combiners with memory in [GBM02].
With the hybrid correlation attack it is possible to successfully attack the NLFG
by applying a fast correlation attack, even if
the filter function $f$ of the NLFG is highly nonlinear, e.g. the normalised
nonlinearity $p_{e,f}$ is $\ge 0.45$.
The concentration attack
maps all computed conditional correlations to $D-B$ unknown LFSR bits,
where $D \ge k$ and $1 \le B \le k$ are parameters which can be chosen
by the attacker, and $k$ is the length of the LFSR of the NLFG.
Even with low values of conditional correlations, it is possible to
mount the hybrid correlation attack and the concentration attack successfully.
This is not the case for the originally version of the conditional correlation attack ([LCPP96])
in a time lower than a full search over all possible initial states.

A Polynomial Time Algorithm for the Braid Diffie-Hellman Conjugacy Problem

We propose the first polynomial time algorithm for the braid Diffie-Hellman conjugacy problem (DHCP) on which the braid key exchange scheme and the braid encryption scheme are based~\cite{KLCHKP01}. We show the proposed method solves the DHCP for the image of braids under the Lawrence-Krammer representation and the solutions play the equivalent role of the original key for the DHCP of braids. Given a braid index $n$ and a canonical length $\ell$, the complexity
is about $2^{-2}\ell^3 n^{4\tau+2}\log n$ bit operations, where
$\tau=\log_27\approx 2.8$ (Theoretically, it can be reduced to $O(\ell^3 n^{8.3}\log n)$ using $\tau=2.376$). Further, we show that the generalization into the decomposition problem causes only 8 times of the complexity.

An Authenticated Group Key Agreement Protocol on Braid groups

In this paper, we extend the 2-party key exchange protocol on braid groups to the group key agreement protocol based on the hardness of Ko-Lee problem. We also provide authenticity to the group key agreement protocol.

Perfect Hash Families with Few Functions

Uncategorized

Uncategorized

An {\em $(s;n,q,t)$-perfect hash family} is a set of functions
$\phi_1,\phi_2,\ldots ,\phi_s$ from a set $V$ of cardinality $n$ to a
set $F$ of cardinality $q$ with the property that every $t$-subset of
$V$ is injectively mapped into $F$ by at least one of the functions
$\phi_i$.
The paper shows that the maximum value $n_{s,t}(q)$ that $n$ can take
for fixed $s$ and $t$ has a leading term that is linear in $q$ if and only if
$t>s$. Moreover, for any $s$ and $t$ such that $t>s$, the paper shows how to
calculate the coefficient of this linear leading term; this
coefficient is explicitly calculated in some cases. As part of this
process, new classes of good perfect hash families are constructed.

A Threshold GQ Signature Scheme

We proposed the first threshold GQ signature scheme. The scheme is unforgeable and robust against any adaptive adversary if the base GQ signature scheme is unforgeable under the chosen message attack and computing the discrete logarithm modulo a safe prime is hard. Our scheme achieve optimal resilience, that is, the adversary can corrupt up to a half of the players. As an extension of our work, we proposed a threshold forward-secure signature scheme, which is the threshold version of the most efficient forward-secure signature scheme up to now.

A Universally Composable Cryptographic Library

Bridging the gap between formal methods and cryptography has recently received a lot of interest, i.e., investigating to what extent proofs of cryptographic protocols made with abstracted cryptographic operations are valid for real implementations. However, a major goal has not been achieved yet: a soundness proof for an abstract crypto-library as needed for the cryptographic protocols typically proved with formal methods, e.g., authentication and key exchange protocols. Prior work that directly justifies the typical Dolev-Yao abstraction is restricted to passive adversaries and certain protocol environments. Prior work starting from the cryptographic side entirely hides the cryptographic objects, so that the operations are not composable: While secure channels or signing of application data is modeled, one cannot encrypt a signature or sign a key.
We make the major step towards this goal: We specify an abstract crypto-library that allows composed operations, define a cryptographic realization, and prove that the abstraction is sound for arbitrary active attacks in arbitrary reactive scenarios. The library currently contains public-key encryption and signatures, nonces, lists, and application data.
The proof is a novel combination of a probabilistic, imperfect bisimulation with cryptographic reductions and static information-flow analysis.

Hiji-bij-bij: A New Stream Cipher with a Self-Synchronizing Mode of Operation

In this paper, we present a new stream cipher called Hiji-bij-bij
(HBB). The basic design principle of HBB is to mix a linear and a
nonlinear map. Our innovation is in the design of the linear and the
nonlinear maps. The linear map is realised using two 256-bit maximal
period 90/150 cellular automata. The nonlinear map is simple and
consists of several alternating linear and nonlinear layers. We prove
that the mixing achieved by the nonlinear map is complete and the
maximum bias in any non-zero linear combination of the input and
output bits of the nonlinear map is at most $2^{-13}$. We also
identify a self-synchronizing mode ({\bf SS}) of operation for HBB.
The performance of HBB is reasonably good in software and is expected
to be very fast in hardware. To the best of our knowledge, a generic
exhaustive search seems to be the only method of attacking the cipher.

Security Constraints on the Oswald-Aigner Exponentiation Algorithm

In smartcard encryption and signature applications, randomized algorithms can be used to increase tamper resistance against attacks based on averaging data-dependent power or EMR variations. Recently, Oswald and Aigner described such an algorithm suitable for point multiplication in elliptic curve cryptography (ECC). With the assumption that an attacker can identify additions and doublings and distinguish them from each other during a single point multiplication, it is shown that the algorithm is insecure for repeated use of the same secret key without blinding of that key.
This scotches hopes that the expense of such blinding might be avoided
by using the algorithm unless the differences between point additions and doublings can be obscured successfully.

The number of initial states of the RC4 cipher with the same cycle structure

Uncategorized

Uncategorized

RC4 cipher is the most widely used stream cipher in software applications. It was designed by R. Rivest in 1987. In this paper we find the number of keys of the RC4 cipher generating initial permutations with the same cycle structure. We obtain that the distribution of initial permutations is not uniform.

Cryptanalysis of Lee-Hwang-Li's Key Authentication Scheme

Uncategorized

Uncategorized

Key authentication is very important in secret communications and
data security. Recently, Lee, Hwang and Li proposed a new public
key authentication scheme for cryptosystems with a trusty server.
However, in this paper, we will show that Lee-Hwang-Li's key
authentication scheme is not secure, from the obtained public
information, any one can get the private key of the user. And
then, we propose an improved scheme. We conclude that our new key
authentication scheme not only resolves the problems appeared but
also is secure.

Differential Fault Analysis on A.E.S.

We explain how a differential fault analysis (DFA) works on AES 128, 192 or 256 bits.

Domain Extenders for UOWHF: A Finite Binary Tree Algorithm

Uncategorized

Uncategorized

We obtain a {\em finite} binary tree algorithm to extend the domain of a UOWHF.
The associated key length expansion is only a constant number of bits more than
the minimum possible. Our finite binary tree algorithm is a practical
parallel algorithm to securely extend the domain of a UOWHF. Also the speed-up
obtained by our algorithm is approximately proportional to the number of processors.

DFA on AES

Uncategorized

Uncategorized

In this paper we describe two different DFA attacks on the AES. The first one uses a fault model that induces a fault on only one bit of an intermediate result, hence allowing us to obtain the key by using 50 faulty ciphertexts for an AES-128. The second attack uses a more realistic fault model: we assume that we may induce a fault on a whole byte. For an AES-128, this second attack provides the key by using less than 250 faulty ciphertexts. Moreover, this attack has been successfully put into practice on a smart card.

Last updated: 2003-08-11

A Price Negotiable Transaction System

We present a practical protocol that allows two players to negotiate price over the Internet in a deniable way so
that a player $A$ can prevent another player $B$ from showing this offer $P$ to a third party $C$ in order to
elicit a better offer while player $B$ should be sure that this offer $P$ generated by $A$, but should $C$ be
unclear whether $P$ is generated by $A$ or $B$ itself, even $C$ and $B$ fully cooperated. Our protocol is a
standard browser-server model and uses a trusted third party, but only in a very limited fashion: the trusted
third party is only needed in the cases where one player attempts to cheat or simply crashes, therefore, in the
vast of majority transactions, the third party is not to be involved at all. In addition, Our price negotiable
transaction system enjoys the following properties:
\begin{description}
\item[(1)]It works in an asynchronous communication model.
\item[(2)]It is inter-operated with existing or proposed scheme for electronics voting system;
\item[(3)]The two players need not sacrifice their privacy in making use of the trusted third party;
\item[(4)]The deniable property can be proved secure in the random oracle paradigm, while the
matching protocol can be proved secure in the standard intractable assumption.
\end{description}

Multi-Party Computation from any Linear Secret Sharing Scheme Secure against Adaptive Adversary: The Zero-Error Case

We use a general treatment of both information-theoretic and cryptographic settings for
Multi-Party Computation (MPC), based on the underlying linear secret sharing scheme.
Our goal is to study the Monotone Span Program (MSP), which is the result of local multiplication
of shares distributed by two given MSPs as well as the access structure that this resulting MSP computes.
First, we expand the construction proposed by Cramer et~al. multiplying two different general access structures
and we prove some properties of the resulting MSP ${\cal M}$.
Next we expand the definition of multiplicative MSPs and we prove that when one uses dual MSPs only all players together can compute the product, i.e., the construction proposed by Cramer et~al. gives only multiplicative MPC.
Third, we propose a solution for the strongly multiplicative MPC (in presence of adversary).
The knowledge of the resulting MSP and the access structure it computes allows us to build an analog
of the algebraic simplification protocol of Gennaro et~al.
We show how to achieve in the computational model MPC secure against adaptive adversary in the zero-error case,
through the application of homomorphic commitments.
There is an open problem how efficiently we can determine $\Gamma$ the access structure of the resulting MSP
${\cal M}$. This open problem reflects negatively on the efficiency of the proposed solution.

Distributing the Encryption and Decryption of a Block Cipher

In threshold cryptography the goal is to distribute the computation of
basic cryptographic primitives across a number of nodes in order to relax trust assumptions on individual nodes, as well as to introduce a level of fault-tolerance against node compromise. Most threshold cryptography has previously looked at the distribution of public key primitives, particularly threshold signatures and threshold decryption mechanisms. In this paper we look at the application of threshold cryptography to symmetric primitives, and in particular the encryption or decryption of a symmetric key block cipher. We comment on some previous work in this area and then propose a model for shared encryption / decryption of a block cipher. We will present several approaches to enable such systems and will compare them.

ID-based tripartite Authenticated Key Agreement Protocols from pairings

This paper proposes ID-based tripartite authenticated key agreement protocols. The authenticated three party key agreement protocols from pairings [15], and the ID-based two party authenticated key agreement protocol [13] are studied. These two protocols are taken as the basis for designing three new ID-based tripartite authenticated key agreement protocols. The security properties of all these protocols are studied listing out the possible attacks on them. Further, these protocols are extended to provide key confirmation.

Plaintext-dependant Repetition Codes Cryptanalysis of Block Ciphers - The AES Case

This paper presents a new ``operational'' cryptanalysis of block ciphers based on the
use of a well-known error-correcting code: the repetition codes. We demonstrate how to
describe a block cipher with such a code before explaining how to design a new ciphertext
only cryptanalysis of these cryptosystems on the assumption that plaintext belongs to
a particular class. This new cryptanalysis may succeed for any block cipher and thus is
likely to question the security of those cryptosystems for encryption. We then apply this
cryptanalysis to the 128-bit key AES. Our results have been experimentallly confirmed with
100 {\bf effective} cryptanalysis. Our attack enables to recover two information bits of
the secret key with only $2^{31}$ ciphertext blocks and a complexity of $\mathcal{O}(2^{31})$
with a success probability of 0.68.

Imperfect Decryption and an Attack on the NTRU Encryption Scheme

A property of the NTRU public-key cryptosystem is that it does not provide
perfect decryption. That is, given an instance of the cryptosystem,
there exist ciphertexts which can be validly created using the public key
but which can't be decrypted using the private key. The valid ciphertexts
which an NTRU secret key will not correctly decipher
determine, up to a cyclic shift, the secret key. In this paper
we present attacks based on this property
against the NTRU primitive and many of the suggested NTRU padding
schemes.
These attacks use an
oracle for determining if valid ciphertexts can be correctly deciphered, and
recover the user's secret key. The attacks are quite practical. For example,
the attack against the NTRU-REACT padding scheme proposed at CRYPTO
2002 with the $N=503$ parameter set
requires on average fewer than 30,000 oracle calls and
can be performed on a PC in a few minutes.
As the traditional definition of a public-key encryption
scheme requires perfect decryption, we also define a new type of encryption
scheme which encompasses both NTRU and an attack model for the attacks
presented against it.

A Mode of Operation with Partial Encryption and Message Integrity

At the recent AES Modes of Operation Conference, several
modes of operation were proposed for using a block cipher to provide
both confidentiality and authentication. These modes require only a little
more work than the cost of encryption alone, and come with proofs of
security. However, these modes require the entire message to be sent in
encrypted form. This can cause problems in situations where some of the
message neeeds to be sent in plaintext while still being authenticated.
This paper describes a simple variation that allows any choice of message
blocks to be sent in plaintext form rather than in encrypted form. This
mode, Partial Encryption with Message Integrity (PEMI), is shown to
be secure for message integrity and message secrecy.

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.