All papers (Page 233 of 23853 results)
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 the elliptic-curve double-and-add
multiplication of a public base point by a secret ,
we show that allowing an adversary access to the projective
representation of results in information being revealed about .
Such access might be granted to an adversary by a poor
software implementation that does not erase the
coordinate of from the computer's memory or by a computationally-constrained secure token that
sub-contracts the affine conversion of 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
after the affine conversion or, alternatively,
randomize 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)- -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- -consistency, of a formal theory. Informally speaking, PTM- -consistency is a {\it polynomial-time bounded} version (in asymptotic proofs) of -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- -consistency is equivalent to -consistency, and (2) (in the light of {\it asymptotic proofs by PTM})
a PTM- -{\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 NP (more generally, any super-polynomial-time lower bound in PSPACE) is unprovable in a PTM- -consistent theory }, where is a consistent PT-extension of PA (although this paper does not show that P NP is unprovable in PA, since PA has not been proven to be PTM- -consistent). This result implies that to prove P NP by any technique requires a PTM- -{\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 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 NP requires the {\it resource unbounded version} of \PTM- -{\it inconsistent} theory, -{\it inconsistent} theory, which suggests another negative result by Baker, Gill and Solovay that no relativizable proof can prove ``P NP'' in PA, which is a -consistent theory.
Therefore, our result gives a unified view to the existing two major negative results on proving P NP, Natural Proofs and relativizable proofs, through the two manners of characterization of PTM- -consistency. We also show that the PTM- -consistency of cannot be proven in any PTM- -consistent theory , where is a consistent PT-extension of . That is, to prove the independence of P vs NP from by proving the PTM- -consistency of requires a PTM- -{\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- -consistent theory is allowed to prove the security.
Safe Prime Generation with a Combined Sieve
A number is a safe prime if both and are prime.
This note describes a method of generating safe primes
that is considerably faster than repeatedly generating random
primes until 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
input variables having nonlinearity strictly greater than
. 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 . 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 -linear transformations of which acts on .
Double-Speed Safe Prime Generation
Safe primes are prime numbers of the form where 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 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 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
``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 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 be an elliptic curve defined over a prime finite field
by a Weierstrass equation. In this paper we introduce a new
partition of into classes which are generally larger than
. 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
, 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.
Commitment Capacity of Discrete Memoryless Channels
In extension of the bit commitment task and following work initiated by Crepeau and Kilian, we introduce and solve the problem of characterising the optimal rate at which a discrete memoryless channel can be used for bit commitment. It turns out that the answer is very intuitive: it is the maximum equivocation of the channel (after removing trivial redundancy), even when unlimited noiseless bidirectional side communication is allowed.
By a well-known reduction, this result provides a lower bound on the channel's capacity for implementing coin tossing, which we conjecture to be an equality.
The method of proving this relates the problem to Wyner's wire--tap channel in an amusing way. We also discuss extensions to quantum channels.
Identity-Based Threshold Decryption
In this paper, we examine issues related to the construction of
identity-based threshold decryption schemes and argue that it is
important in practice to design an identity-based threshold
decryption scheme in which a private key associated with an
identity is shared. A major contribution of this paper is to
construct the first identity-based threshold decryption scheme
secure against chosen ciphertext attack. A formal proof of
security of the scheme is provided in the random oracle model,
assuming the Bilinear Diffie-Hellman problem is computationally
hard. Another contribution of this paper is, by extending the
proposed identity-based threshold decryption scheme, to construct
a mediated identity-based encryption scheme secure against more
powerful attacks than those considered previously.
Multipurpose Identity-Based Signcryption : A Swiss Army Knife for Identity-Based Cryptography
A combined Identity-Based Signature/Encryption system with multiple security properties is presented. The scheme allows Alice to sign a message and encrypt it for Bob ("confidentiality") in such a way that the ciphertext does not reveal anything about their identities ("anonymity"); upon receipt, Bob is convinced that he is Alice's intended addressee ("authentication") but is unable to prove this to a third party ("unlinkability"); nevertheless, the decrypted message bears a signature by Alice that anyone can verify ("non-repudiation"). The construction is based on the Bilinear Diffie-Hellman assumption, and proved secure in the random oracle model.
Cryptanalysis of the Alleged SecurID Hash Function
The SecurID hash function is used for authenticating users to a
corporate computer infrastructure. We analyse an alleged
implementation of this hash function. The block cipher at the
heart of the function can be broken in few milliseconds on a PC
with 70 adaptively chosen plaintexts. The 64-bit secret key of
10 of the cards can be discovered given two months of token
outputs and analysis steps. A larger fraction of cards
can be covered given more observation time.
Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology
The goals of this paper are three-fold. First we introduce and
motivate a generalization of the fundamental concept of the
indistinguishability of two systems, called indifferentiability.
This immediately leads to a generalization of the related notion of
reducibility of one system to another.
Second, we prove that indifferentiability is the necessary and
sufficient condition on two systems S and T such that the security
of any cryptosystem using T as a component is not affected when T is
substituted by S. In contrast to indistinguishability,
indifferentiability is applicable in settings where a possible
adversary is assumed to have access to additional information about
the internal state of the involved systems, for instance the public
parameter selecting a member from a family of hash functions.
Third, we state an easily verifiable criterion for a system U not to
be reducible (according to our generalized definition) to another
system V and, as an application, prove that a random oracle is not
reducible to a weaker primitive, called asynchronous beacon, and
also that an asynchronous beacon is not reducible to a finite-length
random string. Each of these irreducibility results alone implies
the main theorem of Canetti, Goldreich and Halevi stating that there
exist cryptosystems that are secure in the random oracle model but
for which replacing the random oracle by any implementation leads to
an insecure cryptosystem.
A More Secure and Efficacious TTS Signature Scheme
In 2002 the new genre of digital signature scheme TTS (Tame Transformation Signatures) is introduced along with a sample scheme TTS/2. TTS is from the family of multivariate cryptographic schemes to which the NESSIE primitive {SFLASH} also belongs. It is a realization of Moh's theory for digital signatures, based on Tame Transformations or Tame Maps. Properties of multivariate cryptosystems are determined mainly by their central maps. TTS uses Tame Maps as their central portion for even greater speed than -related schemes (using monomials in a large field for the central portion), previously usually acknowledged as fastest. We show a small flaw in TTS/2 and present an improved TTS implementation which we call TTS/4. We will examine in some detail how well TTS/4 performs, how it stands up to previously known attacks, and why it represents an advance over TTS/2. Based on this topical assessment, we consider TTS in general and TTS/4 in particular to be competitive or superior in several aspects to other schemes, partly because the theoretical roots of TTS induce many good traits. One specific area in which TTS/4 should excel is in low-cost smartcards. It seems that the genre has great potential for practical deployment and deserves further attention by the cryptological community.
An efficient variant of the RSA cryptosystem
We describe an efficient combination of two variants of RSA cryptosystem (MPrime and Rebalanced RSA) analysed by Boneh and Schacham. The decryption process resultant is (for 2048-bits moduli) about 8 times faster than that presented by Quisquater and Couvreur and about 27 times faster than original cryptosystem.
A Sufficient Condition and Optimal Domain Extension of UOWHF
Uncategorized
Uncategorized
Here, we present how one can extend domain of a given Hash Family. We will give a sufficient condition for UOWHF-preserving domain extension (the extended Hash Family is UOWHF whenever the base Hash Family is UOWHF). We present also a binary tree based parallel algorithm for extending the domain of a UOWHF whose key-length expansion is optimum in a sub-class of binary tree based domain extension algorithm. We will show the optimality under an assumption.
Some RSA-based Encryption Schemes with Tight Security Reduction
In this paper, we study some RSA-based semantically secure encryption schemes (IND-CPA) in the standard model.
We first derive the exactly tight one-wayness
of Rabin-Paillier encryption scheme
which assumes that factoring Blum integers is hard.
We next propose the first IND-CPA scheme
whose one-wayness is equivalent to factoring {\it general}
(not factoring Blum integers).
Our reductions of one-wayness are very tight
because they require only one decryption-oracle query.
Efficient Provably Secure Public Key Steganography
Uncategorized
Uncategorized
We construct \emph{efficient} public key steganographic schemes, without resort to any peculiar
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 designing a new primitive called -codes.
A Formal Proof of Zhu's Signature Scheme
Uncategorized
Uncategorized
Following from the remarkable works of Cramer and Shoup \cite{CS}, three trapdoor hash signature variations have been
presented in the literature: the first variation was presented in CJE'01 by Zhu \cite{Zhu}, the second variation was
presented in SCN'02 by Camenisch and Lysyanskaya \cite{CL} and the third variation was presented in PKC'03 by Fischlin
\cite{Fis}. All three mentioned trapdoor hash signature schemes have similar structure and the security of the last two
modifications is rigorously proved. We point out that the distribution of variables derived from Zhu's signing oracle
is different from that generated by Zhu's signing algorithm since the signing oracle in Zhu's simulator is defined over
, instead of . Consequently the proof of security of Zhu's signature scheme should be studied more precisely.
We also aware that the proof of Zhu's signature scheme is not a trivial work which is stated below:
\begin{itemize}
\item the technique presented by Cramer and Shoup \cite{CS} cannot be applied directly to prove the security of Zhu's
signature scheme since the structure of Cramer-Shoup's trap-door hash scheme is double deck that is easy to simulate a
signing query as the order of subgroup is a public parameter;
\item the technique presented by Camenisch and
Lysyanskaya \cite{CL} cannot be applied directly since there are extra security parameters and guide the
statistical closeness of the simulated distributions to the actual distribution;
\item the technique presented by
Fischlin cannot be applied directly to Zhu's signature scheme as the security proof of Fischlin's signature relies on a
set of pairs while the security proof of Zhu's signature should rely on a set of
pairs .
\end{itemize}
In this report, we provide an interesting random argument technique to show that Zhu's signature scheme immune to
adaptive chosen-message attack under the assumptions of the strong RSA problem as well as the existence of collision
free hash functions.
ManTiCore: Encryption with Joint Cipher-State Authentication
We describe a new method for authenticated encryption, which uses
information from the internal state of the cipher to provide the
authentication. This methodology has a number of benefits. The
encryption has properties similar to CBC mode, yet the encipherment
and authentication mechanisms can be parallelized and/or
pipelined. The authentication overhead is minimal, so the
computational cost of the authenticated encryption is very nearly that
of the encryption process. Also, the authentication process remains
resistant against some IV reuse. We present a class of encryption
algorithms that are based on cryptographic hash functions. Because of
the hash function construction, the MTC4 class of methods supports
variable encryption block sizes up to twice the hash output block
length and trivially supports variable key lengths. We also provide a
more general construction for using the internal state of any
round-based block cipher as an authenticator. We give a concrete
example of the general construction that uses AES as the encryption
primitive. We provide performance measurements for all of our
constructions.
Attack on an Identification Scheme Based on Gap Diffie-Hellman Problem
In [KK], a new identification scheme based on the Gap Diffie-Hellman problem was proposed at SCIS 2002, and it is shown that the scheme is secure against active attacks under the Gap Diffie-Hellman Intractability Assumption. Paradoxically,this identification scheme is totally breakable under passive attacks. In this paper, we show that any adversary holding only public parameters of the scheme can convince a verifier with probability 1.
Optimal Statistical Power Analysis
A classical model is used for the power consumption of cryptographic devices. It is based on the Hamming distance of the data handled with regard to an unknown but constant reference state. Once validated experimentally it allows an optimal attack to be derived called Correlation Power Analysis. It also explains the defects of former approaches such as Differential Power Analysis.
Secret sharing schemes on sparse homogeneous access structures with rank three
One of the main open problems in secret sharing is the characterization of the ideal access structures. This problem has been studied for several families of access structures with similar results. Namely, in all these families, the ideal access structures coincide with the vector space ones and, besides, the optimal information rate of a non-ideal access structure is at most .
A first approach to the solution of that problem for the family of the -homogeneous access structures is made in this paper. First, we present an ideal -homogeneous access structure that is not vector space. Afterwards, we prove that the -homogeneous access structures that can be realized by a -vector space secret sharing scheme are {\em sparse\/}, that is, any subset of four participants contains at most two minimal qualified subsets. Finally, we solve the characterization problem for the family of the sparse -homogeneous access structures. Specifically, we completely characterize the ideal access structures in this family, we prove that they coincide with the -vector space ones and, besides, we demonstrate that there is no structure in this family having optimal information rate between and . That is, we establish that the properties that were previously proved for several families also hold for the family of the sparse -homogeneous access structures.
On the random-oracle methodology as applied to length-restricted signature schemes
In earlier work, we described a ``pathological'' example of a signature scheme that is secure in the random-oracle model, but for which no secure implementation exists. For that example, however, it was crucial that the scheme is able to sign "long messages" (i.e., messages whose
length is not a-priori bounded). This left open the possibility that
the Random Oracle Methodology is sound with respect to signature schemes
that sign only "short" messages (i.e., messages of a-priori bounded length, smaller than the length of the keys in use), and are "memoryless" (i.e., the only thing kept between different signature
generations is the initial signing-key). In this work, we extend our negative result to address such signature schemes. A key ingredient in our proof is a new type of interactive proof systems, which may be of independent interest.
Last updated: 2003-08-04
Forward-Secure Hierarchical ID-Based Cryptography
We present a forward-secure hierarchical identity-based encryption (FHIBE) scheme, which is based on the hierarchical identity-based encryption (HIBE) scheme by Gentry and Silverberg. Canetti, Halevi and Katz presented a forward-secure public key encryption scheme based on HIBE scheme. They give the formal definition of Binary Encryption Tree (BET), which is a relaxed version of HIBE and is essential to their forward-secure encryption.We unify their idea with HIBE scheme, and present a forward-secure hierarchical identity-based encryption scheme. In the FHIBE scheme, secret keys of each entity on the hierarchy are updated at regular intervals throughout the lifetime of the system; furthermore, exposure of an entity's secret key corresponding to a given interval does not enable an adversary to break the ancestors of the entity for any prior time period. Entities can join in the hierarchy at any time and at any position, and are able to update their secret keys on their own once they are initialized by their parent entities. These features are important in the distributed settings.
The forward-secure hierarchical identity-based encryption scheme can be generalized into a collusion resistant multiple hierarchical identity-based encryption (MHIBE) scheme, where a message can be encrypted under multiple identities of a user.
A Tweakable Enciphering Mode
We describe a block-cipher mode of operation, CMC, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m>=2. When the underlying block cipher is secure in the sense of a strong pseudorandom permutation (PRP), our scheme is secure in the sense of tweakable, strong PRP. Such an object can be used to encipher the sectors of a disk, in-place, offering security as good as can be obtained in this setting. CMC makes a pass of CBC encryption, xors in a mask, and then makes a pass of CBC decryption; no universal hashing, nor any other non-trivial operation beyond the block-cipher calls, is employed.
Besides proving the security of CMC we initiate a more general investigation of tweakable enciphering schemes, considering issues like the non-malleability of these objects.
A Parallelizable Enciphering Mode
We describe a block-cipher mode of operation, EME, that turns an
n-bit block cipher into a tweakable enciphering scheme that acts
on strings of mn bits, where m \in [1..n]. The mode is parallelizable, but as serial-efficient as the non-parallelizable mode CMC. EME can be used to solve the disk-sector encryption problem. The algorithm entails two layers of ECB encryption and a "lightweight mixing" in between. We prove EME secure, in the reduction-based sense of modern cryptography. We motivate some of the design choices in EME by showing that a few
simple modifications of this mode are insecure.
Breaking and Repairing Optimistic Fair Exchange from PODC 2003
In PODC 2003, Park, Chong, Siegel and Ray [PCSR03] proposed an optimistic protocol for fair exchange, based on RSA signatures. We show that their protocol is *totally breakable* already in the registration phase: the honest-but-curious arbitrator can easily determine the signer's secret key.
On a positive note, the authors of [PCSR03] informally introduced a connection between fair exchange and "sequential two-party multisignature schemes" (which we call two-signatures), but used an insecure two-signature scheme in their actual construction. Nonetheless, we show that this connection *can* be properly formalized to imply *provably secure* fair exchange protocols. By utilizing the state-of-the-art non-interactive two-signature of Boldyreva (PKC 2003), we obtain an efficient and provably secure (in the random oracle model) fair exchange protocol, which is based on GDH signatures of Boneh, Lynn and Shacham (Asiacrypt 2001).
Of independent interest, we introduce a unified model for non-interactive fair exchange protocols, which results in a new primitive we call *verifiably committed signatures*. Verifiably committed signatures generalize (non-interactive) verifiably encrypted signatures and two-signatures, both of which are sufficient for fair exchange.
Symmetric Authentication Within a Simulatable Cryptographic Library
Proofs of security protocols typically employ simple abstractions of
cryptographic operations, so that large parts of such proofs are
independent of cryptographic details. The typical abstraction is
the Dolev-Yao model, which treats cryptographic operations as a
specific term algebra. However, there is no cryptographic semantics,
i.e., no theorem that says what a proof with the Dolev-Yao
abstraction implies for the real protocol, even if provably secure
cryptographic primitives are used.
Recently we introduced an extension to the Dolev-Yao model for which
such a cryptographic semantics exists, i.e., where security is
preserved if the abstractions are instantiated with provably secure
cryptographic primitives. Only asymmetric operations (digital
signatures and public-key encryption) are considered so far. Here we
extend this model to include a first symmetric primitive,
message authentication, and prove that the extended model still has
all desired properties. The proof is a combination of a probabilistic,
imperfect bisimulation with cryptographic reductions and static
information-flow analysis.
Considering symmetric primitives adds a major complication to the
original model: we must deal with the exchange of secret keys, which
might happen any time before or after the keys have been used for
the first time. Without symmetric primitives only public keys need
to be exchanged.
ID-based tripartite key agreement with signatures
This paper proposes a new identity based tripartite key agreement protocol which is more efficient than the existing ID-based tripartite protocol. This protocol is based on the Joux's protocol for key agreement, and introduces signature along with key agreement to overcome man-in-the-middle attacks and to provide authentication. The new protocol resists existential forgeries against adaptively chosen message attacks under the random oracle model.
Elliptic curves suitable for pairing based cryptography
We give a method for constructing ordinary elliptic curves over finite
prime field with small security parameter with respect to
a prime dividing the group order such that .
A New Tree based Domain Extension of UOWHF
We present a new binary tree based parallel algorithm for extending the domain of a UOWHF. The key length expansion is m(t+O(log*(t))) bits. In particular, the key length expansion is 2m bits for t=2; m(t+1) bits for 3\leq t\leq 6 and m(t+2) bits for 7\leq t\leq 134, where m is the length of the message digest and t\geq 2 is the height of the binary tree. The previously best known binary tree algorithm required a key length expansion of m(t+[log_2 (t-1)]) bits. We also give a sufficient condition for valid domain extension in sequental domain extension.
General Composition and Universal Composability in Secure Multiparty Computation
\emph{Concurrent general composition} relates to a setting where a
secure protocol is run in a network concurrently with other,
arbitrary protocols. Clearly, security in such a setting is what is
desired, or even needed, in modern computer networks where many
different protocols are executed concurrently. Canetti (FOCS 2001)
introduced the notion of \emph{universal composability}, and showed
that security under this definition is sufficient for achieving
concurrent general composition. However, it is not known whether or
not the opposite direction also holds.
Our main result is a proof that security under concurrent general
composition, when interpreted in the natural way under the
simulation paradigm, is equivalent to a variant of universal
composability, where the only difference relates to the order of
quantifiers in the definition. (In newer versions of universal
composability, these variants are equivalent.) An important
corollary of this theorem is that existing impossibility results for
universal composability (for all its variants) are inherent for
definitions that imply security under concurrent general
composition, as formulated here. In particular, there are large
classes of two-party functionalities for which \emph{it is
impossible} to obtain protocols (in the plain model) that remain
secure under concurrent general composition. We stress that the
impossibility results obtained are not "black-box", and apply even
to non-black-box simulation.
Our main result also demonstrates that the definition of universal
composability is somewhat "minimal", in that the composition
guarantee provided by universal composability implies the definition
itself. This indicates that the security definition of universal
composability is not overly restrictive.
Trading-Off Type-Inference Memory Complexity Against Communication
While bringing considerable flexibility and extending the horizons
of mobile computing, mobile code raises major security issues.
Hence, mobile code, such as Java applets, needs to be analyzed
before execution. The byte-code verifier checks low-level security
properties that ensure that the downloaded code cannot bypass the
virtual machine's security mechanisms. One of the statically
ensured properties is {\sl type safety}. The type-inference phase
is the overwhelming resource-consuming part of the verification
process.
This paper addresses the RAM bottleneck met while verifying mobile
code in memory-constrained environments such as smart-cards. We
propose to modify classic type-inference in a way that
significantly reduces the memory consumption in the
memory-constrained device at the detriment of its distrusted
memory-rich environment.
The outline of our idea is the following, throughout execution,
the memory frames used by the verifier are MAC-ed and exported to
the terminal and then retrieved upon request. Hence a distrusted
memory-rich terminal can be safely used for convincing the
embedded device that the downloaded code is secure.
The proposed protocol was implemented on JCOP20 and JCOP30
Java cards using IBM's JCOP development tool.
On the Randomness of the Editing Generator
In their paper, G.Gong and S.Q.Jiang construct a new pseudo-random sequence generator by using two ternary linear feedback shift registers (LFSR). The new generator is called an editing generator which a combined model of the clock-controlled generator and the shrinking generator. For a special case (Both the base sequence and the control sequence are mm-sequence of degree ), the period, linear complexity, symbol distribution and security analysis are discussed in the same article. In this paper, we expand the randomness results of the edited sequence for general cases, we do not restrict the base sequence and the control sequence has the same length. For four special cases of this generator, the randomness of the edited sequence is discussed in detail. It is shown that for all four cases the editing generator has good properties, such as large periods, high linear complexities, large ratio of linear complexity per symbol, and small un-bias of occurrences of symbol. All these properties make it a suitable crypto-generator for stream cipher applications.
Permutation graphs, fast forward permutations, and
A permutation is a \emph{fast forward permutation} if for each
the computational complexity of evaluating is small
independently of and .
Naor and Reingold constructed fast
forward pseudorandom cycluses and involutions. By studying the
evolution of permutation graphs, we prove that the number of
queries needed to distinguish a random cyclus from a random
permutation in is if one does not use queries of
the form , but is only if one is allowed to
make such queries.
We construct fast forward permutations
which are indistinguishable from random
permutations even when queries of the form
are allowed.
This is done by introducing an efficient
method to sample the cycle structure of a
random permutation,
which in turn solves an open problem of Naor and Reingold.
Bernoulli numbers and the probability of a birthday surprise
A birthday surprise is the event that, given uniformly random
samples from a sample space of size , at least two of them are identical.
We show that Bernoulli numbers can be used to derive arbitrarily exact
bounds on the
probability of a birthday surprise.
This result can be used in arbitrary precision calculators, and it can
be applied to better understand some questions in
communication security and pseudorandom number
generation.
Efficient linear feedback shift registers with maximal period
We introduce and analyze an efficient family of linear
feedback shift registers (LFSR's) with maximal period.
This family is word-oriented and is suitable for implementation
in software, thus provides a solution to a recent challenge \cite{FSE94}.
The classical theory of LFSR's is extended to
provide efficient algorithms for generation of irreducible and primitive
LFSR's of this new type.
Collision Attack on Reduced-Round Camellia
Camellia is the final winner of 128-bit block cipher in NESSIE. In this paper, we construct some efficient distinguishers between 4-round Camellia and a random permutation of the blocks space. By using collision-searching techniques, the distinguishers are used to attack on 6,7,8 and 9 rounds of Camellia with 128-bit key and 8,9 and 10 rounds of Camellia with 192/256-bit key. The 128-bit key of 6 rounds
Camellia can be recovered with chosen plaintexts and
encryptions. The 128-bit key of 7 rounds Camellia can be
recovered with chosen plaintexts and encryptions. The 128-bit key of 8 rounds Camellia can be recovered with chosen plaintexts and encryptions. The 128-bit key of 9 rounds Camellia can be recovered with chosen plaintexts and encryptions. The 192/256-bit key of 8 rounds Camellia can be recovered with chosen plaintexts and encryptions. The 192/256-bit key of 9 rounds Camellia can be recovered with chosen plaintexts and encryptions.The 256-bit key of 10 rounds Camellia can be recovered with chosen plaintexts and encryptions.
Last updated: 2003-07-18
Direct Sum of Non Normal and Normal Bent Functions Always Produces Non Normal Bent Functions
Prof. Claude Carlet has pointed out an error in Theorem 1 of the
paper. The error could not be recovered for the time being.
Thus the statement presented in the title of the paper
is not proved.
Minimum Distance between Bent and 1-resilient Boolean Functions
In this paper we study the minimum distance between the set of bent functions and the set of 1-resilient Boolean functions and present a lower bound on that. The bound is proved to be tight for functions up to input variables. As a consequence, we present a strategy to modify the bent functions, by toggling some of its outputs, in getting a large class of -resilient functions with very good nonlinearity and autocorrelation. In particular, the technique is applied upto -variable functions and we show that the construction provides a large class of -resilient functions reaching currently best known nonlinearity and achieving very low autocorrelation values which were not known earlier. The technique is sound enough to theoretically solve some of the mysteries of -variable, -resilient functions with maximum possible nonlinearity. However, the situation becomes complicated from variables and above, where
we need to go for complicated combinatorial analysis with trial and error using computational facility.
Guaranteeing the diversity of number generators
A major problem in using iterative number generators of the
form is that they can enter unexpectedly short
cycles. This is hard to analyze when the generator is designed,
hard to detect in real time when the generator is used, and can
have devastating cryptanalytic implications. In this paper we
define a measure of security, called \emph{sequence diversity},
which generalizes the notion of cycle-length for non-iterative
generators. We then introduce the class of counter assisted
generators, and show how to turn any iterative generator (even a
bad one designed or seeded by an adversary) into a counter
assisted generator with a provably high diversity, without
reducing the quality of generators which are already
cryptographically strong.
Homomorphic public-key systems based on subgroup membership problems
We describe the group structure underlying several popular homomorphic public-key systems and the problems they are based on. We prove several well-known security results using only the group structure and assumptions about the related problems.
Then we provide examples of two new instances of this group structure and analyse their security.
On the Pseudorandomness of KASUMI Type Permutations
KASUMI is a block cipher which has been adopted as a standard of 3GPP. In this paper, we study the pseudorandomness of idealized KASUMI type permutations for adaptive adversaries. We show that
the four round version is pseudorandom and the six round version is super-pseudorandom.
Attack on Han et al.'s ID-based Confirmer (Undeniable) Signature at ACM-EC'03
Uncategorized
Uncategorized
At the fourth ACM conference on electronic commerce
(EC'03), S. Han, K.Y. Yeung and J. Wang proposed an ID-based
confirmer signature scheme using pairings (actually, this is an
ID-based undeniable signature scheme). However, in this paper, we
will show that this signature scheme is not secure. The signer can
deny any signature, even this signature is his valid signature and
any one can forge a valid confirmer signature of a signer with
identity ID on an arbitrary message and confirm this signature to
the verifier.
Weak Fields for ECC
We demonstrate that some finite fields, including GF(2^210) are weak for elliptic curve cryptography in the sense that any instance of the elliptic curve discrete logarithm problem for any elliptic curve over these fields can be solved in significantly less time than it takes Pollard's rho method to solve the hardest instances. We discuss the implications of our observations to elliptic curve cryptography, and list some open problems.
Using Information Theory Approach to Randomness Testing
Uncategorized
Uncategorized
We address the problem of detecting deviations of binary sequence
from randomness,which is very important for random number (RNG)
and pseudorandom number generators (PRNG). Namely, we consider a
null hypothesis that a given bit sequence is generated by
Bernoulli source with equal probabilities of 0 and 1 and the
alternative hypothesis that the sequence is generated by a
stationary and ergodic source which differs from the source under
. We show that data compression methods can be used as a
basis for such testing and describe two new tests for randomness,
which are based on ideas of universal coding. Known statistical
tests and suggested ones are applied for testing PRNGs, which are
practically used. Those experiments show that the power of the new
tests is greater than of many known algorithms.
Certificateless Public Key Cryptography
This paper introduces the concept of 'certificateless public
key cryptography' (CL-PKC). In contrast to traditional public key
cryptographic systems, CL-PKC does not require the use of
certificates to guarantee the authenticity of public keys. It does
rely on the use of a trusted third party (TTP) who is in
possession of a master key. In these respects, CL-PKC is similar
to identity-based public key cryptography (ID-PKC). On the other
hand, CL-PKC does not suffer from the key escrow property that
seems to be inherent in ID-PKC. Thus CL-PKC can be seen as a model
for the use of public key cryptography that is intermediate
between traditional certificated PKC and ID-PKC.
We make concrete the concept of CL-PKC by introducing
certificateless public key encryption (CL-PKE), signature and key
exchange schemes. We also demonstrate how hierarchical CL-PKC can
be supported. The schemes are all derived from pairings on
elliptic curves. The lack of certificates and the desire to prove
the schemes secure in the presence of an adversary who has access
to the master key requires the careful development of new security
models. For reasons of brevity, the focus in this paper is on the
security of CL-PKE. We prove that our CL-PKE scheme is secure in a
fully adaptive adversarial model, provided that an underlying
problem closely related to the Bilinear Diffie-Hellman Problem is
hard.
Algebraic Attacks on Combiners with Memory and Several Outputs
Algebraic attacks on stream ciphers proposed by Courtois et al. recover the key by solving an overdefined system of multivariate equations. Such attacks can break several interesting cases of LFSR-based stream ciphers, when the output is obtained by a Boolean function. As suggested independently by Courtois and Armknecht, this approach can be successfully extended also to combiners with memory, provided the number of memory bits is small. At Crypto 2003, Krause and Armknecht show that, for ciphers built with LFSRs and an arbitrary combiner using a subset of k LFSR state bits, and with l memory bits, a polynomial attack always do exist when k and l are fixed. Yet this attack becomes very quickly impractical: already when k and l exceed about 4. In this paper we give a much simpler proof of this result and prove a more general theorem. We show that much faster algebraic attacks exist for any cipher that (in order to be fast) outputs several bits at a time. In practice our results substantially reduce the complexity of the best attack known on four well known constructions of stream ciphers when the number of outputs is increased. We present attacks on modified versions of Snow, E0, LILI-128, Turing, and some other ciphers.
A General Correlation Theorem
In 2001, Nyberg proved three important correlation theorems and applied
them to several cryptanalytic contexts. We continue the work of Nyberg in a more theoretical direction. We consider a general functional form and obtain its Walsh transform. Two of Nyberg's correlation theorems are seen to be special cases of our general functional form. S-box look-up, addition modulo and X-OR are three frequently occuring operations in the design of symmetric ciphers. We consider two methods of combining these operations and in each apply our main result to obtain the Walsh transform.
Assessing security of some group based cryptosystems
One of the possible generalizations of the discrete logarithm
problem to arbitrary groups is the so-called conjugacy search
problem. The computational difficulty of this problem in some
particular groups has been used in several group based cryptosystems.
Recently, a few preprints have been in circulation that suggest
various heuristic attacks on the conjugacy search problem.
The goal of the present survey is to stress a (probably well known)
fact that these heuristic attacks alone are not a threat to the
security of a cryptosystem, and, more importantly, to suggest a more
credible approach to assessing security of group based cryptosystems.
Such an approach should be necessarily based on the concept of the
average case complexity (or expected running time) of an algorithm.
These arguments support the following conclusion: although it is
generally feasible to base the security of a cryptosystem on the
difficulty of the conjugacy search problem, the group itself
(the ``platform") has to be chosen very carefully. In particular,
experimental as well as theoretical evidence collected so far
makes it appear likely that braid groups are not a good choice
for the platform. We also reflect on possible replacements.
Cryptanalysis of Al-Riyami-Paterson's Authenticated Three Party Key Agreement Protocols
Recently, Al-Riyami and Paterson proposed four authenticated tripartite key agreement protocols which make use of Weil pairing. In this paper, we show that the protocols are insecure against the man-in-the middle attack, key compromise impersonation attack and several known-key attacks.
A Cryptographically Sound Security Proof of the Needham-Schroeder-Lowe Public-Key Protocol
We present the first cryptographically sound security proof of the
well-known Needham-Schroeder-Lowe public-key protocol. More precisely,
we show that the protocol is secure against arbitrary active attacks
if it is implemented using provably secure cryptographic primitives.
Although we achieve security under cryptographic definitions, our
proof does not have to deal with probabilistic aspects of cryptography
and is hence in the scope of current proof tools. The reason is that
we exploit a recently proposed ideal cryptographic library, which has
a provably secure cryptographic implementation. Besides establishing
the cryptographic security of the Needham-Schroeder-Lowe protocol, our
result also exemplifies the potential of this cryptographic library
and paves the way for cryptographically sound verification of security
protocols by means of formal proof tools.
Physically Observable Cryptography
Complexity-theoretic cryptography considers only abstract notions of computation, and hence cannot protect against attacks that exploit the information leakage (via electromagnetic fields, power consumption, etc.) inherent in the physical execution of any cryptographic algorithm. Such "physical observation attacks" bypass the impressive barrier of mathematical security erected so far, and successfully break mathematically impregnable systems. The great practicality and the inherent availability of physical attacks threaten the very relevance of complexity-theoretic security.
To respond to the present crisis, we put forward physically observable cryptography: a powerful, comprehensive, and precise model for defining and delivering cryptographic security against an adversary that has access to information leaked from the physical execution of cryptographic algorithms.
Our general model allows for a variety of adversaries. In this paper, however, we focus on the strongest possible adversary, so as to capture what is cryptographically possible in the worst possible, physically observable setting. In particular, we
-- consider an adversary that has full (and indeed adaptive) access to any leaked information;
-- show that some of the basic theorems and intuitions of traditional cryptography no longer hold in a physically observable setting; and
-- construct pseudorandom generators that are provably secure against all physical-observation attacks.
Our model makes it easy to meaningfully restrict the power of our general physically observing adversary. Such restrictions may enable schemes that are more efficient or rely on weaker assumptions, while retaining security against meaningful physical observations attacks.
How Secure Are FPGAs in Cryptographic Applications?
Uncategorized
Uncategorized
The use of FPGAs for cryptographic applications is highly
attractive for a variety of reasons but at the same time there are
many open issues related to the general security of FPGAs. This
contribution attempts to provide a state-of-the-art description of
this topic. First, the advantages of reconfigurable hardware for
cryptographic applications are discussed from a systems
perspective. Second, potential security problems of FPGAs are
described in detail, followed by a proposal of a some
countermeasure. Third, a list of open research problems is
provided. Even though there have been many contributions dealing
with the algorithmic aspects of cryptographic schemes implemented
on FPGAs, this contribution appears to be the first comprehensive
treatment of system and security aspects.
Visual Crypto Displays Enabling Secure Communications
In this paper we describe a low-tech and user friendly solution for secure two-way communication between two parties over a network of untrusted devices. We present a solution in which displays play a central role. Our approach guarantees privacy and allows to check the authenticity of information presented on displays. Furthermore, we provide the user with a secure return channel. To this end we propose to provide every user with a small decryption display which is, for example, integrated in a credit card and requires very limited computing power. The authentication and security are based on visual cryptography which was first introduced by Naor and Shamir in 1994. We solve some practical shortcomings of traditional visual cryptography and develop protocols for two-way authentication and privacy in untrusted environments.
An identity-based ring signature scheme from bilinear pairings
At the conference Asiacrypt 2001, Rivest, Shamir and Tauman firstly addressed the concept of ring signature. In this paper we propose an identity-based ring signature scheme from bilinear pairings. As compared with the Zhang-Kim scheme (presented at the conference Asiacrypt 2002), our scheme is more efficient in computation and requires fewer pairing operations.
A New ID-based Group Signature Scheme from Bilinear Pairings
Uncategorized
Uncategorized
We argue that traditional ID-based systems from pairings seem unsuitable for designing group signature schemes due to the problem of key escrow. In this paper we propose new ID-based public key systems without trustful KGC from bilinear pairings. In our new ID-based systems, if dishonest KGC impersonates an honest user to
communicate with others, the user can provide a proof of treachery of the KGC afterwards, which is similar to CA-based systems. Furthermore, we propose a group signature scheme under the new systems, the security and performance of which rely on the new systems. The size of the group public key and the length of the signature are independent on the numbers of the group.
Cryptanalysis of ID-based Tripartite Authenticated Key Agreement Protocols
In this paper, we show that the Nalla-Reddy's one round ID-based tripartite authenticated key agreement protocols are still insecure against the man-in-the-middle attacks. We also break the Nalla's ID-based tripartite authenticated key agreement protocol with signatures.
Unifying Simulatability Definitions in Cryptographic Systems under Different Timing Assumptions
The cryptographic concept of simulatability has become a salient
technique for faithfully analyzing and proving security properties of
arbitrary cryptographic protocols. We investigate the relationship
between simulatability in synchronous and asynchronous frameworks by
means of the formal models of Pfitzmann et. al., which are seminal in
using this concept in order to bridge the gap between the
formal-methods and the cryptographic community. We show that the
synchronous model can be seen as a special case of the asynchronous
one with respect to simulatability, i.e., we present an embedding
between both models that we show to preserve simulatability. We show
that this result allows for carrying over lemmas and theorems that
rely on simulatability from the asynchronous model to its synchronous
counterpart without any additional work. Hence future work can
concentrate on the more general asynchronous case, without having to
neglect the analysis of synchronous protocols.
Security Analysis of Shim's Authenticated Key Agreement Protocols from Pairings
Recently, Shim proposed a tripartite authenticated key agreement protocol from Weil pairing to overcome the security flaw in Joux's protocol. Later, Shim also proposed an ID-based authenticated key agreement protocol which is an improvement of Smart's protocol in order to provide the forward secrecy. In this paper, we show that these two protocols are insecure against the key-compromise impersonation attack and the man-in-the-middle attack respectively.
Accumulating Composites and Improved Group Signing
Constructing practical and provably secure group signature schemes has been
a very active research topic in recent years. A group signature can be viewed
as a digital signature with certain extra properties. Notably, anyone can
verify that a signature is generated by a legitimate group member, while the
actual signer can only be identified (and linked) by a designated entity
called a group manager. Currently, the most efficient group signature scheme
available is due to Camenisch and Lysyanskaya \cite{CL02}. It is obtained
by integrating a novel dynamic accumulator with the scheme by
Ateniese, et al. \cite{ACJT00}.
In this paper, we construct a dynamic accumulator that
accumulates \emph{composites}, as opposed to previous accumulators that
accumulated \emph{primes}. We also present an efficient method for proving
knowledge of factorization of a committed value. Based on these (and other)
techniques we design a novel provably secure group signature scheme. It
operates in the \emph{common auxiliary string} model and offers two important
benefits: 1) the {\sf Join} process is very efficient: a new
member computes only a single exponentiation, and 2) the (unoptimized) cost of
generating a group signature is 17 exponentiations which is appreciably less than
the state-of-the-art.
Last updated: 2006-01-07
Further Cryptanalysis of some Proxy Signature Schemes
Uncategorized
Uncategorized
Proxy signature is a signature that an original signer delegates his or her signing capability to a proxy signer, and then the proxy signer creates a signature on behalf of the original signer. However, Sun et al.[7] showed that the proxy and multi-proxy signatures of Lee et al.[3], and the strong proxy signature scheme with proxy signer privacy protection of Shum et al.[6] are not against the original signer's forgery attack, so these schemes do not process the property of unforgeability. In this paper, we present an extensive forgery method on these schemes, which makes the forgery method of Sun et al.be a special case of ours.
Proposal on Personal Authentication System in which Biological Information is embedded in Cryptosystem Key
Biometric personal authentication systems have a common problem --- the biological information can easily be stolen by other individuals. In line with the process of the activities for the international standardization of the biometric system, this paper proposes a typical way to embed biological information, whatever its kind, into cryptographic keys as a measure for privacy protection and against unauthorized use. We believe that our proposal presents the following advantages: the improvement of protecting the privacy of biological information, economical effectiveness resulting from the practical use of the infrastructure of Public Key Infrastructure (PKI) as a biological information database, and humanity given to a man-machine interface by embedding an individual's biological information into a public key, an important element of the system. This paper also proposes how to build up a practical personal authentication system through the method proposed.
Crytanalysis of SAFER++
This paper presents several multiset and boomerang attacks on SAFER++ up to 5.5 out of its 7 rounds. These are the best known attacks for this cipher and significantly improve the previously known results. The attacks in the paper are practical up to 4 rounds. The methods developed to attack SAFER++ can be applied to other substitution-permutation networks with incomplete diffusion.
Novel Cyclic and Algebraic Properties of AES
Rijndael, or the Advanced Encryption Standard, is an interesting
cipher from a designer's viewpoint. Over the last few decades, the
most notable, and successful attacks against the best block
ciphers were linear and differential cryptanalysis. On the other
hand, Rijndael is designed from the ground up to resist these
attacks, as well as many others, by employing special algebraic
properties of its primitive operations. The byte inversion
operation over finite field was chosen by its
designer to thwart all possibly useful linear and difference
invariances, the basic ingredients of linear and differential
cryptanalysis. However, by using simple algebraic operations with
known properties, the combinations of them may possess many
interesting, and unexpected, algebraic properties that were not
known at design time. This paper presents such new unknown
properties on the combinations of primitive operations of AES.
Fujisaki-Okamoto IND-CCA hybrid encryption revisited
At Crypto'99, Fujisaki and Okamoto~\cite{FO99} presented a nice generic transformation from weak asymmetric and symmetric schemes into an IND-CCA hybrid encryption scheme in the Random Oracle Model.
From this transformation, two specific candidates to standardization were designed:
EPOC-2~\cite{EPOC} and PSEC-2~\cite{PSEC}, based on Okamoto-Uchiyama and El Gamal primitives, respectively.
Since then, several cryptanalysis of EPOC have been published, one in the Chosen Ciphertext Attack game and others making use of a poor implementation that is vulnerable to reject timing attacks.
The aim of this work is to avoid these attacks from the generic transformation, identifying the properties that an asymmetric scheme must hold to obtain a secure hybrid scheme.
To achieve this, some ambiguities in the proof of the generic transformation~\cite{FO99} are described, which can lead to false claims.
As a result the original conversion is modified and the range of asymmetric primitives that can be used is shortened.
In second place, the concept of {\it Easy Verifiable Primitive} is formalized, showing its connection with the Gap problems.
Making use of these ideas, a {\it new} security proof for the modified transformation is given.
The good news is that the reduction is {\it tight}, improving the concrete security claimed in the original work for the Easy Verifiable Primitives.
For the rest of primitives the concrete security is improved at the cost of stronger assumptions.
Finally, the resistance of the new conversion against reject timing attacks is
addressed.
CWC: A high-performance conventional authenticated encryption mode
We introduce CWC, a new block cipher mode of operation for protecting both the privacy and the authenticity of encapsulated data. CWC is currently the only such mode having all five of the following properties: provable security, parallelizability, high performance in hardware, high performance in software, and no intellectual property concerns. We believe that having all five of these properties makes CWC a powerful tool for use in many performance-critical cryptographic applications. CWC is also the only appropriate solution for some applications; e.g., standardization bodies like the IETF and NIST prefer patent-free modes, and CWC is the only such mode capable of processing data at 10Gbps in hardware, which will be important for future IPsec (and other) network devices. As part of our design, we also introduce a new parallelizable universal hash function optimized for performance in both hardware and software.
On Diophantine Complexity and Statistical Zero-Knowledge Arguments
We show how to construct practical honest-verifier statistical zero-knowledge \emph{Diophantine} arguments of knowledge (HVSZK AoK) that a committed tuple of integers belongs to an arbitrary language in bounded arithmetic. While doing this, we propose a new algorithm for computing the Lagrange representation of nonnegative integers and a new efficient representing polynomial for the exponential relation. We apply our results by constructing the most efficient known HVSZK AoK for non-negativity and the first constant-round practical HVSZK AoK for exponential relation. Finally, we propose the outsourcing model for cryptographic protocols and design communication-efficient versions of the Damgård-Jurik multi-candidate voting scheme and of the Lipmaa-Asokan-Niemi st-price auction scheme that work in this model.
New Proxy Signature, Proxy Blind Signature and Proxy Ring Signature Schemes from Bilinear Pairing
Uncategorized
Uncategorized
Proxy signatures are very useful tools when one needs to delegate
his/her signing capability to other party. After Mambo 's
first scheme was announced, many proxy signature schemes and
various types of proxy signature schemes have been proposed. Due
to the various applications of the bilinear pairings in
cryptography, there are many ID-based signature schemes have been
proposed. In this paper, we address that it is easy to design
proxy signature and proxy blind signature from the conventional
ID-based signature schemes using bilinear pairings, and give some
concrete schemes based on existed ID-based signature schemes. At
the same time, we introduce a new type of proxy signature -- proxy
ring signature, and propose the first proxy ring signature scheme
based on an existed ID-based ring signature scheme.
Security analysis on Nalla-Reddy's ID-based tripartite authenticated key agreement protocols
In this paper we propose security analysis on passive attack for
Nalla-Reddy's ID-AK-2 and ID-AK-3 protocols.
Length-Based Attacks for Certain Group Based Encryption Rewriting Systems
In this note, we describe a probabilistic attack on public key cryptosystems based on the word/conjugacy problems for finitely presented groups of the type proposed recently by Anshel, Anshel and Goldfeld. In such a scheme, one makes use of the property that in the given group the word problem has a polynomial time solution, while the conjugacy problem has no known polynomial solution. An example is the braid group from topology in which the word problem is solvable in polynomial time while the only known solutions to the conjugacy problem are exponential. The attack in this paper is based on having a canonical representative of each string relative to which a length function may be computed. Hence the term length attack. Such canonical representatives are known to exist for the braid group.
Last updated: 2003-05-27
Cryptanalysis of HFE
Out of the public key ( ) we recover a
polynomial of the same shape as the private polynomial. Then we give
an algorithm for solving such a special-form polynomial. This fact
puts an eavesdropper in the same position with a legitimate user in
decryption. An upper bound for the complexity of that all is
bit operations for the degree of the field
extension.
Protocols for Bounded-Concurrent Secure Two-Party Computation in the Plain Model
Until recently, most research on the topic of secure computation focused on the stand-alone model, where a single protocol execution takes place. In this paper, we construct protocols for the setting of {\em bounded-concurrent self composition}, where a (single) secure protocol is run many times concurrently, and there is a predetermined bound on the number of concurrent executions. In short, we show that {\em any} two-party functionality can be securely computed under bounded-concurrent self composition, in the {\sf plain model} (where the only setup assumption made is that the parties communicate via authenticated channels). Our protocol provides the first feasibility result for general two-party computation in the plain model, {\em for any model of concurrency}. All previous protocols assumed a trusted setup phase in order to obtain a common reference string. On the downside, the number of rounds of communication in our protocol is super-linear in the bound on the number of concurrent executions. However, we believe that our constructions will lead to more efficient
protocols for this task.
Algorithms in Braid Groups
Braid Groups have recently been considered for use in Public-Key
Cryptographic Systems. The most notable of these system has been the
Birman-Ko-Lee system presented at Crypto 2000. This article gives a brief introduction into braid groups and the hard problems on which public key systems have been defined. It suggests a canonical form max run form using the Artin generators and supplies some supporting algorithms necessary for cryptographic operations.
Side Channel Attacks on CBC Encrypted Messages in the PKCS#7 Format
Vaudenay has shown in [5] that a CBC encryption mode ([2], [9]) combined with the PKCS#5 padding [3] scheme allows an attacker to invert the underlying block cipher, provided she has access to a valid-padding oracle which for each input ciphertext tells her whether the corresponding plaintext has a valid padding or not. Having on mind the countermeasures against this attack, different padding schemes have been studied in [1]. The best one is referred to as the ABYT-PAD. It is designed for byte-oriented messages. It removes the valid-padding oracle, thereby defeating Vaudenay's attack, since all deciphered plaintexts are valid in this padding scheme. In this paper, we try to combine the well-known cryptographic message syntax standard PKCS#7 [8] with the use of ABYT-PAD instead of PKCS#5. Let us assume that we have access to a PKCS#7CONF oracle that tells us for a given ciphertext (encapsulated in the PKCS#7 structure) whether the deciphered plaintext is correct or not according to the PKCS#7 (v1.6) syntax. This is probably a very natural assumption, because applications usually have to reflect this situation in its behavior. It could be a message for the user, an API error message, an entry in the log file, different timing behavior, etc. We show that access to such an oracle again enables an attacker to invert the underlying block cipher. The attack requires single captured ciphertext and approximately 128 oracle calls per one ciphertext byte. It shows that we cannot hope to fully solve problems with side channel attacks on the CBC encryption mode by using a “magic” padding method or an obscure message-encoding format. Strong cryptographic integrity checks of ciphertexts should be incorporated instead.
Low Cost Security: Explicit Formulae for Genus 4 Hyperelliptic Curves
It is widely believed that genus four hyperelliptic curve
cryptosystems (HECC) are not attractive for practical applications
because of their complexity compared to systems based on lower
genera, especially elliptic curves. Our contribution shows that
for low cost security applications genus-4 hyperelliptic curves
(HEC) can outperform genus-2 HEC and that we can achieve a
performance similar to genus-3 HEC. Furthermore our implementation
results show that a genus-4 HECC is an alternative cryptosystem to
systems based on elliptic curves.
In the work at hand we present for the first time explicit
formulae for genus-4 HEC, resulting in a 60% speed-up compared to
the best published results. In addition we implemented genus-4
HECC on a Pentium4 and an ARM microprocessor. Our implementations
on the ARM show that for genus four HECC are only a factor of 1.66
slower than genus-2 curves considering group order ~2^{190}.
For the same group order ECC and genus-3 HECC are about
a factor of 2 faster than genus-4 curves on the ARM. The two most
surprising results are: 1) for low cost security application,
namely considering an underlying group of order 2^{128}, HECC
with genus 4 outperform genus-2 curves by a factor of 1.46 and has
similar performance to genus-3 curves on the ARM and 2) when
compared to genus-2 and genus-3, genus-4 HECC are better suited to
embedded microprocessors than to general purpose processors.
Secure Proxy Signature Schemes for Delegation of Signing Rights
A proxy signature scheme permits an entity to
delegate its signing rights to another entity. These schemes have
been suggested for use in numerous applications, particularly in
distributed computing. But to date, no proxy signature schemes
with guaranteed security have been proposed; no precise
definitions or proofs of security have been provided for such
schemes. In this paper, we formalize a notion of security for
proxy signature schemes and present provably-secure schemes. We
analyze the security of the well-known delegation-by-certificate
scheme and show that after some slight but important
modifications, the resulting scheme is secure, assuming the
underlying standard signature scheme is secure. We then show that
employment of the recently introduced aggregate signature schemes
permits bandwidth and computational savings. Finally, we analyze
the proxy signature scheme of Kim, Park and Won, which offers
important performance benefits. We propose modifications to this
scheme that preserve its efficiency, and yield a proxy signature
scheme that is provably secure in the random-oracle model, under
the discrete-logarithm assumption.