Information Security and Cryptology

We propose new public-key encryption schemes based on the conjugacy search problems (CSP) over noncommutative monoids. Under the newly developed cryptographic assumptions, our basic construction is proven IND-CPA secure in the standard model. Then, we describe two extensions: The first is proven IND-CCA secure in the random oracle model, while the second achieves the IND-CCA security in the standard model. Finally, our proposal is instantiated by using the monoid of matrices over truncated multivariable polynomials over rings. Meanwhile, we also give a discussion on the possibility to instantiate our schemes with braid groups.

It is known that there exists a reduction from the CCA1-security of Damgård’s Elgamal (DEG) cryptosystem to what we call the

$\textrm{ddh}^{\textrm{dsdh}}$

assumption. We show that

$\textrm{ddh}^{\textrm{dsdh}}$

is unnecessary for DEG-CCA1, while DDH is insufficient for DEG-CCA1. We also show that CCA1-security of the Elgamal cryptosystem is equivalent to another assumption

$\textrm{ddh}^{\textrm{csdh}}$

, while we show that

$\textrm{ddh}^{\textrm{dsdh}}$

is insufficient for Elgamal’s CCA1-security. Finally, we prove a generic-group model lower bound

$\Omega (\sqrt[3]{q})$

for the hardest considered assumption

$\textrm{ddh}^{\textrm{csdh}}$

, where

q

is the largest prime factor of the group order.

In this paper, we redefine a cryptographic notion called

Online/Offline Identity-Based Signcryption

. It is an “online/offline” version of identity-based signcryption, where most of the computations are carried out offline while the online part does not require any heavy computations such as pairings or multiplications on elliptic curve. It is particularly suitable for power-constrained devices such as smart cards. We give a concrete implementation of online/offline identity-based signcryption, which is very efficient and flexible. Unlike all the previous schemes in the literature, our scheme does

not

require the knowledge of receiver’s information (either public key or identity) in the offline stage. The receiver’s identity and the message to be signcrypted are only needed in the online stage. This feature provides a great flexibility to our scheme and makes it practical to use in real-world applications. To our knowledge, our scheme is the

first

one in the literature to provide this kind of feature. We prove that the proposed scheme meets strong security requirements in the random oracle model, assuming the Strong Diffie-Hellman (SDH) and Bilinear Diffie-Hellman Inversion (BDHI) are computationally hard.

This paper studies error-free, multi-bit non-committing encryptions in the universally composable (UC) framework with constant round complexity. Previous efficient protocols such as the Beaver’s protocol and the Damgard-Nielsen’s protocol cause errors with certain probability, and require restarting the channel setup procedures if an error happens. This causes the main problem of UC-security of a non-committing protocol with error. The proposed error-free,

l

-bit non-committing encryption is fixed 4-round and it is as efficient as

l

-instance of the Beaver’s protocol running in parallel. We show that the proposed scheme realizes the UC-security in the presence of adaptive adversary assuming that the decisional Diffie-Hellman problem is hard.

A new key recovery attack under related-key model on RC4 is presented in this paper. This novel attack is based on the property that RC4 can generate a large amount of colliding key pairs. By making use of this property, we are able to recover any random key in practical time when the length of the key is large under a new proposed related key model. Differing from the attack against WEP, neither the knowledge of the IVs nor the keystream outputs are required. Also compared with some recent key recovery attacks, which assume that the attacker knows the

S

-Box after KSA algorithm and can only recover very short keys (5 bytes) efficiently, our attack works very well for keys with larger size. We give the theoretical proof for the complexity of our attack which matches with the experimental result very well. An 86-byte random secret key can be recovered in about 21.2 hours time by using a standard desktop PC. This novel attack provides us with another theoretical approach to attack WPA and WEP. Remark that our model can be used for more efficient key recovering if any new key collisions can be further discovered in the future.

In stream ciphers, the ratio of performance to the security is the most important issue. However, the S-boxes used in a stream cipher can become a bottleneck of speed due to use of large memory, difficulty in hardware realization and more processing. This paper proposes an S-box construction that is easy to implement both in hardware and software. The proposed S-box is efficient in speed, parameterized and scalable with excellent security properties. It also provides a designer with the flexibility to trade-off among speed, area and the security properties. The security analysis has been performed on the S-box. The security properties are found to be comparable with the existing standards.

We point out that a family of pseudorandom binary lattices, which were constructed by using the multiplicative inverse, can be generated as binary threshold sequences. Hence we can estimate the well-distribution measure and the correlation measure of order ℓ of the binary lattices in terms of discrepancy bounds on corresponding pseudorandom numbers in the interval [0,1). We also consider the modified well-distribution measure and the modified correlation measure of order ℓ, which were introduced by Sárközy and Winterhof, for the binary lattices.

Verheul’s theorem [20,21] on some certain supersingular elliptic curves is usually considered as an evidence for the difficulty of pairing inversion. Moody in [16] generalized it to some other supersingular curves. In this paper, we construct two types of ordinary elliptic curves with embedding degree

k

 = 1, and give the corresponding distortion maps. Following their method, we generalize Verheul’s theorem to our curves.

Computing the information rate of access structures is an important part of the research of secret sharing schemes. In this paper, we investigate two combinatorial approaches of computing upper bounds on the information rate of access structures - the Csirmaz’s polymatroid approach and the independent sequence approach. We prove that the Csirmaz’s polymatroid approach is only a special variant of the independent sequence approach, and finding an independent sequence with respect to a graph-based access structure with maximum length is equivalent to finding a maximum alternating cycle-free matching in a bipartite graph, which is a NP hard problem.

In the information-theoretic setting, where adversaries have unlimited computational power, the fundamental cryptographic primitive Oblivious Transfer (OT) cannot be securely achieved if the parties are communicating over a clear channel. To preserve secrecy and security, the players have to rely on noise in the communication. Noisy channels are therefore a useful tool to model noise behavior and build protocols implementing OT. This paper explores a source of errors that is inherently present in practically any transmission medium, but has been scarcely studied in this context: delays in the communication.

In order to have a model for the delays that is both general and comparable to the channels usually used for OT – such as the Binary Symmetric Channel (BSC) – we introduce a new noisy channel, the Binary Discrete-time Delaying Channel (BDDC). We show that such a channel realistically reproduces real-life communication scenarios where delays are hard to predict and we propose a protocol for achieving oblivious transfer over the BDDC. We analyze the security of our construction in the semi-honest setting, showing that our realization of OT substantially decreases the protocol sensitivity to the user’s knowledge of the channel compared to solutions relying on other channel properties, and is very efficient for wide ranges of delay probabilities. The flexibility and generality of the model opens the way for future implementation in media where delays are a fundamental characteristic.

We introduce a statistical experiment setting to carry out a multicollision attack on any iterated hash function. We develop a method for finding multicollisions that gives larger multicollision sets for the same amount of work as Joux’s famous method i.e. with

$2.5\cdot k2^{\frac{n}{2}}$

work one can find greater than 2

k

-collisions for large

k

. Furthermore, if the message length is not restricted, we show that we can create arbitrarily large multicollisions by finding two cycles in the iterated hash function. This applies even when an ideal compression function is used.

Grøstl[1] is one of the second round candidates of the SHA-3 competition[2] hosted by NIST, which aims to find a new hash standard. In this paper, we studied equivalent expressions of the generalized AES-like permutation. We found that four rounds of the AES-like permutation can be regarded as a Hyper-Sbox. Then we further analyzed the differential properties of both Super-Sbox and Hyper-Sbox. Based on these observations, we give an 8-round truncated differential path of the generalized AES-like permutation, which can be used to construct a distinguisher of 8-round Grøstl-256 permutation with 2

64

time and 2

64

memory. This is the best known distinguisher of reduced-round Grøstl permutation.

This paper presents the first results on the preimage resistance of ISO standard hash functions RIPEMD-128 and RIPEMD-160. They were designed as strengthened versions of RIPEMD. While preimage attacks on the first 33 steps and intermediate 35 steps of RIPEMD (48 steps in total) are known, no preimage attack exists on RIPEMD-128 (64 steps) or RIPEMD-160 (80 steps). This paper shows three variations of attacks on RIPEMD-128; the first 33 steps, intermediate 35 steps, and the last 32 steps. It is interesting that the number of attacked steps for RIPEMD-128 reaches the same level as RIPEMD. We show that our approach can also be applied to RIPEMD-160, and present preimage attacks on the first 30 steps and the last 31 steps.

In this paper, we present the pseudo-collision, pseudo-second-preimage and pseudo-preimage attacks on the SHA-3 candidate algorithm Luffa. The pseudo-collisions and pseudo-second-preimages can be found easily by computing the inverse of the message injection function at the beginning of Luffa. We explain in details the pseudo-preimage attacks. For Luffa-224/256, given the hash value, only 2 iteration computations are needed to get a pseudo-preimage. For Luffa-384, finding a pseudo-preimage needs about 2

64

iteration computations with 2

67

bytes memory by the extended generalized birthday attack. For Luffa-512, the complexity is 2

128

iteration computations with 2

132

bytes memory.

It is noted that, we can find the pseudo-collision pairs and the pseudo-second images only changing a few different bits of initial values. That is directly converted to the forgery attack on NMAC in related key cases.

This paper presents the first distinguishing attack on the LPMAC based on RIPEMD, 58-step reduced RIPEMD-256 and 48-step reduced RIPEMD-320, and the LPMAC is the secret-prefix MAC with the message length prepended to the message before hashing. Wang et al. presented the first distinguishing attack on HMAC/NMAC-MD5 without the related-key setting in [27], then they extended this technique to give a distinguishing attack on the LPMAC based on 61-step SHA-1 in [24]. In this paper, we utilize the techniques in [24,27] combined with our pseudo-near-collision differential path on the full RIPEMD, 58-step reduced RIPEMD-256 and 48-step reduced RIPEMD-320 to distinguish the LPMAC based on the full RIPEMD, 58-step reduced RIPEMD-256 and 48-step reduced RIPEMD-320 from the LPMAC based on a random function respectively. Because RIPEMD and RIPEMD-{256,320} all contain two different and independent parallel lines of operations, the difficulty of our attack is to choose proper message differences and to find proper near-collision differential paths of the two parallel lines of operations. The complexity of distinguishing the LPMAC based on the full RIPEMD is about 2

66

MAC queries. For the LPMAC based on 58-step reduced RIPEMD-256 and 48-step reduced RIPEMD-320, the complexities are about 2

163.5

MAC queries and 2

208.5

MAC queries respectively.

Three-party password-based authenticated key exchange (3-party PAKE) protocols are attractive due to their convenience in many communication applications, and thus have been receiving much interest in the cryptographic research community. But, until now, how to build provably secure 4-round 3-party PAKE protocol in a formal way is still an open problem. In this paper, we introduce a target driven formal way to build a 4-round provably secure 3-Party PAKE protocol. Aiming at the security target and the efficiency one, we firstly present a new generic construction for 3PAKE protocols which enjoys perfect security. Furthermore, for obtaining a 4-round communication, we carefully simplify the above generic construction so as to get an improved version holding the target security. Finally, using the improved construction and some instantiation techniques, we present a provably secure 4-round 3-party PAKE protocol.

Group key exchange (GKE) allows a group of

n

parties to share a common secret key over insecure channels. Since key management is important, NIST is now looking for a standard. The goal of this paper is to redesign GKE using bilinear pairings, proposed by Desmedt and Lange, from the point of view of arrangement of parties. The arrangement of parties is called a party tree in this paper. Actually, we are able to

redesign

the party tree, to reduce the computational and communicational complexity compared with the previous scheme, when GKE is executed among a small group of parties. We also redesign the general party tree for a large number of parties, in which each party is in a different environment such as having large or limited computational resources, electrical power, etc.

A great deal of authenticated key exchange (AKE) protocols have been proposed in recent years. Most of them were based on 1-factor authentication. In order to increase the security for AKE protocols, various authentication means can be used together. In fact, the existing multi-factor AKE protocols provide an authenticated key exchange only between a client and a server. This paper presents a new multi-factor AKE protocol in the three-party settings (3MFAKE), in which the authentication means combine a password, a secure device, and biometric authentications. We also prove the security of the protocol in the random oracle model.

The constrained resources of sensors restrict the design of a key management scheme for wireless sensor networks (WSNs). In this work, we first formalize the security model of ALwEN, which is a gossip-based wireless medical sensor network (WMSN) for ambient assisted living. Our security model considers the node capture, the gossip-based network and the revocation problems, which should be valuable for ALwEN-like applications. Based on Shamir’s secret sharing technique, we then propose two key management schemes for ALwEN, namely the KALwEN+ schemes, which are proven with the security properties defined in the security model. The KALwEN+ schemes not only fit ALwEN, but also can be tailored to other scalable wireless sensor networks based on gossiping.

In INSCRYPT 2008, Ruj and Roy proposed deterministic key predistribution schemes using codes. Particularly, they used Reed Solomon codes to present key predistribution schemes. They calculate the connectiviey and resiliency of the network when the schemes are based on Reed Solomon codes. However, the connectivity and resiliency of the network for the schemes using other codes haven’t been calculated so far. In the present paper, we will determine the key parameters of predistribution schemes via linear codes in wireless sensor networks. We calculate the connective probability, the probability

fail

(1) and the upper bound of the fraction of links broken when

s

nodes are compromised. We use the theory of matroid. We find that it is very surprising that these parameters can be calculated by making use of the chromatic polynomial of the matroid associated to the codes used in the resulting schemes.

Sanitizable signatures have been introduced recently to provide a means for the signer to authorize a censor to modify some parts of the signed message without the help of the original signer. This paper presents the following three contributions. (1) We point out the weaknesses of Brzuska

et al.

’s (PKC 2009) and Canard

et al.

’s (CT-RSA 2010) constructions respectively. Namely we show that their constructions are not signer-accountable. (2) We point out the weakness of Brzuska

et al.

’s security model (PKC 2009) for sanitizable signatures by showing some potential attacks neglected in their original model. (3) We present a stronger security model based on Brzuska

et al.

’s model and a fully-secure construction based on both Brzuska

et al.

’s and Canard

et al.

’s constructions. We must note that our proposed construction is much more practical than prior ones. In detail, the computation costs of signing, sanitizing and verification algorithm are

constant

and the signature size is

constant

as well.

In this paper, we point out that previous security models for the Designated Verifier Signature (DVS) are not sufficient because some serious problems may be caused such that the verifier cannot confirm the validity of the signature even if a scheme satisfies previous security models. Hence, our aim is to clarify rigorous security requirements for the DVS. We use the universal composability (UC) framework. First, we define an ideal DVS functionality within the UC framework. Next, we propose a new security model for the DVS and show that it is necessary and sufficient by proving the equivalence between the DVS functionality and the proposed model. By our reconsideration, it emerges that the DVS requires stronger unforgeability than previous definitions but privacy of signer’s identity considered in previous definitions is unnecessary. Finally, we revisit the security of previous DVS schemes according to our rigorous security model. Then, we justify the DVS functionality in feasibility by showing some DVS schemes can satisfy the proposed model.

Courtois-Finiasz-Sendrier (CFS) digital signatures critically depend on the ability to efficiently find a decodable syndrome by random sampling the syndrome space, previously restricting the class of codes upon which they could be instantiated to generic binary Goppa codes. In this paper we show how to construct

t

-error correcting quasi-dyadic codes where the density of decodable syndromes is high, while also allowing for a reduction by a factor up to

t

in the key size.

Fast signature verification is desirable in many applications, especially when signature recipients need to make response quickly. In this paper, we present an efficient

online/offline verification of short signature (OVS)

scheme without random oracles. Besides message signing, signature verification can be also separated into offline phase and online phase. Only one multi-exponentiation is required for the verifier in the online phase. In addition, our signature is short which gives about 480 bits for 80-bit security. Our scheme indeed improves the efficiency of signature verification since no pairing operation is required in the online phase. We also give a generic construction of OVS schemes using the idea of double trapdoor chameleon hash.

A primary functionality of public key encryption schemes is data privacy, while in many cases key privacy (aka. anonymity of public keys) may also be important. Traditionally, one has to separately design/prove them, because data privacy and key privacy were shown to be independent from each other [5,40]. Existing constructions of anonymous public key encryption usually take either of the following two approaches:

1

Directly construct it from certain number theoretic assumptions.

2

Find a suitable anonymous encryption scheme with key privacy yet without chosen ciphertext security, then use some dedicated transforms to upgrade it to one with key privacy and chosen ciphertext security.

While the first approach is intricate and a bit mysterious, the second approach is unnecessarily a real solution to the problem, namely, how to acquire key privacy. In this paper, we show how to build anonymous encryption schemes from a class of key encapsulation mechanisms with only weak data privacy, in the random oracle model. Instantiating our generic construction, we obtain many interesting anonymous public key encryption schemes. We note that some underlying schemes are based on gap assumptions or with bilinear pairings, which were previously well-known not anonymous.

During ISC’2008 Yanjiang Yang, Xuhua Ding, Robert H. Deng, and Feng Bao presented a construction for holding an encrypted database in a cloud so that the access pattern remains hidden. The scheme is designed for the case when a user holds a trusted hardware unit, which serves as an interface between the owner of the database and the untrusted environment where the encrypted database is stored. The scheme is relatively efficient and has some provable privacy properties.

In this paper we analyze an idealized version of the above protocol and prove rigorously strong privacy conditions in a model with a powerful adversary observing all operations occurring in the cloud. On the other hand, we show that the full version of the protocol (with some implementation details), as proposed at ISC’2008, leaks some information about the access pattern of the user. This shows that the protocol does not fulfil the property of ideally private information retrieval. While this is not a general full scale attack, at some specific situations information leakage presented might have practical value for an adversary.

Algebraic cryptanalysis is a general tool which permits one to assess the security of a wide range of cryptographic schemes. Algebraic techniques have been successfully applied against a number of multivariate schemes and stream ciphers. Yet, their feasibility against block ciphers remains the source of much speculation. In this context, algebraic techniques have mainly been deployed in order to solve a system of equations arising from the cipher, so far with limited success. In this work we propose a different approach: to use Gröbner basis techniques to compute

structural

features of block ciphers, which may then be used to improve “classical” differential and integral attacks. We illustrate our techniques against the block ciphers

Present

and

Ktantan

32.

In this note, we deduce a bound between fast algebraic immunity and higher order nonlinearity (it is the first time that a bound between these two cryptographic criteria is given), and find that a Boolean function should have high

r

-order nonlinearity to resist fast algebraic attacks. As a corollary, we find that no matter how much effort we make, the Tu-Deng functions cannot be repaired in a standard way to behave well against fast algebraic attacks. Therefore, we should give up repairing this class of Boolean functions and try to find other classes of functions with good cryptographic properties or to prove that the Carlet-Feng function behaves well.

Chameleon signatures simultaneously provide the properties of non-repudiation and non-transferability for the signed message. However, the initial constructions of chameleon signatures suffer from the key exposure problem of chameleon hashing. This creates a strong disincentive for the recipient to forge signatures, partially undermining the concept of non-transferability. Recently, some specific constructions of key-exposure free chameleon hashing based on various assumptions are presented.

In this paper, we present some security flaws of the key-exposure free chameleon hash scheme based on factoring [10]. Besides, we propose an improved chameleon hash scheme without key exposure based on factoring which enjoys all the desired security notions of chameleon hashing.

In 2010, Yeh, Lo and Winata [1] proposed a process-oriented ultralightweight RFID authentication protocol. This protocol is claimed to provide strong security and robust privacy protection, while at the same time the usage of resources on tags is optimized. Nevertheless, in this paper we show how the protocol does not achieve any of its intended security objectives; the main result is that the most valuable information stored on the tag, that is, the static identifier

ID

, is easily recovered even by a completely passive attacker in a number of ways. More precisely, we start by presenting a traceability attack on the protocol that allows tags to be traced. This essentially exploits the fact that the protocol messages leak out at least one bit of the static identifier. We then present a passive attack (named Norwegian attack) that discloses

$\lfloor \log_2 L \rfloor$

bits of the

ID

, after observing roughly

O

(

L

) authentication sessions. Although this attack may seem less feasible in retrieving the full 96-bits of the

ID

due to the large number of eavesdropped sessions involved, it is already powerful enough to serve as a basis for a very effective traceability attack. Finally, our last attack represents a step forward in the use of a recent cryptanalysis technique (called Tango attack [2]), which allows for an extremely efficient full disclosure attack, capable of revealing the value of the whole

ID

after eavesdropping only a very small number of sessions.

A zap is a two-round public coin witness indistinguishable proof system, where the first round is a random string from the verifier to the prover. This notion is proposed by Dwork and Naor. They constructed a zap for NP from any non-interactive zero-knowledge (NIZK) proof which has many applications in the literature. In this note, we start with a more explicit proof of their soundness through enumeration. Based on this proof view point, we further show that if NIZK used in their zap has an adaptive soundness, then the zap soundness error can be reduced by a factor of 2

|

x

|

, where |

x

| is the length of the

${\cal NP}$

-statement and is fixed before the protocol starts (but

x

itself can be chosen adaptively). Our improved bound is optimal in the sense that for any

${\cal NP}$

-language

L

, there exists a NIZK that asymptotically achieves this bound. Finally, we investigate their deniable authentication protocol from this zap. We show that this protocol in fact can be simplified without a zap.

An online/offline signature scheme allows separation of its signing algorithm into

offline

phase and

online

phase. There have been many constructions in the literature, and they are provably secure under chosen-message attacks. However, it has recently been shown that this security notion is insufficient due to

side-channel attacks

, where an adversary can exploit leakage of information from the implementation of the signing algorithm. Regarding the implementation of online/offline signatures, we found that the online phase is much more critical than the offline phase. In this paper, we propose two efficient online/offline signature schemes. Our online phase is secure with unbounded leakage resilience as long as the assumption that only computation leaks information holds. Our constructions offer a very

short

signature length and they are efficient in the online phase with modular additions only.

In this article, we propose a new approach to characterize the EM leakage of electronic devices by identifying and focusing on the signals’ frequencies leaking the most information. We introduce a set of tests based on cryptanalysis methods that will help vendors and users of sensitive devices to estimate the security risks due to leakage through electromagnetic emanations. We propose two approaches: an empirical one and another based on information theory. Both provide a characterization of the leakage

i.e.

the frequencies and the bandwidths where information is contained. These techniques are low cost, automatic, and fast as they can be performed with an oscilloscope and some softwares for the characterization. Such evaluation could also be carried out with TEMPEST. But TEMPEST evaluations require dedicated apparatus and time consuming step work that consists in scanning all the spectrum frequencies. Our approach does not substitute to regulatory TEMPEST evaluation, but nonetheless can identify the leakage with high confidence. To illustrate the relevance of our approach, we show that an online software filtering at some identified frequencies allows us to recover a key stroked in one measurement at the distance of 5 meters from the keyboard.

In recent years, theoretical cryptography community has focused on a fascinating research line of obfuscating programs (circuits). Loosely speaking, obfuscating a program

P

is to construct a new program which can preserve

P

’s functionality, but its code is fully “unintelligent”. No adversary can understand the obfuscated program or reverse-engineering it.

In TCC’10, Goyal et al. showed how to obfuscate any circuit (program) with tamer-proof (stateless) hardware. In their construction, the hardware executes most computation and the software executes a few, and the software needs to interact with the hardware Θ(

z

) times if the original circuit is of size

z

. Thus if a user wants to gain the outputs of the obfuscated circuit on different inputs, he cannot fast the computation by running multiple instances of the obfuscated circuit concurrently well.

In this paper we propose an alternative construction of obfuscating circuits (programs) with tamper-proof hardware. The notable characters of our construction are that the required hardware is still universal in obfuscating circuits and that for a specific circuit the computation on the instantiated hardware is independent of the size of the circuit. When a user runs multiple instances of the obfuscated circuit with different inputs concurrently, the software and hardware have reasonable computation load and thus the entire computation can run almost in parallel and thus be fasten.

It is important for malware analysis that comparing unknown files to previously-known malicious samples to quickly characterize the type of behavior and generate signatures. Malware writers often use obfuscation, such as packing, junk-insertion and other means of techniques to thwart traditional similarity comparison methods. In this paper, we introduce DepSim, a novel technique for finding dependency similarities between malicious binary programs. DepSim constructs dependency graphs of control flow and data flow of the program by taint analysis, and then conducts similarity analysis using a new graph isomorphism technique. In order to promote the accuracy and anti-interference capability, we reduce redundant loops and remove junk actions at the dependency graph pre-processing phase, which can also greatly improve the performance of our comparison algorithm. We implemented a prototype of DepSim and evaluated it to malware in the wild. Our prototype system successfully identified some semantic similarities between malware and revealed their inner similarity in program logic and behavior. The results demonstrate that our technique is accurate.