Fast Software Encryption

MDS matrices allow to build optimal linear diffusion layers in block ciphers. However, MDS matrices cannot be sparse and usually have a large description, inducing costly software/hardware implementations. Recursive MDS matrices allow to solve this problem by focusing on MDS matrices that can be computed as a power of a simple companion matrix, thus having a compact description suitable even for constrained environments. However, up to now, finding recursive MDS matrices required to perform an exhaustive search on families of companion matrices, thus limiting the size of MDS matrices one could look for. In this article we propose a new

direct

construction based on shortened BCH codes, allowing to efficiently construct such matrices for whatever parameters. Unfortunately, not all recursive MDS matrices can be obtained from BCH codes, and our algorithm is not always guaranteed to find the best matrices for a given set of parameters.

Side-channel analysis is an important issue for the security of embedded cryptographic devices, and masking is one of the most investigated solutions to mitigate such attacks. In this context, efficient masking has recently been considered as a possible criteria for new block cipher designs. Previous proposals in this direction were applicable to different types of masking schemes (e.g. Boolean and polynomial). In this paper, we study possible optimizations when specializing the designs to Boolean masking. For this purpose, we first observe that bitslice ciphers have interesting properties for improving both the efficiency and the regularity of masked software implementations. Next we specify a family of block ciphers (denoted as LS-designs) that can systematically take advantage of bitslicing in a principled manner. Eventually, we evaluate both the security and performance of such designs and two of their instances, confirming excellent properties for physically secure applications.

Recently, Banerjee, Peikert and Rosen (EUROCRYPT 2012) proposed new theoretical pseudorandom function candidates based on “rounded products” in certain polynomial rings, which have rigorously provable security based on worst-case lattice problems. The functions also enjoy algebraic properties that make them highly parallelizable and attractive for modern applications, such as evaluation under homomorphic encryption schemes. However, the parameters required by BPR’s security proofs are too large for practical use, and many other practical aspects of the design were left unexplored in that work.

In this work we give two concrete and practically efficient instantiations of the BPR design, which we call SPRING, for “subset-product with rounding over a ring.” One instantiation uses a generator matrix of a binary BCH error-correcting code to “determinstically extract” nearly random bits from a (biased) rounded subset-product. The second instantiation eliminates bias by working over suitable moduli and decomposing the computation into “Chinese remainder” components.

We analyze the concrete security of these instantiations, and provide initial software implementations whose throughputs are within small factors (as small as 4.5) of those of AES.

Recent years have seen considerable interest in lightweight cryptography. One particular consequence is a renewed study of meet-in-the-middle attacks, which aim to exploit the relatively simple key schedules often encountered in lightweight ciphers. In this paper we propose a new technique to extend the number of rounds covered by a meet-in-the-middle attack, called a match box. Furthermore, we demonstrate the use of this technique on the lightweight cipher KATAN, and obtain the best attack to date on all versions of KATAN. Specifically, we are able to attack 153 of the 254 rounds of KATAN32 with low data requirements, improving on the previous best attack on 115 rounds which requires the entire codebook.

In this paper, we investigate the properties of iterative non-injective functions and the security of primitives where they are used. First, we introduce the Collision Probability Spectrum (

cps

) parameter to quantify how far from a permutation a function is. In particular, we show that the output size decreases linearly with the number of iterations whereas the collision trees grow quadratically.

Secondly, we investigate the

t

-sponge construction and show how certain

cps

and rate values lead to an improved preimage attack on long messages. As an example, we find collisions for the

gluon

-64 internal function, approximate its

cps

, and show an attack that violates the security claims. For instance, if a message ends with a sequence of 1 Mb (respectively 1 Gb) of zeros, then our preimage search takes time

$$2^{115.3}$$

(respectively

$$2^{105.3}$$

) instead of

$$2^{128}$$

.

The all-subkeys recovery (ASR) attack is an extension of the meet-in-the-middle attack, which allows evaluating the security of a block cipher without analyzing its key scheduling function. Combining the ASR attack with some advanced techniques such as the function reduction and the repetitive ASR attack, we show the improved ASR attacks on the 7-round reduced

FOX64

and

FOX128

. Moreover, the improved ASR attacks on the 119-, 105- and 99-round reduced

KATAN32

,

KATAN48

and

KATAN64

, and the 42-round reduced

SHACAL-2

are also presented, respectively. As far as we know, all of those attacks are the best single-key attacks with respect to the number of attacked rounds in literature.

This paper focuses on key-recovery attacks on 9-round AES-192 and AES-256 under single-key model with the framework of the meet-in-the-middle attack. A new technique named

key-dependent sieve

is introduced to further reduce the size of lookup table of the attack, and the 9-round AES-192 is broken with

$$2^{121}$$

chosen plaintexts,

$$2^{187.5}$$

9-round encryptions and

$$2^{185}$$

128-bit words of memory. If the attack starts from the third round, the complexities would be further reduced by a factor of 16. Moreover, the whole attack is split up into a series of weak-key attacks. Then the memory complexity of the attack is saved significantly when we execute these weak attacks in streaming mode. This method is also applied to reduce the memory complexity of the attack on 9-round AES-256.

We define and analyze the security of a blockcipher mode of operation,

$$\mathrm {CLOC}$$

, for provably secure authenticated encryption with associated data. The design of

$$\mathrm {CLOC}$$

aims at optimizing previous schemes, CCM, EAX, and EAX-prime, in terms of the implementation overhead beyond the blockcipher, the precomputation complexity, and the memory requirement. With these features,

$$\mathrm {CLOC}$$

is suitable for handling short input data, say 16 bytes, without needing precomputation nor large memory. This property is especially beneficial to small microprocessors, where the word size is typically 8 bits or 16 bits, and there are significant restrictions in the size and the number of registers.

$$\mathrm {CLOC}$$

uses a variant of CFB mode in its encryption part and a variant of CBC MAC in the authentication part. We introduce various design techniques in order to achieve the above mentioned design goals. We prove

$$\mathrm {CLOC}$$

secure, in a reduction-based provable security paradigm, under the assumption that the blockcipher is a pseudorandom permutation. We also present our preliminary implementation results.

The domain of lightweight cryptography focuses on cryptographic algorithms for extremely constrained devices. It is very costly to avoid nonce reuse in such environments, because this requires either a hardware source of randomness, or non-volatile memory to store a counter. At the same time, a lot of cryptographic schemes actually require the nonce assumption for their security. In this paper, we propose APE as the first permutation-based authenticated encryption scheme that is resistant against nonce misuse. We formally prove that APE is secure, based on the security of the underlying permutation. To decrypt, APE processes the ciphertext blocks in reverse order, and uses inverse permutation calls. APE therefore requires a permutation that is both efficient for forward and inverse calls. We instantiate APE with the permutations of three recent lightweight hash function designs:

Quark

,

Photon

, and

Spongent

. For any of these permutations, an implementation that supports both encryption and decryption requires less than 1.9 kGE and 2.8 kGE for 80-bit and 128-bit security levels, respectively.

We present a new, misuse-resistant scheme for online authenticated encryption, following the framework set forth by Fleischmann et al. (FSE 2012). Our scheme, COBRA, is roughly as efficient as the GCM mode of operation for nonce-based authenticated encryption, performing one block cipher call plus one finite field multiplication per message block in a parallelizable way. The major difference from GCM is that COBRA preserves privacy up to prefix under nonce repetition. However, COBRA only provides authenticity against nonce-respecting adversaries. As compared to COPA (ASIACRYPT 2013), our new scheme requires no block cipher inverse and hence enjoys provable security under a weaker assumption about the underlying block cipher. In addition, COBRA can possibly perform better than COPA on platforms where finite field multiplication can be implemented faster than the block cipher in use, since COBRA essentially replaces half of the block cipher calls in COPA with finite field multiplications.

Correct authenticated decryption requires the receiver to buffer the decrypted message until the authenticity check has been performed. In high-speed networks, which must handle large message frames at low latency, this behavior becomes practically infeasible. This paper proposes

CCA

-secure on-line ciphers as a practical alternative to AE schemes since the former provide some defense against malicious message modifications. Unfortunately, all published on-line ciphers so far are either inherently sequential, or lack a

CCA

-security proof.

This paper introduces

POE

, a family of on-line ciphers that combines provable security against chosen-ciphertext attacks with pipelineability to support efficient implementations.

POE

combines a block cipher and an

$$\epsilon $$

-AXU family of hash functions. Different instantiations of

POE

are given, based on different universal hash functions and suitable for different platforms. Moreover, this paper introduces

POET

, a provably secure on-line AE scheme, which inherits pipelineability and chosen-ciphertext-security from

POE

and provides additional resistance against nonce-misuse attacks.

FIDES

is a lightweight authenticated cipher, presented at CHES 2013. The cipher has two version, providing either 80-bit or 96-bit security. In this paper, we describe internal state-recovery attacks on both versions of

FIDES

, and show that once we recover the internal state, we can use it to immediately forge

any

message. Our attacks are based on a guess-and-determine algorithm, exploiting the slow diffusion of the internal linear transformation of

FIDES

. The attacks have time complexities of

$$2^{75}$$

and

$$2^{90}$$

for

FIDES-80

and

FIDES-96

, respectively, use a very small amount of memory, and their most distinctive feature is their very low data complexity: the attacks require at most 24 bytes of an arbitrary plaintext and its corresponding ciphertext, in order to break the cipher with probability 1.

We study the security of

key-alternating Feistel

ciphers, a class of key-alternating ciphers with a Feistel structure. Alternatively, this may be viewed as the study of Feistel ciphers where the pseudorandom round functions are of the form

$$F_i(x\oplus k_i)$$

, where

$$k_i$$

is the (secret) round key and

$$F_i$$

is a

public

random function that the adversary is allowed to query in a black-box way. Interestingly, our results can be seen as a generalization of traditional results

à la

Luby-Rackoff in the sense that we can derive results for this model by simply letting the number of queries of the adversary to the public random functions

$$F_i$$

be zero in our general bounds. We make an extensive use of the coupling technique. In particular (and as a result of independent interest), we improve the analysis of the coupling probability for balanced Feistel schemes previously carried out by Hoang and Rogaway (CRYPTO 2010).

It is well known that the classical three- and four-round Feistel constructions are provably secure under chosen-plaintext and chosen-ciphertext attacks, respectively. However, irrespective of the number of rounds, no Feistel construction can resist related-key attacks where the keys can be offset by a constant. In this paper we show that, under suitable reuse of round keys, security under related-key attacks can be provably attained. Our modification is simpler and more efficient than alternatives obtained using generic transforms, namely the PRG transform of Bellare and Cash (CRYPTO 2010) and its random-oracle analogue outlined by Lucks (FSE 2004). Additionally we formalize Luck’s transform and show that it does not

always

work if related keys are derived in an oracle-dependent way, and then prove it sound under appropriate restrictions.

Given

$$k$$

independent pseudorandom permutations

$$f_1,\ldots ,f_k$$

over

$$\{0,1\}^n$$

, it is natural to define a pseudorandom function by XORing the permutations:

$$f_1\oplus \ldots \oplus f_k$$

. In [

9

] Stefan Lucks studied the security of this PRF. In this paper we improve the security bounds of [

9

] by using different proof techniques.

ANSI X9.24-1:2009 specifies the key check value, which is used to verify the integrity of the blockcipher key. This value is defined as the most significant bits of the ciphertext of the zero block, and is assumed to be publicly known data for verification. ISO/IEC 9797-1:2011 illustrates a total of ten CBC MACs, where one of these MACs, the basic CBC MAC, is widely known to be insecure. In this paper, we consider the remaining nine CBC MACs and derive the quantitative security impact of using the key check value. We first show attacks against five MACs by taking advantage of the knowledge of the key check value. We then

prove

that the analysis is tight, in a concrete security paradigm. For the remaining four MACs, we prove that

the standard birthday bound still holds

even with the presence of the key check value. As a result, we obtain a complete characterization of the impact of using ANSI X9.24-1 key check value with the ISO/IEC 9797-1 MACs.

We conduct an analysis of the RC4 algorithm as it is used in the IEEE WPA/TKIP wireless standard. In that standard, RC4 keys are computed on a per-frame basis, with specific key bytes being set to known values that depend on 2 bytes of the WPA frame counter (called the TSC). We observe very large, TSC-dependent biases in the RC4 keystream when the algorithm is keyed according to the WPA specification. These biases permit us to mount an effective statistical, plaintext-recovering attack in the situation where the same plaintext is encrypted in many different frames (the so-called “broadcast attack” setting). We assess the practical impact of these attacks on WPA/TKIP.

The first three bytes of the RC4 key in WPA are public as they are derived from the public parameter

IV

, and this derivation leads to a strong mutual dependence between the first two bytes of the RC4 key. In this paper, we provide a disciplined study of RC4 biases resulting specifically in such a scenario. Motivated by the work of AlFardan et al. (2013), we first prove the interesting sawtooth distribution of the first byte in WPA and the similar nature for the biases in the initial keystream bytes towards zero. As we note, this sawtooth characteristics of these biases surface due to the dependence of the first two bytes of the RC4 key in WPA, both derived from the same byte of the

IV

. Our result on the nature of the first keystream byte provides a significantly improved distinguisher for RC4 used in WPA than what had been presented by Sepehrdad et al. (2011–2012). Further, we revisit the correlation of initial keystream bytes in WPA to the first three bytes of the RC4 key. As these bytes are known from the

IV

, one can obtain new as well as significantly improved biases in WPA than the absolute biases exploited earlier by AlFardan et al. or Isobe et al. We notice that the correlations of the keystream bytes with publicly known

IV

values of WPA potentially strengthen the practical plaintext recovery attack on the protocol.

This paper aims to enhance the application of slide attack which is one of the most well-known cryptanalysis methods using self-similarity of a block cipher. The typical countermeasure against slide cryptanalysis is to use round-dependent constants. We present a new probabilistic technique and show how to overcome round-dependent constants in a slide attack against a block cipher based on the general Even-Mansour scheme with a single key. Our technique can potentially break more rounds than any previously known cryptanalysis for a specific class of block ciphers. We show employing round constants is not always sufficient to provide security against slide variant cryptanalysis, but also the relation between the round constants should be taken into account. To demonstrate the impact of our model we provide analysis of two round-reduced block ciphers LED-64 and Zorro, presented in CHES 2011 and CHES 2013, respectively. As a first application we recover the key for 16 rounds of Zorro. This result improves the best cryptanalysis presented by the designers which could be applied upto 12 rounds of its 24 rounds. In the case of LED-64 the cryptanalysis leads to the best results on 2-step reduced LED-64 in the known-plaintext model.

In this paper, we present advanced meet-in-the-middle (MITM) attacks against the lightweight block cipher LED-64, improving the best known attacks on several step-reduced variants of the cipher in both single-key and related-key models. In particular, we present a known-plaintext attack on 2-step LED-64 with complexity of

$$2^{48}$$

and a related-key attack on 3-step LED-64 with complexity of

$$2^{49}$$

. In both cases, the previously known attacks have complexity of

$$2^{60}$$

, i.e., only 16 times faster than exhaustive key search.

While our attacks are applied to the specific scheme of LED-64, they contain several general methodological contributions: First, we present the

linear key sieve

technique, which allows to exploit linear dependencies between key bits to obtain filtering conditions in MITM attacks on block ciphers. While similar ideas have been previously used in the domain of hash functions, this is the first time that such a technique is applied in block cipher cryptanalysis. As a second contribution, we demonstrate for the first time that a

splice-and-cut

attack (which so far seemed to be an inherently chosen-plaintext technique) can be used in the known-plaintext model, with data complexity which is significantly below the code-book size. Finally, we extend the differential MITM attack on AES-based designs, and apply it independently in two stages from both sides of the cipher, while using the linear key sieve and other enhancements.

Block ciphers are arguably the most widely used type of cryptographic primitives. We are not able to assess the security of a block cipher as such, but only its security against known attacks. The two main classes of attacks are linear and differential attacks and their variants. While a fundamental link between differential and linear cryptanalysis was already given in 1994 by Chabaud and Vaudenay, these attacks have been studied independently. Only recently, in 2013, Blondeau and Nyberg used the link to compute the probability of a differential given the correlations of many linear approximations. On the cryptanalytical side, differential and linear attacks have been applied on different parts of the cipher and then combined to one distinguisher over the cipher. This method is known since 1994 when Langford and Hellman presented the first differential-linear cryptanalysis of the DES. In this paper we take the natural step and apply the theoretical link between linear and differential cryptanalysis to differential-linear cryptanalysis to develop a concise theory of this method. We give an exact expression of the bias of a differential-linear approximation in a closed form under the sole assumption that the two parts of the cipher are independent. We also show how, under a clear assumption, to approximate the bias efficiently, and perform experiments on it. In this sense, by stating minimal assumptions, we hereby complement and unify the previous approaches proposed by Biham et al. in 2002-2003, Liu et al. in 2009, and Lu in 2012, to the study of the method of differential-linear cryptanalysis.

In 2013, Borghoff

et al

. introduced a slender-set linear cryptanalysis on PRESENT-like ciphers with key-dependent secret S-boxes. In this paper, we propose an improved slender-set linear attack to PRESENT-like ciphers with secret S-boxes. We investigate three new cryptanalytic techniques, and use them to recover the secret S-boxes efficiently. Our first new idea is that we propose a new technique to support consistency of partitions of the input to the secret S-boxes. Our second new technique is that we present a more efficient method to recover the coordinate functions of secret S-boxes based on more information than that of Borghoff’s attack. The third new technique is that we propose a method of constructing all correct coordinate function of secret S-boxes by pruning search algorithm. In particular, we implemented a successful linear attack on the full round Maya in practice. In our experiments, the correct S-box can be recovered with

$$2^{36}$$

known plaintexts,

$$2^{18.9}$$

time complexity and negligible memory complexity at a success rate of 87.5 % based on 200 independent trials. Our attack is the improvement and sequel of Borghoff’s work on PRESENT-like cipher with secret S-boxes.

Due to the recent emergence of resource-constrained devices, cryptographers are facing the problem of designing dedicated lightweight ciphers. KLEIN is one of the resulting primitives, proposed at RFIDSec in 2011 by Gong et al. This family of software-oriented block ciphers has an innovative structure, as it combines 4-bit Sboxes with the AES MixColumn transformation, and has woken up the attention of cryptanalysts. Several security analyses have been published, in particular on the 64-bit key version. The best of these results could attack up to 10 rounds out of the total number of 12. In this paper we propose a new family of attacks that can cryptanalyze for the first time all the 12 rounds of the complete version of KLEIN-64. Our attacks use truncated differential paths and are based both on some of the notions developed in previous attacks and on our new ideas that allow to considerably improve the performance. To prove the validity of our attacks, we have implemented reduced-round versions of them. In particular we were able to reproduce a practical attack that recovers the whole key on 10 rounds, which also corresponds to the best practical attack against KLEIN-64.

In this work, we present practical semi-free-start collisions for SHA-512 on up to 38 (out of 80) steps with complexity

$$2^{40.5}$$

. The best previously published result was on 24 steps. The attack is based on extending local collisions as proposed by Mendel et al. in their Eurocrypt 2013 attack on SHA-256. However, for SHA-512, the search space is too large for direct application of these techniques. We achieve our result by improving the branching heuristic of the guess-and-determine approach to find differential characteristics and conforming message pairs. Experiments show that for smaller problems like 27 steps of SHA-512, the heuristic can also speed up the collision search by a factor of

$$2^{20}$$

.

Let

$$d \ge 1$$

be an integer and

$$R_1$$

be a finite ring whose elements are called

block

. A

$$d$$

-block universal hash over

$$R_1$$

is a vector of

$$d$$

multivariate polynomials in message and key block such that the maximum

differential probability

of the hash function is “low”. Two such single block hashes are pseudo dot-product (

PDP

) hash and Bernstein-Rabin-Winograd (

BRW

) hash which require

$$\frac{n}{2}$$

multiplications for

$$n$$

message blocks. The Toeplitz construction and

$$d$$

independent invocations of

PDP

are

$$d$$

-block hash outputs which require

$$d \times \frac{n}{2}$$

multiplications. However, here we show that

at least

$$(d-1) + \frac{n}{2}$$

multiplications are necessary

to compute a universal hash over

$$n$$

message blocks. We construct a

$$d$$

-

block universal hash, called

EHC

, which requires the matching

$$(d -1) + \frac{n}{2}$$

multiplications for

$$d \le 4$$

. Hence it is optimum and our lower bound is tight when

$$d \le 4$$

. It has similar parllelizibility, key size like Toeplitz and so it can be used as a light-weight universal hash.

In this article, we describe a novel collision attack for up to 5 rounds of the

Grøstl

hash function. This significantly improves upon the best previously published results on 3 rounds. By using a new type of differential trail spanning over more than one message block we are able to construct collisions for

Grøstl

-256 on 4 and 5 rounds with complexity of

$$2^{67}$$

and

$$2^{120}$$

, respectively. Both attacks need

$$2^{64}$$

memory. Due to the generic nature of our attack we can even construct meaningful collisions in the chosen-prefix setting with the same attack complexity.

This paper presents differential attacks on

Simon

and

Speck

, two families of lightweight block ciphers that were presented by the U.S. National Security Agency in June 2013. We describe attacks on up to slightly more than half the number of rounds. While our analysis is only of academic interest, it demonstrates the drawback of the intensive optimizations in

Simon

and

Speck

.

In this paper we continue the previous line of research on the analysis of the differential properties of the lightweight block ciphers

Simon

and

Speck

. We apply a recently proposed technique for automatic search for differential trails in ARX ciphers and improve the trails in

Simon32

and

Simon48

previously reported as best. We further extend the search technique for the case of differentials and improve the best previously reported differentials on

Simon32

,

Simon48

and

Simon64

by exploiting more effectively the strong differential effect of the cipher. We also present improved trails and differentials on

Speck32

,

Speck48

and

Speck64

. Using these new results we improve the currently best known attacks on several versions of

Simon

and

Speck

. A second major contribution of the paper is a graph based algorithm (linear time) for the computation of the exact differential probability of the main building block of

Simon

: an AND operation preceded by two bitwise shift operations. This gives us a better insight into the differential property of the

Simon

round function and differential effect in the cipher. Our algorithm is general and works for any rotation constants. The presented techniques are generic and are therefore applicable to a broader class of ARX designs.

A main contribution of this paper is an improved analysis against

HMAC

instantiating with reduced

Whirlpool

. It recovers equivalent keys, which are often denoted as

$$K_{in}$$

and

$$K_{out}$$

, of

HMAC

with 7-round

Whirlpool

, while the previous best attack can work only for 6 rounds. Our approach is applying the meet-in-the-middle (MITM) attack on

AES

to recover

MAC

keys of

Whirlpool

. Several techniques are proposed to bypass different attack scenarios between a block cipher and a

MAC

,

e.g.,

the chosen plaintext model of the MITM attacks on

AES

cannot be used for

HMAC

-

Whirlpool

. Besides, a larger state size and different key schedule designs of

Whirlpool

leave us a lot of room to study. As a result, equivalent keys of

HMAC

with 7-round

Whirlpool

are recovered with a complexity of

$$(\mathrm {Data},\mathrm {Time},\mathrm {Memory})=(2^{481.7},2^{482.3},2^{481})$$

.

PRINCE is a lightweight block cipher proposed by Borghoff

et al.

at Asiacrypt 2012. Due to its originality, novel design and low number of rounds, it has already attracted the attention of a large number of cryptanalysts. Several results on reduced versions have been published to date; the best one is an attack on

$$8$$

rounds out of the total number of

$$12$$

. In this paper we improve this result by two rounds: we provide an attack on

$$10$$

rounds of the cipher with a data complexity of

$$2^{57.94}$$

and a time complexity of

$$2^{60.62}$$

, corresponding to

$$118.56$$

security bits, instead of

$$126$$

for the generic attacks. Our attack uses multiple differentials and exploits some properties of PRINCE for recovering the whole key. PRINCE is defined as a member of a family of ciphers, differing by the choice of an Sbox among a distinguished set. We also show that the security offered by all the members of the family is not equivalent, by identifying an Sbox for which our attack can be extended up to

$$11$$

rounds with a data complexity of

$$2^{59.81}$$

and a time complexity of

$$2^{62.43}$$

.

We study the problem of efficient (sub-linear) fuzzy search on encrypted outsourced data, in the symmetric-key setting. In particular, a user who stores encrypted data on a remote untrusted server forms queries that enable the server to efficiently locate the records containing the requested keywords, even though the user may misspell keywords or provide noisy data in the query. We define an appropriate primitive, for a general

closeness

function on the message space, that we call

efficiently fuzzy-searchable encryption

(

EFSE

). Next we identify an optimal security notion for EFSE. We demonstrate that existing schemes do not meet our security definition and propose a new scheme that we prove secure under basic assumptions. Unfortunately, the scheme requires large ciphertext length, but we show that, in a sense, this space-inefficiency is unavoidable for a general, optimally-secure scheme. Seeking the right balance between efficiency and security, we then show how to construct schemes that are more efficient and satisfy a weaker security notion that we propose. To illustrate, we present and analyze a more space-efficient scheme for supporting fuzzy search on biometric data that achieves the weaker notion.