Extending FORK-256 attack to the full hash function

In a paper published in FSE 2007, a way of obtaining near-collisions and in theory also collisions for the FORK-256 hash function was presented [8]. The paper contained examples of near-collisions for the compression function, but in practice the attack could not be extended to the full function due to large memory requirements and computation time. In this paper we improve the attack and show that it is possible to find near-collisions in practice for any given value of IV. In particular, this means that the full hash function with the prespecified IV is vulnerable in practice, not just in theory. We exhibit an example near-collision for the complete hash function.

Generalised cumulative arrays in secret sharing

Cumulative arrays have played an important role in the early development of the secret sharing theory. They have not been subject to extensive study so far, as the secret sharing schemes built on them generally result in much larger sizes of shares, when compared with other conventional approaches. Recent works in threshold cryptography show that cumulative arrays may be the appropriate building blocks in non-homomorphic threshold cryptosystems where the conventional secret sharing methods are generally of no use. In this paper we study several extensions of cumulative arrays and show that some of these extensions significantly improve the performance of conventional cumulative arrays. In particular, we derive bounds on generalised cumulative arrays and show that the constructions based on perfect hash families are asymptotically optimal. We also introduce the concept of ramp perfect hash families as a generalisation of perfect hash families for the study of ramp secret sharing schemes and ramp cumulative arrays.

Higher order universal one-way hash functions from the subset sum assumption

Universal One-Way Hash Functions (UOWHFs) may be used in place of collision-resistant functions in many public-key cryptographic applications. At Asiacrypt 2004, Hong, Preneel and Lee introduced the stronger security notion of higher order UOWHFs to allow construction of long-input UOWHFs using the Merkle-Damgård domain extender. However, they did not provide any provably secure constructions for higher order UOWHFs. We show that the subset sum hash function is a kth order Universal One-Way Hash Function (hashing n bits to m < n bits) under the Subset Sum assumption for k = O(log m). Therefore we strengthen a previous result of Impagliazzo and Naor, who showed that the subset sum hash function is a UOWHF under the Subset Sum assumption. We believe our result is of theoretical interest; as far as we are aware, it is the first example of a natural and computationally efficient UOWHF which is also a provably secure higher order UOWHF under the same well-known cryptographic assumption, whereas this assumption does not seem sufficient to prove its collision-resistance. A consequence of our result is that one can apply the Merkle-Damgård extender to the subset sum compression function with ‘extension factor’ k+1, while losing (at most) about k bits of UOWHF security relative to the UOWHF security of the compression function. The method also leads to a saving of up to m log(k+1) bits in key length relative to the Shoup XOR-Mask domain extender applied to the subset sum compression function.

Homogeneous bent functions of degree n in 2n variables do not exist for n>3

We prove that homogeneous bent functions f:GF(2)^2n --> GF(2) of degree n do not exist for n>3. Consequently homogeneous bent functions must have degree 3.

Efficient one-time proxy signatures

One-time proxy signatures are one-time signatures for which a primary signer can delegate his or her signing capability to a proxy signer. In this work we propose two one-time proxy signature schemes with different security properties. Unlike other existing one-time proxy signatures that are constructed from public key cryptography, our proposed schemes are based one-way functions without trapdoors and so they inherit the communication and computation efficiency from the traditional one-time signatures. Although from a verifier point of view, signatures generated by the proxy are indistinguishable from those created by the primary signer, a trusted authority can be equipped with an algorithm that allows the authority to settle disputes between the signers. In our constructions, we use a combination of one-time signatures, oblivious transfer protocols and certain combinatorial objects. We characterise these new combinatorial objects and present constructions for them.

Efficient extension of standard Schnorr/RSA signatures into Universal Designated-Verifier Signatures

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

Ideal secret sharing schemes from permutations

The work presents a new method for the design of ideal secret sharing. The method uses regular mappings that are well suited for construction of perfect secret sharing. The restriction of regular mappings to permutations gives a convenient tool for investigation of the relation between permutations and ideal secret sharing generated by them.

Identyfikacja blednych podpisow w kolekcjach

Weryfikacja poprawnosci podpisów cyfrowych jest obliczeniowo kosztowna. Aby ja zwiekszyc, zamiast pojedynczych podpisów weryfikacji poddaje sie kolekcje. Jezeli wszystkie podpisy w kolekcji sa poprawne, to cała kolekcja jest akceptowana. Pojawienie sie błednych podpisów w kolekcji powoduje, ze weryfikacja jest błedna. Nie mozna odrzucic całej kolekcji, zachodzi wiec koniecznosc identyfikacji błednych podpisów w kolekcji. W artykule zdefiniowano metody identyfikacji błednych podpisów. W szczególnosci okreslono weryfikacje typu „dziel i rzadz”, w których wejsciowe kolekcje sa dzielone na podkolekcje tak długo, az koncowe błedne kolekcje zawieraja pojedyncze podpisy. Opisano równiez weryfikator Hamminga identyfikujacy jeden błedny podpis w kolekcji oraz uogólniono ten weryfikator do postaci dwupoziomowego weryfikatora, umozliwiajacego identyfikacje dwóch błednych podpisów. Podano tez definicje ogólnego weryfikatora zdolnego do identyfikacji dowolnej liczby błednych podpisów w kolekcjach.

Improvement of a dynamic accumulator at ICICS 07 and its application in multi-user keyword-based retrieval on encrypted data

A dynamic accumulator is an algorithm, which merges a large set of elements into a constant-size value such that for an element accumulated, there is a witness confirming that the element was included into the value, with a property that accumulated elements can be dynamically added and deleted into/from the original set. Recently Wang et al. presented a dynamic accumulator for batch updates at ICICS 2007. However, their construction suffers from two serious problems. We analyze them and propose a way to repair their scheme. We use the accumulator to construct a new scheme for common secure indices with conjunctive keyword-based retrieval.

Parallel authentication and public-key encryption

A parallel authentication and public-key encryption is introduced and exemplified on joint encryption and signing which compares favorably with sequential Encrypt-then-Sign (ɛtS) or Sign-then-Encrypt (Stɛ) schemes as far as both efficiency and security are concerned. A security model for signcryption, and thus joint encryption and signing, has been recently defined which considers possible attacks and security goals. Such a scheme is considered secure if the encryption part guarantees indistinguishability and the signature part prevents existential forgeries, for outsider but also insider adversaries. We propose two schemes of parallel signcryption, which are efficient alternative to Commit-then-Sign-and- Encrypt (Ct&G3&S). They are both provably secure in the random oracle model. The first one, called generic parallel encrypt and sign, is secure if the encryption scheme is semantically secure against chosen-ciphertext attacks and the signature scheme prevents existential forgeries against random-message attacks. The second scheme, called optimal parallel encrypt. and sign, applies random oracles similar to the OAEP technique in order to achieve security using encryption and signature components with very weak security requirements — encryption is expected to be one-way under chosen-plaintext attacks while signature needs to be secure against universal forgeries under random-plaintext attack, that is actually the case for both the plain-RSA encryption and signature under the usual RSA assumption. Both proposals are generic in the sense that any suitable encryption and signature schemes (i.e. which simply achieve required security) can be used. Furthermore they allow both parallel encryption and signing, as well as parallel decryption and verification. Properties of parallel encrypt and sign schemes are considered and a new security standard for parallel signcryption is proposed.

Privacy enhanced electronic cheque system

With the introduction of Check 21 law and the development of FSTC's echeck system, there has been an increasing usage of e-cheque conversions and acceptance among retailers, banks, and consumers. However, the current e-cheque system does not address issues concerning privacy, confidentiality, and traceability. We highlight the issues concerning the current electronic cheque system and provide a solution to overcome those drawbacks.

Ideal threshold schemes from MDS codes

We observe that MDS codes have interesting properties that can be used to construct ideal threshold schemes. These schemes permit the combiner to detect cheating, identify cheaters and recover the correct secret. The construction is later generalised so the resulting secret sharing is resistant against the Tompa-Woll cheating.

Ideal threshold schemes from orthogonal arrays

The work investigates the design of ideal threshold secret sharing in the context of cheating prevention. We showed that each orthogonal array is exactly a defining matrix of an ideal threshold scheme. To prevent cheating, defining matrices should be nonlinear so both the cheaters and honest participants have the same chance of guessing of the valid secret. The last part of the work shows how to construct nonlinear secret sharing based on orthogonal arrays.

How to strengthen any weakly unforgeable signature into a strongly unforgeable signature

Standard signature schemes are usually designed only to achieve weak unforgeability – i.e. preventing forgery of signatures on new messages not previously signed. However, most signature schemes are randomised and allow many possible signatures for a single message. In this case, it may be possible to produce a new signature on a previously signed message. Some applications require that this type of forgery also be prevented – this requirement is called strong unforgeability. At PKC2006, Boneh Shen and Waters presented an efficient transform based on any randomised trapdoor hash function which converts a weakly unforgeable signature into a strongly unforgeable signature and applied it to construct a strongly unforgeable signature based on the CDH problem. However, the transform of Boneh et al only applies to a class of so-called partitioned signatures. Although many schemes fall in this class, some do not, for example the DSA signature. Hence it is natural to ask whether one can obtain a truly generic efficient transform based on any randomised trapdoor hash function which converts any weakly unforgeable signature into a strongly unforgeable one. We answer this question in the positive by presenting a simple modification of the Boneh-Shen-Waters transform. Our modified transform uses two randomised trapdoor hash functions.