## All papers in 2005 (469 results)

A lower bound on the higher order nonlinearity of algebraic immune functions

We extend the lower bound, obtained by M. Lobanov, on the first order nonlinearity of functions with given algebraic immunity, into a bound on the higher order nonlinearities.

Blind Attacks on Engineering Samples

In addition to its usual complexity assumptions, cryptography
silently assumes that information can be physically protected in a
single location. As we now know, real-life devices are
not ideal and confidential information leaks through different physical
channels.\smallskip
Whilst most aspects of side channel leakage (cryptophthora)
are now well understood, no attacks on totally unknown algorithms
are known to date. This paper describes such an attack.\smallskip
By {\sl totally unknown} we mean that no
information on the algorithm's mathematical description (including the plaintext
size),
the microprocessor or the chip's power consumption model is available to the attacker.\smallskip
We successfully experimented the attack on a commercially available device produced by a
non-European smart-card manufacturer.

A Probabilistic Hoare-style logic for Game-based Cryptographic Proofs (Extended Version)

Uncategorized

Uncategorized

We extend a Probabilistic Hoare-style logic to formalize game-based
cryptographic proofs. Our approach provides a systematic and rigorous
framework, thus preventing errors from being introduced. We illustrate
our technique by proving semantic security of ElGamal.

Cryptanalysis of the Yang -Wang's password authentication schemes

In 1999, Yang and shieh proposed two password authentication schemes using smart cards. But in 2003, Sun and Yeh indicated that their schemes are subject to the forgery attack. So in 2005, Yang and Wang proposed an improvement of Yang and Shieh¡¦s schemes to resist against Sun and Yeh¡¦s attack. However in this paper, we will point out that Yang and Wang¡¦s schemes still suffer from the forgery attack. Because in their schemes, one can masquerade as a legal user and cheat the remote server successfully in the authentication phase.

A sequence approach to constructing perfect hash families

A linear $(q^d,q,t)$-perfect hash family of size $s$ in a
vector space $V$ of order $q^d$ over a field $F$ of order $q$ consists of a
set $\phi_1,\ldots,\phi_s$ of linear functionals from $V$ to $F$
with the following property: for all $t$ subsets $X\subseteq V$
there exists $i\in\{1,\ldots,s\}$ such that $\phi_i$ is injective
when restricted to $F$. A linear $(q^d,q,t)$-perfect hash family of
minimal size $d(t-1)$ is said to be {\em optimal}. In this paper we
extend the theory for linear perfect hash families based on sequences
developed by Blackburn and Wild. We develop techniques which we use to
construct new optimal linear $(q^2,q,5)$-perfect hash families and
$(q^4,q,3)$-perfect hash families. The sequence approach also
explains a relationship between linear $(q^3,q,3)$-perfect hash
families and linear $(q^2,q,4)$-perfect hash families.

Equivalent Keys in Multivariate Quadratic Public Key Systems

Multivariate Quadratic public key schemes have been suggested back in 1985 by Matsumoto and Imai
as an alternative for the RSA scheme.
Since then, several other schemes have been proposed, for example Hidden Field Equations,
Unbalanced Oil and Vinegar schemes, and Stepwise Triangular Schemes.
All these schemes have a rather large key space for a secure choice of parameters.
Surprisingly, the question of equivalent keys has not been discussed in the open literature
until recently.
In this article, we show that for all basic classes mentioned above,
it is possible to reduce the private --- and hence the public ---
key space by several orders of magnitude. For the Matsumoto-Imai scheme, we are even able to show that
the reductions we found are the only ones possible, i.e., that these reductions are tight.
While the theorems developed in this article are of independent interest themselves
as they broaden our understanding of Multivariate Quadratic public key systems,
we see applications of our results both in cryptanalysis and in
memory efficient implementations of MQ-schemes.

More short signatures without random oracles

We construct three new signatures and prove their securities without random oracles. They are motivated, respectively, by Boneh and Boyen's, Zhang, et al.'s, and Camenisch and Lysyanskaya's signatures without random oracles. The first two of our signatures are as short as Boneh and Boyen's (resp. Zhang, et al.'s} state-of-the-art short signatures. Our third signature is reducible to a modified LRSW Assumption but without their hypothesized external signing oracle. New and interesting variants of the q-SDH Assumption, the q-SR (Square Root) Assumption are also presented. New and independently interesting proof techniques extending the two-mode technique of Boneh and Boyen are used, including a combined three-mode simulation and rewinding in the standard model.

A Simplified Quadratic Frobenius Primality Test

The publication of the quadratic Frobenius primality test by
Grantham, 1998 has stimulated a lot of researchin this area. In this test as well as in the Miller-Rabin test a composite number may be
declared as probably prime. Repeating several tests decreases that
error probability. While most research papers in this subject focus on minimising the error probability as a function of the number of
tests (or, more generally, of the computational effort)
asymptotically, we present a simplified variant SQFT of the
quadratic Frobenius test. This test is so simple that it can easily
be implemented on a smart card.
During prime number generation, a large number of composite numbers
must be tested before a (probable) prime is found. Therefore we need
a fast test, such as the Miller-Rabin test with a small basis, to
rule out most prime candidates quickly before a promising candidate
will be tested with a more sophisticated variant of the QFT. Our
test SQFT makes optimum use of the information gathered by a
previous Miller-Rabin test. It has run time equivalent to two
Miller-Rabin tests; and it achieves a worst-case error probability
of $2^{-12t}$ with $t$ tests.
Most cryptographic standards require an average-case error
probability of at most $2^{-80}$ or $2^{-100}$, when prime numbers
are generated in public key systems. Our test SQFT achieves an average-case error probability of $2^{-134}$ with two test rounds for $500-$bit primes.
We also present a more sophisticated version SQFT3 of our test that has run time and worst-case error probability comparable to the test EQFTwc by Damg\aa rd and Frandsen, 2003, in all cases. Our test SQFT3 avoids the computation of cubic residuosity symbols, as required in the test EQFTwc.

Parallel and Concurrent Security of the HB and HB+ Protocols

At Crypto 2005, Juels and Weis (building on work of Hopper and Blum) proposed and analyzed two shared-key authentication protocols --- HB and HB+ --- whose extremely low computational cost makes them attractive for low-cost devices such as radio-frequency identification (RFID) tags. Security of these protocols is based on the conjectured hardness of the ``learning parity with noise'' (LPN) problem: the HB protocol is proven secure against a passive (eavesdropping) adversary, while the HB+ protocol is proven secure against active attacks.
Juels and Weis prove security of these protocols only for the case of sequential executions, and explicitly leave open the question of whether security holds also in the case of parallel or concurrent executions. In addition to guaranteeing security against a stronger class of adversaries, a positive answer to this question would allow the HB+ protocol to be parallelized, thereby reducing its round complexity from super-logarithmic (in the security parameter) to 3.
Using a recent result by Regev (STOC 2005) regarding the LPN problem, we answer the aforementioned question in the affirmative and prove security of the HB and HB+ protocols under parallel/concurrent executions. Applying Regev's result also yields what we find to be substantially simpler security proofs for these protocols which are also more complete in that they explicitly address the dependence of the soundness error on the number of iterations.

One-Time HNP or Attacks on a Flawed El Gamal Revisited

We present a modification of the well-known hidden number problem (HNP) which we refer to as a one-time HNP (OT-HNP). We also present an algorithm for solving such a problem together with its formal analysis. We show then that carefully designed instances of OT-HNP can be used to break certain flawed implementations of public key schemes efficiently. We work, for instance, with Nguyen’s attack on El Gamal’s signature scheme in the GNU Privacy Guard of version 1.2.3. The technique employed there was not based on HNP, since it was supposed that more than one signature would be necessary, which seemed to be a wastage. We will see, however, that by using OT-HNP one signature is still far enough, while retaining certain elegance of the HNP approach. We also present an experimental confirmation of this result.

A Practical Attack on the Root Problem in Braid Groups

Uncategorized

Uncategorized

Using a simple heuristic approach to the root problem in braid groups, we show that cryptographic parameters proposed in this context must be considered as insecure. In our experiments we can, often within seconds, extract the secret key of an authentication system based on the root problem in braid groups.

Seifert's RSA Fault Attack: Simplified Analysis and Generalizations

Seifert recently described a new fault attack against an implementation of RSA signature verification. Here we give a simplified analysis of Seifert's attack and gauge its practicality against RSA moduli of practical sizes. We suggest an improvement to Seifert's attack which has the following consequences: if an adversary is able to cause random faults in only 4 bits of a 1024-bit RSA modulus stored in a device, then there is a greater than 50% chance that they will be able to make that device accept a signature on a message of their choice. For 2048-bit RSA, 6 bits suffice.

Weakness of shim¡¦s New ID-based tripartite multiple-key agreement protocol

In this article we show that Shim¡¦s new ID-based tripartite multiple-key agreement protocol still suffers from the impersonation attack, a malicious user can launch an impersonation attack on their protocol.

A Secure Scheme for Authenticated Encryption

The paper proposes a new scheme of authenticated encryption that is either publicly verifiable or not publicly verifiable depending on the quantity of information the recipient released. This property would give recipient much flexibility in many applications. This scheme combines the ElGamal encryption with Schnorr signature. Considering the security goal of signature, the resultant scheme is at least as secure as that of the combined signature scheme. The security goal of encryption is examined under the chosen ciphertext attack, it is proven directly related to the security of signature. Furthermore, this new scheme is also secure against one-more-decryption attack. This novel security goal may be valuable in the applications of private information retrieval.

Enhancing CK-Model for Key Compromise Impersonation Resilience and Identity-based Key Exchange

Uncategorized

Uncategorized

In 2001, Canetti and Krawczyk proposed a security model (CK-model) for authentication protocols. They also gave an indistinguishability-based definition for key exchange protocols. Since then the model has almost exclusively been used for analyzing key exchange protocols, although it can be applied to authentication protocols in general. The model not only captures a large class of attacks but also provides a modular approach to the design of authentication protocols. However, the model does not capture the property of Key Compromise Impersonation (KCI) Resilience. Until now, analysis concerning this property has mostly been done heuristically and restricted to key exchange protocols only. Previous attempts on formalizing KCI have mostly been done in some ad hoc manner and additional proofs have to be given, specifically for the security of KCI resilience. In this paper, we propose an extension to the CK-model, which allows, for the first time, the KCI attacks to be considered in authentication protocols in general, rather than restricted to key exchange protocols, and no more additional proofs are required specifically for KCI security.
With the revival of interest in identity-based (ID-based) cryptography, there have been many new ID-based key exchange protocols proposed. Despite the fact that some of them have been proven in some restricted versions of a model proposed by Bellare and Rogaway in 1993 and some others have been proven in the original CK-model, there is no rigorous model specifically for ID-based key exchange security. In particular, forward secrecy against compromised Key Generation Server (KGS-FS) has never been captured even though this notion is more important and stronger than the perfect forward secrecy in ID-based key exchange. For this, we further extend our model to ID-based setting and capture the property of KGS-FS for ID-based key exchange security.

Efficient Arithmetic on Subfield Elliptic Curves over Small Odd Characteristics

In elliptic curve cryptosystems, scalar multiplications performed on the curves have much effect on the efficiency of the schemes, and many efficient methods have been proposed. In particular, recoding methods of the scalars play an important role in the performance of the algorithm used. For integer radices, non-adjacent form (NAF) and its generalizations (e.g., generalized non-adjacent form (GNAF) and radix-$r$ non-adjacent form ($r$NAF) \cite{CL73,TYW04}) are proposed for minimizing the non-zero densities in the representations of the scalars. On the other hand, for subfield elliptic curves, Frobenius-adic expansions of the scalars can be used for improving efficiency (\cite{Sma99+}). Unfortunately, there are only a few methods apply the techniques of NAF or its analogue to Frobenius-adic expansion, namely $\tau$-adic NAF techniques (\cite{Kob98,Sol00,BMX04} and \cite{GLS01}) for Koblitz curves and hyperelliptic Koblitz curves. In this paper, we try to combine these techniques, namely recoding methods for reducing non-zero density and Frobenius-adic expansion, and propose two new efficient recoding methods of scalars for more general family of subfield elliptic curves over odd characteristics. We also prove that the non-zero densities for the new methods are same as those for original GNAF and $r$NAF. As a result, the speed of the proposed schemes improve between 12.5{\%} and 79{\%} over that for previously known schemes.

Further Constructions of Almost Resilient Functions

Almost resilient function is the generalization of resilient
function and have important applications in multiple authenticate
codes and almost security cryptographic Boolean functions.In this
paper,some secondary constructions are provided.In particular, the
theorem $3$ in {\cite {ke}} is improved. As $\varepsilon
$-almost$(n,1,k)$-CI functions plays an important role in the
secondary constructions, we concluded some properties and
constructions. Specially we presented a spectrum characterization
of balanced almost CI function, which can be used to identify a
balanced almost CI function by computing its walsh
spectra.

Using Probabilistic I/O Automata to Analyze an Oblivious Transfer Protocol

Uncategorized

Uncategorized

The Probabilistic I/O Automata framework of
Lynch, Segala and Vaandrager provides
tools for precisely specifying protocols and reasoning about their
correctness using multiple levels of abstraction, based on
implementation relationships between these levels.
We enhance this framework to allow analyzing
protocols that use cryptographic primitives. This requires resolving and
reconciling issues
such as nondeterministic behavior and scheduling, randomness,
resource-bounded computation, and computational hardness assumptions.
The enhanced framework allows for more rigorous and systematic
analysis of cryptographic protocols. To demonstrate the use of this
framework, we present an example analysis that we have done for an
Oblivious Transfer protocol.

Weaknesses of the Boyd-Mao Deniable Authenticated key Establishment for Internet Protocols

In 2003, Boyd and Mao proposed two deniable authenticated key establishment
protocols using elliptic curve pairings for Internet protocols, one is based on
Diffie-Hellman key exchange and the other is based on Public-Key Encryption
approach. For the use of elliptic curve pairings, they declared that their schemes could
be more efficient than the existing Internet Key Exchange (IKE), nowadays. However
in this paper, we will show that both of Boyd-Mao¡¦s protocols suffer from the
key-Compromise Impersonation attack.

Improvement of Manik et al.¡¦s remote user authentication scheme

In 2005, Manik et al. propose a novel remote user authentication scheme using bilinear pairings which allows a valid user to login to the remote system but prohibits too many users to login with the same login-ID. It also provides a flexible password change
function. In this paper, we will show that this remote user authentication scheme is not secure, an adversary can always pass the authentication.

On the Boolean functions With Maximum Possible Algebraic Immunity : Construction and A Lower Bound of the Count

This paper gives a construction method which can get a large class
of Boolean functions with maximum algebraic immunity(AI) from one
such giving function. Our constructions get more functions than any
previous construction. The cryptographic properties, such as
balance, algebraic degree etc, of those functions are studied. It
shows that we can construct Boolean functions with better
cryptographic properties, which gives the guidance for the design of
Boolean functions to resist algebraic attack, and helps to design
good cryptographic primitives of cryptosystems. From these
constructions, we show that the count of the Boolean functions with
maximum AI is bigger than ${2^{2^{n-1}}}$ for $n$ odd, bigger than
${2^{2^{n-1}+\frac{1}{2}\binom{n}{\frac{n}{2}} }}$ for $n$ even,
which confirms the computer simulation result that such boolean
functions are numerous. As far as we know, this is the first bound
about this count.

On the (In)security of Stream Ciphers Based on Arrays and Modular Addition (Full Version)

Uncategorized

Uncategorized

Stream ciphers play an important role in symmetric cryptology because of
their suitability in high speed applications where block ciphers fall short. A large number
of fast stream ciphers or pseudorandom bit generators (PRBG's) can be found in the
literature that are based on arrays and simple operations such as modular additions,
rotations and memory accesses (e.g. RC4, RC4A, Py, Py6, ISAAC etc.). This paper
investigates the security of array-based stream ciphers (or PRBG's) against certain types
of distinguishing attacks in a unified way. We argue, counter-intuitively, that the most
useful characteristic of an array, namely, the association of array-elements with unique
indices, may turn out to be the origins of distinguishing attacks if adequate caution is
not maintained. In short, an adversary may attack a cipher simply exploiting the dependence
of array-elements on the corresponding indices. Most importantly, the weaknesses are not
eliminated even if the indices and the array-elements are made to follow uniform
distributions separately. Exploiting these weaknesses we build distinguishing attacks with
reasonable advantage on five recent stream ciphers (or PRBG's), namely, Py6 (2005, Biham
\emph{et al.}), IA, ISAAC (1996, Jenkins Jr.), NGG, GGHN (2005, Gong \emph{et al.}) with
data complexities $2^{68.61}$, $2^{32.89}$, $2^{16.89}$, $2^{32.89}$ and $2^{32.89}$
respectively. In all the cases we worked under the assumption that the key-setup algorithms
of the ciphers produced uniformly distributed internal states. We only investigated the
mixing of bits in the keystream generation algorithms. In hindsight, we also observe that
the previous attacks on the other array-based stream ciphers (e.g. Py, etc.), can also be
explained in the general framework developed in this paper. We hope that our analyses will
be useful in the evaluation of the security of stream ciphers based on arrays and modular
addition.

A new key exchange protocol based on the decomposition problem

In this paper we present a new key establishment protocol based on the decomposition problem in non-commutative groups which is: given two elements w, w_1 of the platform group G and two subgroups A, B of G (not necessarily distinct), find elements a in A, b in B such that w_1 = a w b. Here we introduce two new ideas that improve the security of key establishment protocols based on the decomposition problem.
In particular, we conceal (i.e., do not publish explicitly) one of the subgroups A, B, thus introducing an additional computationally hard problem for the adversary, namely, finding the centralizer of a given
finitely generated subgroup.

Democratic Group Signatures on Example of Joint Ventures

In the presence of economic globalization joint venture is one of the most common and effective means of conducting business internationally. By building joint ventures companies form strategic alliances that help them to enter new economic markets and further their business goals in a cooperative effort without loosing own independence. Upon building a joint venture company, two or more "parent" companies agree to share capital, technology, human ressources, risks and rewards in a formation of a new entity under shared control by a "board of directors", which consists of representatives of "parent" companies. The establishment of such shared control is tricky and relies generally on the "trust, but verify" relationship, i.e., companies trust the information they receive from prospective partners, but it is a good business practice to verify the facts. In this paper we focus on the issue of the shared financial control in a joint venture. We consider the mostly preferred form of the control where every member of the board is able to issue payment orders on behalf of the joint venture, but at the same time representatives of other companies, should be able to monitor the accounting to achieve fairness in the spending of shared funds. For this form of the shared control we propose a new secure group-oriented signature scheme, called a {\it democratic group signature} scheme, which results from the modification of the standard notion of group signatures by eliminating the role of the group manager. We also show that existing schemes, e.g., ring and group signatures, cannot be used to realize the required shared control based on the "trust, but verify" relationship.

An Anonymous Authentication Scheme for Trusted Computing Platform

The Trusted Computing Platform is the industrial initiative to implement computer
security. However, privacy protection is a critical problem that must be solved
in Trusted Computing Platform. In this paper, we propose a simple and efficient method to
implement anonymous authentication in such setting.
The new scheme is proved to be secure under
the strong RSA assumption and decisional Diffie-Hellman assumption.

Privacy-Preserving Polling using Playing Cards

Uncategorized

Uncategorized

Visualizing protocols is not only useful as a step towards
understanding and ensuring security properties, but is also a
beneficial tool to communicate notions of security to decision
makers and technical people outside the field of cryptography. We
present a simple card game that is a visualization for a secure
protocol for private polling where it is simple to see that
individual responses cannot be traced back to a respondent, and
cheating is irrational. We use visualization tricks to illustrate a
somewhat complex protocol, namely the Cryptographic Randomized
Response Technique protocol of Lipmaa et al. While our tools ---
commitments and cut-and-choose --- are well known, our construction
for oblivious transfer using playing cards is new. As part of
visualizing the protocol, we have been able to show that, while
cut-and-choose protocols normally get more secure with an increasing
number of choices, the protocol we consider --- surprisingly ---
does not. This is true for our visualization of the protocol and
for the real protocol.

Revised: Block Cipher Based Hash Function Construction From PGV

Uncategorized

Uncategorized

Preneel, Govaerts, and Vandewalle[12] considered the 64 most basic ways to construct a hash function from a block cipher, and regarded 12 of these 64 schemes as secure. Black, Pogaway and Shrimpton[3] proved that, in black-box model, the 12 schemes that PGV singled out as secure really are secure and given tight upper and lower bounds on their collision resistance. And also they pointed out, by stepping outside of the Merkle-Damgard[5] approach to analysis, an additional 8 of the 64 schemes are just as collision resistant as the first group of schemes. In this paper we point out that the 12 compression functions that PGV singled out are free start collision resistant and others are not, the additional 8 compression functions are only fix start collision resistant as singled out by BRS, the
hash functions based on those 20 schemes are fix start collision resistant, the upper bound of collision resistance and preimage resistant are given based on conditional probability of compression function, not based on assumption of random oracle model, the bounds
have more practical value than the bounds given by BRS. In view point of collision resistant, the best 4 schemes are not among the 12 schemes singled by PGV, and among the 8 schemes point out by BRS,
and block cipher E itself is the best compression to build a collision resistant hash function. At the end of the paper, two recommend structure of block cipher based hash function are given, and a prove of their securities are also given.

One-Time Signatures Revisited: Have They Become Practical?

Uncategorized

Uncategorized

One-time signatures have been known for more than two decades, and
have been studied mainly due to their theoretical value. Recent
works motivated us to examine the practical use of one-time
signatures in high-performance applications. In this paper we
describe FMTseq - a signature scheme that merges recent
improvements in hash tree traversal into Merkle's one-time signature
scheme. Implementation results show that the scheme provides a
signature speed of up to 35 times faster than a 2048-bit RSA
signature scheme, for about one million signatures, and a signature
size of only a few kilobytes. We provide an analysis of practical
parameter selection for the scheme, and improvements that can be
applied in more specific scenarios.

Tight bound between nonlinearity and algebraic immunity

We obtain tight bound between nonlinearity and algebraic immunity
of a Boolean function and construct balanced functions that
achive this bound for all possible values of parameters.

Last updated: 2006-02-08

HB++: a Lightweight Authentication Protocol Secure against Some Attacks

At Crypto'05, Juels and Weis introduce HB+, an enhancement of the Hopper and Blum (HB) authentication protocol. This protocol HB+ is proven secure against active attacks, though preserving HB's advantages: mainly, requiring so few resources to run that it can be implemented on an RFID tag. However, in a wider adversarial model, Gilbert, Robshaw and Sibert exhibit a very effective attack against HB+.
We here show how a modification of the HB+ protocol thwarts Gilbert et al's attack. The resulting protocol, HB++, remains a good candidate for RFID tags authentication.

A note on the n-spendable extension of Ferguson's single-term off-line coins

We show that an adversary can over-spend a coin n(n+1)! times without being detected and identified in the n-spendable extension of Ferguson's single-term off-line coin, simply by permuting the witness messages in the three-move zero-knowledge proof payment protocol. We repair the detection scheme by adding a simple verification rule in the payment protocol. We repair the identification scheme by restricting the identity format.

Minimal Assumptions for Efficient Mercurial Commitments

Mercurial commitments were introduced by Chase et al. (Eurocrypt 2005)
and form a key building block for constructing zero-knowledge sets
(introduced by Micali, Rabin and Kilian (FOCS'03)}). Unlike regular
commitments, which are strictly binding, mercurial commitments allow
for certain amount of (limited) freedom. The notion of Chase et al.
also required that mercurial commitments should be equivocable given a
certain trapdoor, although the notion is interesting even without this
condition. While trivially implying regular (trapdoor) commitments, it
was not clear from the prior work if the converse was true: Chase et
al. gave several constructions of mercurial commitments from various
incompatible assumptions, leaving open if they can be built from any
(trapdoor) commitment scheme, and, in particular, from any one-way
function. We give an affirmative answer to this question, by giving
two simple constructions of mercurial commitments from any trapdoor
bit commitment scheme. By plugging in various (trapdoor) bit
commitment schemes, we get *all* the efficient constructions from
Chase et al. and Micali et al., as well as several immediate new
constructions.
Our results imply that (a) ** mercurial commitments can be viewed as
surprisingly simple variations of regular (trapdoor) commitments **
(and, thus, can be built from one-way functions and, more efficiently,
from a variety of other assumptions); and (b) ** the existence of
zero-knowledge sets is equivalent to the existence of
collision-resistant hash functions ** (moreover, the former can be
efficiently built from the latter and trapdoor commitments). Of
independent interest, we also give a stronger and yet much simpler
definition of mercurial commitments than that of Chase et al. (which
is also met by our constructions). Overall, we believe that our
results eludicate the notion of mercurial commitments, and better
explain the rational following the previous constructions of
mercurial commitments.

Last updated: 2005-12-06

On Boolean functions with maximum algebraic immunity

Uncategorized

Uncategorized

In this paper two important issues in theory of algebraic
attacks are addressed. We first provide a theoretical framework for better
understanding of design rationale in construction of Boolean
functions with maximum algebraic immunity. Based on these results,
an iterative design of functions with maximum possible algebraic
immunity is proposed. In contrast to known constructions, our method
generates balanced functions of maximum degree and high
nonlinearity, that is functions satisfying all main cryptographic
criteria. Additionally, functions in this class have a low
implementation cost due to a small number of terms in the ANF.
Secondly, for a given
Boolean function, a novel algorithm
for deciding the existence of annihilators of small degree
is presented. The algorithm utilizes the known
methods in a slightly different manner which results in
a significantly reduced complexity of computation.

A Note on the Kasami Power Function

This work is motivated by the observation that the function $\F{m}$ to $\F{m}$
defined by $x^d+(x+1)^d+a$ for some $a\in \F{m}$ can be used to construct difference sets.
A desired condition is, that the function $\varphi _d(x):=x^d+(x+1)^d$ is a $2^s$-to-1 mapping.
If $s=1$, then the function $x^d$ has to be APN.
If $s>1$, then there is up to equivalence only one function known:
The function $\varphi _d$ is a $2^s$-to-1 mapping if
$d$ is the Gold parameter $d=2^k+1$ with $\gcd (k,m)=s$.
We show in this paper, that $\varphi _d$ is also a $2^s$-to-1 mapping if
$d$ is the Kasami parameter $d=2^{2k}-2^k+1$ with $\gcd (k,m)=s$ and $m/s$ odd.
We hope, that this observation can be used to construct more difference sets.

Concurrent Blind Signatures without Random Oracles

Uncategorized

Uncategorized

We present a blind signature scheme that is efficient and provably
secure without random oracles under concurrent attacks utilizing
only four moves of short communication. The scheme is based on
elliptic curve groups for which a bilinear map exists and on
extractable and equivocable commitments. The unforgeability of the
employed signature scheme is guaranteed by the LRSW assumption
while the blindness property of our scheme is guaranteed by the
Decisional Linear Diffie-Hellman assumption.
We prove our construction secure under the above assumptions as
well as Paillier's DCR assumption in the concurrent attack model
of Juels, Luby and Ostrovsky from Crypto '97 using a common
reference string. Our construction is the first efficient
construction for blind signatures in such a concurrent model
without random oracles. We present two variants of our basic
protocol: first, a blind signature scheme where blindness still
holds even if the public-key generation is maliciously controlled;
second, a blind signature scheme that incorporates a ``public-tagging'' mechanism. This latter variant of our scheme gives rise to a partially blind signature with essentially the same efficiency and security properties as our basic scheme.

Prompted User Retrieval of Secret Entropy: The Passmaze Protocol

A prompting protocol permits users to securely retrieve secrets with
greater entropy than passwords. The retrieved user secrets can have
enough entropy to be used to derive cryptographic keys.

Proxy Re-Signatures: New Definitions, Algorithms, and Applications

In 1998, Blaze, Bleumer, and Strauss (BBS) proposed proxy re-signatures, in which a semi-trusted proxy acts as a translator between Alice and Bob. To translate, the proxy converts a signature from Alice into a signature from Bob on the same message. The proxy, however, does not learn any signing key and cannot sign arbitrary messages on behalf of either Alice or Bob. Since the BBS proposal, the proxy re-signature primitive has been largely ignored, but we show that it is a very useful tool for sharing web certificates, forming weak group signatures, and authenticating a network path.
We begin our results by formalizing the definition of security for a proxy re-signature. We next substantiate the need for improved schemes by pointing out certain weaknesses of the original BBS proxy re-signature scheme which make it unfit for most practical applications. We then present two secure proxy re-signature schemes based on bilinear maps.
Our first scheme relies on the Computational Diffie-Hellman (CDH) assumption; here the proxy can translate from Alice to Bob and vice-versa. Our second scheme relies on the CDH and 2-Discrete Logarithm (2-DL) assumptions and achieves a stronger security guarantee -- the proxy is only able to translate in one direction. Constructing such a scheme has been an open problem since proposed by BBS in 1998. Furthermore in this second scheme, even if the delegator and the proxy collude, they cannot sign on behalf of the delegatee. Both schemes are efficient and secure in the random oracle model.

On the Security of Kaweichel

In this report the block cipher Kaweichel is examined with regard to linear and differential cryptanalysis. As a result of this investigation new versions with a reduced number of rounds are proposed.

Is it possible to have CBE from CL-PKE?

Recently, Al-Riyami and Paterson proposed a generic conversion from
CL-PKE (Certificateless Public Key Encryption) to CBE (Certificate
Based Encryption) and claimed that the derived CBE scheme is secure
and even more efficient than the original scheme of Gentry. In this
paper, we show that their conversion is wrong due to the flaw of the
security proof. It leads the new concrete CBE scheme by Al-Riyami
and Paterson to be invalidated. In addition, our result supports the
impossibility to relate both notions in any directions.

F-HASH: Securing Hash Functions Using Feistel Chaining

Uncategorized

Uncategorized

The Feistel structure is well-known as a good structure for building block ciphers, due to its property of invertibility. It can be made non-invertible by fixing the left half of the input to 0, and by discarding the left half of the output bits. It then becomes suitable as a hash function construction. This paper uses the structure to build a hash function called F-Hash, which is immune to recent attack styles. In this paper, a more precise evaluation method, based upon conditional probability, is given.

Signature from a New Subgroup Assumption

We present a new signature whose security is reducible to a new assumptions about subgroups, the {\em Computational Conjugate Subgroup Members (CCSM) Assumption}, in the random oracle model.

Loud and Clear: Human-Verifiable Authentication Based on Audio

Uncategorized

Uncategorized

Secure pairing of electronic devices that lack
any previous association is a challenging problem which has been
considered in many contexts and in various flavors.
In this paper, we investigate an alternative and complementary approach--the use of the audio channel for human-assisted
authentication of previously un-associated devices.
We develop and evaluate a system we call Loud-and-Clear
(L&C) which places very little demand on
the human user. L&C involves the use of a text-to-speech (TTS)
engine for vocalizing a robust-sounding and syntactically-correct
(English-like) sentence derived from the hash of a device's public key. By coupling vocalization on one device with the display of the same information on another device, we demonstrate that L&C is suitable for secure device pairing (e.g., key exchange) and similar tasks. We also describe several common use cases, provide some performance data for our prototype implementation and discuss the security properties of L&C.

Solutions to Key Exposure Problem in Ring Signature

In this paper, we suggest solutions to the key exposure problem in ring signature. In particular, we propose the first forward secure ring signature scheme and the first key-insulated ring signature schemes. Both constructions allow a $(t,n)$-threshold setting. That is, even $t$ secret keys are compromised, the validity of all forward secure ring signatures generated in the past is still preserved. In the other way, the compromise of up to all secret keys does not allow any adversary to generate a valid key-insulated ring signature for the remaining time periods.

On the Security of a Certificateless Public-Key Encryption

Certificateless public-key cryptosystem is a recently proposed
attractive paradigm using public key cryptosystem, which avoids
the key escrow inherent in identity-based public-key
cryptosystems, and does not need certificates to generate trust in
public keys. In 2005, Al-Riyami and Paterson proposed a new
certificateless public-key encryption scheme and proved its security in the random oracle model. This paper shows that their scheme is vulnerable to adaptive chosen ciphertext attacks, and presents a countermeasure to overcome such a security flaw.

Improved Collision Attack on Hash Function MD5

Uncategorized

Uncategorized

In this paper, we present a fast attack algorithm to find two-block collision of hash function MD5. The algorithm is based on the two-block collision differential path of MD5 that was presented by Wang et al. in EUROCRYPT 2005[6]. We found that the derived conditions for the desired differential path in [6] were not sufficient to guarantee the differential path to hold and that some conditions could be relaxed to enlarge the collision set. By using technique of small range searching and omitting the computing steps to check the characteristics in algorithm, we can speed up the attack of MD5 efficiently. Compared with the Advanced Message Modification technique [5,6], the small range searching technique can correct 4 more conditions for the first iteration differential and 3 more conditions for the second iteration differential, thus improving the probability and the complexity to find collisions. The whole attack on the MD5 can be accomplished within 5 hours using a PC with Pen-tium4 1.70GHZ CPU.

Efficient Mutual Data Authentication Using Manually Authenticated Strings

Solutions for an easy and secure setup of a wireless connection between two devices are urgently needed for WLAN, Wireless USB, Bluetooth and similar standards for short range wireless communication. In this paper we analyse the SAS protocol by Vaudenay and propose a new three round protocol MA-3 for mutual data authentication based on a cryptographic commitment scheme and short manually authenticated out-of-band messages. We show that non-malleability of the commitment scheme is essential for the security of the SAS and the MA-3 schemes and that extractability or equivocability do not imply non-malleability. We also give new proofs of security for the SAS and MA-3 protocols and suggestions how to instantiate the MA-3 protocol in practise.

Last updated: 2005-12-13

ID-based signature and Key-insulated threshold signature

Identity-based (simply ID-based) cryptosystem was proposed in
order to simplify key management procedures of certificate-based
public key infrastructures. In 2003 Sakai and Kasahara proposed a
new ID-based encryption scheme (SK-IBE). In our paper, it is
intended to build a new ID-based signature (IBS) scheme which
shares the same system parameters with SK-IBE. SK-IBE and our
signature scheme yield a new complete ID-based public key
cryptosystem. The proposed signature scheme is provably secure
against existential forgery for adaptive chosen message and
identity attack in the random oracle model based on a reasonably
well-explored hardness assumption. Another contribution of this
paper is that we first propose the notion of key-insulated
threshold signature and present a generic method for constructing
key-insulated threshold signature scheme.

On Anonymity of Group Signatures

A secure group signature is required to be anonymous, that is,
given two group signatures generated by two different members on
the same message or two group signatures generated by the same
member on two different messages, they are indistinguishable
except for the group manager. In this paper we prove the
equivalence of a group signature's anonymity and its
indistinguishability against chosen ciphertext attacks if we view
a group signature as an encryption of member identity.
Particularly, we prove ACJT's group signature is IND-CCA2 secure,
so ACJT's scheme is anonymous in the strong sense. The result is
an answer to an open question in literature.

Key-dependent Message Security under Active Attacks -- BRSIM/UC-Soundness of Symbolic Encryption with Key Cycles

Key-dependent message security, short KDM security, was introduced by
Black, Rogaway and Shrimpton to address the case where key cycles
occur among encryptions, e.g., a key is encrypted with itself. It was
mainly motivated by key cycles in Dolev-Yao models, i.e., symbolic
abstractions of cryptography by term algebras, and a corresponding
soundness result was later shown by Adão et al. However, both the
KDM definition and this soundness result do not allow the general
active attacks typical for Dolev-Yao models and for security protocols
in general.
We extend these definitions so that we can obtain a soundness result
under active attacks. We first present a definition AKDM as a KDM
equivalent of authenticated symmetric encryption, i.e., it provides
chosen-ciphertext security and integrity of ciphertexts even for key
cycles. However, this is not yet sufficient for the desired
soundness, and thus we give a definition DKDM that additionally allows
limited dynamic revelation of keys. We show that this is sufficient
for soundness, even in the strong sense of blackbox reactive
simulatability (BRSIM)/UC and including joint terms with other
operators.
We also present constructions of schemes secure under the new
definitions, based on current KDM-secure schemes. Moreover, we
explore the relations between the new definitions and existing ones
for symmetric encryption in detail, in the sense of implications or
separating examples for almost all cases.

Efficient Scalar Multiplication by Isogeny Decompositions

On an elliptic curve, the degree of an isogeny corresponds essentially to
the degrees of the polynomial expressions involved in its application.
The multiplication--by--$\ell$ map $[\ell]$ has degree~$\ell^2$, therefore
the complexity to directly evaluate $[\ell](P)$ is $O(\ell^2)$.
For a small prime $\ell\, (= 2, 3)$ such that the additive binary
representation provides no better performance, this represents the true
cost of application of scalar multiplication.
If an elliptic curves admits an isogeny $\varphi$ of degree $\ell$ then
the costs of computing $\varphi(P)$ should in contrast be $O(\ell)$ field
operations. Since we then have a product expression $[\ell] =
\hat{\varphi}\varphi$, the existence of an $\ell$-isogeny $\varphi$ on
an elliptic curve yields a theoretical improvement from $O(\ell^2)$ to
$O(\ell)$ field operations for the evaluation of $[\ell](P)$ by naïve
application of the defining polynomials. In this work we investigate
actual improvements for small $\ell$ of this asymptotic complexity.
For this purpose, we describe the general construction of families of
curves with a suitable decomposition $[\ell] = \hat{\varphi}\varphi$,
and provide explicit examples of such a family of curves with simple
decomposition for~$[3]$. Finally we derive a new tripling algorithm
to find complexity improvements to triplication on a curve in certain
projective coordinate systems, then combine this new operation to non-adjacent forms
for $\ell$-adic expansions in order to obtain an improved
strategy for scalar multiplication on elliptic curves.

Unified Point Addition Formulæ and Side-Channel Attacks

The successful application to elliptic curve cryptography of side-channel attacks, in which information about the secret key can be recovered from the observation of side channels like power consumption or timing, has motivated the recent development of unified formulæ for elliptic curve point operations. In this paper, we give a version of a previously-developed family of unified point addition formulæ that uses projective coordinates for improved efficiency. We discuss the applicability of a recent attack by Walter on this family of projective formulæ and describe how the field arithmetic can be implemented to obtain fully unified formulæ and avoid this type of attack.

Generic On-Line/Off-Line Threshold Signatures

We propose on-line/off-line threshold signature schemes, in which the bulk of signature computation can take place ``off-line" during lulls in service requests. Such precomputation can help systems using threshold signatures quickly respond to requests. For example, tests of the Pond distributed file system showed that computation of a threshold RSA signature consumes roughly 86% of the time required to service writes to small files. Because a large number of writes in file systems are for small files, threshold signatures form a performance bottleneck in Pond and similar systems. We apply the ``hash-sign-switch" paradigm of Shamir and Tauman and the distributed key generation protocol of Gennaro et al. to convert any existing secure threshold digital signature scheme into a threshold on-line/off-line signature scheme. Our construction is fully distributed and requires no trusted dealers. We show that the straightforward attempt at proving security of the resulting construction runs into a subtlety that does not arise for Shamir and Tauman's construction. We resolve the subtlety and prove our signature scheme secure against a static adversary in the partially synchronous communication model under the one-more-discrete-logarithm assumption. The on-line phase of our scheme is efficient: computing a signature takes one round of communication and a few modular multiplications in the common case.

Correlation-Resistant Storage via Keyword-Searchable Encryption

We consider the problem of using untrusted components to build correlation-resistant survivable storage systems that protect file replica locations, while allowing nodes to continuously re-distribute files throughout the network. The principal contribution is a chosen-ciphertext secure, searchable public key encryption scheme which allows for dynamic re-encryption of ciphertexts, and provides for node-targeted searches based on keywords or other identifiers. The scheme is provably secure under the SXDH assumption which holds in certain subgroups of elliptic curves, and a closely related assumption that we introduce.

Cryptography in Theory and Practice: The Case of Encryption in IPsec

This paper studies the gaps that exist between cryptography as studied in theory, as defined in standards, as implemented by software engineers, and as actually consumed by users. Our focus is on IPsec, an important and widely-used suite of protocols providing security at the IP layer of network communications. Despite well-known results in theoretical cryptography highlighting the vulnerabilities of unauthenticated encryption, the IPsec standards currently mandate its support. We present evidence that such ``encryption-only'' configurations are in fact still often selected by users in practice, even with strong warnings advising against this in the IPsec standards. We then describe a variety of attacks against such configurations and report on their successful implementation in the case of the Linux kernel implementation of IPsec. Our attacks are
realistic in their requirements, highly efficient, and recover the complete contents of IPsec-protected datagrams. Our attacks still apply when integrity protection is provided by a higher layer protocol, and in some cases even when it is supplied by IPsec itself.
Finally in this paper, we reflect on the reasons why this unsatisfactory situation persists, and make some recommendations for the future development of IPsec and cryptographic software in general.

Last updated: 2007-04-03

A Presentation on VEST Hardware Performance, Chip Area Measurements, Power Consumption Estimates and Benchmarking in Relation to the AES, SHA-256 and SHA-512

A wide-sweeping multi-dimensional analysis and comparison between VEST and the hardware implementations of the AES, AES-HMAC and SHA-2 primitives.

Last updated: 2007-04-03

Authenticated Encryption Mode of VEST Ciphers

This paper demonstrates operation of the authenticated encryption mode in VEST ciphers. All VEST ciphers operating in the authenticated encryption mode with infinite error propagation provide keyed message authentication at the same speed as their keystream generation, with negligible overhead and maintaining their security ratings.

Last updated: 2007-04-03

VEST Hardware-Dedicated Stream Ciphers

VEST ciphers are based on bijective non-linear parallel feedback shift registers assisted by non-linear Residue Number System (RNS) based counters. Four VEST cipher family trees are introduced: 80-bit secure VEST-4, 128-bit secure VEST-8, 160-bit secure VEST-16 and 256-bit secure VEST-32. VEST ciphers return 4 to 32 bits of output per clock cycle while occupying ~5K to ~22K ASIC gates including the finite state machine logic overhead. All VEST ciphers support family keying, variable key sizes and instant re-keying. VEST ciphers are designed exploiting all the advantages of ASIC and FPGA hardware offering high-speed encryption with very low latency and substantial performance improvements comparing with general-purpose or software ciphers implemented in the same area.

Constant-Size Hierarchical Identity-Based Signature/Signcryption without Random Oracles

Uncategorized

Uncategorized

We construct the first constant-size hierarchical identity-based signature (HIBS) without random oracles - the signature size is $O(\lambda_s)$ bits, where $\lambda_s$ is the security parameter, and it is independent of the number of levels in the hierarchy.
We observe that an efficient hierarchical identity-based signcryption (HIBSC) scheme without random oracles can be compositioned from our HIBS and Boneh, Boyen, and Goh's hierarchical identity-based encryption (HIBE). We further optimize it to a constant-factor efficiency improvement. This is the first constant-size HIBSC without random oracles.

More Compact E-Cash with Efficient Coin Tracing

In 1982, Chaum \cite{Chaum82} pioneered the anonymous e-cash which finds many applications in e-commerce. In 1993, Brands \cite{Brands93apr,Brands93,Brands93tm} and Ferguson \cite Ferguson93c,Ferguson93} published on single-term offline anonymous e-cash which were the first practical e-cash. Their constructions used blind signatures and were inefficient to implement multi-spendable e-cash. In 1995, Camenisch, Hohenberger, and Lysyanskaya
\cite{CaHoLy05} gave the first compact $2^\ell$-spendable e-cash, using zero-knowledge-proof techniques. They left an open problem of the simultaneous attainment of $O(1)$-unit wallet size and efficient coin tracing. The latter property is needed to revoke {\em bad} coins from over-spenders. In this paper, we solve \cite{CaHoLy05}'s open problem, and thus enable the first practical compact e-cash. We use a new technique whose security reduces to a new intractability Assumption: the {\em Decisional Harmonic-Relationed Diffie-Hellman (DHRDH) Assumption}.

Short (resp. Fast) CCA2-Fully-Anonymous Group Signatures using IND-CPA-Encrypted Escrows

In the newest and strongest security models for group signatures \cite{BMW03,BellareShZh05,KiayiasYu04}, attackers are given the capability to query an Open Oracle, $\oo$, in order to obtain the signer identity of the queried signature. This oracle mirrors the Decryption Oracle in security experiments involving encryption schemes, and the security notion of CCA2-full-anonymity for group signatures mirrors the security notion of IND-CCA2-security for encryption schemes. Most group signatures escrows the signer identity to a TTP called the {\em Open Authority (OA)} by encrypting the signer identity to OA. Methods to efficiently instantiate $O(1)$-sized CCA2-fully-anonymous group signatures using IND-CCA2-secure encryptions, such as the Cramer-Shoup scheme or the twin encryption scheme, exist \cite{BMW03,BellareShZh05,KiayiasYu04,NguyenSN04}. However, it has long been suspected that IND-CCA2-secure encryption
to OA is an overkill, and that CCA2-fully-anonymous group signature can be constructed using only IND-CPA-secure encryptions. Here, we settle this issue in the positive by constructing CCA2-fully-anonymous group signatures from IND-CPA-secure encryptions for the OA, without ever using IND-CCA2-secure encryptions. Our technique uses a single ElGamal or similar encryption plus Dodis and Yampolskiy \cite{DodisYa05}'s VRF (Verifiable Random Function). The VRF provides a sound signature with zero-knowledge in both the signer secret and the signer identity, while it simultaneously defends active $\oo$-query attacks. The benefits of our theoretical advance is improved efficiency. Instantiations in pairings result in the shortest CCA2-fully-anonymous group signature at 11 rational points or $\approx 1870$ bits for 170-bit curves. It is 27\% shorter (and slightly faster) than the previous fastest \cite{BBS04,KiayiasYu04} at 15 rational points. Instantiations in the strong RSA framework result in the fastest CCA2-fully-anonymous group signature at 4 multi-base exponentiations for 1024-bit RSA. It is 25\% faster than the previous fastest at 5 multi-base exponentiations \cite{ACJT00,CL02,KiayiasYu04}.

Last updated: 2007-06-21

Intrusion-Resilient Authentication in the Limited Communication Model

We describe a general technique for building authentication systems
that resist compromises at the client side. We derive this resistance
by storing key information on hardware fast enough for valid use
but too slow for an intruder (e.g., a virus) to capture much of the key before being detected and removed. We give formal models for two types of protocols: user authentication and authenticated session-key
generation. The first can be used for physical authentication tokens, e.g., used for gaining access to a building. The second can be used for conducting secure remote sessions on laptops that are occasionally
infected by viruses. We present and analyze protocols for each of these tasks and describe how they can be implemented. With one example setting of parameters, in the case of user authentication, we are able to guarantee security for 6 months using a device storing 384MB, and in the key generation protocol, a 128GB drive guarantees that an adversary would need 700 days to compromise the key information.
The model for intrusion resilience considered in this paper was
first introduced by Dagon et al. \cite{DLL05} and motivated by
the bounded storage model for cryptography \cite{Mau92}. Recently Dziembowski \cite{Dzi05} independently developed this model, and studied the same problems as the ones addressed in this paper. Our user authentication protocol is essentially the same as that of \cite{Dzi05}, while our authenticated session-key generation protocol builds on that of \cite{Dzi05}.

Compartmented Secret Sharing Based on the Chinese Remainder Theorem

Uncategorized

Uncategorized

A secret sharing scheme starts with a secret and then derives from it
certain shares (or shadows) which are distributed to users.
The secret may be recovered only by certain
predetermined groups. In case of compartmented secret sharing, the
set of users is partitioned into compartments and the secret
can be recovered only if the number of participants from
any compartment is greater than a fixed compartment threshold
and the total number of participants is greater than a global threshold.
In this paper we present a new compartmented secret sharing scheme by
extending the Brickell's construction to the case that the global threshold
is strictly greater than the sum of the compartment thresholds and we
indicate how to use the threshold secret sharing schemes
based on the Chinese remainder theorem in order to decrease the size of shares.

Anonymous Signature Schemes

Digital signature is one of the most important primitives in public key cryptography. It provides authenticity, integrity and non-repudiation to many kinds of applications. On signer privacy however, it is generally unclear or suspicious of whether a signature scheme itself can guarantee the anonymity of the signer. In this paper, we give some affirmative answers to it. We formally define the signer anonymity for digital signature and propose some schemes of this type. We show that a signer anonymous signature scheme can be very useful by proposing a new anonymous key exchange protocol which allows a client Alice to establish a session key with a server Bob securely while keeping her identity secret from eavesdroppers. In the protocol, the anonymity of Alice is already maintained when Alice sends her signature to Bob in clear, and no additional encapsulation or mechanism is needed for the signature. We also propose a method of using anonymous signature to solve the collusion problem between organizers and reviewers of an anonymous paper review system.

Relations amount Statistical Security Notions - or - Why Exponential Adversaries are Unlimited

In the context of Universal Composability, we introduce the concept of universal environments and simulators. Then, Universal Composability is equivalent to Universal Composability wrt. universal environments and simulators.
We prove the existence of universal environments and simulators and investigate their computational complexity.
From this, we get a number of consequences: First, we see that for polynomial-time protocols, exponential adversarial entities are as powerful as unlimited ones.
Further, for a large class of protocols (those with bounded communication-complexity) we can show that UC and specialised-simulator UC coincide in the case of statistical security, i.e., that it is does not matter whether the simulator is chosen in dependence of the environment or not. This also implies that for the Universal Composition Theorem for polynomial-time protocols specialised-simulator UC is sufficient.
This result is the last piece needed to find all implications and non-implications between the notions of UC, specialised-simulator UC, O(1)-bounded and polynomially-bounded general composability for polynomial-time protocols in the cases of perfect, statistical and polynomial security.
Finally, we introduce the notion of bounded-risk UC, which allows to give explicit security guarantees for concrete security parameters and show that in the above case also this variant coincides with UC.

Building Better Signcryption Schemes with Tag-KEMs

Signcryption schemes aim to provide all of the advantages of simultaneously signing and encrypting a message. Recently, Dent and Bjørstad investigated the possibility of constructing provably secure signcryption schemes using hybrid KEM-DEM techniques. We build on this work by showing that more efficient insider secure hybrid signcryption schemes can be built using Tag-KEMs. To prove the effectiveness of this construction, we will provide several examples of secure signcryption Tag-KEMs, including a brand new construction based on the Chevallier-Mames signature scheme which has the tightest known security reductions for both confidentiality and unforgeability.

Preventing Attacks on Machine Readable Travel Documents (MRTDs)

After the terror attacks of 9/11, the U.S. Congress passed legislation
that requires in the US Visa Waiver Program to begin issuing issuing machine readable passports that are tamper resistant and incorporate biometric and document authentication identifiers. The International Civil Aviation Organization (ICAO) has issued specifications for Machine Readable Travel Documents (MRTD) that are equipped with a smart card processor to perform biometric identification of the holder. Some countries, such as the United States, will issue
machine readable passports that serve only as passports. Other countries, such as the United Kingdom, intend to issue more sophisticated, multi-application passports that can also serve as national identity cards. We have conducted a detailed security analysis of these specificationsm, and we illustrate possible scenarios that could cause a compromise in the security and privacy of holders of such travel documents. Finally, we suggest improved cryptographic protocols and high-assurance smart card operating systems to prevent these compromises and to support electronic visas as well as passports.

Collisions in the Original Version of a Chaotic Hash Function

Uncategorized

Uncategorized

At the Crypto 2005 rump session, a new hash function based upon a
chaotic map was presented.
We display several messages that collide to the same output for this
hash function.

Some Analysis of Radix-r Representations

We deal with the radix-r representation used for the scalar
multiplication of pairing-based cryptosystems with characteristic
r. Our goal of this paper is to present some invariant
properties about the signed radix-r representation; (1)
approximation formulae for the average significant length and the
average hamming weight of gNAF and wrNAF representation, (2)
some classification formulae of equivalent classes called as
Cutting Lemma, Collision Lemma, and Search Space Theorem. We also
analyze the security of signed radix-r representations in the
sense of side channel attacks, and to this end we propose a secure
countermeasure.

A Computationally Sound Mechanized Prover for Security Protocols

We present a new mechanized prover for secrecy properties of
cryptographic protocols. In contrast to most previous provers, our
tool does not rely on the Dolev-Yao model, but on the computational
model. It produces proofs presented as sequences of games; these
games are formalized in a probabilistic polynomial-time process
calculus. Our tool provides a generic method for specifying security
properties of the cryptographic primitives, which can handle shared-
and public-key encryption, signatures, message authentication codes,
and hash functions. Our tool produces proofs valid for a number of
sessions polynomial in the security parameter, in the presence of an
active adversary. We have implemented our tool and tested it on a
number of examples of protocols from the literature.

Improved Collision Attack on MD5

In EUROCRYPT2005, a collision attack on MD5 was proposed by Wang et al.
In this attack, conditions which are sufficient to generate collisions (called
``sufficient condition") are introduced.
This attack raises the success probability by modifing messages to satisfy these conditions.
In this attack, 37 conditions cannot be satisfied even messages are modified. Therefore, the complexity is $2^{37}$.
After that, Klima improved this result. Since 33 conditions cannot be satisfied in his method, the
complexity is $2^{33}$.
In this paper, we propose new message modification techniques which are more efficient than attacks proposed so far.
In this method, 29 conditions cannot be satisfied. However, this method is probabilistic, and the probability that
this method work correctly is roughly 1/2. Therefore, the complexity of this attack is $2^{30}$. Furthermore, we propose a more efficient
collision search algorithm than that of Wang et al. By using this algorithm, the total complexity is reduced into roughly 5/8.

On affine rank of spectrum support for plateaued function

The plateaued functions have a big interest for the studying of bent functions and by the reason that many cryptographically important functions are plateaued. In this paper we study the possible values of
the affine rank of spectrum support for plateaued functions. We consider for any positive integer $h$ plateaued functions with a spectrum support of cardinality $4^h$ (the cardinality must have such form), give the bounds on the affine rank for such functions and
construct functions where the affine rank takes all integer values from $2h$ till $2^{h+1}-2$. We solve completely the problem for $h=2$, namely, we prove that the affine rank of any plateaued function with a spectrum support of cardinality $16$ is $4$, $5$ or $6$.

Preliminary Analysis of DHA-256

Uncategorized

Uncategorized

DHA-256 was presented at the Cryptographic Hash Workshop hosted by NIST in November 2005. DHA-256 (Double Hash Algorithm) was proposed to enhance the security of SHA-256. We present a preliminary analysis of the message expansion and give an alternative 9-step local collision for DHA-256.

Enhancing the MD-Strengthening and Designing Scalable Families of One-Way Hash Algorithms

One-way hash algorithms are an indispensable tool in data
security. Over the last decade or so a number of one-way hash
algorithms have been designed and many of them have been used in
numerous applications. Recent progress in cryptanalytic attacks on
one-way hash algorithms by Wang and co-workers, however,
has brought up the urgency of research into new and more secure
algorithms. The goal of this paper is two-folded. On one hand we
propose a simple technique to affix authentication tags to
messages prior to being hashed by an iterative one-way hash
algorithm with the aim of increasing the overall security of the
algorithm against cryptanalytic attacks. One the other hand we
advocate the importance of a system oriented approach towards the
design and deployment of new families of one-way hash algorithms
that support greater scalability and facilitate migration to newer
member algorithms upon the compromise of deployed ones. We base
our observations on a common sense premise that there is no
specific one-way hash algorithm can remain secure forever and it
will eventually be broken by a cryptanalytic attack faster than
exhaustive research.

Design and Analysis of a Robust and Efficient Block Cipher using Cellular Automata

Cellular Automaton (CA) has been shown to be capable of generating
complex and random patterns out of simple rules. There
has been constant efforts of applying CA to develop ciphers, but
the attempts have not been successful. This paper
describes how repeated application of simple CA transforms
may be used to achieve confusion and diffusion, needed
in block ciphers. The components have been evaluated
for their robustness against conventional cryptanalysis and
the results have been found to be comparable to standards.
Finally, the parts are
assembled in an unconventional way to construct
a self-invertibe CA based round, which is resistant
against linear and differential cryptanalysis and yet
can be efficiently implemented.

Secure Group Key Establishment Revisited

We examine the popular proof models for group key establishment of
Bresson et al. and point out missing security
properties that are present in some models for two-party key
establishment. These properties are actually of more importance
in group key establishments due to the possibility of malicious
insiders. We show that established group key establishment
schemes from CRYPTO 2003 and ASIACRYPT 2004 do
not fully meet these new requirements. Next to giving a formal
definition of these extended security properties, we prove a
variant of the explored proposal from ASIACRYPT 2004
secure in this stricter sense.

How to Shuffle in Public

Uncategorized

Uncategorized

We show how to public-key obfuscate two commonly used shuffles:
decryption shuffles which permute and decrypt ciphertexts, and
re-encryption shuffles which permute and re-encrypt ciphertexts. Given
a trusted party that samples and obfuscates a shuffle \emph{before}
any ciphertexts are received, this reduces the problem of constructing
a mix-net to verifiable joint decryption.
We construct a decryption shuffle from any additively homomorphic
cryptosystem and show how it can be public-key obfuscated. This
construction does not allow efficient distributed verifiable
decryption. Then we show how to public-key obfuscate: a decryption
shuffle based on the Boneh-Goh-Nissim (BGN) cryptosystem, and a
re-encryption shuffle based on the Paillier cryptosystem. Both
constructions allow \emph{efficient} distributed verifiable
decryption. In the Paillier case we identify and exploit a previously
overlooked ``homomorphic'' property of the cryptosystem.
Finally, we give a distributed protocol for sampling and obfuscating
each of the above shuffles and show how it can be used in a trivial
way to construct a universally composable mix-net. Our constructions
are practical when the number of senders $N$ is reasonably small,
e.g. $N=350$ in the BGN case and $N=2000$ in the Paillier case.

Multivariate Quadratic Polynomials in Public Key Cryptography

This thesis gives an overview of Multivariate Quadratic polynomial equations and their use in public key cryptography.
In the first chapter, some general terms of cryptography are introduced.
In particular, the need for public key cryptography and alternative
schemes is motivated, i.e., systems which neither use factoring (like RSA, Rivest-Shamir-Adleman)
nor the discrete logarithm (like ECC, elliptic curve cryptography).
This is followed by a brief introduction of finite fields and a general
discussion about Multivariate Quadratic systems of equations and ways of representing
them. In this context, affine transformations and their representations are also discussed.
After these tools are introduced, they are used to show how Multivariate Quadratic
equations can be used for signature and encryption applications. In addition,
the problem of Multivariate Quadratic polynomial equations is put into perspective and a link
with the theory of NP-completeness is established. The second chapter concludes with the two related problems "isomorphism of polynomials" and "minimal rank" of the sum of matrices.
Both prove useful in the cryptanalysis of Multivariate Quadratic systems.
The main part of this thesis is about concrete trapdoors for the problem of Multivariate Quadratic public key systems. We can show that all such systems fall in one of the following four classes: unbalanced oil and vinegar systems (UOV), stepwise triangular systems (STS), Matsumoto-Imai Scheme A (MIA), and hidden field equations (HFE).
Moreover, we demonstrate the use of several modifiers. In order to evaluate the security of these four basic trapdoors and their modifiers, we review some cryptanalytic results. In particular, we were able to develop our own contributions in this field by
demonstrating an affine approximation attack and an attack using Gr"obner base computations against the UOV class. Moreover, we derived a key recovery and inversion attack against the STS class.
Using our knowledge of the HFE class, we develop two secure versions of the signature scheme Quartz.
Another important part of this thesis is the study of the key space of Multivariate Quadratic public key systems. Using special classes of affine transformations, denoted ``sustainers", we are able to show that all four basic classes have some redundancy in their
key spaces and hence, have a smaller key space than previously expected. In particular for the UOV and the STS class, this reduction proves quite dramatic. For HFE and MIA, we only find some minor
redundancies. Moreover, we are able to show that our results for MIA are the only ones possible, i.e., there are no other redundancies than the one we describe in this thesis. In addition, we extend our results to several important variations of HFE and MIA, namely HFE-, HFEv, HFEv-, and MIA-. They have been used in practice for the construction
of signature schemes, namely Quartz and Sflash.
In order to demonstrate the practical relevance of Multivariate Quadratic constructions and also of our taxonomy, we show some concrete examples. In particular, we consider the NESSIE submissions Flash, Sflash, and Quartz and discuss their advantages and disadvantages. Moreover, we describe some more recent developments, namely the STS-based schemes enhanced TTS, Tractable Rational Maps, and Rainbow. Then we move on to some application domains for Multivariate Quadratic public key systems. In particular, we
see applications in the area of product activation keys, electronic stamps and fast one-way functions. Finally, we suggest some new schemes. In particular, we give a generalisation of MIA to odd characteristics and also investigate some other trapdoors like STS and UOV with the branching and the homogenisation modifiers.
All in all, we believe that Multivariate Quadratic polynomial systems are a very practical solution to the problem of public key cryptography. At present, it is not possible to use them for encryption. However, we are confident that it will be possible to overcome this problem soon and use Multivariate Quadratic constructions both for encrypting and signing.

An Efficient Variant of RSA Cryptosystem

Uncategorized

Uncategorized

An efficient variant of RSA cryptosystem was proposed by Cesar [2]. He called it Rprime RSA. The Rprime RSA is a combination of Mprime RSA [3] and Rebalanced RSA [9, 1]. Although the decryption speed of Rprime RSA is 27 times faster than the standard RSA and 8 times faster than the QC RSA [6] in theoretically, yet due to the large encryption exponent, the encryption process becomes slower than the standard RSA. In this paper we tried to improve the efficiency of encryption process with less compromising with the decryption speed.

Some thoughts on Collision Attacks in the Hash Functions MD5, SHA-0 and SHA-1

The design principle of Merkle-Damgård construction is collision resistance of the compression function implies collision resistance of the hash function. Recently multi-block collisions have been found on the hash functions MD5, SHA-0 and SHA-1 using differential cryptanalysis. These multi-block collisions raise several questions on some definitions and properties used in the hash function literature. In this report, we take a closer look at some of the literature in cryptographic hash functions and give our insights on them. We bring out some important differences between the 1989's Damgård's hash function and the hash functions that followed it. We conclude that these hash functions did not consider the pseudo-collision attack in their design criteria. We also doubt whether these hash functions achieve the design principle of Merkle-Damgård's construction. We formalise some definitions on the properties of hash functions in the literature.

3C- A Provably Secure Pseudorandom Function and Message Authentication Code.A New mode of operation for Cryptographic Hash Function

We propose a new cryptographic construction called 3C, which works as a pseudorandom function (PRF), message authentication code (MAC) and cryptographic hash function. The 3C-construction is obtained by modifying the Merkle-Damgard iterated construction used to construct iterated hash functions. We assume that the compression functions of Merkle-Damgard iterated construction realize a family of fixed-length-input pseudorandom functions (FI-PRFs). A concrete security analysis for the family of 3C- variable-length-input pseudorandom functions (VI-PRFs) is provided in a precise and quantitative manner. The 3C- VI-PRF is then used to realize the 3C- MAC construction called one-key NMAC (O-NMAC). O-NMAC is a more efficient variant of NMAC and HMAC in the applications where key changes frequently and the key cannot be cached. The 3C-construction works as a new mode of hash function operation for the hash functions based on Merkle-Damgard construction such as MD5 and SHA-1. The generic 3C- hash function is more resistant against the recent differential multi-block collision attacks than the Merkle-Damgard hash functions and the extension attacks do not work on the 3C- hash function. The 3C-X hash function is the simplest and efficient variant of the generic 3C hash function and it is the simplest modification to the Merkle-Damgard hash function that one can achieve. We provide the security analysis for the functions 3C and 3C-X against multi-block collision attacks and generic attacks on hash functions. We combine the wide-pipe hash function with the 3C hash function for even better security against some generic attacks and differential attacks. The 3C-construction has all these features at the expense of one extra iteration of the compression function over the Merkle-Damgard construction.

How to Generate Universally Verifiable Signatures in Ad-Hoc Networks

This paper addresses the problem of making signatures of one domain (an ad-hoc network) available in another domain (the Internet).
Universal verifiability is a highly desirable property when signed documents need to be permanently non-repudiable so as to prevent dishonest signers from disavowing signatures they have produced. As a practical solution, we construct a new signature scheme where a valid signature should be generated by a couple of distinct signing keys. In the random oracle model, the signature scheme is provably secure in the sense of existential unforgeability under adaptive chosen message attacks assuming the hardness of the computational Diffie-Hellman problem in the Gap Diffie-Hellman groups.

Side-Channel Attacks: Ten Years After Its Publication and the Impacts on Cryptographic Module Security Testing

Side-channel attacks are easy-to-implement whilst powerful attacks against cryptographic implementations, and their targets range from primitives, protocols, modules, and devices to even systems. These attacks pose a serious threat to the security of cryptographic modules. In consequence, cryptographic implementations have to be evaluated for their resistivity against such attacks and the incorporation of different countermeasures has to be considered. This paper surveys the methods and techniques employed in these attacks, the destructive effects of such attacks, the countermeasures against such attacks and evaluation of their feasibility and applicability. Finally, the necessity and feasibility of adopting this kind of physical security testing and evaluation in the development of FIPS 140-3 standard are explored. This paper is not only a survey paper, but also more a position paper.

On highly nonlinear S-boxes and their inability to thwart DPA attacks (completed version)

Prouff has introduced recently, at FSE 2005, the notion of transparency order of S-boxes. This new characteristic is related to the ability of an S-box, used in a cryptosystem in which the round keys are introduced by addition, to thwart single-bit or multi-bit DPA attacks on the system. If this parameter has sufficiently small value, then the S-box is able to withstand DPA attacks without that ad-hoc modifications in the implementation be necessary (these modifications make the encryption about twice slower). We prove lower bounds on the transparency order of highly nonlinear S-boxes. We show that some highly nonlinear functions (in odd or even numbers of variables) have very bad transparency orders: the inverse functions (used as S-box in the AES), the Gold functions and the Kasami functions (at least under some assumption).

A New Short Signature Scheme Without Random Oracles from Bilinear Pairings

Uncategorized

Uncategorized

In this paper, we propose a new signature scheme that is
existentially unforgeable under a chosen message attack without random oracle. The security of our scheme depends on a
new complexity assumption called the $k$+1 square roots
assumption. We also discuss the relationship between the $k$+1
square roots assumption and some related problems and provide some
conjectures. Moreover, the $k$+1 square roots assumption can be
used to construct shorter signatures under the random oracle
model. As some applications, a new chameleon hash signature scheme
and a on-line/off-line signature scheme and a new efficient
anonymous credential scheme based on the proposed signature scheme
are presented.

Practical Group Signatures without Random Oracles

Uncategorized

Uncategorized

We provide a construction for a
group signature scheme that is provably secure in a universally composable framework,
within the standard model with trusted parameters.
Our proposed scheme is fairly simple and its efficiency falls
within small factors of the most efficient group signature schemes
with provable security in any model (including random oracles).
Security of our constructions require new
cryptographic assumptions, namely the Strong LRSW, EDH, and Strong SXDH assumptions. Evidence for any assumption we introduce is provided by proving hardness in the generic group model.
Our second contribution is the first definition of security for group signatures based on the simulatability
of real protocol executions in an ideal setting that captures
the basic properties of unforgeability, anonymity, unlinkability, and exculpability for
group signature schemes.

Some Explicit Formulae of NAF and its Left-to-Right Analogue

Non-Adjacent Form (NAF) is a canonical form of signed binary representation of integers. We present some explicit formulae of NAF and its left-to-right analogue (FAN) for randomly chosen n-bit integers. Interestingly, we prove that the zero-run length appeared in FAN is asymptotically 16/7, which is longer than that of the standard NAF. We also apply the proposed formulae to the speed estimation of elliptic curve cryptosystems.

Key Mixing in Block Ciphers through Addition modulo $2^n$

The classical technique to perform key mixing in block ciphers
is through exclusive-or (exor). In this paper we show that
when the $n$-bit key is mixed in a block cipher of size $n$
bits via addition modulo $2^n$, the bias of the linear approximations
falls exponentially fast. Experimental results have been provided
to show that such a scheme cannot be cryptanalyzed
using Linear Cryptanalysis.

One-Wayness Equivalent to General Factoring

This paper shows the first practical semantically secure public-key encryption scheme such that its one-wayness is equivalent to
{\it general} factoring in the {\it standard} model (in the sense of IND-CPA).
Next our proof technique is applied to Rabin-Paillier encryption scheme and a variant of RSA-Paillier encryption scheme to prove their exactly tight one-wayness.

Compact Group Signatures Without Random Oracles

We present the first efficient group signature scheme that is provably
secure without random oracles. We achieve this result by combining
provably secure hierarchical signatures in bilinear groups with a
novel adaptation of the recent Non-Interactive Zero Knowledge proofs
of Groth, Ostrovsky, and Sahai. The size of signatures in our scheme is
logarithmic in the number of signers; we prove it secure under the
Computational Diffie-Hellman and the Subgroup Decision assumptions in
the model of Bellare, Micciancio, and Warinshi, as relaxed by Boneh,
Boyen, and Shacham.

Breaking RSA May Be As Difficult As Factoring

If factoring is hard, this paper shows that straight line programs cannot efficiently solve the low public exponent RSA problem. More precisely, no efficient algorithm can take an RSA public key as input and then output a straight line program that efficiently solves the low public exponent RSA problem for the given public key --- unless factoring is easy.

Handling Expected Polynomial-Time Strategies in Simulation-Based Security Proofs

The standard class of adversaries considered in cryptography is that of {\em strict} polynomial-time probabilistic machines. However, {\em expected} polynomial-time machines are often also considered. For example, there are many zero-knowledge protocols for which the only known simulation techniques run in expected (and not strict) polynomial time. In addition, it has been shown that expected polynomial-time simulation is {\em essential} for achieving constant-round black-box zero-knowledge protocols. This reliance on expected polynomial-time simulation introduces a number of conceptual and technical difficulties. In this paper, we develop techniques for dealing with expected polynomial-time adversaries in simulation-based security proofs.

A New Protocol for Conditional Disclosure of Secrets And Its Applications

Many protocols that are based on homomorphic encryption are private only if a client submits inputs from a limited range $S$. Conditional disclosure of secrets (CDS) helps to overcome this restriction. In a CDS protocol for a set $S$, the client obtains server's secret if and only if the client's inputs belong to $S$ and thus the server can guard itself against malformed queries. We extend the existing CDS protocols to work over additively homomorphic cryptosystems for every set from $NP/poly$. The new construction is modular and easy to apply. As an example, we derive a new oblivious transfer protocol with log-squared communication and a millionaire's protocol with logarithmic communication. We also implement private, universally verifiable and robust multi-candidate electronic voting so that all voters only transmit an encryption of their vote. The only hardness assumption in all these protocols is that the underlying public-key cryptosystem is IND-CPA secure and the plaintext order does not have small factors.

Exclusion-Intersection Encryption

Identity-based encryption (IBE) has shown to be a useful cryptographic scheme enabling secure yet flexible role-based access control. We propose a new variant of IBE named as exclusion-intersection encryption: during encryption, the sender can specify the targeted groups that are legitimate and interested in reading the documents; there exists a trusted key generation centre generating the intersection private decryption keys on request. This special private key can only be used to decrypt the ciphertext which is of all the specified groups' interests, its holders are excluded from decrypting when the documents are not targeted to all these groups (e.g., the ciphertext of only a single group's interest). While recent advances in cryptographic techniques (e.g., attribute-based encryption or wicked IBE) can support a more general access control policy, the private key size may be as long as the number of attributes or identifiers that can be specified in a ciphertext, which is undesirable, especially when each user may receive a number of such keys for different decryption power. One of the applications of our notion is to support an ad-hoc joint project of two or more groups which needs extra helpers that are not from any particular group. We also present an online/offline variant such that encryption can be computed quickly after offline pre-computation.

Representing small identically self-dual matroids by self-dual codes

The matroid associated to a linear code is the representable matroid that is defined by the columns of any generator matrix. The matroid associated to a self-dual code is identically self-dual, but it is not known whether every identically self-dual representable matroid can be represented by a self-dual code.
This open problem was proposed by Cramer et al ("On Codes, Matroids and Secure Multi-Party Computation from Linear Secret Sharing Schemes", Crypto 2005), who proved it to be equivalent to an open problem on the complexity of multiplicative linear secret sharing schemes.
Some contributions to its solution are given in this paper. A new family of identically self-dual matroids that can be represented by self-dual codes is presented. Besides, we prove that every identically self-dual matroid on at most eight points is representable by a self-dual code.

Truncated differential cryptanalysis of five rounds of Salsa20

We present an attack on Salsa20 reduced to five of its twenty rounds. This attack uses many clusters of truncated differentials and requires 2^{165} work and 2^{6} plaintexts.

Computation of Tate Pairing for Supersingular Curves over characteristic 5 and 7

We compute Tate pairing over supersingular elliptic curves via the generic BGhES\cite{BGES} method for $p=5,7$. In those cases, the point multiplication by $p$ is efficiently computed by the Frobenius endomorphism. The function in a cycle can be efficiently computed by the method of continued fraction.

Efficient Broadcast Encryption Scheme with Log-Key Storage

In this paper, we present a broadcast encryption scheme with efficient transmission cost under the \emph{log-key} restriction. Given $n$ users and $r$ revoked users, our scheme has the transmission cost of $O(r)$ and requires the storage of $O(\log n)$ keys at each receiver. These are optimal complexities in broadcast encryptions using one-way hash functions (or pseudo-random generators.) To achieve these complexities, the stratified subset difference (SSD) scheme and the $\overline{B1}$ scheme were introduced by Goodrich et al. and Hwang et al. respectively. However,
their schemes have the disadvantage that transmission cost increases linearly according to the number of stratifications. By assigning the related keys between stratifications, our scheme remedies the defect and achieves very efficient transmission cost even in an environment where the key storage is restricted. To the best of our knowledge, our scheme has the most efficient transmission cost in the existing schemes with log-key storage. In addition, our result is comparable to other schemes that allow a large key storage.

Secret color images sharing schemes based on XOR operation

Uncategorized

Uncategorized

This paper presents two new constructions for the secret color images sharing schemes .One is a (n, n) threshold scheme, which can be constructed based on XOR operation. The other is a (2, n) threshold scheme, which can be constructed by using AND and XOR operations. The two schemes have no pixel expansion, and the time complexity for constructing shared images is O(k1n), excluding the time needed for generating n distinct random matrices (here k1 is the size of the shared image). The reconstructed images can be obtained in the two schemes by using the XOR operation alone. The relative differences of the two schemes are 1 and 1/2, respectively. The time complexity of the recovered images is O(k1n) and O(2k1), respectively. The two schemes also provide perfect secrecy.

On a Traitor Tracing Scheme from ACISP 2003

At ACISP 2003 conference, Narayanan, Rangan and Kim proposed a secret-key traitor tracing scheme used for pay TV system. In this note, we point out a flaw in their scheme.

Resource Fairness and Composability of Cryptographic Protocols

We introduce the notion of {\em resource-fair} protocols.
Informally, this property states that if one party learns the
output of the protocol, then so can all other parties, as long as
they expend roughly the same amount of resources. As opposed to
similar previously proposed definitions, our definition follows
the standard simulation paradigm and enjoys strong composability
properties. In particular, our definition is similar to the
security definition in the universal composability (UC) framework,
but works in a model that allows any party to request additional
resources from the environment to deal with dishonest parties that
may prematurely abort.
In this model we specify the ideally fair functionality as
allowing parties to ``invest resources'' in return for outputs,
but in such an event offering all other parties a fair deal. (The
formulation of fair dealings is kept independent of any particular
functionality, by defining it using a ``wrapper.'') Thus, by
relaxing the notion of fairness, we avoid a well-known
impossibility result for fair multi-party computation with
corrupted majority; in particular, our definition admits
constructions that tolerate arbitrary number of corruptions. We
also show that, as in the UC framework, protocols in our framework
may be arbitrarily and concurrently composed.
Turning to constructions, we define a ``commit-prove-fair-open''
functionality and design an efficient resource-fair protocol that
securely realizes it, using a new variant of a cryptographic
primitive known as ``time-lines.'' With (the fairly wrapped
version of) this functionality we show that some of the existing
secure multi-party computation protocols can be easily transformed
into resource-fair protocols while preserving their security.