## All papers in 2003 (265 results)

Concurrent/Resettable Zero-Knowledge With Concurrent Soundness in the Bare Public-Key Model and Its Applications

Uncategorized

Uncategorized

In this work, we investigate concurrent knowledge-extraction (CKE)
and concurrent non-malleability (CNM) for concurrent (and stronger,
resettable) ZK protocols in the bare public-key model.
We formulate, driven by concrete attacks, and achieve CKE for
constant-round concurrent/resettable arguments in the BPK model
under standard polynomial assumptions. We get both generic and
practical implementations. Here, CKE is a new concurrent verifier
security that is strictly stronger than concurrent soundness in
public-key model.
We investigate, driven by concrete attacks, and clarify the
subtleties in formulating CNM in the public-key model. We then give
a new (augmented) CNM formulation in the public-key model and a
construction of CNMZK in the public-key model satisfying the new
CNM formulation.

Inversion of Several Field Elements: A New Parallel Algorithm

In many crypographic hardware or software packages, a considerable part is devoted to finite field arithmetic. The finite field arithmetic is a very costly operation in comparison to other finite field operations. Taming the complexity of this operation has been a major challenge for researchers and implementers. One approach for the purpose is accumulate all the elements to be inverted and to compute several inversions simultaneously at the cost of one inversion and some multiplictions. One such algorithm is known as Montgomery's trick. However Montgomery's trick does not allow much parallelism. In~\cite{SMB03} an algorithm for computation of inverses of several field elements simultaneously in parallel has been proposed. The algorithm allows ample scope for parallelism and performes well if there is no restriction on the number of processors used. In the current work, we present an algorithm, which is same in complexity as Montgomery's trick but suitable for a parallel implementation. In parallel implementation, it computes inverse of $n$ elements in $2\log n$ parallel rounds. It performs better than both the previous algorithms under the circumstances where the restricted number of multipliers is used.

Security Analysis of Lal and Awasthi's Proxy Signature Schemes

In this paper, we analyze two proxy signatures scheme [1], [2] proposed by Lal and Awasthi and found that both the schemes suffer with the security flaws. The scheme [1] suffers with proxy signer's forgery attacks and misuse of original signer's delegated information. The other scheme [2] suffers with original signer's forgery attack, proxy signer's undeniability and misuse of delegated information.

A Secure Modified ID-Based Undeniable Signature Scheme

Verifiable Pairing and its Applications. In Chae Hoon Lim and Moti Yung, editors, Information Security Applications: 5th International Workshop, WISA 2004, Jeju Island, Korea, August 23-25, 2004, Revised Selected Papers, volume 3325 of Lecture Notes in Computer Science, pp. 170-187. (http://www.springerlink.com/index/C4QB7C13NL0EY5VN)
which contains an improved and generalized result of this paper.

A provably secure ID-based ring signature scheme

Identity-based (ID) cryptosystems avoid the necessity of certificates to authenticate public keys
in a digital communications system. This is desirable, specially for these applications which
involve a large number of public keys in each execution. For example, any computation and
verification of a ring signature scheme, where a user anonymously signs a message on behalf of a
set of users including himself, requires to authenticate the public keys of all the members of the
set.
We use bilinear pairings to design a new ID-based ring signature scheme. We extend to the
ID-based scehario some known results about the security of generic ring signature schemes.
This allows us to formally prove the security of our scheme, under the assumption that the
Computational Diffie-Hellman problem is hard to solve.

An Improved ID-based Authenticated Group Key Agreement Scheme

Authenticated group key agreement problem is important in many modern collaborative and distributed applications. There are two ID-based authenticated group key agreement schemes have been proposed by Choi et al. and us, which are based on bilinear pairings and BD scheme. Recently, Zhang and Chen propose an impersonation attack on the two schemes, which means the schemes are not fully authenticated. In this paper, we propose an improved ID-based authenticated group key agreement scheme which can resist this attack.

Attack on Two ID-based Authenticated Group Key Agreement Schemes

Uncategorized

Uncategorized

Authenticated group key agreement problem is important in many modern collaborative and distributed applications. Recently, there are two ID-based authenticated group key agreement schemes have been proposed, one is Choi $et\ al.$'s \cite{CHL04} scheme, the other is Du $et\ al.$'s \cite{Du03} scheme. They are all constructed from bilinear pairings based on Burmester and Desmedt scheme \cite{BD94}. In this paper, we propose an impersonation attack on the two schemes. We show that any two malicious users can impersonate an entity to agree some session keys in a new group if these two malicious users have the previous authentication transcripts of this entity. So, the two ID-based authenticated group key agreement schemes can not provide the authenticity as claimed. We propose a proposal to repair these schemes.

Analysis of Implementation Hierocrypt-3 algorithm (and its comparison to Camellia algorithm) using ALTERA devices.

Alghoritms: HIEROCRYPT-3, CAMELLIA and ANUBIS, GRAND CRU, NOEKEON, NUSH, Q, RC6, SAFER++128, SC2000, SHACAL were requested for the submission of block ciphers (high level block cipher) to NESSIE (New European Schemes for Signatures, Integrity, and Encryption) project. The main purpose of this project was to put forward a portfolio of strong cryptographic primitives of various types. The NESSIE project was a three year long project and has been divided into two phases. The first was finished in June 2001r. CAMELLIA, RC6, SAFER++128 and SHACAL were accepted for the second phase of the evaluation process.
HIEROCRYPT-3 had key schedule problems, and there were attacks for up to 3,5 rounds out of 6, at least hardware implementations of this cipher were extremely slow. HIEROCRYPT-3 was not selected to Phase II.
CAMELLIA was selected as an algorithm suggested for future standard.
In the paper we present the hardware implementations these two algorithms with 128-bit blocks and 128-bit keys, using ALTERA devices and their comparisons.

Trading Inversions for Multiplications in Elliptic Curve Cryptography

Recently, Eisentraeger-Lauter-Montgomery proposed a method for speeding up scalar multiplication on elliptic curves. That method relies on improved formulae for evaluating S = 2P + Q from given points P and Q on an elliptic curve. Compared to the naive approach, the improved formulae save a field multiplication each time the operation is performed.
This paper proposes a variant which is faster whenever a field inversion is more expensive than six field multiplications. We also give an improvement when tripling or quadrupling a point, and present a ternary/binary method to perform efficient scalar multiplication.

Last updated: 2004-08-11

On the Security of a Multi-Party Certified Email Protocol

As a value-added service to deliver important data over the Internet with guaranteed receipt for each successful delivery, certified email has been discussed for years and a number of research papers appeared in the literature. But most of them deal with the two-party scenarios, i.e., there are only one sender and one recipient. In some applications, however, the same certified message may need to be sent to a set of recipients. In ISC'02, Ferrer-Gomila et. al. presented a multi-party certified email protocol~\cite{FPH02}. It has two major features. A sender could notify multiple recipients of the same information while only those recipients who acknowledged are able to get the information. In addition, its exchange protocol is optimized, which has only three steps. In this paper, we demonstrate some flaws and weaknesses in that protocol, and propose an improved version which is robust against the identified attacks while preserving the features of the original protocol.

Improved Constructions for Universal Re-encryption.

Golle et al introduced universal re-encryption, defining it as re- encryption by a player who does not know the key used for the original encryption, but which still allows an intended player to recover the plaintext. Universal re-encryption is potentially useful as part of many information-hiding techniques, as it allows any player to make ciphertext unidentifiable without knowing the key used.
Golle et al’s techniques for universal re-encryption are reviewed, and improved constructions for both simple and hybrid universal re-encryption systems are presented, including a hybrid construction that permits indefinite re-encryptions with better efficiency and an almost-optimally small increase in file size. Some implementational issues and possible future directions are also discussed.

Committing Encryption and Publicly-Verifiable SignCryption

Encryption is often conceived as a committing process, in the sense that the ciphertext may serve as a commitment to the plaintext. But this does not follow from the standard definitions of secure encryption.
We define and construct symmetric and asymmetric committing encryption schemes, enabling publicly verifiable non-repudiation. Committing encryption eliminates key-spoofing attacks and has also the robustness to be signed afterwards. Our constructions are very efficient and practical. In particular, we show that most popular asymmetric encryption schemes, e.g. RSA, are committing encryption schemes; we also have an (efficient) construction given an arbitrary asymmetric encryption scheme. Our construction of symmetric committing encryption retains the efficiency of the symmetric encryption for real-time operations, although it uses few public key signatures in the setup phase.
Finally, we investigate how to achieve both confidentiality and non-repudiation, and present a publicly verifiable signcryption scheme. Contrary to previous signcryption schemes, which are not publicly verifiable, our publicly verifiable signcryption supports non-repudiation. We construct a simple and efficient publicly verifiable signcryption scheme based on a new composition method which we call “commit-encrypt-then-sign” (CEtS) that preserves security properties of both committing encryption and digital signature schemes.

Aspects of Hyperelliptic Curves over Large Prime Fields in Software Implementations

This paper presents an implementation of genus 2 and 3
hyperelliptic curves over prime fields, with a comparison with
elliptic curves. To allow a fair comparison, we developed an ad-hoc
arithmetic library, designed to remove most of the overheads that
penalise implementations of curve-based cryptography over prime
fields. These overheads get worse for smaller fields, and thus for
large genera. We also use techniques such as lazy and incomplete
modular reduction, originally developed for performing arithmetic in
field extensions, to reduce the number of modular reductions occurring
in the formulae for the group operations.
The result is that the performance of hyperelliptic curves of genus
2 over prime fields is much closer to the performance of elliptic
curves than previously thought. For groups of 192 and 256 bits the
difference is about 18% and 15% respectively.

On Simulation-Sound Trapdoor Commitments

We study the recently introduced notion of a simulation-sound trapdoor
commitment (SSTC) scheme. In this paper, we present a new, simpler
definition for an SSTC scheme that admits more efficient constructions
and can be used in a larger set of applications. Specifically, we
show how to construct SSTC schemes from any one-way functions, and how
to construct very efficient SSTC schemes based on specific
number-theoretic assumptions. We also show how to construct
simulation-sound, non-malleable, and universally-composable
zero-knowledge protocols using SSTC schemes, yielding, for instance,
the most efficient universally-composable zero-knowledge protocols
known. Finally, we explore the relation between SSTC schemes and
non-malleable commitment schemes by presenting a sequence of
implication and separation results, which in particular imply that
SSTC schemes are non-malleable.

Isomorphism Classes of Hyperelliptic Curves of genus 3 over finite fields

Uncategorized

Uncategorized

We give the number of the isomorphism classes of hyperelliptic
curves of genus 3 defined over finite fields F_{p^n},
$p \neq 2,7. These results have applications to cryptography.

Breaking the Stream Cipher Whitenoise

Whitenoise is a stream cipher with specification given at http://eprint.iacr.org/2003/249. In this paper, we show that Whitenoise is extremely weak. It can be broken by solving about 80,000 linear equations. And only about 80,000 bytes keystream are needed in the attack.

Software Specifications For Tinnitus Utilizing Whitenoise(Revised Feb 2004)

Whitenoise Substitution Stream Cipher is a multi-key-Super key hierarchical cryptographic process. This cryptographic system utilizes a method of encryption that can reasonably be described conceptually as an algorithmic representation of a multi-dimensional encrypting cipher matrix. The Whitenoise algorithm takes several sub keys and then creates a very long non-repeating key stream.
This was revised to respond to security concerns brought up in 2003/250.

Efficient Implementation of Genus Three Hyperelliptic Curve Cryptography over GF(2^n)

The optimization of the Harley algorithm is an active area of
hyperelliptic curve cryptography.
We propose an efficient method for software implementation of
genus three Harley algorithm over GF(2^n).
Our method is based on fast finite field multiplication using one SIMD operation, SSE2 on Pentium 4, and parallelized Harley algorithm.
We demonstrated that software implementation using proposed method is about 11% faster than conventional implementation.

ID-based Authenticated Two Round Multi-Party Key Agreement

This paper proposes an ID-based authenticated two round multi-party key agreement among n parties. Several ID-based two-party and tripartite key agreement schemes were proposed recently. Our two round multi-party key agreement scheme utilizes the idea of the two-round group key exchange protocol of Burmester and Desmedt. The authenticity of the protocol is assured by a special signature scheme, so the messages carrying the information of ephemeral key can be broadcasted authentically by an entity. Security attributes of our protocol are presented, and computational overhead and band width of the broadcast messages are analyzed as well.

Quantum Digital Signature Based on Quantum One-way Functions

A quantum digital signature scheme based on quantum mechanics is proposed in this paper. The security of the protocol relies on the existence of quantum one-way functions by fundamental quantum principles. Our protocol involves a so-called arbitrator who validates and authenticates the signed message. This scheme uses public quantum keys publicized by the signatory to verify the validity of the signature and uses quantum one-time pad to ensure the security of quantum information on channel. To guarantee the authenticity of the transmitted quantum states, a family of quantum stabilizer code is employed. The proposed scheme presents a novel method to construct secure quantum signature systems for future secure communications.

A Key Substitution Attack on SFLASH^{v3}

A practical key substitution attack on SFLASH^{v3} is described: Given a valid (message, signature) pair (m,\sigma) for some public key v_0, one can derive another public key v_1 (along with matching secret data) such that (m,\sigma) is also valid for v_1. The computational effort needed for finding such a `duplicate' key is comparable to the effort needed for ordinary key generation.

Efficient Public Key Steganography Secure Against Adaptively Chosen Stegotext Attacks

We define the notion of adative chosen stegotext security. We then construct \emph{efficient} public key
steganographic schemes secure against adaptively chosen stegotext attacks, without resort to any special
existence assumption such as unbiased functions. This is the first time such a construction is
obtained. Not only our constructions are \emph{secure}, but also are essentially optimal and have
\emph{no error} decoding. We achieve this by applying a primitive called $\ch{P}$-codes.

An Attack on Not-interactive Designated Verifier Proofs for Undeniable Signatures

At Crypto'89, Chaum and van Antwerpen first introduced the concept of undeniable signatures, which has a special property such that a signature cannot be verified without the signer's cooperation. In 1996, Jakobsson, Sako, and Impagliazzo proposed a not-interactive undeniable signature scheme by employing a new primitive called designated verifier proofs. However, this paper shows that their scheme is insecure by demonstrating a simple attack that allows a dishonest signer to convince a designated verifier receiving invalid signatures. In addition, two intuitive countermeasures are presented.

Improved Weil and Tate pairings for elliptic and hyperelliptic curves

We present algorithms for computing the {\it squared} Weil and Tate pairings on an elliptic curve and the {\it squared} Tate pairing for hyperelliptic curves. The squared pairings introduced in this paper have the advantage that our algorithms for evaluating them are deterministic and do not depend on a random choice of points. Our pairings save about 20-30\% over the usual pairings.

Hybrid Broadcast Encryption and Security Analysis

Uncategorized

Uncategorized

A broadcast encryption scheme for stateless receivers
is a data distribution method which
never updates users' secret information while in order to maintain the
security the system
efficiency decreases with the number of revoked users.
Another method, a rekeying scheme is a data distribution approach
where it revokes
illegal users in an {\em explicit} and {\em immediate} way whereas it
may cause inconvenience for users.
A hybrid approach that appropriately combines these two types of
mechanisms
seems resulting in a good scheme.
In this paper, we suggest such a
hybrid framework by proposing a rekeying algorithm for subset cover
broadcast encryption
framework (for stateless receivers) due to Naor et al. Our rekeying
algorithm
can simultaneously revoke a number of users.
A hybrid approach that appropriately combines these two types of
mechanisms
seems resulting in a good scheme.
In this paper, we suggest such a
hybrid framework by proposing a rekeying algorithm for subset cover
broadcast encryption
framework (for stateless receivers) due to Naor et al. Our rekeying
algorithm
can simultaneously revoke a number of users.
As an important contribution, we formally prove that this hybrid
framework has a pre-CCA like security, where in addition to pre-CCA
power, the adversary is allowed to {\em adaptively}
corrupt and revoke users.
Finally, we realize the hybrid framework by
two secure concrete schemes that are
based on complete subtree method and Asano
method, respectively.

How to Break and Repair a Universally Composable Signature Functionality

Canetti and Rabin recently proposed a universally composable ideal functionality F_SIG for digital signatures. We show that this functionality cannot be securely realized by \emph{any} signature scheme, thereby disproving their result that any signature scheme that is existentially unforgeable under adaptive chosen-message attack is a secure realization.
Next, an improved signature functionality is presented. We show that our improved functionality can be securely realized by precisely those signature schemes that are secure against existential forgery under adaptive chosen-message attacks.

Universally Composable Signatures, Certification and Authentication

Recently some efforts were made towards capturing the security requirements from digital signature schemes as an ideal functionality within a
composable security framework. This modeling of digital signatures
potentially has some significant analytical advantages (such as enabling component-wise analysis of complex systems that use signature schemes, as well as symbolic and automatable analysis of such systems). However, it turns out that
formulating ideal functionalities that capture the properties
expected from signature schemes in a way that is both sound and
enjoys the above advantages is not a trivial task.
This work has several contributions. We first correct some flaws in the definition of the ideal signature functionality of Canetti, 2001, andsubsequent formulations. Next we provide a minimal
formalization of ``ideal certification authorities'' and
show how authenticated communication can be obtained using ideal signatures and an ideal certification authority. This is done while guaranteeing full modularity (i.e., each component is analyzed as stand-alone), and in an unconditional and errorless way.
This opens the door to symbolic and
automated analysis of protocols for these tasks, in a way that is
both modular and cryptographically sound.

Chameleon Signature from Bilinear Pairing

Chameleon signatures are non-interactive signatures based on a hash-and-sign paradigm, and similar in efficiency to regular signatures. The distinguishing characteristic of chameleon signatures is that there are non-transferable, with only the designated recipient capable of asserting its validity. In this paper, we introduce a new ID-based chameleon hash function based on bilinear pairing and build the ID-based chameleon signature scheme. Compared with the conventional chameleon hashing functions, the owner of a public hash key in the ID-based chameleon hashing scheme does not necessarily need to retrieve the associated secret key. The scheme enjoys all the attributes in the normal chameleon signature and the added characteristics of ID-based cryptography based on bilinear pairing.

Low-Cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity

This paper introduces simple methods to convert a cryptographic algorithm into an algorithm protected against simple side-channel attacks. Contrary to previously known solutions, the proposed techniques are not at the expense of the execution time. Moreover, they are generic and apply to virtually any algorithm.
In particular, we present several novel exponentiation algorithms, namely a protected square-and-multiply algorithm, its right-to-left counterpart, and several protected sliding-window algorithms. We also illustrate our methodology applied to point multiplication on elliptic curves. All these algorithms share the common feature that the complexity is globally unchanged compared to the corresponding
unprotected implementations.

Combinational Logic Design for AES SubByte Transformation on Masked Data

Low power consumption, low gate count and high throughput used to
be standard design criteria for cryptographic coprocessors
designated for smart cards and related embedded devices. Not
anymore. With the advent of side channel attacks, the first and
foremost concern is device resistance to such attacks.
This paper describes how to to embed data masking technique at a hardware level for an AES coprocessor. We concentrate on inversion in the field since it is the only non-linear operation that was assumed to require complex transformations on masked data and on masks. Our paper demonstares that it is possible to compute inverses directly on masked data, without ever revealing unmasked intermediate results in the process.
Our approach consists in transition to composite fields, where inversion can be efficiently implemented in combinational logic using only bitwise XOR and AND operations. A breakthrough idea is to replace these operations on masked data by simple combinational circuits operating on bits of masked data and on bits of a mask in such a manner that a proper "mask correction" is computed on-the fly. Combining these elementary building blocks, we obtain a complete hardware solution for a "masked AES", thus effectively resolving the problem of a secure AES co-processor.

Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data

We provide formal definitions and efficient secure techniques for
-- turning noisy information into keys usable for any cryptographic application, and, in particular,
-- reliably and securely authenticating biometric data.
Our techniques apply not just to biometric information, but to any keying material that, unlike traditional cryptographic keys, is (1) not reproducible precisely and (2) not distributed uniformly. We propose two primitives: a fuzzy extractor reliably extracts nearly uniform randomness R from its input; the extraction is error-tolerant in the sense that R will be the same even if the input changes, as long as it remains reasonably close to the original. Thus, R can be used as a key in a cryptographic application. A secure sketch produces public information about its input w that does not reveal w, and yet allows exact recovery of w given another value that is close to w. Thus, it can be used to reliably reproduce error-prone biometric inputs without incurring the security risk inherent in storing them.
We define the primitives to be both formally secure and versatile, generalizing much prior work. In addition, we provide nearly optimal constructions of both primitives for various measures of "closeness" of input data, such as Hamming distance, edit distance, and set difference.

Generalized Key-Evolving Signature Schemes or How to Foil an Armed Adversary

Key exposures, known or inconspicuous, are a real security threat.
Recovery mechanisms from such exposures are required. For digital
signatures such a recovery should ideally ---and when possible---
include invalidation of the signatures issued with the compromised
keys. We present new signature schemes with such recovery capabilities. We consider two models for key exposures: full and partial reveal. In the first, a key exposure reveals {\em all} the secrets currently existing in the system. This model is suitable for the pessimistic inconspicuous exposures scenario. The partial reveal model permits the signer to conceal some information under exposure: e.g., under coercive exposures the signer is able to reveal a ``fake'' secret key. We propose a definition of {\em generalized key-evolving signature scheme}, which unifies forward-security and security against the coercive and inconspicuous key exposures (previously considered separately \cite{BM99,NPT02-mono,I02-TE}).
The new models help us address repudiation problems inherent in the
monotone signatures \cite{NPT02-mono}, and achieve performance
improvements.

Public Key Steganography

Informally, a public-key steganography protocol allows two parties, who
have never met or exchanged a secret, to send hidden messages over a
public channel so that an adversary cannot even detect that these hidden
messages are being sent. Unlike previous settings in which provable
security has been applied to steganography, public-key steganography is
information-theoretically impossible. In this work we introduce
computational security conditions for public-key steganography similar to those introduced by Hopper, Langford and von Ahn for the private-key setting. We also give the first protocols for public-key steganography and steganographic key exchange that are provably secure under standard cryptographic assumptions.
Additionally, in the random oracle model, we present a protocol that is secure against adversaries that have access to a decoding oracle (the steganographic equivalent of CCA-2 adversaries).

The Statistical Zero-knowledge Proof for Blum Integer Based on Discrete Logarithm

Blum integers (BL), which has extensively been used in the domain
of cryptography, are integers with form $p^{k_1}q^{k_2}$, where
$p$ and $q$ are different primes both $\equiv
3\hspace{4pt}mod\hspace{4pt}4$ and $k_1$ and $k_2$ are odd
integers. These integers can be divided two types: 1) $M=pq$, 2)
$M=p^{k_1}q^{k_2}$, where at least one of $k_1$ and $k_2$ is
greater than 1.\par
In \cite{dbk3}, Bruce Schneier has already proposed an open
problem: {\it it is unknown whether there exists a truly practical
zero-knowledge proof for $M(=pq)\in BL$}. In this paper, we
construct two statistical zero-knowledge proofs based on discrete
logarithm, which satisfies the two following properties: 1) the
prover can convince the verifier $M\in BL$ ; 2) the prover can
convince the verifier $M=pq$ or $M=p^{k_1}q^{k_2}$, where at least
one of $k_1$ and $k_2$ is more than 1.\par
In addition, we propose a statistical zero-knowledge proof in
which the prover proves that a committed integer $a$ is not equal
to 0.\par

Public-Key Steganography with Active Attacks

A complexity-theoretic model for public-key steganography with
active attacks is introduced. The notion of steganographic
security against adaptive chosen-covertext attacks (SS-CCA) and a
relaxation called steganographic security against
publicly-detectable replayable adaptive chosen-covertext attacks
(SS-PDR-CCA) are formalized. These notions are closely related
to CCA-security and PDR-CCA-security for public-key
cryptosystems. In particular, it is shown that any SS-(PDR-)CCA
stegosystem is a (PDR-)CCA-secure public-key cryptosystem and that
an SS-PDR-CCA stegosystem can be realized from any PDR-CCA-secure
public-key cryptosystem with pseudorandom ciphertexts.

A Fast Provably Secure Cryptographic Hash Function

Uncategorized

Uncategorized

We propose a family of fast and provably secure cryptographic hash
functions. The security of these functions relies directly on the
well-known syndrome decoding problem for linear codes. Attacks on this
problem are well identified and their complexity is known. This
enables us to study precisely the practical security of the hash
functions and propose valid parameters for implementation.
Furthermore, the design proposed here is fully scalable, with respect
to security, hash size and output rate.

Algebraic Attacks on Summation Generators

Uncategorized

Uncategorized

We apply the algebraic attacks
on stream ciphers with memories to the summation generator.
For a summation generator that uses $n$ LFSRs, the
algebraic equation relating the key stream bits
and LFSR output bits
can be made to be of degree less than or equal to
$2^{\lceil\log_2 n \rceil}$, using $\lceil\log_2 n \rceil + 1$
consecutive key stream bits.
This is much lower than the upper bound given by
previous general results.

Verifiably Committed Signatures Provably Secure in The Standard Complexity Model

In this paper, we study the security notions of verifiably committed signatures by introducing privacy and cut-off time,
and then we propose the first scheme which is provably secure in the standard complexity model based on the strong RSA
assumption. The idea behind the construction is that given any valid partial signature of messages, if a co-signer with
its auxiliary input is able to generate variables called the resolution of messages such that the distribution of the
variables is indistinguishable from that generated by the primary signer alone from the views of the verifier/arbitrator,
a verifiably committed signature can be constructed.

Attacks on a Secure Group Communication Scheme With Hierarchical Access Control

At ICICS 2001, Zou, Ramamurthy, and Magliveras proposed CRTHACS, a chinese remainder theorem based scheme for secure group communication with hierarchical access control. The scheme is designed in such a way that the underlying hierarchy remains hidden from the participating parties/users.
This contribution describes several practical attacks on CRTHACS which can reveal significant parts of the hierarchy.

On the Security of a Group Signature Scheme with Forward Security

A group signature scheme allows a group member of a given group to sign messages on behalf of the group in an anonymous and unlinkable way. In case of a dispute, however, a designated group manager can reveal the signer of a valid group signature. Based on Song's forward-secure group signature schemes, Zhang, Wu, and Wang proposed a new group signature scheme with forward security at ICICS 2003. Their scheme is very efficient in both communication and computation aspects. Unfortunately, their scheme is insecure. In this paper we present a security analysis to show that their scheme is linkable, untraceable, and forgeable.

Masking Based Domain Extenders for UOWHFs: Bounds and Constructions

Uncategorized

Uncategorized

We study the class of masking based domain extenders for UOWHFs. Our first contribution
is to show that any correct masking based domain extender for UOWHF which invokes
the compression UOWHF $s$ times must use at least $\lceil\log s\rceil$ masks. As a
consequence we obtain the optimality of Shoup's algorithm among the class of masking
based domain extenders. Our second contribution is to present a new parallel domain
extender for UOWHF. The new algorithm obtains an asymptotically optimal speed-up over
the sequential algorithm and the key expansion is almost everywhere optimal, i.e., it
is optimal for almost all possible number of invocations of the compression UOWHF.

Last updated: 2004-03-08

--Withdrawn--

Uncategorized

Uncategorized

In this paper we present two new protocols from the Tate Pairing. The first is a secret handshake, in which we introduce a covert channel into Smarts “An identity based key agreement protocol based on the weil pairing” and the second is an efficient Signcryption scheme for
low bandwidth channels.

Cryptanalysis of a Cryptosystem based on Drinfeld modules

A public key cryptosystem based on Drinfeld modules has been proposed
by Gillard, Leprevost, Panchishkin and Roblot. The paper shows how an
adversary can directly recover a private key using only
the public key, and so the cryptosystem is insecure.

A Verifiable Secret Sharing Scheme with Statistical zero-knowledge

In this paper, we first propose a protocol in which the prover can
show that a=b holds for two committed integers a and b;
also, we present a protocol in which the prover can prove that
a\neq 0 holds for committed integer a; then, we construct a
protocol to prove that the degree of a polynomial f(x) equals to
t-1 exactly, which has been as an open problem(see[21]);
finally, we provide a protocol in which the prover proves that a
pair (x,y) is generated by a polynomial f(x), i.e., y=f(x)(mod m), where m is a prime.
Based on above four protocols, we put forward a verifiable
(t,n)-secret sharing scheme, which can avoid all known the
dealer's cheats.
In particular, all above protocols are statistical zero-knowledge.

A Cryptanalysis of the Original Domingo-Ferrer's Algebraic Privacy Homomophism

Uncategorized

Uncategorized

We propose a cryptanalysis of the original Domingo-Ferrer's algebraic privacy homomorphism. We show that the scheme over $\Z_n$ can be broken by $d+1$ known plaintexts in $O(d^3\log^2 n)$ time when it has $d$ times expansion through the encryption. Furthermore even when the public modulus $n$ is kept secret, it can be broken by $d+2$ known plaintexts in time at most $O(d^5\log^2(dn))$.

A short comment on the affine parts of SFLASH^{v3}

In [http://eprint.iacr.org/2003/211/] SFLASH^{v3} is presented, which supersedes SFLASH^{v2}, one of the digital signature schemes in the NESSIE Portfolio of recommended cryptographic primitives. We show that a known attack against the affine parts of SFLASH^{v1} and SFLASH^{v2} carries over immediately to the new version SFLASH^{v3}: The 861 bit representing the affine parts of the secret key can easily be derived from the public key alone.

Cryptanalysis of the Repaired Public-key Encryption Scheme Based on the Polynomial Reconstruction Problem

At Eurocrypt 2003, Augot and Finiasz proposed a new public-key
encryption scheme based on the polynomial reconstruction problem. The scheme was subsequently broken by Coron,
who showed that given the public-key and a ciphertext, one could
recover the corresponding plaintext in polynomial time. Recently,
Augot, Finiasz and Loidreau published on the IACR eprint archive a
reparation of the cryptosystem. The reparation is based on
the trace operator, and is resistant against the previous attack.
However, we describe a new cryptanalysis of the repaired scheme.
Given the public-key and a ciphertext, we can still recover the
corresponding plaintext in polynomial time. Our technique is
a variant of the Berlekamp-Welsh algorithm, and works very
well in practice, as for the proposed parameters, we recover the
plaintext in less than 8 minutes on a single PC.

A Security Evaluation of Whitenoise

This report studies the security of Whitenoise, a stream cipher invented by BSB Utilities Inc. http://bsbutil.com
"Even if we hypothesized the existence of some magic computer that could test a trillion trillion key trials per second (very unlikely!), and even if we could place a trillion trillion such computers somewhere throughout the universe (even more unlikely!), and even if we were willing to wait a trillion trillion years (not a chance!), then the probability that we would discover the correct key would be negligible (about (1/2)^1340, which is unimaginably small)."

Chemical Combinatorial Attacks on Keyboards

This paper presents a new attack on keyboards.
\smallskip
The attack consists in depositing on each keyboard key a small
ionic salt quantity ({\sl e.g.} some NaCl on key 0, some KCl on
key 1, LiCl on key 2, SrCl$_2$ on key 3, BaCl$_2$ on key 4,
CaCl$_2$ on key 5...). As the user enters his PIN, salts get mixed
and leave the keyboard in a state that leaks secret information.
Nicely enough, evaluating the entropy loss due to the chemical
trace turns out to be a very interesting combinatorial exercise.
\smallskip
Under the assumption that mass spectroscopic analysis can reveal with accuracy
the mixture of chemical compounds
generated by the user, we show that, for moderate-size
decimal PINs, the attack would generally disclose the PIN.
\smallskip
The attack may apply to door PIN codes, phone numbers dialed from
a hotel rooms, computer keyboards or even ATMs.
\ss
While we did not implement the chemical part of the attack, a number of mass spectrometry
specialists confirmed to the authors its feasibility.

Secure Indexes

Uncategorized

Uncategorized

A secure index is a data structure that allows a querier with a ``trapdoor'' for a word x to test in O(1) time only if the index contains x; The index reveals no information about its contents without valid trapdoors, and trapdoors can only be generated with a secret key. Secure indexes are a natural extension of the problem of constructing data structures with privacy guarantees such as those provided by oblivious and history independent data structures. In this paper, we formally define a secure index and formulate a security model for indexes known as semantic security against adaptive chosen keyword attack (IND-CKA). We also develop an efficient IND-CKA secure index construction called Z-IDX using pseudo-random functions and Bloom filters, and show how to use Z-IDX to implement searches on encrypted data. This search scheme is the most efficient encrypted data search scheme currently known; It provides O(1) search time per document, and handles compressed data, variable length words, and boolean and certain regular expression queries. The techniques developed in this paper can also be used to build encrypted searchable audit logs, private database query schemes, accumulated hashing schemes, and secure set membership tests.

Divide and Concatenate: A Scalable Hardware Architecture for Universal MAC

We present a cryptographic architecture optimization technique called divide-and-concatenate based on two observations: (i) the area of a multiplier and associated data path decreases exponentially and their speeds increase linearly as their operand size is reduced. (ii) in hash functions, message authentication codes and related cryptographic algorithms, two functions are equivalent if they have the same collision probability property. In the proposed approach we divide a 2w-bit data path (with collision probability 2-2w) into two w-bit data paths (each with collision probability 2-w) and concatenate their results to construct an equivalent 2w-bit data path (with a collision probability 2-2w).
We applied this technique on NH hash, a universal hash function that uses multiplications and additions. When compared to the 100% overhead associated with duplicating a straightforward 32-bit pipelined NH hash data path, the divide-and-concatenate approach yields a 94% increase in throughput with only 40% hardware overhead. The NH hash associated message authentication code UMAC architecture with collision probability 2-32 that uses four equivalent 8-bit divide-and-concatenate NH hash data paths yields a throughput of 79.2 Gbps with only 3840 FPGA slices when implemented on a Xilinx XC2VP7-7 Field Programmable Gate Array (FPGA).

Multi-Trapdoor Commitments and their Applications to Non-Malleable Protocols

We introduce the notion of multi-trapdoor commitments
which is a stronger form of trapdoor commitment schemes.
We then construct two very efficient instantiations of
multi-trapdoor commitment schemes, based on the Strong
RSA Assumption and the recently introduced Strong Diffie-Hellman
Assumption.
The main applications of our result are non-malleable
trapdoor commtiments and a compiler} that takes any proof of knowledge
and transforms it into one which is secure against a concurrent
man-in-the-middle attack. Such a proof of knowledge immediately
yields concurrently secure identification protocols.
When using our number-theoretic istantiations, the non-malleable
commitment and the
compiler are very efficient (require no more than
four exponentiations). The latter also maintains the round complexity of
the original proof of knowledge; it works in the common reference string
model, which in any case is necessary to prove security of proofs
of knowledge under this kind of attacks. Compared to previously
known efficient solutions, ours is a factor of two faster.

Isomorphism Classes of Hyperelliptic Curves of Genus 2 over $\mathbb{F}_{2^n}$

We give the exact number and representatives of the
isomorphism, which preserves infinity, classes of hyperelliptic
curves of genus $2$ over finite fields with characteristic $2 $ in
most cases. These results have applications to hyperelliptic curve
cryptography.

High Performance Arithmetic for Hyperelliptic Curve Cryptosystems of Genus Two

Nowadays, there exists a manifold variety of cryptographic applications: from low level embedded crypto implementations up to high end cryptographic engines for servers. The latter require a flexible implementation of a variety of cryptographic primitives in order to be capable of communicating with several clients. On the other hand, on the client it only requires an implementation of one specific algorithm with fixed parameters such as a fixed field size or fixed curve parameters if using ECC/ HECC. In particular for embedded environments like PDAs or mobile communication devices, fixing these parameters can be crucial regarding speed and power consumption. In this contribution, we propose a highly efficient algorithm for a hyperelliptic curve cryptosystem of genus two, well suited for these constraint devices.
In recent years, a lot of effort was made to speed up arithmetic on genus-2 HEC. This work is based on the work of Lange and presents a major improvement of HECC arithmetic for curves defined over fields of characteristic two. We optimized the group doubling operation for certain types of genus-2 curves and we were able to reduce the number of required multiplications to a total of 9 multiplications. The saving in multiplications is 47% for the cost of one additional squaring. Thus, the efficiency of the whole cryptosystem was drastically increased.

SFLASHv3, a fast asymmetric signature scheme

SFLASH-v2 is one of the three asymmetric signature schemes recommended by the European consortium for low-cost smart cards. The latest implementation report published at PKC 2003 shows that SFLASH-v2 is the fastest signature scheme known.
This is a detailed specification of SFLASH-v3 produced in 2003 for fear of v2 being broken. HOWEVER after detailed analysis by Chen Courtois and Yang [ICICS04], Sflash-v2 is not broken and we still recommend the previous version Sflash-v2, already recommended by Nessie, instead of this version.

On a Relation Between Verifiable Secret Sharing Schemes and a Class of Error-Correcting Codes

In this paper we try to shed a new insight on Verifiable Secret
Sharing Schemes (VSS). We first define a new ``metric" (with slightly
different properties than the standard Hamming metric). Using
this metric we define a very particular class of codes that we call
{\it error-set correcting codes}, based on a set of forbidden distances which is a
monotone decreasing set. Next we redefine the packing problem for the new
settings and generalize the notion of error-correcting capability of the
error-set correcting codes accordingly (taking into account the new metric and the
new packing). Then we consider burst-error interleaving codes
proposing an efficient burst-error correcting technique, which is in fact the well
known VSS and Distributed Commitments (DC) pair-wise checking protocol and we prove
the error-correcting capability of the error-set correcting interleaving codes.
Using the known relationship, due to Van Dijk, between a Monotone
Span Program (MSP) and a generator matrix of the code generated by
the suitable set of vectors, we prove that the error-set
correcting codes in fact has the allowed (opposite to forbidden)
distances of the dual access structure of the access structure
that the MSP computes. We give an efficient construction for them
based on this relation and as a consequence we establish a link
between Secret Sharing Schemes (SSS) and the error-set correcting
codes.
Further we give a necessary and sufficient condition for the existence
of linear SSS (LSSS), to be secure against $(\Delta,\Delta_A)$-adversary
expressed in terms of an error-set correcting code. Finally, we present necessary
and sufficient conditions for the existence of a VSS scheme,
based on an error-set correcting code, secure against $(\Delta,\Delta_A)$-adversary.
Our approach is general and covers all known linear VSS/DC. It allows
us to establish the minimal conditions for security of VSSs. Our
main theorem states that the security of a scheme is equivalent to
a pure geometrical (coding) condition on the linear mappings describing
the scheme. Hence the security of all known schemes, e.g. all known bounds
for existence of unconditionally secure VSS/DC including the recent result of
Fehr and Maurer, can be expressed as certain (geometrical) coding conditions.

Using the Trace Operator to repair the Polynomial Reconstruction based Cryptosystem presented at Eurocrypt 2003

In this paper, we present a modification of the Augot-Finiasz
cryptosystem presented at EUROCRYPT 2003. Coron managed to
design an attack against the original cryptosystem enabling an
attacker to decrypt any intercepted ciphertext efficiently. We
introduce here a modification of the scheme which appears to
resist to this attack. We furthermore propose parameters
thwarting the state of the art attacks.

ID-Based Chameleon Hashes from Bilinear Pairings

Chameleon hash function is a trapdoor one-way hash function. The
ID-based chameleon hash function was first introduced by Ateniese
and Medeiros \cite{AM03}. As discussed by \cite{AM03}, the general
advantages of ID-based cryptography over conventional cryptography
with respect to key distribution are even more pronounced in a
chameleon hashing scheme, because the owner of a public key does
not necessarily need to retrieve the associated secret key. In
this paper, we propose two new ID-based Chameleon hashing schemes
from bilinear pairings. Also we analyze their security and
efficiency. Based on these ID-based chameleon hashes, ID-based
chameleon signature schemes can be designed.

Security Flaws in Several Group Signatures Proposed by Popescu

In resent years, Popescu proposed several group signature schemes based on the Okamoto-Shiraishi assumption in [8-11], and claimed his schemes are secure. However, this paper demonstrates that all these schemes are insecure by identifying some security flaws. Exploiting these flaws, an attacker without any secret can mount universally forging attacks. That is, anybody (not necessarily a group member) can forge valid group signatures on arbitrary messages of his/her choice.

Identity Based Undeniable Signatures

In this paper, we give a first example of identity based
undeniable signature using pairings over elliptic curves. We
extend to the identity based setting the security model for the
notions of invisibility and anonymity given by Galbraith and Mao
in 2003 and we prove that our scheme is existentially unforgeable
under the Bilinear Diffie-Hellman assumption in the random oracle
model. We also prove that it has the invisibility property under
the Decisional Bilinear Diffie-Hellman assumption and we discuss
about the efficiency of the scheme.

Improved Cryptanalysis of SecurID

Uncategorized

Uncategorized

SecurID is a widely used hardware token for strengthening
authentication in a corporate environment. Recently,
Biryukov, Lano, and Preneel presented an attack on the alleged
SecurID hash function~\cite{BLP}. They showed
that {\it vanishing differentials} -- collisions
of the hash function -- occur quite frequently, and that
such differentials allow an attacker to recover the secret key in the
token much faster than exhaustive search. Based on
simulation results, they estimated that given a single 2-bit vanishing
differential, the running time of their attack would be about $2^{48}$
full hash operations.
In this paper, we first give a more detailed analysis of the
attack in~\cite{BLP} and present several techniques to improve it
significantly. Our theoretical analysis and implementation experiments show
that the running time of our improved attack is about $2^{44}$
hash operations, though special cases involving $\ge$ 4-bit
differentials (which happen about one third of the time)
reduce the time further.
We then investigate into the use of extra information that an
attacker would typically have: multiple vanishing differentials
or knowledge that other vanishing differentials do not occur
in a nearby time period.
When using the extra information, it appears that key recovery can
always be accomplished within about $2^{40}$ hash operations.

A Composition Construction of Bent-Like Boolean Functions from Quadratic Polynomials

In this paper, we generalize the composition construction of Khoo et al. for highly nonlinear Boolean functions. We utilize general quadratic forms instead of the trace map in the construction. The construction composes an n-variable Boolean function and an m-variable quadratic form over field with characteristic 2 to get an nm-variable Boolean function with beautiful spectrum property and a doubled algebraic degree. Especially, the method is suitable to construct functions with 3-valued spectra (bent-like functions) or ones with better spectra (near-bent functions). Our proof technique is based on classification of quadratic forms over finite fields and enumeration of solutions of quadratic equations. We also prove the p-ary analogy of these results for odd prime p.

Novel Efficient Implementations of Hyperelliptic Curve Cryptosystems using Degenerate Divisors

Uncategorized

Uncategorized

It has recently been reported that the performance of hyperelliptic curve cryptosystems (HECC) is competitive to that of elliptic curve cryptosystems (ECC).
However, it is expected that HECC still can be improved due to their mathematically rich structure. We consider here the application of degenerate divisors of HECC to scalar multiplication. We investigate the operations of the degenerate divisors in the Harley algorithm and the Cantor algorithm of genus 2. The timings of these operations
are reported. We then present a novel efficient scalar multiplication method using the degenerate divisors. This method is applicable to cryptosystems with fixed base point, e.g., ElGamal-type encryption, sender of Diffie-Hellman, and DSA. Using a Xeon
processor, we found that the double-and-add-always method using the degenerate base point can achieve about a 20% increase in speed for a 160-bit HECC. However, we mounted an timing attack using the time difference to designate the degenerate divisors. The attack assumes that the secret key is fixed and the base point can be
freely chosen by the attacker. Therefore, the attack is applicable to ElGamal-type decryption and single-pass Diffie-Hellman — SSL using a hyperelliptic curve could be vulnerable to the proposed attack. Our experimental results show that one bit of the secret key for a 160-bit HECC can be recovered by calling the decryption oracle 500 times.

Yet Another Sieving Device

A compact mesh architecture for supporting the relation collection step of the number field sieve is described. Differing from TWIRL, only isolated chips without inter-chip communication are used. According to a preliminary analysis for 768-bit numbers, with a 130 nm process one mesh-based device fits on a single chip of ca. (4.9 cm)^2 - the largest proposed chips in the TWIRL cluster for 768-bit occupy ca. (6.7 cm)^2.
A 300 mm silicon wafer filled with the mesh-based devices is about 6.3 times slower than a wafer with TWIRL clusters, but due to the moderate chip size, lack of inter-chip communication, and the comparatively regular structure, from a practical point of view the mesh-based approach might be as attractive as TWIRL.

an attack on a multisignature scheme

In this letter, we show that structured ElGamal-type multisignature scheme due to Burmester et al. is not secure if the adversary attacks key generation.

Cryptanalysis of B.Lee-S.Kim-K.Kim Proxy Signature

Blind signature is the concept to ensure anonymity of e-cion. Untracebility and unlinkability are two main properties of real coin, which require mimicking electronically. Proxy signature schemes allow a proxy signer to generate a proxy signature on behalf of an original signer.All the previous proxy signature schemes are based on ElGamal-type schemes.In this paper, we propose a new proxy blind signature scheme based on an ID-based signature scheme, which uses bilinear pairings of elliptic curves or hyperelliptic curves.

Cryptanalysis of a Message Authentication Code due to Cary and Venkatesan

We present a cryptanalysis of a MAC proposal at CRYPTO 2003 due to
Cary and Venkatesan. Our attacks find collisions for the MAC and yield MAC forgeries, both faster than a straightforward application of the birthday paradox would suggest.

Construction of Perfect Nonlinear and Maximally Nonlinear Multi-Output Boolean Functions Satisfying Higher Order Strict Avalanche Criteria

We consider the problem of constructing perfect nonlinear multi-output Boolean functions satisfying higher order strict avalanche criteria (SAC). Our first construction is an infinite family of 2-ouput perfect nonlinear functions satisfying higher order SAC.
This construction is achieved using the theory of bilinear forms and symplectic matrices. Next we build on a known connection between 1-factorization of a complete graph and SAC to construct
more examples of 2 and 3-output perfect nonlinear functions. In certain cases, the constructed S-boxes have optimal trade-off between the following parameters: numbers of input and output variables, nonlinearity and order of SAC. In case the number
of input variables is odd, we modify the construction for perfect nonlinear S-boxes to obtain a construction for maximally nonlinear S-boxes satisfying higher order SAC. Our constructions present the first examples of perfect nonlinear and maximally nonlinear multioutput S-boxes satisfying higher order SAC. Lastly, we present a simple method for improving the degree of the constructed functions with a small trade-off in nonlinearity and the
SAC property. This yields functions which have possible applications in the design of block ciphers.

Revisiting fully distributed proxy signature schemes

In a proxy signature scheme, a potential signer delegates his
capabilities to a proxy signer, who can sign documents on behalf of
him. The recipient of the signature verifies both identities: that of
the delegator and that of the proxy signer. There are many proposals
of proxy signature schemes, but security of them has not been considered
in a formal way until the appearance of the work by Boldyreva et al.
If the entities which take part in a proxy signature scheme are formed
by sets of participants, then we refer to it as a fully distributed
proxy signature scheme.
In this work, we extend the security definitions introduced by
Boldyreva et al. to the scenario of fully distributed proxy signature
schemes, and we propose a specific scheme which is secure in this new
model.

Security Analysis of Some Proxy Signatures

A proxy signature scheme allows an entity to delegate his/her signing capability to another entity in such a way that the latter can sign messages on behalf of the former. Such schemes have been suggested for use in a number of applications, particularly in distributed computing where delegation of rights is quite common. Followed by the first schemes introduced by Mambo, Usuda and Okamoto in 1996, a number of new schemes and improvements have been proposed. In this paper, we present a security analysis of four such schemes newly proposed in [15,16]. By successfully identifying several interesting forgery attacks, we show that all the four schemes are insecure. Consequently, the fully distributed proxy scheme in [11] is also insecure since it is based on the (insecure) LKK scheme [14,15]. In addition, we point out the reasons why the security proofs provided in [15] are invalid.

Public Key Encryption with keyword Search

We study the problem of searching on data that is encrypted using a
public key system. Consider user Bob who sends email to user Alice
encrypted under Alice's public key. An email gateway wants to test
whether the email contains the keyword `urgent' so that it could
route the email accordingly. Alice, on the other hand does not wish
to give the gateway the ability to decrypt all her messages. We define
and construct a mechanism that enables Alice to provide a key to the
gateway that enables the gateway to test whether the word `urgent'
is a keyword in the email without learning anything else about the
email. We refer to this mechanism as <I>Public Key Encryption with
keyword Search</I>. As another example, consider a mail server that
stores various messages publicly encrypted for Alice by others. Using
our mechanism Alice can send the mail server a key that will enable
the server to identify all messages containing some specific keyword,
but learn nothing else. We define the concept of public key
encryption with keyword search and give several constructions.

Security Analysis of Several Group Signature Schemes

At Eurocrypt'91, Chaum and van Heyst introduced the concept of group signature. In such a scheme, each group member is allowed to sign messages on behalf of a group anonymously. However, in case of later disputes, a designated group manager can open a group signature and identify the signer. In recent years, researchers have proposed a number of new group signature schemes and improvements with different levels of security. In this paper, we present a security analysis of five group signature schemes proposed in [25,27,18,30,10]. By using the same method, we successfully identify several universally forging attacks on these schemes. In our attacks, anyone (not necessarily a group member) can forge valid group signatures on any messages such that the forged signatures cannot be opened by the group manager. We also discuss the linkability of these schemes, and further explain why and how we find the attacks.

Efficient Extension of Standard Schnorr/RSA signatures into Universal Designated-Verifier Signatures

Uncategorized

Uncategorized

Universal Designated-Verifier Signature (UDVS) schemes are digital signature schemes with additional
functionality which allows any holder of a signature to designate the signature to any desired
designated-verifier such that the designated-verifier can verify that the message was signed by the
signer, but is unable to convince anyone else of this fact.
Since UDVS schemes reduce to standard signatures when no verifier designation is performed, it is natural to ask
how to extend the classical Schnorr or RSA signature schemes into UDVS schemes, so that the existing key
generation and signing implementation infrastructure for these schemes can be used without modification. We show
how this can be efficiently achieved, and provide proofs of security for our schemes in the random oracle model.

Universal Designated-Verifier Signatures

Uncategorized

Uncategorized

Motivated by privacy issues associated with dissemination of signed digital certificates, we define a new type of signature scheme called a ‘Universal Designated-Verifier Signature’ (UDVS). A UDVS scheme can function as a standard publicly-verifiable digital signature but has additional functionality which allows any holder of a signature (not necessarily the signer) to designate the signature to any desired designated-verifier (using the verifier’s public key). Given the designated-signature, the designated-verifier can verify that the message was signed by the signer, but is unable to convince anyone else of this fact.
We propose an efficient deterministic UDVS scheme constructed using any bilinear group-pair. Our UDVS scheme functions as a standard Boneh-Lynn-Shacham (BLS) signature when no verifier-designation is performed, and is therefore compatible with the key-generation, signing and verifying algorithms of the BLS scheme. We prove that our UDVS scheme is secure in the sense of our unforgeability and privacy notions for UDVS schemes, under the Bilinear Diffie-Hellman (BDH) assumption for the underlying group-pair, in the random-oracle model. We also demonstrate a general constructive equivalence between a class of unforgeable and unconditionally-private UDVS schemes having unique signatures (which includes the deterministic UDVS schemes) and a class of ID-Based Encryption (IBE) schemes which contains the Boneh-Franklin IBE scheme but not the Cocks IBE scheme.

Projective Coordinates Leak

Uncategorized

Uncategorized

Denoting by $P=[k]G$ the elliptic-curve double-and-add
multiplication of a public base point $G$ by a secret $k$,
we show that allowing an adversary access to the projective
representation of $P$ results in information being revealed about $k$.
Such access might be granted to an adversary by a poor
software implementation that does not erase the $Z$
coordinate of $P$ from the computer's memory or by a computationally-constrained secure token that
sub-contracts the affine conversion of $P$ to the external world.
From a wider perspective, our result proves that the choice of
representation of elliptic curve points {\sl can reveal}
information about their underlying discrete logarithms, hence
casting potential doubt on the appropriateness of blindly
modelling elliptic-curves as generic groups.
As a conclusion, our result underlines the necessity to sanitize
$Z$ after the affine conversion or, alternatively,
randomize $P$ before releasing it out.

Last updated: 2003-09-15

Extending Joux's Protocol to Multi Party Key Agreement

We present a secure unauthenticated as well as an authenticated multi party key agreement protocol. The authenticated version of our protocol uses ternary trees and is based on bilinear maps and Joux's three party protocol. The number of rounds, computation/communication complexity of our protocol compares favourably with previously known protocols. The authenticated version of our protocol also uses ternary trees and is based on public IDs and Key Generation Centres. The authenticated version of our protocol is more efficient than all previously known authenticated key agreement protocols.

Cryptanalysis of publicly verifiable authenticated encryption

Ma and Chen proposed a new authenticated encryption scheme with public verifiability. This scheme requires less computational costs and communication overheads than the conventional signature-then-encryption approaches. In this letter, we show that the Ma-Chen scheme does not satisfy three security properties: unforgeability, confidentiality and non-repudiation.

A New Forward Secure Signature Scheme using Bilinear Maps

Forward-secure signatures are used to defeat signature forgeries in cases of key exposure. In this model, the signature key evolves with time and it is computationally infeasible for an adversary to forge a signature for some time-period prior to the key’s exposure.
In this paper a new forward-secure digital signature scheme is presented, which is based on the use of bilinear maps recently advocated by Boneh and Franklin [9]. This scheme is efficiently constructed and can be used with a large number of time periods with a log magnitude complexity. The signing and key-update operations are very efficient when compared with other previously available schemes. A formal definition, as well as a detailed analysis of the security performance or this scheme, is presented. The security proof for this scheme is based on the Computational Diffie-Hellman assumption, which leads to a unique approach to proving security in the random oracle model. Furthermore, within the proof both the hash oracle and the signing oracle are constructed in an innovative manner.

Resource Bounded Unprovability of Computational Lower Bounds

This paper introduces new notions of asymptotic proofs, PT(polynomial-time)-extensions, PTM(polynomial-time Turing machine)-$\omega$-consistency, etc. on formal theories of arithmetic including PA (Peano Arithmetic). An asymptotic proof is a set of infinitely many formal proofs, which is introduced to define and characterize a property, PTM-$\omega$-consistency, of a formal theory. Informally speaking, PTM-$\omega$-consistency is a {\it polynomial-time bounded} version (in asymptotic proofs) of $\omega$-consistency, and characterized in two manners: (1) (in the light of the {\it extension of PTM to TM}) the resource {\it unbounded} version of PTM-$\omega$-consistency is equivalent to $\omega$-consistency, and (2) (in the light of {\it asymptotic proofs by PTM})
a PTM-$\omega$-{\it inconsistent} theory includes an axiom that only a super-polynomial-time Turing machine can prove asymptotically over PA, under some assumptions. This paper shows that {\it P$\not=$NP (more generally, any super-polynomial-time lower bound in PSPACE) is unprovable in a PTM-$\omega$-consistent theory $T$}, where $T$ is a consistent PT-extension of PA (although this paper does not show that P$\not=$NP is unprovable in PA, since PA has not been proven to be PTM-$\omega$-consistent). This result implies that to prove P$\not=$NP by any technique requires a PTM-$\omega$-{\it inconsistent} theory, which should include an axiom that only a super-polynomial-time machine can prove asymptotically over PA (or implies a super-polynomial-time computational upper bound) under some assumptions. This result is a kind of generalization of the result of ``Natural Proofs'' by Razborov and Rudich, who showed that to prove ``P$\not=$NP'' by a class of techniques called ``Natural Proofs'' implies a super-polynomial-time (e.g., sub-exponential-time) algorithm that can break a typical cryptographic primitive, a pseudo-random generator. Our result also implies that any relativizable proof of P$\not=$NP requires the {\it resource unbounded version} of \PTM-$\omega$-{\it inconsistent} theory, $\omega$-{\it inconsistent} theory, which suggests another negative result by Baker, Gill and Solovay that no relativizable proof can prove ``P$\not=$NP'' in PA, which is a $\omega$-consistent theory.
Therefore, our result gives a unified view to the existing two major negative results on proving P$\not=$NP, Natural Proofs and relativizable proofs, through the two manners of characterization of PTM-$\omega$-consistency. We also show that the PTM-$\omega$-consistency of $T$ cannot be proven in any PTM-$\omega$-consistent theory $S$, where $S$ is a consistent PT-extension of $T$. That is, to prove the independence of P vs NP from $T$ by proving the PTM-$\omega$-consistency of $T$ requires a PTM-$\omega$-{\it inconsistent} theory, or implies a super-polynomial-time computational upper bound under some assumptions. This seems to be related to the results of Ben-David and Halevi and Kurz, O'Donnell and Royer, who showed that to prove the independence of P vs NP from PA using any currently known mathematical paradigm implies an extremely-close-to-polynomial-time (but still super-polynomial-time) algorithm that can solve NP-complete problems. Based on this result, we show that {\it the security of any computational cryptographic scheme is unprovable} in the setting where adversaries and provers are modeled as polynomial-time Turing machines and only a PTM-$\omega$-consistent theory is allowed to prove the security.

Safe Prime Generation with a Combined Sieve

A number $p$ is a safe prime if both $p$ and $(p-1)/2$ are prime.
This note describes a method of generating safe primes
that is considerably faster than repeatedly generating random
primes $q$ until $p=2q+1$ is also prime.

VMPC Stream Cipher

The VMPC Stream Cipher is a simple encryption algorithm, designed as a proposed practical application of the VMPC one-way function. The general structure of the Cipher is based on an internal 256-element permutation. The VMPC Cipher, together with its Key Scheduling Algorithm, were designed in particular to eliminate some of the known weaknesses characteristic of the alleged RC4 keystream generator.

What do DES S-boxes Say to Each Other ?

DES is not only very widely implemented and used today, but triple DES and other derived schemes will probably still be around in ten or twenty years from now. We suggest that, if an algorithm is so widely used, its security should still be under scrutiny, and not taken for granted.
In this paper we study the S-boxes of DES. Many properties of these are already known, yet usually they concern one particular S-box. This comes from the known design criteria on DES, that strongly suggest that S-boxes have been chosen independently of each other.
On the contrary, we are interested in properties of DES S-boxes that concern a subset of two or more DES S-boxes. For example we study the properties related to Davies-Murphy attacks on DES, recall the known uniformity criteria to resist this attack, and discuss a stronger criterion.
More generally we study many different properties, in particular related to linear cryptanalysis and algebraic attacks. The interesting question is to know if there are any interesting properties that hold for subsets of S-boxes bigger than 2. Such a property has already been shown by Shamir at Crypto'85 (and independently discovered by Franklin), but Coppersmith et al. explained that it was rather due to the known S-box design criteria. Our simulations confirm this, but not totally.
We also present several new properties of similar flavour.
These properties come from a new type of algebraic attack on block ciphers that we introduce. What we find is not easily explained by the known S-box design criteria, and the question should be asked if the S-boxes of DES are related to each other, or if they follow some yet unknown criteria.
Similarly, we also found that the s5DES S-boxes have an unexpected common structure that can be exploited in a certain type of
generalised linear attack. This fact substantially decreases the credibility of s5DES as a DES replacement.
This paper has probably no implications whatsoever on the security of DES.

Certificate-Based Encryption and the Certificate Revocation Problem

We introduce the notion of certificate-based encryption. In this model, a certificate -- or, more generally, a signature -- acts not only as a certificate but also as a decryption key. To decrypt a message, a keyholder needs both its secret key and an up-to-date certificate from its CA (or a signature from an authorizer). Certificate-based encryption combines the best aspects of identity-based encryption (implicit certification) and public key encryption (no escrow). We demonstrate how certificate-based encryption can be used to construct an efficient PKI requiring less infrastructure than previous proposals, including Micali's Novomodo, Naor-Nissim and Aiello-Lodha-Ostrovsky.

Chosen-Ciphertext Security from Identity-Based Encryption

We show how to construct a CCA-secure public-key encryption scheme
from any CPA-secure identity-based encryption (IBE) scheme. Our
conversion from IBE to a CCA-secure scheme is simple,
efficient, and provably secure in the standard model (i.e., security
of the resulting scheme does not rely on the random oracle model).
In addition, the resulting scheme achieves CCA security even if the
underlying IBE scheme satisfies only a ``weak'' notion of security
which is known to be achievable in the standard model based on the
bilinear Diffie-Hellman assumption. Thus, our results yield a new
construction of CCA-secure public-key encryption in the
standard model. Interestingly, the resulting scheme avoids any
non-interactive proofs of ``well-formedness'' which were shown to
underlie all previously-known constructions.
We also extend our technique to obtain a simple and reasonably efficient
method for securing any BTE scheme against adaptive chosen-ciphertext
attacks. This, in turn, yields more efficient constructions of CCA-secure
(hierarchical) identity-based and forward-secure encryption schemes in the
standard model.
Our results --- building on previous black-box separations ---
rule out black-box constructions of IBE from CPA-secure public-key encryption.

On the Security of Multiple Encryption or CCA-security+CCA-security=CCA-security?

In a practical system, a message is often encrypted more than once
by different encryptions, here called multiple encryption, to
enhance its security. Additionally, new features may be achieved
by multiple encrypting a message for a scheme, such as the
key-insulated cryptosystems \cite{DKXY02} and anonymous channels
\cite{Cha81}. Intuitively, a multiple encryption should remain
``secure'', whenever there is one component cipher unbreakable in
it. In NESSIE's latest Portfolio of recommended cryptographic
primitives (Feb. 2003), it is suggested to use multiple encryption
with component ciphers based on different assumptions to acquire
long term security. However, in this paper we show this needs
careful discussion. Especially, this may \emph{not} be true
according to (adaptive) chosen ciphertext attack ({\sf CCA}), even
with all component ciphers {\sf CCA} secure. We define an extended
version of {\sf CCA} called \emph{chosen ciphertext attack for
multiple encryption} ({\sf ME-CCA}) to emulate real world partial
breaking of assumptions, and give constructions of multiple
encryption satisfying {\sf ME-CCA} security. Since {\sf CCA}
security seems so stringent, we further relax it by introducing
\emph{weak} {\sf ME-CCA} ({\sf ME-wCCA}), and prove {\sf
IND-ME-wCCA} secure multiple encryption can be acquired from {\sf
IND-gCCA} secure component ciphers. We also study the relation of
various security notions for multiple encryption. We then apply
these results to key-insulated cryptosystem. It is only previously
known in \cite{DKXY02} that a generic construction exists provably
secure against {\sf CPA} attack, however, we prove that this
generic construction is in fact secure against {\sf ME-wCCA} by
choosing all components {\sf IND-CCA} secure. We also give an
efficient generic construction of key-insulated cryptosystem,
which is so far the \emph{first} generic construction provably
secure against {\sf CCA} (in the random oracle model).

Parallelizing Explicit Formula for Arithmetic in the Jacobian of Hyperelliptic Curves

One of the recent thrust areas in research on hyperelliptic curve cryptography has been to obtain explicit formulae for performing arithmetic in the Jacobian of such curves. We continue this line of research by obtaining parallel versions of such formulae. Our first contribution is to develop a general methodology for obtaining parallel algorithm of any explicit formula. Any parallel algorithm obtained using our methodology is provably optimal in the number of multiplication rounds. We next apply this methodology to Lange's explicit formula for arithmetic in genus 2 hyperelliptic curve -- both for the affine coordinate and inversion free arithmetic versions. Since encapsulated add-and-double algorithm is an important countermeasure against side channel attacks, we develop parallel
algorithms for encapsulated add-and-double for both of Lange's versions of explicit formula. For the case of inversion free arithmetic, we present parallel algorithms using 4, 8 and 12 multipliers. All parallel algorithms described in this paper are optimal in the number of parallel rounds. One of the conclusions from our work is the fact that the parallel version of inversion free arithmetic is more efficient than the parallel version of
arithmetic using affine coordinates.

VMPC One-Way Function

The VMPC function is a combination of two basic operations: permutation composition and integer addition. The function resulting from this combination shows to have very high resistance to inverting. Computational effort of about 2^260 operations is estimated to be required to invert the VMPC function. The value of the function can be computed with 3 elementary computer processor instructions per byte. An open question is whether the function's simplicity raises a realistic chance that the lower bound on the complexity of inverting it might be proved.

Constructing Optimistic Fair Exchange Protocols from Committed Signatures

In PODC 2003, Park et al. \cite{PCSR} first introduce a connection between fair exchange and sequential two-party
multi-signature scheme and provide a novel method of constructing fair exchange protocol by distributing the computation
of RSA signature. This approach avoids the design of verifiable encryption scheme at the expense of having co-signer
store a piece of prime signer's secret key. Dodis and Reyzin \cite{DR} showed that the protocol in \cite{PCSR} is totally
breakable in the registration phase, then presented a remedy scheme which is provably secure in the random oracle model,
by utilizing Boldyreva non-interactive two-party multi-signature scheme \cite{Bo}. Security in the random oracle model
does not imply security in the real world. In this paper, we provide the first two efficient committed signatures which
are provably secure in the standard complexity model from strong RSA assumption. Then we construct efficient optimistic
fair exchange protocols from those new primitives.

Building Secure Cryptographic Transforms, or How to Encrypt and MAC

We describe several notions of ``cryptographic transforms,''
symmetric schemes designed to meet a variety of privacy and
authenticity goals. We consider goals, such as replay-avoidance and
in-order packet delivery, that have not been fully addressed in
previous works in this area. We then provide an analysis of
possible ways to combine standard encryption and message
authentication schemes in order to provably meet these
goals. Our results further narrow the gap between
the provable-security results from the theoretical community and the
needs of developers who implement real systems.

Patterson-Wiedemann Construction Revisited

In 1983, Patterson and Wiedemann constructed Boolean functions on
$n = 15$ input variables having nonlinearity strictly greater than
$2^{n-1} - 2^{\frac{n-1}{2}}$. Construction of Boolean functions on
odd number of variables with such high nonlinearity was not known earlier and also till date no other construction method of such functions are known. We note that the Patterson-Wiedemann construction can be understood in terms of interleaved sequences as introduced by Gong in 1995 and subsequently these functions can be described as repetitions of a particular binary string. As example we elaborate the cases for $n = 15, 21$. Under this framework, we map the problem of finding Patterson-Wiedemann functions into a problem of solving a system of linear inequalities over the set of integers and provide
proper reasoning about the choice of the orbits. This, in turn, reduces the search space. Similar analysis also reduces the complexity of calculating autocorrelation and generalized nonlinearity for such functions. In an attempt to understand the above construction from the group theoretic view point, we characterize the group of all $GF(2)$-linear transformations of $GF(2^{ab})$ which acts on $PG(2,2^a)$.

Double-Speed Safe Prime Generation

Safe primes are prime numbers of the form $p=2\/q+1$ where $q$ is
prime. This note introduces a simple method for doubling the speed
of safe prime generation. The method is particularly suited to
settings where a large number of RSA moduli must be generated.

Relaxing Chosen-Ciphertext Security

Security against adaptive chosen ciphertext attacks (or, CCA security) has been accepted as the standard requirement from encryption schemes that need to withstand active attacks. In particular, it is regarded as the appropriate security
notion for encryption schemes used as components within general protocols and applications. Indeed, CCA security was shown to suffice in a large variety of contexts. However, CCA security often appears to be somewhat {\em too strong:} there exist encryption schemes (some of which come up naturally in practice) that are not CCA secure, but seem sufficiently secure ``for most practical purposes.''
We propose a relaxed variant of CCA security, called {\sf Replayable CCA (RCCA)} security. RCCA security accepts as secure the non-CCA (yet arguably secure) schemes mentioned above; furthermore, it suffices for most existing applications of CCA security.
We provide three formulations of RCCA security. The first one follows the spirit of semantic security and is formulated via an ideal functionality in the universally composable security framework. The other two are formulated following the indistinguishability and non-malleability approaches,
respectively. We show that the three formulations are equivalent in most interesting cases.

Domain Extender for Collision Resistant Hash Functions: Improving Upon Merkle-Damgaard Iteration

We study the problem of securely extending the domain of a collision resistant compression
function. A new construction based on directed acyclic graphs is described. This generalizes
the usual iterated hashing constructions. Our main contribution is to introduce a new technique
for hashing arbitrary length strings. Combined with DAG based hashing, this
technique gives a new hashing algorithm. The amount of padding and the number of invocations of the
compression function required by the new algorithm is smaller than the general \MD algorithm.
Lastly, we describe the design of a new parallel hash algorithm.

NAEP: Provable Security in the Presence of Decryption Failures

We consider the impact of the possibility of decryption failures in proofs of security for padding schemes, where these failures are both message and key dependent. We explain that an average case failure analysis is not necessarily sufficient to achieve provable security with existing CCA2-secure schemes. On a positive note, we introduce NAEP, an efficient padding scheme similar to PSS-E designed especially for the NTRU one-way function. We show that with this padding scheme we can prove security in the presence of decryption failures, under certain explicitly stated assumptions. We also discuss the applicability of proofs of security to instantiated cryptosystems in general, introducing a more practical notion of cost to describe the power of an adversary.

Scalable Protocols for Authenticated Group Key Exchange

We consider the fundamental problem of authenticated group key
exchange among $n$ parties within a larger and insecure public
network. A number of solutions to this problem have been proposed;
however, all provably-secure solutions thus far are not scalable and,
in particular, require $O(n)$ rounds. Our main contribution is the
first {\em scalable} protocol for this problem along with a rigorous
proof of security in the standard model under the DDH assumption;
our protocol uses a constant number of rounds and requires only $O(1)$
``full'' modular exponentiations per user. Toward this goal and of
independent interest, we first present a scalable compiler that
transforms any group key-exchange protocol secure against a passive
eavesdropper to an \emph{authenticated} protocol which is secure
against an active adversary who controls all communication in the
network. This compiler adds only one round and $O(1)$ communication
(per user) to the original scheme. We then prove secure --- against a
passive adversary --- a variant of the two-round group key-exchange
protocol of Burmester and Desmedt. Applying our compiler to this
protocol results in a provably-secure three-round protocol for
\emph{authenticated} group key exchange which also achieves
forward secrecy.

HARPS: HAshed Random Preloaded Subset Key Distribution

In this paper, we introduce HAshed Random Preloaded Subset (HARPS)
key distribution, a scalable key predistribution scheme employing
only symmetric crypto primitives. HARPS is ideally suited for
resource constrained nodes that need to operate without a trusted authority (TA) for extended periods (as is the case for nodes
forming mobile ad hoc networks (MANETs)). The performance of HARPS is compared with that of two other key predistribution schemes. The first, RPS, is a based on random intersection
of keys preloaded in nodes. The second, is (a slight modification to) a scheme proposed by Leighton and Micali (LM). HARPS is a generalization of both RPS and LM. All the three schemes, rely on some degree of resistance to hardware tampering, and have probabilistic measures for the ``merit'' of the system. The merit of the schemes is a function of the probability that an attacker who has compromised N nodes (or has access to keys buried in N nodes) can ``eavesdrop'' on a conversation between R nodes (R=2 for unicast communications). We analyze and compare the performance of the three schemes for unicast and multicast communications.
We show that HARPS has significant performance advantage over SIMS and LM.

Properties of the Transformation Semigroup of the Solitaire Stream Cipher

Stream ciphers are often used in applications where high speed and low delay are a requirement. The Solitaire stream cipher was developed by B. Schneier as a paper-and-pencil cipher. Solitaire gets its security from the inherent randomness in a shuffled deck of cards. In this paper we investigate semigroups and groups properties of the Solitaire stream cipher and its regular modifications.

Robust discretization, with an application to graphical passwords

When data or the processing on the data have some uncertainty, discretization of those data can lead to significantly different output.
For example, in certain graphical password schemes, a slight
uncertainty in the clicking places can produce a different password.
We present a discretization method, called robust discretization,
which gives stable outputs in the presence of uncertainties.
Robust discretization enables us to implement graphical password schemes
that are much more flexible and versatile than previously know ones.

Identity-based Chameleon Hash and Applications

Uncategorized

Uncategorized

Chameleon signatures are non-interactive signatures based on a hash-and-sign para\-digm, and similar in efficiency to regular signatures. The distinguishing characteristic of chameleon signatures is that their are non-transferable, with only the designated recipient capable of asserting its validity. In
this paper, we introduce the first identity-based chameleon hash function.
The general advantages of identity-based cryptography over conventional schemes
relative to key distribution are even more pronounced in a chameleon hashing scheme, because the owner of a public key does not necessarily need to retrieve the associated secret key.
We use the identity-based chameleon hashing scheme to build the id-based chameleon signature and a novel sealed-bid auction scheme that is robust, communication efficient (bidders send a single message), and secure under a particular trust model.

A reduction of the space for the parallelized Pollard lambda search on elliptic curves over prime finite fields and on anomalous binary elliptic curves

Let $E$ be an elliptic curve defined over a prime finite field
$F_p$ by a Weierstrass equation. In this paper we introduce a new
partition of $E(F_p)$ into classes which are generally larger than
$\{\pm R\}$. We give an effective procedure to compute
representatives of such classes. So one can iterate the
pseudorandom function, related to a discrete logarithm problem in
$E(F_p)$, on the set of representatives of classes and get
probably some speed up in computing discrete logarithms. The
underlying idea how to enlarge known classes on anomalous binary
elliptic curves is given.