### All papers in 2002 (195 results)

Show abstract

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.

Last updated: 2002-12-23

Show abstract

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.

Last updated: 2002-12-23

Show abstract

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$.

Last updated: 2002-12-23

Uncategorized

Show abstract

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.

Last updated: 2003-10-23

Show abstract

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.

Last updated: 2003-08-13

Show abstract

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

Last updated: 2005-02-01

Uncategorized

Show abstract

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.

Last updated: 2002-12-12

Show abstract

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.

Last updated: 2003-04-19

Show abstract

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.

Last updated: 2002-12-13

Show abstract

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).

Last updated: 2002-12-05

Show abstract

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.

Last updated: 2003-11-17

Show abstract

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.

Last updated: 2004-05-27

Uncategorized

Show abstract

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.

Last updated: 2002-12-01

Show abstract

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.

Last updated: 2004-03-09

Show abstract

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$.

Last updated: 2003-05-12

Show abstract

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.

Last updated: 2003-03-10

Show abstract

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)$.

Last updated: 2002-11-21

Show abstract

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.

Last updated: 2002-11-21

Uncategorized

Show abstract

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.

Last updated: 2002-11-19

Uncategorized

Show abstract

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.

Last updated: 2002-11-18