## All papers in 2004 (375 results)

New Distributed Ring Signatures for General Families of Signing Subsets

In a distributed ring signature scheme, a subset of users
cooperate to compute a distributed anonymous signature on a
message, on behalf of a family of possible signing subsets. The
receiver can verify that the signature comes from a subset of the
ring, but he cannot know which subset has actually signed.
In this work we use the concept of dual access structures to
construct a distributed ring signature scheme which works with
general families of possible signing subsets. The length of each
signature is linear on the number of involved users, which is
desirable for some families with many possible signing subsets.
The scheme achieves the desired properties of correctness,
anonymity and unforgeability. The reduction in the proof of
unforgeability is tighter than the reduction in the previous
proposals which work with general families.
We analyze the case in which our scheme runs in an identity-based
scenario, where public keys of the users can be derived from their
identities. This fact avoids the necessity of digital
certificates, and therefore allows more efficient implementations
of such systems. But our scheme can be extended to work in more
general scenarios, where users can have different types of keys.

Cryptanalysis of RCES/RSES Image Encryption Scheme

Recently, a chaos-based image encryption scheme called RCES (also called RSES) was proposed. This paper analyzes the security of RCES, and points out that it is insecure against the known/chosen-plaintext attacks: the number of required known/chosen plain-images is only one or two. In addition, the security of RCES against the brute-force attack was overestimated. Both theoretical and experimental analyses are given to show the performance of the suggested known/chosen-plaintext attacks. The insecurity of RCES is due to its special design, which makes it a typical example of insecure image encryption schemes. Some lessons are drawn from RCES to show some common principles for ensuring the high level of security of an image encryption scheme.

Efficient Pairing Computation on Supersingular Abelian Varieties

We present a general technique for the efficient computation of pairings on supersingular Abelian varieties. This formulation, which we call the eta pairing, generalises results of Duursma and Lee for computing the Tate pairing on supersingular elliptic curves in characteristic three.
We then show how our general technique leads to a new algorithm which is about twice as fast as the Duursma-Lee method.
These ideas are then used for elliptic and hyperelliptic curves in characteristic 2 with very efficient results. In particular, the hyperelliptic case is faster than all previously known pairing algorithms.

A general quantitative cryptanalysis of permutation-only multimedia ciphers against plaintext attacks

Uncategorized

Uncategorized

In recent years secret permutations have been widely used for protecting different types of multimedia data, including speech files, digital images and videos. Based on a general model of permutation-only multimedia ciphers, this paper performs a quantitative cryptanalysis on the performance of these kind of ciphers against plaintext attacks. When the plaintext is of size $M\times N$ and with $L$ different levels of values, the following quantitative cryptanalytic findings have been concluded under the assumption of a uniform distribution of each element in the plaintext: 1) all permutation-only multimedia ciphers are practically insecure against known/chosen-plaintext attacks in the sense that only $O(log_L(MN))$ known/chosen plaintexts are sufficient to recover not less than (in an average sense) half elements of the plaintext; 2) the computational complexity of the known/chosen-plaintext attack is only $O(n\cdot(MN)^2)$, where n is the number of known/chosen plaintexts used. When the plaintext has a non-uniform distribution, the number of required plaintexts and the computational complexity is also discussed. Experiments are given to demonstrate the real performance of the known-plaintext attack for a typical permutation-only image cipher.

Delegateable Signature Using Witness Indistinguishable and Witness Hiding Proofs

A delegateable signature scheme is a signature scheme where the
owner of the signing key(Alice) can securely delegate to another
party(Bob) the ability to sign on Alice's behalf on a restricted
subset $S$ of the message space. Barak first defined and
constructed this signature scheme using non-interactive
zero-knowledge proof of knowledge(NIZKPK)\cite{Barak}. In his
delegateable signature scheme, the function of NIZKPK is to
prevent the signing verifier from tell which witness(i.e.
restricted subset) is being used.
Witness indistinguishable(WI) and witness hiding(WH) proof systems
are weaker proof model than zero-knowledge proof and were proposed
by Feige and Shamir in \cite{FS}, however, the verifier cannot
also distinguish the witness which is being used in these two
protocols. In this paper, we construct delegateable signature
scheme using WI and WH proof protocols.

Last updated: 2005-02-04

On The Security of Two Key-Updating Signature Schemes

Uncategorized

Uncategorized

In ICICS 2004, Gonzalez-Deleito, Markowitch and Dall'Olio proposed an efficient strong key-insulated signature scheme. They claimed that it is (N-1,N)-key-insulated, i.e., the compromise of the secret keys for arbitrarily many time periods does not expose the secret keys for any of the remaining time periods. But in this paper, we demonstrate an attack and show that an adversary armed with the signing keys for any two time periods can compute the signing keys for the remaining time periods except for some very special cases. In a second attack, the adversary can forge signatures for many remaining time periods without computing the corresponding signing keys. Therefore it is only equivalent to a (1,N)-key-insulated signature scheme. A variant forward-secure signature scheme was also presented in ICICS 2004 and claimed more robust than traditional forward-secure signature schemes. But we find that the scheme has two similar weaknesses. We try to repair the two schemes in this paper.

Construction and Traversal of Hash Chain with Public Links

Current hash chain traversal techniques require that the intermediate links of the hash chain be stored secretly on a trusted storage. This requirement is undesirable in several applications. We propose a new construction of hash chains based on inserting a ‘breakpoint’ after fixed number of links in the chain. We also propose a method with which the current hash chain traversal techniques can be applied to our construction without any significant changes in the storage and computation requirements and with the added advantage that the intermediate links may be stored on a public and non-trusted storage. We are also able to prove the security of our construction by replacing the hash function with a MAC function.

Tracing-by-Linking Group Signautres

Uncategorized

Uncategorized

In a group signature \cite{CvH91}, any group member can sign on behalf of the group while remaining anonymous, but its identity can be traced in an future dispute investigation. Essentially all state-of-the-art group signatures implement the tracing mechnism by requiring the signer to escrow its identity to an Open Authority (OA) \cite{ACJT00,CL02scn,BMW03,KiayiasYu04,BSZ05,BBS04,KiayiasTsYu04}. We call them {\em Tracing-by-Escrowing (TbE)} group signatures. One drawback is that the OA also has the unnecessary power to trace without proper cause.
In this paper we introduce {\em Tracing-by-Linking (TbL)} group signatures. The signer's anonymity is irrevocable by any authority if the group member signs only once (per event). But if a member signs twice, its identity can be traced by a public algorithm without needing any trapdoor. We initiate the formal study of TbL group signatures by introducing its security model, constructing the first examples, and give several applications. Our core construction technique is the successful transplant of the TbL technique from single-term offline e-cash from the blind signature framework \cite{Brands93,Ferguson93,Ferguson93c} to the group signature framework. Our signatures have size $O(1)$.

SCA1 Model: Towards a concrete security approach to the design of cryptosystems secure against side-channel attacks

When implementing cryptosystems in general purpose cryptographic hardware, one takes profit of the Application Programming Interfaces (APIs) displaced by the hardware to code the required cryptosystems. The functions made available by these APIs are divided into two groups, the group of the non-cryptographic functions and the group of the cryptographic primitives. When using these functions, one assumes that the functions of the first group are protected against simple side-channel attacks and the functions of the second group are protected against both simple and differential side-channel attacks. Nonetheless, the cryptosystems that make use of these functions may leak information through side-channels. To close this gap of security, a new model is introduced here. It deeply explains how the functions made available by the hardware's APIs must be protected against side-channel attacks and how this hardware must manage memory. In addition, it introduces an adversary that can undertake side-channel attacks against the cryptosystems to test, and teaches how to represent these attacks in pseudo-code. This paper terminates with both the introduction of some security notions and the presentation of the results of testing some well known cryptosystems in accordance with the latter security notions.

Cryptographic Asynchronous Multi-Party Computation with Optimal Resilience

We consider secure multi-party computation in the asynchronous model and present an efficient protocol with optimal resilience. For $n$ parties, up to $t<n/3$ of them being corrupted, and security parameter $\kappa$, a circuit with $c$ gates can be securely computed with communication complexity $O(c n^3 \kappa)$ bits. In contrast to all previous asynchronous protocols with optimal resilience, our protocol requires access to an expensive broadcast primitive only $O(n)$ times --- independently of the size $c$ of the circuit. This results in a practical protocol with a very low communication overhead.
One major drawback of a purely asynchronous network is that the inputs of up to $t$ honest parties cannot be considered for the evaluation of the circuit. Waiting for all inputs could take infinitely long when the missing inputs belong to corrupted parties. Our protocol can easily be extended to a hybrid model, in which we have one round of synchronicity at the end of the input stage, but are fully asynchronous afterwards. In this model, our protocol allows to evaluate the circuit on the inputs of every honest party.

On the Affine Transformations of HFE-Cryptosystems and Systems with Branches

We show how to recover the affine parts of the secret key for a
certain class of HFE-Cryptosystems. Further we will show that any
system build on branches can be decomposed in its single branches
in polynomial time on average. The first part generalizes the
result from \cite{geisel} to a bigger class of systems and is
achieved by a different approach. Dispite the fact that systems
with branches are not used anymore (see
\cite{patarin1, goubin}), our second result is a still of
interest as it applies to a very general class of
HFE-cryptosystems and thus is a contribution to the list of
algebraic properties, which cannot be hidden by composition with
the secret affine transformations. We derived both algorithms by
considering the cryptosystem as objects from the theory of
nonassociative algebras and applying classical techniques from
this theory. This general framework might be useful for future
investigations of HFE-Cryptosysstems or to generalize other
attacks known so far.

Piece In Hand Concept for Enhancing the Security of Multivariate Type Public Key Cryptosystems: Public Key Without Containing All the Information of Secret Key

We propose a new concept, named piece in hand, which can be applicable to a wide class of multivariate type public key cryptosystems to enhance their security. The piece in hand provides such cryptosystems with a new type of trapdoor which is compatible with the trapdoor originally equipped in them. The piece in hand concept is based on a new paradigm for public key cryptosystem in general. On the one hand, in most traditional public key cryptosystems such as the RSA and ElGamal schemes, the public key contains all the information of the secret key. On the other hand, in our scheme, the piece in hand, which is a part of the secret key, is not contained in the public key but is taken from outside of the public key to plug in during the decryption. In this paper, we illustrate how to apply the piece in hand concept to enhance the security of multivariate type public key cryptosystems, by presenting the general theory for the use of the concept.

Ordinary abelian varieties having small embedding degree

Miyaji, Nakabayashi and Takano (MNT) gave families of group orders of ordinary elliptic curves with embedding degree suitable for pairing applications. In this paper we generalise their results by giving
families corresponding to non-prime group orders. We also consider the case of ordinary abelian varieties of dimension 2. We give families of
group orders with embedding degrees 5, 10 and 12.

Finding good differential patterns for attacks on SHA-1

Uncategorized

Uncategorized

In this paper we describe a method of finding differential patterns that may be used to attack reduced versions of SHA-1. We show that the problem of finding optimal differential patterns for SHA-1 is equivalent to the problem of finding minimal weight codeword in a linear code. Finally, we present a number of patterns of different lengths suitable for finding collisions and near-collisions and discuss some bounds on minimal weights of them.

Rethinking the security of some authenticated group key agreement schemes

In this paper we analyse three improved authenticated group key
agreement schemes, all of which are based on the conference key
distribution systems proposed by Burmester and Desmedt. We show
that all the schemes suffer from a type of impersonation attack,
although these schemes are claimed to be secure.

A new security proof for Damgård's ElGamal

We provide a new security proof for a variant of ElGamal proposed by Damgård, showing that it is secure against non-adaptive chosen ciphertext. Unlike previous security proofs for this cryptosystem, which rely on somewhat problematic assumptions, our computational problem is similar to accepted problems such the Gap and Decision Diffie-Hellman problems.

Superfluous Keys in Multivariate Quadratic Asymmetric Systems

In this article, we show that public key schemes based on multivariate quadratic
equations allow many equivalent, and hence superfluous private keys.
We achieve this result by investigating several transformations to identify these keys and
show their application to Hidden Field Equations (HFE), C$^*$,
and Unbalanced Oil and Vinegar schemes (UOV).
In all cases, we are able to reduce the size of the private --- and hence the public ---
key space by at least one order of magnitude.
We see applications of our technique both in cryptanalysis of these
schemes and in memory efficient implementations.

Equivalent Keys in HFE, C$^*$, and variations

In this article, we investigate the question of equivalent keys for
two $\mathcal{M}$ultivariate $\mathcal{Q}$uadratic
public key schemes HFE and C$^{*--}$ and
improve over a previously known result, to appear at PKC 2005.
Moreover, we show a new non-trivial extension of these results to the
classes HFE-, HFEv, HFEv-, and C$^{*--}$, which are cryptographically
stronger variants of the original
HFE and C$^*$ schemes.
In particular, we are able to reduce the size of the private --- and hence the public ---
key space by at least one order of magnitude.
While the results are of independent interest themselves,
we also see applications both in cryptanalysis
and in memory efficient implementations.

Secure Computation of the Mean and Related Statistics

In recent years there has been massive progress in the development of
technologies for storing and processing of data. If statistical
analysis could be applied to such data when it is distributed between several organisations, there could be huge benefits. Unfortunately, in many cases, for legal or commercial reasons, this is not possible.
The idea of using the theory of multi-party computation to analyse
efficient algorithms for privacy preserving data-mining was
proposed by Pinkas and Lindell. The point is that algorithms developed
in this way can be used to overcome the apparent impasse described
above: the owners of data can, in effect, pool their data while
ensuring that privacy is maintained.
Motivated by this, we describe how to securely compute the mean of an
attribute value in a database that is shared between two parties. We
also demonstrate that existing solutions in the literature that could
be used to do this leak information, therefore underlining the
importance of applying rigorous theoretical analysis rather than
settling for ad hoc techniques.

Reusable Cryptographic Fuzzy Extractors

We show that a number of recent definitions and constructions of fuzzy extractors are not adequate for multiple uses of the same fuzzy secret---a major shortcoming in the case of biometric applications. We propose two particularly stringent security models that specifically address the case of fuzzy secret reuse, respectively from an outsider and an insider perspective, in what we call a chosen perturbation attack. We characterize the conditions that fuzzy extractors need to satisfy to be secure, and present generic constructions from ordinary building blocks. As an illustration, we demonstrate how to use a biometric secret in a remote error tolerant authentication protocol that does not require any storage on the client's side.

MD5 To Be Considered Harmful Someday

Joux and Wang's multicollision attack has yielded collisions for several one-way hash algorithms. Of these, MD5 is the most problematic due to its heavy deployment, but there exists a perception that the flaws identified have no applied implications. We show that the appendability of Merkle-Damgard allows us to add any payload to the proof-of-concept hashes released by Wang et al. We then demonstrate a tool, Stripwire, that uses this capability to create two files -- one which executes an arbitrary sequence of commands, the other which hides those commands with the strength of AES -- both with the same MD5 hash. We show how this affects file-oriented system auditors such as Tripwire, but point out that the failure is nowhere near as catastrophic as it appears at first glance. We examine how this failure affects HMAC and Digital Signatures within Digital Rights Management (DRM) systems, and how the full attack expands into an unusual pseudo-steganographic strikeback methodology against peer to peer networks.

Practical Attacks on Digital Signatures Using MD5 Message Digest

Uncategorized

Uncategorized

We use the knowledge of the single MD5 collision published by Wang et al. [1] to show an example of a pair of binary self-extract packages with equal MD5 checksums, whereas resulting extracted contracts have fundamentally different meaning. Secondly, we demonstrate how an attacker could create custom pair of such packages containing files arbitrarily chosen by the attacker with equal MD5 sums where each of the package extracts different file. Once the algorithm for finding MD5 collisions is published, attack could be made even more effective as we explain further. Authors of [1] claim to know such algorithm for any MD5 initialization vector. A real-world scenario of such attack is outlined. Finally, we point out the consequences resulting from such attack for signature schemes based on MD5 message digest on an example using GPG.
[1] X. Wang, D. Feng, X. Lai, H. Yu, "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD", rump session, CRYPTO 2004, Cryptology ePrint Archive, Report 2004/199, http://eprint.iacr.org/2004/199

A Small-Scale Voting Protocol Hiding Vote-Counts of All Candidates

In this paper, we focus on the design of the winner-determination procedure of an electronic voting protocol used at critical elections, e.g. at the meeting of the board of a company for critical business decisions or a parliamentary committee for legislation. The number of participating voters is limited to several hundreds but the voting should satisfy a new privacy requirement that the accumulated vote-counts of all candidates should be kept as secret as possible. This additional requirement is significant only for small/medium-scale elections. Traditional electronic voting frameworks simply take the announcement of vote-counts for granted and hope that each individual¡¦s actual vote is hidden in the accumulated vote-counts. Therefore, it is not easy to modify an existing scheme to approach this new goal. In the proposed protocol, the homomorphic ElGamal cryptosystem is used. An electronic bulletin board holds public announced values. A ballot consists of separate encrypted ¡¥yes¡¦/¡¦no¡¦ vote for each candidate such that the accumulated vote-counts can be calculated from the ciphertexts without any decryption. The correctness of each ballot is guaranteed through ZKPs. The accumulated vote-count ciphertexts are then converted to encrypted unary representation through a mix-and-match sub-protocol such that the vote-counts can be concealed in the winner-determination stage. This protocol is suited for both equal-voting and weighted-voting schemes. Also, the type of voter¡¦s selection can be single choice, multiple choices, ranking choice, or the allocative choice.

Classes of Plateaued Rotation Symmetric Boolean Functions under Transformation of Walsh Spectra

Construction methods of Boolean functions with cryptographically
significant properties is an important and difficult problem.
In this work we investigate the class of rotation symmetric
Boolean functions (RSBFs). These functions
are invariant under circular translation of indices and
were mainly introduced for efficient implementation purposes.
First, we derive general results on these functions. Afterwards,
we concentrate on plateaued RSBFs on odd number of variables,
which have three valued Walsh Spectra ($0, \pm \lambda$), and
can have maximum nonlinearity.
We consider both cases when the number of
variables $n$ is composite and prime.
%
When $n$ is odd and prime, we derive the constructive relation
between {\it balanced/unbalanced} plateaued RSBFs and show how
from one given such function the complete sub class can be generated.
As long as search for one plateaued RSBF is of high complexity,
our proposed manipulation technique with Walsh spectra imediately give us
the way to construct many such functions without time
consuming. Since the most important properties of a function are
determined via the values of Walsh spectra, then such transformation
technique is important to create new function with, possible, better
properties. The application of our transformation technique construct
a class of
$\left((2^{\frac{n-1}{2}}+1)/n\right)!\cdot
\left(2^{\frac{n-1}{2}}-1\right)$
balanced/unbalanced plateaued RSBFs.
%
In our practical implementation of this technique,
given one balanced PRSBF on $n=11$ variables we could
construct 185 new such functions. To find the
first function took us several days, whereas to construct new 185 functions
took us just a second. However, this technique can
be applied only when the Legendre symbol $(2/n)$ is $-1$, and
the first such $n$'s are $3, 5, 7, 11, 13, 19, 29, 37, 43, \ldots$.

Direct Division in Factor Rings

Conventional techniques for division in the polynomial factor ring
$\Ftm$ or the integer ring $\Zzs$ use a combination of inversion
and multiplication. We present a new algorithm that computes the
division directly and therefore eliminates the multiplication
step. The algorithm requires $2\,{\rm degree\/}{(m)}$ (resp. $2
\log_2 n$) steps, each of which uses only shift and
multiply-subtract operations.

Practical Cryptography in High Dimensional Tori

At Crypto 2004, van Dijk and Woodruff introduced a new way of using the algebraic tori T_n in cryptography, and obtained an asymptotically optimal n/phi(n) savings in bandwidth and storage for a number of cryptographic applications. However, the computational requirements of compression and decompression in their scheme were impractical, and it was left open to reduce them to a practical level. We give a new method that compresses orders of magnitude faster than the original, while also speeding up the decompression and improving on the compression factor (by a constant term). Further, we give the first efficient implementation that uses T_30, compare its performance to XTR, CEILIDH, and ECC, and present new applications. Our methods achieve better compression than XTR and CEILIDH for the compression of as few as two group elements. This allows us to apply our results to ElGamal encryption with a small message domain to obtain ciphertexts that are 10% smaller than in previous schemes.

Last updated: 2009-05-12

Efficient and Optimistic Fair Exchanges Based on Standard RSA with Provable Security

Uncategorized

Uncategorized

In this paper, we introduce a new and natural paradigm for fair exchange protocols, called verifiable probabilistic signature scheme. A security model with precise and formal definitions is presented, and an RSA-based efficient and provably secure verifiable probabilistic signature scheme is proposed. Our scheme works well with standard RSA signature schemes, and the proposed optimistic fair exchange protocol is much concise and efficient, and suitable for practical applications.

Multivariable public--key cryptosystems

Recently Landau and Diffie gave in a series of articles in the Notices of the American Mathematical Society and in the American Mathematical Monthly excellent expositions on how the theory of multivariable polynomials are used in cryptography. However they covered only half of the story. They covered only the theory of polynomials in symmetric or secret cryptography. There is another half of the story, namely the story about the theory of multivariable polynomials in asymmetric or public key cryptosystems. We give an overview of the families of public key cryptosystems, which have been developed in the last ten years.

A DPA Attack on the Improved Ha-Moon Algorithm

The algorithm proposed by Ha and Moon [HM02] is a
countermeasure against power analysis. The Ha-Moon algorithm has
two drawbacks in that it requires an inversion and has a
right-to-left approach. Recently, Yen, Chen, Moon and Ha improved
the algorithm by removing these drawbacks [YCMH04]. Their new
algorithm is inversion-free, has a left-to-right approach and
employs a window method. They insisted that their algorithm leads
to a more secure countermeasure in computing modular
exponentiation against side-channel attacks. This algorithm,
however, still has a similar weakness observed in
[FMPV04,SPL04]. This paper shows that the improved Ha-Moon
algorithm is vulnerable to differential power analysis even if we
employ their method in selecting $s_i$.

A weakness in Sun-Chen-Hwang's three-party key agreement protocols using passwords

Recently, Sun, Chen and Hwang [J. Syst. Software, 75 (2005),
63-68] have proposed two new three-party protocols, one for
password-based authenticated key agreement and one for
verifier-based authenticated key agreement. In this paper, we show
that both of Sun-Chen-Hwang's protocols are insecure against an
active adversary who can intercept messages, start multiple
sessions of a protocol, or otherwise control the communication in
the network. Also, we present a simple solution to the security
problem with the protocols.

Addendum to ``On the Generalized Linear Equivalence of Functions over Finite Fields''

In this paper we discuss the example of APN permutation introduced in the paper ``On the Generalized Linear Equivalence of Functions over Finite Fields'', presented at Asiacrypt 2004. We show that the permutation given there is indeed classically linearly equivalent to a power monomial. More in general, we show that no new class of APN functions can be discovered starting from permutation polynomials of the type used in the paper, and applied on the APN monomial $x^3$.

Random Switching Logic: A Countermeasure against DPA based on Transition Probability

In this paper, we propose a new model for directly evaluating DPA leakage from logic information in CMOS circuits.This model is based on the transition probability for each gate, and is naturally applicable to various actual devices for simulating power analysis. We also report on our study of the effects of the previously known countermeasures on both our model and FPGA, and show the possibility of leaking information, which is caused by strict precondition for implementing a secure circuit. Furthermore, we present an efficient countermeasure, \textit{Random Switching Logic}(RSL), for relaxing the precondition, and show that RSL makes a cryptographic circuit secure through evaluation on both our model and FPGA.

On Session Identifiers in Provably Secure Protocols: The Bellare-Rogaway Three-Party Key Distribution Protocol Revisited

We examine the role of session identifiers (SIDs) in security proofs for key establishment protocols. After reviewing the practical importance of SIDs we use as a case study the three-party server-based key distribution (3PKD) protocol of Bellare and Rogaway, proven secure in 1995. We show incidentally that the partnership function used in the existing security proof is flawed. There seems to be no way to define a SID for the 3PKD protocol that will preserve the proof of security. A small change to the protocol allows a natural definition for a SID and we prove that the new
protocol is secure using this SID to define partnering.

Modified Parameter Attacks: Practical Attacks against CCA2 Secure Cryptosystems and Countermeasures

We introduce the concept of Modified Parameter Attacks, a natural extension of the idea of Adapative Chosen Ciphertext Attacks (CCA2) under which some CCA2 secure systems can be shown to be insecure. These insecurities can be addressed at the application level, but can also be addressed when cryptographic schemes are being designed. We survey some existing CCA2 secure systems which are vulnerable to this attack and suggest practical countermeasures.

Revisit Of McCullagh--Barreto Two-Party ID-Based Authenticated Key Agreement Protocols

The recently proposed two-party ID-based authenticated key agreement protocols (with and without escrow) and its variant resistant to key-compromise impersonation by McCullagh & Barreto are revisited. The protocol carries a proof of security in the Bellare & Rogaway (1993) model. In this paper, it is demonstrated that the protocols and its variant are not secure if the adversary is allowed to send a Reveal query to reveal non-partner players who had accepted the same session key.

A comb method to render ECC resistant against Side Channel Attacks

Side Channel Attacks may exploit leakage information to break cryptosystems on smard card devices. In this paper we present a new SCA-resistant elliptic curve scalar multiplication algorithm, based on the Lim and Lee technique. The proposed algorithm builds a sequence of bit-strings representing the scalar $k$, characterized by the fact that all bit-strings are different from zero; this property will ensure a uniform computation behaviour for the algorithm, and thus will make it secure against SPA (Simple Power Analysis) attacks. The use of a recently introduced randomization technique achieves the security of the proposed scheme against other SCA attacks. Furthermore, the proposed countermeasures do not penalize the computation time

Reducing Complexity Assumptions for Statistically-Hiding Commitment

Determining the minimal assumptions needed to construct various
cryptographic building blocks has been a focal point of research in
theoretical cryptography. For most --- but not all! --- cryptographic
primitives, complexity assumptions both necessary and sufficient for their existence are known. Here, we revisit the following, decade-old question: what are the minimal assumptions needed to construct a statistically-hiding bit commitment scheme? Previously, it was known how to construct such schemes based on any one-way permutation.
In this work, we show that regular one-way functions suffice.
We show two constructions of statistically-hiding commitment schemes from regular one-way functions. Our first construction is more direct, and serves as a ``stepping-stone'' for our second construction which has improved round complexity. Of independent interest, as part of our work we show a compiler transforming any commitment scheme which is statistically-hiding against an honest-but-curious receiver to one which is statistically-hiding against a malicious receiver. This demonstrates the equivalence of these two formulations of the problem.
Our results also improve the complexity assumptions needed for statistical zero-knowledge arguments.

Request for Review of Key Wrap Algorithms

A key wrap algorithm is a secret key algorithm for the authenticated encryption of specialized data such as cryptographic keys. Four key wrap algorithms have been proposed for the draft ASC X9 standard, ANS X9.102. NIST is serving as the editor of ANS X9.102, and, on behalf of the X9F1 working group, NIST requests a cryptographic review of the four algorithms. This document specifies the algorithms and suggests security models for their analysis. Comments will be accepted until May 21, 2005.

Divisors in Residue Classes, Constructively

Let $r,s,n$ be integers satisfying $0 \leq r < s < n$,
$s \geq n^{\alpha}$, $\alpha > 1/4$, and $\gcd(r,s)=1$. Lenstra showed that the number of integer divisors of $n$ equivalent to
$r \pmod s$ is upper bounded by $O((\alpha-1/4)^{-2})$. We re-examine this problem; showing how to explicitly construct all such divisors and incidentally improve this bound to $O((\alpha-1/4)^{-3/2})$.

Identity-Based Hierarchical Strongly Key-Insulated Encryption and Its Application

In this paper, we discuss non-interactive updating of decryption keys in identity-based encryption (IBE). IBE is a public key cryptosystem where a public key is an arbitrary string. In practice, key revocation is a necessary and inevitable process and IBE is no exception when it comes to having to manage revocation of decryption keys without losing its merits in efficiency. Our main contribution of this paper is to propose novel constructions of IBE where the decryption key can be renewed without having to make changes to its public key, i.e. user's identity. We achieve this by tactfully extending the hierarchical IBE (HIBE). Regarding security, we address semantic security against adaptive chosen cipher-text attack for a very strong attack environment that models all possible types of key exposures in the random oracle model. Straightforward extension of the HIBE, however, does not achieve our goal and such scheme is completely insecure under our attack model. In addition to this, we show method of constructing (partially collusion resistant) HIBE from arbitrary IBE in the random oracle model. By combining these results, we can construct an IBE with non-interactive key update from only an arbitrary IBE.

Security on Generalized Feistel Scheme with SP Round Function

This paper studies the security against differential/linear
cryptanalysis and the pseudorandomness for a class of generalized
Feistel scheme with SP round function called $GFSP$. We consider
the minimum number of active s-boxes in some consecutive rounds of
$GFSP$,i.e., in four, eight and sixteen consecutive rounds, which
provide the upper bound of the maximum differential/linear
probabilities of 16-round $GFSP$ scheme, in order to evaluate the
strength against differential/linear cryptanalysis. Furthermore,
We investigate the pseudorandomness of $GFSP$, point out 7-round
$GFSP$ is not pseudorandom for non-adaptive adversary, by using
some distinguishers, and prove that 8-round $GFSP$ is pseudorandom
for any adversaries.

Oblivious Transfer Is Symmetric

We show that oblivious transfer of bits from $A$ to $B$ can be
obtained from a single instance of the same primitive from $B$ to $A$.
Our reduction is perfect and shows that oblivious transfer is in fact
a symmetric functionality. This solves an open problem posed by
Crépeau and Sántha in 1991.

Statistical Zero-Knowledge Arguments for NP Using Approximable-Preimage-Size One-Way Functions

A statistical zero knowledge argument for NP is a cryptographic primitive that allows a polynomial-time prover to convince another
polynomial-time verifier of the validity of an NP statement. It is guaranteed that even an infinitely powerful verifier does not learn any
additional information but the validity of the claim.
Naor et al., Journal of Cryptology 1998, showed how to implement such a protocol using any one-way permutation. We achieve such a
protocol using any approximable-preimage-size one-way function. These are one-way functions with the additional feature that there is a
feasible way to approximate the number of preimages of a given output. A special case is regular one-way functions where each output has the
same number of preimages.
Our result is achieved by showing that a variant of the computationally-binding bit-commitment protocol of Naor et al. can be implemented using
a any one-way functions with ``sufficiently dense'' output distribution. We construct such functions from approximable-preimage-size one-way
functions using ``hashing techniques'' inspired by Hastad et al., SIAM Journal on Computing 1998.

Universally Composable Symbolic Analysis of Cryptographic Protocols (The case of encryption-based mutual authentication and key exchange)

Symbolic analysis of cryptographic protocols is dramatically simpler than full-fledged cryptographic analysis. In particular, it is readily amenable to automation. However, symbolic analysis does not a priori carry any cryptographic soundness guarantees. Following recent work on cryptographically sound symbolic analysis, we demonstrate how Dolev-Yao style symbolic analysis can be used to assert the security of cryptographic protocols within the universally composable (UC) security framework. Consequently, our methods enable security analysis that is completely symbolic, and at the same time cryptographically sound with strong composability properties.
More specifically, we define a mapping from a class of cryptographic protocols to Dolev-Yao style symbolic protocols. For this mapping, we show that the symbolic protocol satisfies a certain symbolic criterion if and only if the corresponding cryptographic protocol is UC-secure. We concentrate on mutual authentication and key-exchange protocols that use public-key encryption as their only cryptographic primitive. For mutual authentication, our symbolic criterion is similar to the traditional Dolev-Yao criterion. For key exchange, we demonstrate that the traditional Dolev-Yao style symbolic criterion is insufficient, and formulate an adequate symbolic criterion.
Finally, to demonstrate the viability of the treatment, we use an existing automated verification tool to assert UC security of some prominent key exchange protocols.

Secure Multi-party Computation for selecting a solution according to a uniform distribution over all solutions of a general combinatorial problem

Secure simulations of arithmetic circuit and boolean circuit
evaluations are known to save privacy while providing solutions to any
probabilistic function over a field. The problem we want to solve is
to select a random solution of a general combinatorial problem. Here
we discuss how to specify the need of selecting a random solution of a
general combinatorial problem, as a probabilistic function. Arithmetic
circuits for finding the set of all solutions are simple to
design.
We know no arithmetic circuit proposed in the past, selecting a single
solution according to a uniform distribution over all solutions of a
general constraint satisfaction problem. The only one (we) are able to design has a factorial complexity in the size of the search space
(O(d^m!d^m) multiplications of secrets), where m is the number of
variables and d the maximal size of a variable's domain.
Nevertheless, we were able to develop a methodology combining secure
arithmetic circuit evaluation and mix-nets, able to compile the
problem of selecting a random solution of a CSP to a n/2-private
multi-party computation assuming passive attackers. The complexity of
this solution is more acceptable, O(d^m) multiplications, being
therefore applicable for some reasonable problems, like meeting
scheduling.
Constraint satisfaction is a framework extensively used in some areas
of artificial intelligence to model problems like meeting scheduling,
timetabling, the stable marriages problem, and some negotiation
problems. It is based on abstracting a problem as a set of variables,
and a set of constraints that specify unacceptable combination of values for sets of distinct variables.

Sequences of games: a tool for taming complexity in security proofs

Uncategorized

Uncategorized

This paper is a brief tutorial on a technique for structuring security proofs as sequences of games.

Code-Based Game-Playing Proofs and the Security of Triple Encryption

Uncategorized

Uncategorized

The game-playing technique is a powerful tool for analyzing cryptographic constructions. We illustrate this by using games as the central tool for proving security of three-key triple-encryption, a long-standing open problem. Our result, which is in the ideal-cipher model, demonstrates that for DES parameters (56-bit keys and 64-bit plaintexts) an adversary's maximal advantage is small until it asks about $2^{78}$ queries. Beyond this application, we develop the foundations for game playing, formalizing a general framework for game-playing proofs and discussing techniques used within such proofs. To further exercise the game-playing framework we show how to use games to get simple proofs for the PRP/PRF Switching Lemma, the security of the basic CBC~MAC, and the chosen-plaintext-attack security of OAEP.

Multicollision Attacks on Generalized Hash Functions

Uncategorized

Uncategorized

In a recent paper in crypto-04, A. Joux showed a
multicollision attacks on the classical iterated hash function. He
also showed how the multicollision attack can be used to get a
collision attack on the concatenated hash function. In this paper
we have shown that the multicollision attacks exist in a general
class of sequential or tree based hash functions even if message
blocks are used twice unlike the classical hash function.

Hardness amplification of weakly verifiable puzzles

Is it harder to solve many puzzles than it is to solve just one? This
question has different answers, depending on how you define puzzles.
For the case of inverting one-way functions it was shown by Yao that
solving many independent instances simultaneously is indeed harder
than solving a single instance (cf. the transformation from weak to
strong one-way functions). The known proofs of that result, however,
use in an essential way the fact that for one-way functions, verifying
candidate solutions to a given puzzle is easy. We extend this result
to the case where solutions are efficiently verifiable only by
the party that generated the puzzle. We call such puzzles weakly
verifiable. That is, for weakly verifiable puzzles we show that if no
efficient algorithm can solve a single puzzle with probability more
than $\eps$, then no efficient algorithm can solve $n$ independent
puzzles simultaneously with probability more than $\eps^n$. We also
demonstrate that when the puzzles are not even weakly verifiable,
solving many puzzles may be no harder than solving a single one.
Hardness amplification of weakly verifiable puzzles turns out to be
closely related to the reduction of soundness error under parallel
repetition in computationally sound arguments. Indeed, the proof of
Bellare, Impagliazzo and Naor that parallel repetition reduces
soundness error in three-round argument systems implies a result
similar to our first result, albeit with considerably worse
parameters. Also, our second result is an adaptation of their proof
that parallel repetition of four-round systems may not reduce the
soundness error.

Last updated: 2004-11-29

Security Analysis of a 2/3-rate Double Length Compression Function in Black-Box Model

Uncategorized

Uncategorized

In this paper, we propose a $2/3$-rate double length compression
function and study its security in black-box model. We prove that
to get a collision attack for the compression function requires
$\Omega(2^{2n/3})$ queries, where $n$ is the single length output
size. Thus, it has better security than a most secure single
length compression function. This construction is more efficient
than the construction given in~\cite{Hirose04}. Also the three
computations of underlying compression functions can be done in
parallel. The proof idea uses a concept of computable message
which can be helpful to study security of other constructions like
~\cite{Hirose04},~\cite{Lucks04},~\cite{Nandi04} etc.

Efficient Identity Based Ring Signature

Identity-based (ID-based) cryptosystems eliminate the need for validity checking of the certificates and the need for registering for a certificate before getting the public key. These two features are desirable especially for the efficiency and the real spontaneity of ring signature, where a user can anonymously sign a message on behalf of a group of spontaneously conscripted users including the actual signer.
In this paper, we propose a novel construction of ID-based ring signature which only needs two pairing computations for any group size. The proposed scheme is proven to be existential unforgeable against adaptive chosen message-and-identity attack under the random oracle model, using the forking lemma for generic ring signature schemes. We also consider its extension to support the general access structure.

Cryptanalysis of Qiu-Gu-Chen Variant Group Signature Scheme

Qiu et al. proposed
a variant group signature scheme in [1].
We find that the group manager can successfully forge signature because he has absolute predominance in Join Phase.

Complexity of the Collision and Near-Collision Attack on SHA-0 with Different Message Schedules

SHA-0 employs a primitive polynomnial of degree 16 over GF(2) in its message schedule. There are 2048 primitive polynomials of degree 16 over GF(2). For each primitive polynomial, a SHA-0 variant can be constructed. In this paper, the security of 2048 variants is analyzed against the Chabaud-Joux attack proposed in CRYPTO'98. The analysis shows that all the variants could be collision-attacked by using near-collisions as a tool and thus the replacement of the primitive polynomial is not a proper way to make SHA-0 secure. However, it is shown that the selection of the variants highly affects the complexity of the attack. Furthermore, a collision in the most vulnerable variant is presented. It is obtained by the original Chabaud-Joux attack without any improvements.

On a Probabilistic Approach to the Security Analysis of Cryptographic Hash Functions

In this paper we focus on the three basic security requirements for a cryptographic hash function, commonly referred as preimage, second preimage and collision resistance. We examine these security requirements in the case of attacks which do not take advantage on how the hash function is computed, expressing them as success probabilities of suitable randomized algorithms. We give exact mathematical expressions for such resistance indices, and obtain their functional behaviour in relation to the amount of uniformity in the hash function outcomes. Our work provides a mathematical framework for the study of cryptographic hash functions, which enable us to give proofs for some prevailing beliefs.

A note on López-Dahab coordinates

López-Dahab coordinates are usually the system of choice for
implementations of elliptic curves over binary fields. We give new
formulas for doubling which need one squaring less and one more
addition. This leads to a speed-up for binary fields in polynomial
basis representation.

Separable and Anonymous Identity-Based Key Issuing

In identity-based (ID-based) cryptosystems, a local registration authority (LRA) is responsible for authentication of users while the key generation center (KGC) is responsible for computing and sending the private keys to users and therefore, a secure channel is required. For privacy-oriented applications, it is important to keep in secret whether the private key corresponding to a certain identity has been requested. All of the existing ID-based key issuing schemes have not addressed this anonymity issue. Besides, the separation of duties for authentication and private key computation has not been discussed as well. In this paper, based on a signature scheme similar to a short blind signature, we propose a novel separable and anonymous ID-based key issuing scheme without secure channel. Our protocol supports the separation of duties between LRA and KGC. The private key computed by the KGC can be sent to the user in an encrypted form such that only the legitimate key requester authenticated by LRA can decrypt it, and any eavesdropper cannot know the identity corre-sponding to the secret key.

The conjugacy search problem in public key cryptography: unnecessary and insufficient

The conjugacy search problem in a group $G$ is the problem
of recovering an $x \in G$ from given $g \in G$ and $h=x^{-1}gx$.
This problem is in the core of several recently suggested
public key exchange protocols, most notably the one due to
Anshel, Anshel, and Goldfeld, and the one due to Ko, Lee at al.
In this note, we make two observations that seem to have
eluded most people's attention. The first observation
is that solving the conjugacy search problem is not necessary
for an adversary to get the common secret key in the Ko-Lee
protocol. It is sufficient to solve an apparently easier problem
of finding $x, y \in G$ such that $h=ygx$ for given $g, h \in G$.
Another observation is that solving the conjugacy search problem is not sufficient for an adversary to get the common secret key in the
Anshel-Anshel-Goldfeld protocol.

Upper Bounds for the Selection of the Cryptographic Key Lifetimes: Bounding the Risk of Key Exposure in the Presence of Faults

With physical attacks threatening the security of current cryptographic schemes, no security policy can be developed without taking into account the physical nature of computation. In this article we first introduce the notion of \emph{Cryptographic Key Failure Tolerance}, then we offer a framework for the determination of upper bounds to the key lifetimes for any cryptographic scheme used in the presence of faults, given a desired (negligible) error-bound to the risk of key exposure. Finally we emphasize the importance of choosing keys and designing schemes with good values of failure tolerance, and recommend minimal values for this metric. In fact, in \emph{standard environmental conditions}, cryptographic keys that are especially susceptible to erroneous computations (e.g., RSA keys used with CRT-based implementations) are exposed with a probability greater than a standard error-bound (e.g., ${2^{-40}}$) after operational times shorter than one year, if the failure-rate of the cryptographic infrastructure is greater than ${1.04\times10^{-16}}$ {\it failures/hours}.

Badger - A Fast and Provably Secure MAC

We present Badger, a new fast and provably secure MAC based on universal hashing. In the construction, a modified tree hash that is more efficient than standard tree hash is used and its security is being proven. Furthermore, in order to derive the core hash function of the tree, we use a novel technique for reducing $\Delta$-universal function families to universal families. The resulting MAC is very efficient on standard platforms both for short and long messages. As an example, for a $64$-bit tag, it achieves performances up to 2.2 and 1.2 clock cycles per byte on a Pentium III and Pentium 4 processor, respectively. The forgery probability is at most $2^{-52.2}$.

Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation

We give improved upper bounds on the communication complexity of optimally-resilient secure multiparty computation in the cryptographic model. We consider evaluating an $n$-party randomized function and show that if $f$ can be computed by a circuit of size $c$, then $\O(c n^2 \kappa)$ is an upper bound for active security with optimal resilience $t < n/2$ and security parameter $\kappa$. This improves on the communication complexity of previous protocols by a factor of at least $n$. This improvement comes from the fact that in the new protocol, only $\O(n)$ messages (of size $\O(\kappa)$ each) are broadcast during the \emph{whole} protocol execution, in contrast to previous protocols which require at least $\O(n)$ broadcasts \emph{per gate}.
Furthermore, we improve the upper bound on the communication complexity of passive secure multiparty computation with resilience $t<n$ from $\O(c n^2 \kappa)$ to $\O(c n \kappa)$. This improvement is mainly due to a simple observation.

Adaptively-Secure, Non-Interactive Public-Key Encryption

Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of already-corrupted parties. Ideally, an adaptively-secure encryption scheme should, like standard public-key encryption, allow arbitrarily-many parties to use a single encryption key to securely encrypt arbitrarily-many messages to a given receiver who maintains only a single short decryption key. However, it is known that these requirements are impossible to achieve: no non-interactive encryption scheme that supports encryption of an unbounded number of messages and uses a single, unchanging decryption key can be adaptively secure.
Impossibility holds even if secure data erasure is possible.
We show that this limitation can be overcome by updating the decryption key over time and making some mild assumptions about
the frequency of communication between parties. Using this approach,
we construct adaptively-secure, completely non-interactive encryption
schemes supporting secure encryption of arbitrarily-many messages from
arbitrarily-many senders. Our schemes additionally provide
forward security and security against chosen-ciphertext attacks.

On a Threshold Group Signature Scheme and a Fair Blind Signature Scheme

In the paper, we analyze two signature schemes.
The first is a $(t_j, t, n) $ threshold group
signature scheme proposed by Shi and Feng in [1]. The second
is a fair blind signature scheme proposed by Feng in [2]. Our
results show that both schemes are forgeable.
Besides, we introduce a concept, i.e., suspended factor, to describe the common error in designing signature scheme, which means that some signature data lie at neither base position nor exponent position in verifying equation, instead lie at factor position solely .

Security Arguments for Partial Delegation with Warrant Proxy Signature Schemes

Proxy signature is an important cryptographic primitive and has
been suggested in numerous applications. In this paper, we present
an attack on the aggregate-signature-based proxy signature
schemes, then point out there are two flaws in BPW notion of
security for proxy signature. Furthermore, we give arguments for
partial delegation with warrant proxy signature schemes. We
construct a new proxy signature scheme and prove that it is secure
against existentially forgery on adaptively chosen-message attacks
and adaptively chosen-warrant attacks under the random oracle
model.

A Technical Comparison of IPSec and SSL

IPSec (IP Security) and SSL (Secure Socket Layer) have been the most robust and most potential tools available for securing communications over the Internet. Both IPSec and SSL have advantages and shortcomings. Yet no paper has been found comparing the two protocols in terms of characteristic and functionality. Our objective is to present an analysis of security and performance properties for IPSec and SSL.

Cryptanalysis of a threshold proxy signature with known signers

A scheme of threshold proxy signature with known signers was proposed by Hwang et al. In their scheme, the receiver can identify the proxy signers that actually generated a proxy signature. Tzeng et al. demonstrated that this signature scheme is insecure and proposed an improvement to mend the information leakage. This paper shows that the improved scheme is still insecure under the original signer¡¦s forgery attack.

Ramanujan Graphs and the Random Reducibility of Discrete Log on Isogenous Elliptic Curves

Cryptographic applications using an elliptic curve over a finite field
filter curves for suitability using their order as the primary criterion: e.g. checking that their order has a large prime divisor before accepting it. It is therefore natural to ask whether the discrete log problem (DLOG) has the same difficulty for all curves with the same order; if so it would justify the above practice. We prove that this is essentially true by showing random reducibility of dlog among such curves, assuming the Generalized Riemann Hypothesis (GRH). Our reduction proof works for curves with (nearly) the same endomorphism rings, but it is unclear if such a reduction exists in general. This suggests that in addition to the order, the conductor of its endomorphism ring may play a role. The random self-reducibility for dlog over finite fields is well known; the non-trivial part here is that one must relate non-isomorphic algebraic groups of two isogenous curves. We construct certain expander graphs with elliptic curves as nodes and low degree isogenies as edges, and utilize the rapid mixing of random walks on this graph. We also briefly look at some recommended curves, compare “random” type NIST FIPS 186-2 curves to other special curves from this standpoint, and suggest a parameter to measure how generic a given curve is.

Hierarchical Group Signatures

We introduce the notion of \emph{hierarchical group signatures}. This
is a proper generalization of group signatures, which allows multiple
group managers organized in a tree with the signers as leaves. For a
signer that is a leaf of the subtree of a group manager, the group
manager learns which of its children that (perhaps indirectly) manages
the signer.
We provide definitions for the new notion and construct a scheme that
is provably secure given the existence of a family of trapdoor
permutations.
We also present a construction which is relatively practical, and
prove its security in the random oracle model under the strong RSA
assumption and the DDH assumption.

A Verifiable Random Function With Short Proofs and Keys

Uncategorized

Uncategorized

We give a simple and efficient construction of a verifiable random function (VRF) on bilinear groups. Our construction is direct.
In contrast to prior VRF constructions [MRV99, Lys02], it avoids using an inefficient Goldreich-Levin transformation, thereby saving several factors in security. Our proofs of security are based on a decisional bilinear Diffie-Hellman inversion assumption, which seems reasonable given current state of knowledge. For small message spaces, our VRF's proofs and keys have constant size. By utilizing a collision-resistant hash function, our VRF can also be used with arbitrary message spaces. We show that our scheme can be instantiated with an elliptic group of very reasonable size.
Furthermore, it can be made distributed and proactive.

The Power of Verification Queries in Message Authentication and Authenticated Encryption

This paper points out that, contrary to popular belief,
allowing a message authentication adversary multiple verification attempts
towards forgery is NOT equivalent to allowing it a single one, so that
the notion of security that most message authentication schemes are proven to
meet does not guarantee their security in practice. We then show, however, that
the equivalence does hold for STRONG unforgeability. Based on this we
recover security of popular classes of message authentication schemes such as
MACs (including HMAC and PRF-based MACs) and CW-schemes. Furthermore, in many
cases we do so with a TIGHT security reduction, so that in the end
the news we bring is surprisingly positive given the initial negative result.
Finally, we show analogous results for authenticated encryption.

Cryptanalysis of Noel McCullagh and Paulo S. L. M. Barreto¡¯s two-party identity-based key agreement

Uncategorized

Uncategorized

Noel McCullagh and Paulo S. L. M. Barreto[1] proposed a two-party identity-based key agreement protocol in 2004,which can be used in either escrowed or escrowless mode. They also described conditions under which users of different Key Generation Centres can agree on a shared secret key. In this paper, we show that these two protocols are insecure against the key compromis impersonate attack,and the fix protocol has not the property of Perfect-Forword-Secrecy.We modify these protocols in three ways,which are secure against all attack and satisfy the property of Known-Key Security, Perfect-Forward-Secrecy, Key-Compromise Impersonation, Unknown Key-Share,and Key control and so on.

Universal Forgeability of Wang-Wu-Wang Key-Insulated Signature Scheme

Wang et al. recently proposed
a new perfect and strong key-insulated signature scheme in [1].
We find that the scheme is universally forgeable. In the
paper we present a simple and direct attack on it.

The Static Diffie-Hellman Problem

The static Diffie-Hellman problem (SDHP) is the special case
of the classic Diffie-Hellman problem where one of the public keys
is fixed. We establish that the SDHP is almost as hard as the
associated discrete logarithm problem. We do this by giving a
reduction that shows that if the SDHP can be solved then the
associated private key can be found.
The reduction also establishes that certain systems have less
security than anticipated. The systems affected are based on static
Diffie-Hellman key agreement and do not use a key derivation
function. This includes some cryptographic protocols: basic ElGamal
encryption; Chaum and van Antwerpen's undeniable signature scheme; and Ford and Kaliski's key retrieval scheme, which is currently being
standardized in IEEE P1363.2.

A note on efficient computation of cube roots in characteristic 3

Uncategorized

Uncategorized

The cost of the folklore algorithm for computing cube roots in $\F_{3^m}$ in standard polynomial basis is less that one multiplication, but still $O(m^2)$. Here we show that, if $\F_{3^m}$ is represented in trinomial basis as $\F_3[x]/(x^m + ax^k + b)$ with $a, b = \pm 1$, the actual cost of computing cube roots in $\F_{3^m}$ is only $O(m)$.

Second Preimages on n-bit Hash Functions for Much Less than 2^n Work

We provide a second preimage attack on all $n$-bit iterated
hash functions with Damgard-Merkle strengthening and $n$-bit
itermediate states, allowing a second preimage to be found for a
$2^k$-message-block message with about $k \times 2^{n/2+1}+2^{n-k+1}$
work. Using SHA1 as an example, our attack can find a second preimage
for a $2^{60}$ byte message in $2^{106}$ work, rather than the
previously expected $2^{160}$ work. We also provide slightly cheaper
ways to find multicollisions than the method of Joux. Both
of these results are based on expandable messages--patterns for
producing messages of varying length, which all collide on the
intermediate hash result immediately after processing the
message. We also provide algorithms for finding expandable messages for a hash function, using only a small multiple of the work done to find a single collision in the hash function.

Efficient Tate Pairing Computation for Supersingular Elliptic Curves over Binary Fields

We present a closed formula for the Tate pairing computation for
supersingular elliptic curves defined over the binary field F_{2^m} of odd dimension. There are exactly three isomorphism classes of supersingular elliptic curves over F_{2^m} for odd m and our result is applicable to all these curves. Moreover we show that our algorithm and also the Duursma-Lee algorithm can be modified to another algorithm which does not need any inverse Frobenius operation (square root or cube root extractions) without sacrificing any of the computational merits of the original algorithm. Since the computation of the inverse Frobenius map is not at all trivial in a polynomial basis and since a polynomial basis is still a preferred choice for the Tate pairing computation in many situations, this new algorithm avoiding the inverse Frobenius operation has some advantage over the existing algorithms.

Security of Wang-Li Threshold Signature Scheme

In 2003, Wang et al.[1] proposed a
$(t, n)$ threshold signature scheme without a trusted party based
on the discrete logarithm problem. In this paper, according to
[5]'s attacking method, we show that there are still some security
leaks in that scheme, and give some methods of forgery attack.
Moreover, we point out this scheme is vulnerable to universal
forgery by an insider attacker under reasonable assumptions.

VMPC-MAC: A Stream Cipher Based Authenticated Encryption Scheme

A stream cipher based algorithm for computing Message Authentication Codes is described. The algorithm employs the internal state of the underlying cipher to minimize the required additional-to-encryption computational effort and maintain general simplicity of the design.
The scheme appears to provide proper statistical properties, a comfortable level of resistance against forgery attacks in a chosen ciphertext attack model and high efficiency in software implementations.

Relating Symbolic and Cryptographic Secrecy

We investigate the relation between symbolic and cryptographic secrecy
properties for cryptographic protocols. Symbolic secrecy of payload
messages or exchanged keys is arguably the most important notion of
secrecy shown with automated proof tools. It means that an adversary
restricted to symbolic operations on terms can never get the entire
considered object into its knowledge set. Cryptographic secrecy
essentially means computational indistinguishability between the real
object and a random one, given the view of a much more general
adversary. In spite of recent advances in linking symbolic and
computational models of cryptography, no relation for secrecy under
active attacks is known yet.
For exchanged keys, we show that a certain strict symbolic secrecy
definition over a specific Dolev-Yao-style cryptographic library
implies cryptographic key secrecy for a real implementation of this
cryptographic library. For payload messages, we present the first
general cryptographic secrecy definition for a reactive scenario. The
main challenge is to separate secrecy violations by the protocol under
consideration from secrecy violations by the protocol users in a
general way. For this definition we show a general secrecy
preservation theorem under reactive simulatability, the cryptographic
notion of secure implementation. This theorem is of independent
cryptographic interest. We then show that symbolic secrecy implies
cryptographic payload secrecy for the same cryptographic library as
used in key secrecy. Our results thus enable existing formal proof
techniques to establish cryptographically sound proofs of secrecy for
payload messages and exchanged keys.

Security Flaws in a Pairing-based Group Signature Scheme

Deng and Zhao recently proposed a group signature scheme.
We find that the scheme cannot satisfy all of the requirements of a secure group signature.

Nominative Proxy Signature Schemes

In a nominative proxy signature
scheme, an original singer delegates his signing power to a proxy,
who generates a nominative signature on behalf of the original
signer. In a nominative proxy signature scheme, only the nominee
can verify the signature and if necessary, only the nominee can
prove its validity to the third party. In this paper, we first
classify the nominative proxy signature into two types,
original-nominative proxy signature and proxy-nominative proxy
signature. Then we analyze the nominative proxy scheme proposed by
Park and Lee. We show that the scheme suffers from universal
verification. We also point out that the scheme presented by S.-H.
Seo and S.-H. Lee is insecure and the scheme cannot provide
non-repudiation. Finally we present our nominative proxy signature
schemes which overcome the weakness mentioned above. Compared with
the scheme recently proposed by G.-L. Wang, our scheme is more
efficient.

Post-Quantum Signatures

Digital signatures have become a key technology for making the Internet and other IT infrastructures secure. But in 1994 Peter Shor showed that quantum computers can break all digital signature schemes that are used today and in 2001 Chuang and his coworkers implemented Shor s algorithm for the first time on a 7-qubit NMR quantum computer. This paper studies the question: What kind of digital signature algorithms are still secure in the age of quantum computers?

Designs of Efficient Secure Large Hash Values

Uncategorized

Uncategorized

A double length hash function is a 2n-bit hash function based on
an n-bit compression function. To increase the security level,
designs of good double length hash functions are important. In
this paper we construct a class of maximally secure double length
hash functions in random oracle model based on some good
permutations. This class contains recently proposed double length
hash functions. We also propose an efficient double length hash function and study its security level in the random oracle model. We prove that any attack algorithm in the random oracle model needs \Omega(2^n/(s^2n^s)) time complexity, where $s$ is some parameter related to the rate of the hash function. Thus there is a trade-off between the efficiency and security. We use the notion of computable
message to make the security analysis of proposed hash functions. We also see that the security analysis of hash functions based on random permutations and hash functions based on random functions are very much related.

An Access Control Scheme for Partially Ordered Set Hierarchy with Provable Security

In a hierarchical structure, an entity has access to another if and only if the former is a superior of the later. The access control scheme for a hierarchy represented by a partially ordered set (poset) has been researched intensively in the past years. In this paper, we propose a new scheme that achieves the best performance of previous schemes and is provably secure under a comprehensive security model.

Solving Systems of Differential Equations of Addition and Cryptanalysis of the Helix Cipher

Uncategorized

Uncategorized

Mixing addition modulo 2^n (+) and exclusive-or has a host of applications
in symmetric cryptography as the operations are fast and nonlinear over GF(2). We deal with
a frequently encountered equation (x+y)XOR((x XOR a)+(y XOR b))=c$. The difficulty
of solving an arbitrary system of such equations -- named differential equations of
addition (DEA) -- is an important consideration in the evaluation of the security of many
ciphers against differential attacks. This paper shows that the satisfiability of an
arbitrary set of DEA -- which has so far been assumed \emph{hard} for large $n$ -- is in
the complexity class P. We also design an efficient algorithm to obtain all solutions to an
arbitrary system of DEA with running time linear in the
number of solutions.
Our second contribution is solving DEA in an adaptive query model where an equation
is formed by a query (a,b) and oracle output c. The challenge is to optimize the
number of queries to solve (x+y)XOR((x XOR a)+(y XOR b))=c. Our algorithm solves
this equation with only 3 queries in the worst case. Another algorithm solves the equation
(x+y)XOR(x+(y XOR b))=c$ with (n-t-1) queries in the worst case (t is the
position of the least significant `1' of x), and thus, outperforms the previous best
known algorithm by Muller -- presented at FSE~'04 -- which required 3(n-1) queries. Most
importantly, we show that the upper bounds, for our algorithms, on the number of queries
match worst case lower bounds. This, essentially, closes further research in this direction
as our lower bounds are optimal.
We used our
results to cryptanalyze a recently proposed cipher Helix, which was a candidate
for consideration in the 802.11i standard. We are successful in reducing the data
complexity of a DC attack on the cipher by a factor of 3 in the worst case (a factor
of 46.5 in the best case).

Provably Secure Authentication of Digital Media Through Invertible Watermarks

The recent advances in multimedia technology have made the manipulation of digital images, videos or audio files easy. On the one hand the broad availability of these new capabilities enabled numerous new applications. On the other hand, for the same reasons, digital media can easily be forged by almost anyone. To counteract this risk, fragile watermarks were proposed to protect the integrity and authenticity of digital multimedia objects. Traditional watermarking schemes employ non-cryptographic and signal processing oriented techniques, which fail to provide any provable security guarantee against malicious modification attempts. In this paper, we give for the first time a provably secure authentication mechanism for digital multimedia files that is based on both cryptographic signatures and invertible watermarks. While traditional watermarking schemes introduce some small irreversible distortion in the digital content, invertible watermarks can be completely removed from a watermarked work.

Asynchronous Proactive RSA

Uncategorized

Uncategorized

Nowadays, to model practical systems better, such as the Internet network and ad hoc networks, researchers usually regard these systems as asynchronous networks. Meanwhile, proactive secret sharing schemes are often employed to tolerate a mobile adversary. Considering both aspects, an asynchronous proactive threshold signature scheme is needed to keep computer systems secure.
So far, two asynchronous proactive secret sharing schemes have been proposed. One is proposed by Zhou in 2001, which is for RSA schemes. The other scheme is proposed by Cachin in 2002, which is a proactive secret sharing scheme for discrete-log schemes. There exist several drawbacks in both schemes. In Zhou¡¯s scheme, the formal security proof of this scheme is missing. Furthermore, Zhou¡¯s scheme needs to resort to the system administrator as the trusted third party for further run when some Byzantine errors occur. In Cachin¡¯s scheme, the building block is based on the threshold RSA scheme proposed by Shoup. However, how to proactivize Shoup¡¯s scheme is omitted in Cachin¡¯s scheme, so this scheme is incomplete.
In this paper, we present a complete provably secure asynchronous proactive RSA scheme (APRS). Our paper has four contributions. Firstly, we present a provably secure asynchronous verifiable secret sharing for RSA schemes (asynchronous verifiable additive secret sharing, AVASS), which is based on a verifiable additive secret sharing over integers. Secondly, we propose an asynchronous threshold RSA signature scheme that is based on the AVASS scheme and the random oracle model, and is capable of being proactivized. Thirdly, we present a provably secure threshold coin-tossing scheme on the basis of the above threshold RSA scheme. Fourthly, we propose an asynchronous proactive secret sharing based on the threshold RSA scheme and the coin-tossing scheme. Finally, combining the proactive secret sharing scheme and the threshold RSA scheme, we achieve a complete provably secure asynchronous proactive RSA scheme.

The Rabbit Stream Cipher - Design and Security Analysis

The stream cipher Rabbit was rst presented at FSE 2003 [6]. In the paper at hand, a full security analysis of Rabbit is given, focusing on algebraic attacks, approximations and dierential analysis. We determine the algebraic normal form of the main nonlinear parts of the cipher as part of a comprehensive algebraic analysis. In addition, both linear and nonlinear approximations of the next-state function are presented, as well as a differential analysis of the IV-setup function. None of the investigations have revealed any exploitable weaknesses. Rabbit is characterized by high performance in software with a measured encryption/decryption speed of 3.7 clock cycles per byte on a Pentium III processor.

The Security of the FDH Variant of Chaum's Undeniable Signature Scheme

In this paper,
we first introduce a new kind of adversarial goal
called {\em forge-and-impersonate} in
undeniable signature schemes.
Note that
forgeability does not necessarily imply impersonation ability.
We then classify the security of the FDH
variant of Chaum's undeniable signature scheme
according to three dimensions,
the goal of adversaries, the attacks
and the ZK level of confirmation and disavowal protocols.
We finally relate each security to some
well-known computational problem.
In particular,
we prove that the security of the FDH variant of Chaum's scheme with
NIZK confirmation and disavowal protocols
is equivalent to the CDH problem,
as opposed to the GDH problem
as claimed by Okamoto and Pointcheval.

Fault attack on the DVB Common Scrambling Algorithm

The Common Scrambling Algorithm (CSA) is used to encrypt streams of video data in the Digital Video Broadcasting (DVB) system. The algorithm uses a combination of a stream and a block cipher, apparently for a larger security margin. However these two algorithms share a common key. In this paper we present a fault attack on the block cipher which can be launched without regarding the stream cipher part. This attack allows us to reconstruct the common key and thus breaks the complete Algorithm.

Last updated: 2005-07-25

A New Designated Confirmer Signature Variant with Intended Recipient

Previous designated confirmer signature schemes were less
efficient because complex zero-knowledge proof employed in
confirmation and disavowal protocol. In this paper, we propose a
new efficient signature scheme which is recipient-specific and
confirmer-specific. The new scheme is transformed from ID-based
chameleon signature and inherits its advantage in simplicity and
efficiency. The scheme's security relies on the underlying secure
chameleon signature and public key encryption scheme. We also
considers the case of confirmer as an adversary in security proof.

Almost Ideal Contrast Visual Cryptography with Reversing

A drawback of visual cryptography schemes (VCS) is much loss of contrast in the reconstructed image. This paper shows a new paradigm of VCS in which the original image is almost perfectly reconstructed. A very simple non-cryptographic operation is assumed, reversing black and white, which many copy machines have these days. We first show a $(k,n)$-VCS with {\it reversing} such that white pixels are almost perfectly reconstructed in addition to the perfect reconstruction of black pixels. The proposed scheme is fully compatible with traditional VCS in the following sense: Even if we do not have a copy machine as described above, we can reconstruct the secret image $I$ exactly in the same way as in
the underlying VCS. In other words, we use a copy machine as a hedge to obtain better contrast.
We next show how to convert a perfect {\it black} $(k,n)$-VCS (with reversing) into a perfect {\it white} $(k,n)$-VCS with reversing. Thirdly, we show a perfect black VCS for any monotone access structure. Finally, we show applications of our idea to colored VCS and grey level VCS, respectively.

Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions

We investigate the average case complexity of a generalization of the compact knapsack problem to arbitrary rings: given $m$ (random) ring elements a_1,...,a_m in R and a (random) target value b in R, find coefficients x_1,...,x_m in S (where S is an appropriately chosen subset of R) such that a_1*x_1 + ... + a_m*x_m = b. We consider compact versions of the generalized knapsack where the set S is large and the number of weights m is small. Most variants of this problem considered in the past (e.g., when R = Z is the ring of the integers) can be easily solved in polynomial time even in the worst case. We propose a new choice of the ring R and subset S that yields generalized compact knapsacks that are seemingly very hard to solve on the average, even for very small values of m. Namely, we prove that for any unbounded function m = omega(1) with arbitrarily slow growth rate, solving our generalized compact knapsack problems on the average is at least as hard as the worst-case instance of various approximation problems over cyclic lattices. Specific worst-case lattice problems considered in this paper are the shortest independent vector problem SIVP and the guaranteed distance decoding problem GDD (a variant of the closest vector problem, CVP) for approximation factors n^{1+epsilon} almost linear in the dimension of the lattice.
Our results yield very efficient and provably secure one-way functions (based on worst-case complexity assumptions) with key size and time complexity almost linear in the security parameter n. Previous constructions with similar security guarantees required quadratic key size and computation time. Our results can also be formulated as a connection between the worst-case and average-case complexity of various lattice problems over cyclic and quasi-cyclic lattices.

Generation of random Picard curves for cryptography

Based on ideas in an earlier paper by Mark Bauer, Edlyn Teske and myself and ideas of Pierrick Gaudry and Eric Schost, we present an algorithm for counting the number of elements in the Jacobian of a random Picard curve over a finite prime field of cryptosize. We give two examples of curves with a Jacobian of prime group order.

ON THE DEGREE OF HOMOGENEOUS BENT FUNCTIONS

It is well known that the degree of a $2m$-variable bent function
is at most $m.$ However, the case in homogeneous bent functions is
not clear. In this paper, it is proved that there is no
homogeneous bent functions of degree $m$ in $2m$ variables when
$m>3;$ there is no homogenous bent function of degree $m-1$ in 2m
variables when $m>4;$ Generally, for any nonnegative integer $k$,
there exists a positive integer $N$ such that when $m>N$, there is
no homogeneous bent functions of degree $m-k$ in $2m$ variables.
In other words, we get a tighter upper bound on the degree of
homogeneous bent functions. A conjecture is proposed that for any
positive integer $k>1$, there exists a positive integer $N$ such
that when $m>N$, there exists homogeneous bent function of degree
$k$ in $2m$ variables.

Fault and Side-Channel Attacks on Pairing Based Cryptography

Current side-channel analytic attacks against public key cryptography focus on traditional schemes such as RSA and ECC, and to a lesser extent primitives such as XTR. However, bilinear maps, or pairings, have presented theorists with a new and increasingly popular way of constructing cryptographic protocols. Most notably, this has resulted in efficient methods for Identity Based Encryption (IBE). Since identity based cryptography seems an ideal partner for identity aware devices such as smart-cards, in this paper we examine the security of concrete pairing instantiations in terms of side-channel analysis.

New Monotone Span Programs from Old

Uncategorized

Uncategorized

In this paper we provide several known and one new constructions of new
linear secret sharing schemes (LSSS) from existing ones.
This constructions are well-suited for didactic purposes, which is a main
goal of this paper. It is well known that LSSS are in one-to-one correspondence with monotone span programs (MSPs).
MSPs introduced by Karchmer and Wigderson, can be viewed as a linear algebra model for computing a monotone function (access structure).
Thus the focus is in obtaining a MSP computing the new access
structure starting from the MSPs that compute the existing ones,
in the way that the size of the MSP after the transformation is well defined.
Next we define certain new operations on access structures and prove certain related
properties.

Short Linkable Ring Signatures for E-Voting, E-Cash and Attestation

A ring signature scheme can be viewed as a group signature scheme
with no anonymity revocation and with simple group setup. A
\emph{linkable} ring signature (LRS) scheme additionally allows
anyone to determine if two ring signatures have been signed by the
same group member. Recently, Dodis et al. \cite{DKNS04} gave a
short (constant-sized) ring signature scheme. We extend it to the
first short LRS scheme, and reduce its security to a new hardness
assumption, the Link Decisional RSA (LD-RSA) Assumption. We also
extend \cite{DKNS04}'s other schemes to a generic LRS scheme and a
generic linkable group signature scheme. We discuss three
applications of our schemes. Kiayias and Yung \cite{KY04}
constructed the first e-voting scheme which simultaneously
achieves efficient tallying, public verifiability, and write-in
capability for a typical voter distribution under which only a
small portion writes in. We construct an e-voting scheme based on
our short LRS scheme which achieves the same even for all
worst-case voter distribution. Direct Anonymous Attestation (DAA)
\cite{BCC04} is essentially a ring signature scheme with certain
linking properties that can be naturally implemented using LRS
schemes. The construction of an offline anonymous e-cash scheme
using LRS schemes is also discussed.

Cryptanalysis of Park-Lee Nominative Proxy Signature Scheme

Park and Lee have proposed a digital nominative proxy signature
scheme for mobile communication in [1]. They claimed that neither Origin signer nor Proxy agent can generate a valid signature solely. In this paper we show that Origin signer can generate a valid signature without the cooperation of the agent. In fact, the flaw comes from that Verifier dose not use the public key of Proxy agent in verifying phase. It's a serious designing error.

Parallel Montgomery Multiplication in $GF(2^k)$ using Trinomial Residue Arithmetic

We propose the first general multiplication algorithm in $\mathrm{GF}(2^k)$ with a
subquadratic area complexity of $\mathcal{O}(k^{8/5}) = \mathcal{O}(k^{1.6})$.
Using the Chinese Remainder Theorem, we represent the elements of
$\mathrm{GF}(2^k)$; i.e. the polynomials in
$\mathrm{GF}(2)[X]$ of degree at most $k-1$, by their remainder
modulo a set of $n$ pairwise prime trinomials,
$T_1,\dots,T_{n}$, of degree $d$ and such that $nd \geq k$.
Our algorithm is based on Montgomery's multiplication applied to the ring formed
by the direct product of the trinomials.

The Extended Codebook (XCB) Mode of Operation

We describe a block cipher mode of operation that implements a `tweakable' (super) pseudorandom permutation with an arbitrary block length. This mode can be used to provide the best possible security in systems that cannot allow data expansion, such as disk-block encryption and some network protocols. The mode accepts an additional input, which can be used to protect against attacks that manipulate the ciphertext by rearranging the ciphertext blocks.
Our mode is similar to a five-round Luby-Rackoff cipher in which the first and last rounds do not use the conventional Feistel structure, but instead use a single block cipher invocation. The third round is a Feistel structure using counter mode as a PRF. The second and fourth rounds are Feistel structures using a universal hash function; we re-use the polynomial hash over a binary field defined in the Galois/Counter Mode (GCM) of operation for block ciphers. This choice provides efficiency in both hardware and software and allows for re-use of implementation effort. XCB also has several useful properties: it accepts arbitrarily-sized plaintexts and associated data, including any plaintexts with lengths that are no smaller than the width of the block cipher.
This document is a pre-publication draft manuscript.