gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2009-01-06 07:32:30
We prove that Lenstra proposition suggesting existence of many counterexamples to Agrawal conjecture is true in a more general case. At the same time we obtain a strictly ascending chain of subgroups of the group (Zp[X]/(Cr(X)))* and state the modified conjecture that the set {X-1, X+2} generate big enough subgroup of this group.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2009-01-05 08:41:35
This paper presents implementation results of a reconfigurable elliptic curve processor defined over prime fields $GF(p)$. We use this processor to compare a new algorithm for point addition and point doubling operations on the twisted Edwards curves, against a current standard algorithm in use, namely the Double-and-Add. Secure power analysis versions of both algorithms are also examined and compared. The algorithms are implemented on an FPGA, and the speed, area and power performance of each are then evaluated for various modes of circuit operation using parallel processing. To the authors' knowledge, this work introduces the first documented FPGA implementation for computations on twisted Edwards curves over fields $GF(p)$.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2009-01-05 08:41:34
Looking up -- you realize that one of the twelve light bulbs of your living room chandelier has to be replaced. You turn electricity off, move a table to the center of the room, put a chair on top of the table and, new bulb in hand, you climb up on top of the chair. As you reach the chandelier, you notice that\ldots all bulbs look alike and that you have forgotten which bulb needed to be changed.\smallskip
Restart all over again?\smallskip
Luckily, an effortless creative solution exists. By just touching the light bulbs you can determine the cold one and replace it! Put differently, information about the device's malfunction leaked-out via its temperature...
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2009-01-05 08:41:34
We analyse two new and related families of one-way authentication
protocols, where a party wants to authenticate its public information to another. In the first, the objective is to do without shared passwords or a PKI, making use of low-bandwidth empirical/authentic
channels where messages cannot be faked or modified. The analysis of these leads to a new security principle, termed separation of security concerns, under which protocols should be designed to tackle one-shot attacks and combinatorial search separately. This also leads us develop a new class of protocols for the case such as PKI where a relatively expensive signature mechanism exists. We demonstrate as part of this work that a popular protocol in the area, termed MANA I, neither optimises human effort nor offers as much security as had previously been believed. We offer a number of improved versions for MANA I that provides more security for half the empirical work, using a more general empirical channel.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2009-01-05 08:41:34
We consider the construction and analysis of pseudorandom
functions (PRF) for message authentication. Earlier work due to Bernstein and Vaudenay
show how to reduce the analysis of PRFs to some probability calculations. We revisit this
result and use it to prove some general results on constructions which use a PRF with
``small'' domain to build a PRF with ``large'' domain.
These results are then used to
analyse several existing and new constructions. Important among them is a simplified
proof of a bound on the PRF-property of the cipher block chaining (CBC) mode of operation
of a block cipher for message authentication code (MAC). Several existing variants of CBC-MAC are
analysed using our framework and new schemes are described. One of the new schemes improve
upon the NIST standard CMAC scheme by reducing the number of block cipher invocations by
one for messages which are longer than $n$ bits.
Next, we consider parallelizable constructions. An improved version of the well known PMAC
scheme is described; the improvement consists of removing the requirement of a discrete
log computation in the design stage of PMAC. An earlier parallel construction called
the protected counter sum (PCS) had been proposed by Bernstein. PCS uses a keyed
compressing function rather than a block cipher. We describe a variant of PMAC which works
with keyed compressing function and compared to PCS requires lesser number of invocations.
All our constructions are in the stateless setting, i.e., a setting where the sender and
the receiver do not share any state (apart from the common secret key). One of the aspects
of our work is the simple and direct approach to the analysis of PRFs. In particular, we avoid
the extensive and heavy machinery of game-playing technique which is used in most
papers on this topic.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2009-01-05 08:41:33
In this paper, the impossible differential cryptanalysis is extended to MAC algorithms \textsc{Pelican}, MT-MAC and PC-MAC based on AES and 4-round AES. First, we collect message pairs that produce the inner near-collision with some specific differences by the birthday attack. Then the impossible differential attack on 4-round AES is implemented using a 3-round impossible differential property. For \textsc{Pelican}, our attack can recover the internal state, which is an equivalent subkey. For MT-MAC-AES, the attack turns out to be a subkey recovery attack directly. The data complexity of the two attacks is $2^{85.5}$ chosen messages, and the time complexity is about $2^{85.5}$ queries. For PC-MAC-AES, we can recover the 256-bit key with $2^{85.5}$ chosen messages and $2^{128}$ queries.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2009-01-05 08:41:33
In this paper we present a multicollision and multipreimage attack on the hash function Blender-n [1] for all output sizes n = 224, 256, 384 and 512. The complexity and memory requirements for finding 2^{2n} multipreimages (multicollisions) of Blender-n is roughly 10 times more than finding a collision for n/2-bit random hash function.
All previous attacks were based on the trick by Joux [2] using many messages. Our attacks are based on one message with several fixpoints. The state register has eight words. By properly choosing message words we force half of the register to go to the original state. Then we will find a collision in the rest with complexity 2^{n/4}. The collision creates a fix point in the sequence of states of the state register. We use 10 such fix points.
Previously known attacks [4, 5] on Blender-n have the complexity at least 2^{n/2}. Our 2^{2n}-multicollision and multipreimage attacks have a complexity 10*2^{n/4}.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2009-01-05 08:41:33
We present a homomorphic trapdoor commitment to group elements. In contrast, previous homomorphic trapdoor commitment schemes only allow the messages to be exponents. Our commitment scheme is length-reducing, we can make a short commitment to many group elements at once, and it is perfectly hiding and computationally binding. The construction is based on groups with a bilinear map and the binding property follows from the simultaneous triple pairing assumption. While the simultaneous triple pairing assumption is new, we demonstrate that it is implied by the well-known decision linear assumption.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2009-01-04 09:57:22
This paper examines the methods in which the ideas behind a KEM--DEM hybrid encryption scheme can be extended to other types of asymmetric primitives, particularly to signcryption schemes. The central principle is a keyed symmetric algorithm can be used to provide a security service for in an asymmetric algorithm provided that that symmetric primitive is under the control of the asymmetric part of the cipher (say, if asymmetric techniques are used to generate the key that the symmetric primitive uses).
This theory is applied to signcryption schemes with outsider security and an efficient, provably secure scheme, termed ECISS-KEM, is proposed. The theory is also applied to signature schemes, where it is shown that efficient hybrid signature schemes can never exist, and to signcryption schemes with insider security, where it is shown that several existing schemes can be considered hybrid signcryption schemes.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-30 16:18:31
In this paper we study the link between formal and cryptographic
models for security protocols in the presence of a passive adversary.
In contrast to other works, we do not consider a fixed set of
primitives but aim at results for an arbitrary equational theory. We
define a framework for comparing a cryptographic implementation and
its idealization w.r.t. various security notions. In
particular, we concentrate on the computational soundness of static
equivalence, a standard tool in cryptographic pi calculi. We present a
soundness criterion, which for many theories is not only sufficient
but also necessary. Finally, we establish new soundness results for
the Exclusive Or, as well as a theory of ciphers and lists.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-30 16:18:31
Canetti, Goldreich, Goldwasser, and Micali (STOC 2000) introduced the notion of resettable zero-knowledge proofs, where the protocol must be zero-knowledge even if a cheating verifier can reset the state of the prover at will. Soon afterwards, Barak, Goldreich, Goldwasser, and Lindell (FOCS 2001) studied the closely related notion of resettable soundness, where the soundness condition of the protocol must hold even if the cheating prover can reset the state of the verifier it is trying to convince. The major problem left open by this work was whether it is possible to have a single protocol that is simultaneously resettable zero knowledge and resettably sound. We resolve this question by constructing such a protocol.
At the heart of our construction is a new non-black-box simulation strategy, which we believe to be of independent interest. This new strategy allows for simulators which ``marry'' recursive rewinding techniques (common in the context of concurrent simulation) with non-black-box simulation. Previous non-black-box strategies led to exponential blowups in computational complexity in such circumstances, which our new strategy is able to avoid.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-29 17:34:13
We present a multivariate version of Hidden Field Equations (HFE)
over a finite field of odd characteristic, with an extra
``embedding'' modifier. Combining these known ideas makes our new
MPKC (multivariate public key cryptosystem) more efficient
and scalable than any other extant multivariate encryption scheme.
Switching to odd characteristics in HFE-like schemes affects how an
attacker can make use of field equations. Extensive empirical tests
(using MAGMA-2.14, the best commercially available \mathbold{F_4}
implementation) suggests that our new construction is indeed secure
against algebraic attacks using Gr\"obner Basis algorithms. The
``embedding'' serves both to narrow down choices of pre-images and
to guard against a possible Kipnis-Shamir type (rank-based) attack. We
may hence reasonably argue that for practical sizes, prior attacks
take exponential time.
We demonstrate that our construction is in fact efficient by
implementing practical-sized examples of our ``odd-char HFE'' with 3
variables (``THFE'') over $\mathrm{GF}(31)$. To be precise, our preliminary
THFE implementation is $15\times$--$20\times$ the speed of RSA-1024.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-29 17:34:13
Recently, Tsai and Liao et al. each proposed a multi-server authentication protocol. They claimed their protocols are secure and can withstand various attacks. But we found some security loopholes in each protocol. We will show the attacks on their schemes.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-28 18:45:59
This paper presents a recursive hiding scheme for 2 out of 3 secret sharing. In recursive hiding of secrets, the user encodes additional information about smaller secrets in the shares of a larger secret without an expansion in the size of the latter, thereby increasing the efficiency of secret sharing. We present applications of our proposed protocol to images as well as text.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-28 18:45:58
Predicate encryption is a new encryption paradigm which
gives the secret key owner fine-grained control over access to
encrypted data. The secret key owner can generate tokens corresponding to predicates. An encryption of a
plaintext x can be decrypted using a token corresponding to a
predicate f if the plaintext satisfies the predicate, i.e., f(x) = 1.
Prior work on public-key predicate encryption has focused on the
notion of plaintext privacy, the property that ciphertexts
reveal no information about the encrypted plaintext. In this paper,
we consider a new notion called predicate privacy, the
property that tokens reveal no information about the encoded query
predicate. Predicate privacy is inherently impossible to achieve in
the public-key setting and has therefore received little attention
in prior work. In this work, we consider predicate encryption in the
symmetric-key setting and present a symmetric-key predicate
encryption scheme which supports inner product queries. We prove
that our scheme achieves both plaintext privacy and predicate
privacy.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-28 18:45:58
At Indocrypt 2005, Viet et al., [22] have proposed an
anonymous password-authenticated key exchange (PAKE) protocol and
its threshold construction both of which are designed for client's
password-based authentication and anonymity against a passive
server, who does not deviate the protocol. In this paper, we first
point out that their threshold construction is completely insecure
against off-line dictionary attacks. For the threshold t > 1, we
propose a secure threshold anonymous PAKE (for short, TAP)
protocol with the number of clients n upper-bounded, such that n
\leq 2 \sqrt{N-1} -1, where N is a dictionary size of passwords.
We rigorously prove that the TAP protocol has semantic
security of session keys in the random oracle model by showing the
reduction to the computational Diffie-Hellman problem. In addition,
the TAP protocol provides unconditional anonymity against a
passive server. For the threshold t=1, we propose an efficient
anonymous PAKE protocol that significantly improves efficiency in
terms of computation costs and communication bandwidth compared to
the original (not threshold) anonymous PAKE protocol [22].
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-28 18:45:58
In this short note, we present an extension of Nguyen's bilinear-map
based accumulator scheme to support
\emph{non-membership witnesses} and corresponding
\emph{non-membership proofs}, i.e., cryptographic proofs that an
element has not been accumulated to a given set. This complements
the non-membership proofs developed by Li \emph{et
al.} for the RSA
accumulator, making the
functionality of the bilinear-map accumulator equivalent to that of
the RSA accumulator. Our non-membership extension of Nguyen's
scheme makes use of the $q$-Strong Diffie-Hellman
assumption the security of the original scheme is based on.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-28 18:45:58
The success of electronic authentication systems, be it e-ID card systems or Internet authentication
systems such as CardSpace, highly depends on the provided level of user-privacy.
Thereby, an important requirement is an efficient means for revocation of the authentication credentials.
In this paper we consider the problem of revocation for certificate-based privacy-protecting authentication systems.
To date, the most efficient solutions for revocation for such systems are based on cryptographic accumulators.
Here, an accumulate of all currently valid certificates is published regularly and each user holds
a {\em witness} enabling her to prove the validity of her (anonymous) credential while retaining anonymity.
Unfortunately, the users' witnesses must be updated at least each time a credential is revoked.
For the know solutions, these updates are computationally very expensive for users and/or certificate issuers which is very problematic
as revocation is a frequent event as practice shows.
In this paper, we propose a new dynamic accumulator scheme based on bilinear maps and show how to apply it to the problem
of revocation of anonymous credentials.
In the resulting scheme, proving a credential's validity and updating witnesses both come at (virtually) no cost for
credential owners and verifiers.
In particular, updating a witness requires the issuer to do only one multiplication per addition or revocation of a credential
and can also be delegated to untrusted entities from which a user could just retrieve the updated witness.
We believe that thereby we provide the first authentication system offering privacy protection suitable for implementation
with electronic tokens such as eID cards or drivers' licenses.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-28 18:45:58
In this paper we apply impossible differential attacks to reduced
round AES. Using various techniques, including the early abort
approach and key schedule considerations, we significantly improve
previously known attacks due to Bahrak-Aref and Phan. The improvement
of these attacks leads to the best known impossible differential
attacks on 7-round AES-128 and AES-192, as well as to the best known
impossible differential attacks on 8-round AES-256.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-28 18:45:57
We construct resettably-sound resettable zero knowledge arguments
for NP based on standard hardness assumption (the existence of
claw-free permutations) in the plain model. This proves the
simultaneous resettability conjecture posed by Barak et al. in [FOCS
2001].
\setlength{\parindent}{2em} Our construction, inspired by the
paradigm for designing concurrent zero knowledge protocols, makes
crucial use of a tool called instance-dependent resettably-sound
resettable WI argument of knowledge (\textsf{IDWIAOK} (and a
special-purpose variant), introduced recently by Deng and Lin in
[Eurocrypt 2007]).Roughly speaking, for a NP statement of the form $x_0\vee x_1$,\textsf{IDWIAOK} is an argument for which resettable WI property holds when both $x_0$ and $x_1$ are YES instances, and
resettably-sound argument of knowledge property holds when $x_0$ is
a NO instance.
The heart of the simulator for our protocol is a new technique that
allows us to embed the (non-black-box) straight-line simulation
strategy in the (black-box) recursive rewinding simulation strategy.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-28 18:45:57
In this paper, we first present a new distinguisher on the CBC-MAC based on a block cipher in Cipher Block Chaining (CBC) mode. It can also be used to distinguish other CBC-like MACs from random functions. The main results of this paper are on the second-preimage attack on CBC-MAC and CBC-like MACs include TMAC, OMAC, CMAC, PC-MAC and MACs based on three-key encipher CBC mode. Instead of exhaustive search, this attack can be performed with the birthday attack complexity.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-20 01:43:27
We present an innovative technique to add elliptic curve points with the form P+-Q, and discuss its application to the generation of precomputed tables for the scalar multiplication. Our analysis shows that the proposed schemes offer, to the best of our knowledge, the lowest costs for precomputing points on both single and multiple scalar multiplication and for various elliptic curve forms, including the highly efficient Jacobi quartics and Edwards curves.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-20 01:43:26
This paper extends the work of Rogaway and Shrimpton (2004), where they formalized seven security properties: notions of preimage resistance (Pre, aPre, ePre), second-preimage resistance (Sec, aSec, eSec) and collision resistance (Coll). They also give all the implications and separations among the properties. In this paper we consider three additional security properties which are important in applications of hash functions: unforgeability (MAC), pseudo-random function (Prf) and pseudo-random oracle (Pro). We give a new type of the implication and separation between the security notions since the ones defined by Rogaway and Shrimpton were too constraining, and work out all the relationships among the ten security notions above. Some of the relations have been proven before, some of them appear to be new. We show that a property pseudo-random oracle (Pro) introduced by Coron, Dodis, Malinaud and Puniya is (as expected) the strongest one, since it implies almost all of the other properties.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-20 01:43:26
We give a generic methodology to unlinkably anonymize cryptographic schemes in bilinear groups using the Boneh-Goh-Nissim cryptosystem and NIZK proofs in the line of Groth, Ostrovsky and Sahai.
We illustrate our techniques by presenting the first instantiation of anonymous proxy signatures, a recent primitive unifying the functionalities and strong security notions of group and proxy signatures. To construct our scheme, we introduce various efficient NIZK and witness-indistinguishable proofs, and a relaxed version of simulation soundness.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-20 01:43:26
The submissions to the SHA-3 competition include a reference implementation in C, built on top of a standard programmer's interface (API). This greatly improves the evaluation process: it enables portability across platforms, and it makes performance comparison of the algorithms easy. For hardware crypto-implementations, such a stan-dard interface does not exist. As a result, the evaluation and comparison of hardware hashing algorithms becomes complex and error prone. The first step to improve the evaluation process for hardware is the definition of an interface. This document describes a general hardware interface for hashing algorithms. The operation of the interface is discussed, and the appendix lists a SHA-256 reference implementation that uses the interface.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-20 01:43:26
When using pairing-friendly ordinary elliptic curves over prime fields to implement identity-based protocols, there is often a need to hash identities to points on one or both of the two elliptic curve groups of prime order $r$ involved in the pairing. Of these $G_1$ is a group of points on the base field $E(\F_p)$ and $G_2$ is instantiated as a group of points with coordinates on some extension field, over a twisted curve $E'(\F_{p^d})$, where $d$ divides the embedding degree $k$. While hashing to $G_1$ is relatively easy, hashing to $G_2$ has been less considered, and is regarded as likely to be more expensive as it appears to require a multiplication by a large cofactor. In this paper we introduce a fast method for this cofactor multiplication on $G_2$ which exploits an efficiently computable homomorphism.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-20 01:43:26
We give a method that appears to be able to find colliding messages for the Waterfall hash function with approximately $O(2^{70})$ work for all hash sizes. If correct, this would show that the Waterfall hash function does not meet the required collision resistance.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-20 01:43:26
Blender is a cryptographic hash function submitted to NIST's SHA3 competition. We have found a semi-free start collision attack on Blender with trivial complexity. One pair of semi-free start collision messages with zero initial values is presented.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-20 01:43:25
Collusion-free protocols prevent subliminal communication (i.e., covert channels) between parties running the protocol. In the standard communication model (and assuming the existence of one-way functions), protocols satisfying any reasonable degree of privacy cannot be collusion-free. To circumvent this impossibility result, Alwen et al. recently suggested the mediated model where all communication passes through a mediator; the goal is to design protocols where collusion-freeness is guaranteed as long as the mediator is honest, while standard security guarantees continue to hold if the mediator is dishonest. In this model, they gave constructions of collusion-free protocols for commitments and zero-knowledge proofs in the two-party setting.
We strengthen the definition of Alwen et al. in several ways, and resolve the key open questions in this area by showing a collusion-free protocol (in the mediated model) for computing any multi-party functionality.
gerelateerde items | rss feed | toevoegen | e-mail nieuwsalarm | | 2008-12-20 01:43:25
Designing efficient cryptographic protocols tolerating adaptive
adversaries, who are able to corrupt parties on the fly as the
computation proceeds, has been an elusive task. Indeed, thus far no
\emph{efficient} protocols achieve adaptive security for general
multi-party computation, or even for many specific two-party tasks
such as oblivious transfer (OT). In fact, it is difficult and
expensive to achieve adaptive security even for the task of
\emph{secure communication}, which is arguably the most basic task
in cryptography.
In this paper we make progress in this area. First, we introduce a
new notion called \emph{second-corruption adaptive} security which
is slightly stronger than static security but \emph{significantly
weaker than fully adaptive security}. As its names indicates, it
limits the adversary's dynamic behavior to only one corruption --
the second, in the case of two-party tasks -- and as such, it is
much easier to achieve. We then give a simple, generic protocol
compiler which transforms any second-corruption secure protocol into
a fully adaptively secure one. The compilation effectively
decomposes the problem of adaptive security into two (simpler)
problems which can be tackled separately: the problem of
second-corruption adaptive security and the problem of realizing a
weaker variant of secure channels.
We solve the latter problem by means of a new primitive that we call
{\em somewhat non-committing encryption} resulting significant
efficiency improvements over the standard method for realizing
(fully) secure channels using (fully) non-committing encryption.
Somewhat non-committing encryption has two parameters: an
equivocality parameter $\ell$ (measuring the number of ways that a
ciphertext can be ``opened'') and the message sizes $k$. Our
implementation is very efficient for small values $\ell$,
\emph{even} when $k$ is large. This translates into a very efficient
compilation of many second-corruption adaptively secure protocols
(in particular, for a task with small input/output domains such as
bit-OT) into a fully adaptively secure protocol.
Finally, we showcase the power of our methodology by applying it to
the recent Oblivious Transfer protocol by Peikert \etal\ [Crypto
2008], which is only secure against static corruptions, to obtain
the first efficient (expected-constant round, expected-constant number of
public-key operations) and adaptively secure bit-OT protocol.
