All papers in 2002 (195 results)

H. D. L. Hollmann, J. H. v. Lint, L. Tolhuizen, P. Tuyls
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
P. Tuyls, H. D. L. Hollmann, J. H. v. Lint, L. Tolhuizen
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
Michael J. Collins
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
Emmanuel Bresson, Olivier Chevassut, David Pointcheval
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
Frederik Armknecht
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
Eric Hall, Charanjit S. Jutla
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
Kaoru Kurosawa, Wakaha Ogata
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
Daewan Han, Jin Hong, Jae Woo Han, Daesung Kwon
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
Hervé SIBERT, Patrick DEHORNOY, Marc GIRAULT
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
Oded Goldreich
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
Greg Rose, Philip Hawkes
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
Liqun Chen, Caroline Kudla
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
Claude Crépeau, Alain Slakmon
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
Wakaha Ogata, Kaoru Kurosawa
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
Eisaku Furukawa, Mitsuru Kawazoe, Tetsuya Takahashi
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
Tetsu Iwata, Kaoru Kurosawa
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
Juan Manuel Garcia Garcia, Rolando Menchaca Garcia
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
Fangguo Zhang, Shengli Liu, Kwangjo Kim
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
Jianhong Zhang, Jilin Wang, Yumin Wang
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
Masahiko Takenaka, Takeshi Shimoyama, Takeshi Koshiba
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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.