International Association
for Cryptologic Research

In this short note, we analyze the security of the quadratic zero-testing procedure for the GGH13 graded encoding scheme, which was recently proposed by Gentry, Halevi and Lepoint. We show that this modification fails to immunize the GGH13 construction against zeroizing attacks, and that the modified scheme is susceptible to the same attacks as the original one.

Masking schemes based on tables recomputation are classical countermeasures against high-order side-channel attacks.

Still, they are known to be attackable at order $d$ in the case the masking involves $d$ shares.

In this work, we mathematically show that an attack of order strictly greater than $d$ can be more successful than an attack at order $d$.

To do so, we leverage the idea presented by Tunstall, Whitnall and Oswald at FSE 2013:

we exhibit attacks which exploit the multiple leakages linked to one mask during the recomputation of tables.

Specifically, regarding first-order table recomputation, improved by a shuffled execution, we show that there is a window of opportunity, in terms of noise variance, where a novel highly multivariate third-order attack is more efficient than a classical bivariate second-order attack.

Moreover, we show on the example of the high-order secure table computation presented by Coron at EUROCRYPT 2014 that the window of opportunity enlarges linearly with the security order $d$.

Witness encryption (WE) is an exciting new primitive introduced by Garg et al. (STOC 2013). WE is defined for some NP language $L$ and allows to encrypt a message relative to an instance $x$ so that one can decrypt with any $w$ witnessing $x \\in L$. Garg et al. construct WE for one NP-complete language from multilinear maps and give another construction from indistinguishability obfuscation (FOCS 2013). Due to the reliance on such heavy tools, WE can currently hardly be implemented on powerful hardware and will not be realizable on constrained devices like smart cards any time soon.

In this paper we construct a witness encryption scheme where \\emph{encryption} is a single Naor-Yung encryption (two CPA-encryptions and one NIZK proof showing the ciphertexts encrypt the same message), so encryption can even be done on a smart card. To achieve this, our scheme has a setup phase, which outputs public parameters containing an obfuscated circuit (only required for decryption), two public keys for a standard public-key encryption scheme and a common reference string for the NIZK (used for encryption). This setup phase need only be run once, and the parameters can be used for arbitrary many encryptions. Our scheme can easily be turned into a \\emph{functional} WE scheme, where a message is encrypted w.r.t. a statement and a function $f$, and using a witness $w$ one learns $f(m,w)$.

Our construction and its proof are inspired by those of functional encryption by Garg et al. (FOCS 2013) and to prove (selective) security of our scheme we also assume indistinguishability obfuscation and statistically simulation-sound NIZK. We give a construction of the latter in bilinear groups and combining it with ElGamal encryption, our ciphertexts are of size 1.3 kB at a 128-bit security level.

In 2011, B.B.Brumley and N.Tuveri found a remote timing attack on OpenSSL\'s ECDSA implementation for binary curves. We will study if the title of their paper was indeed relevant (Remote Timing Attacks are Still Practical). We improved on their lattice attack using the Embedding Strategy that reduces the Closest Vector Problem to the Shortest Vector Problem so as to avoid using Babai\'s procedures to solve the CVP and rely on the better experimental results of LLL. We will detail (along with publishing the source code of the tools we used) our attempts to reproduce their experiments from a remote machine located on the same network with the server, and see that such attacks are not trivial and far from being practical. Finally we will see other attacks and countermeasures.

Khudra is a 18-round lightweight block cipher proposed by Souvik Kolay and Debdeep Mukhopadhyay in the SPACE 2014 conference which is applicable to Field Programmable Gate Arrays (FPGAs). In this paper, we obtain $2^{16}$ 14-round related-key impossible differentials of Khudra, and based on these related-key impossible differentials for 32 related keys, we launch an attack on the full Khudra with data complexity of $2^{63}$ related-key chosen-plaintexts, time complexity of about $2^{68.46}$ encryptions and memory complexity of $2^{64}$.

The energy cost of asymmetric cryptography is a vital component of modern secure communications, which inhibits its wide spread adoption within the ultra-low energy regimes such as Implantable Medical Devices (IMDs) and Radio Frequency Identification (RFID) tags. The ciphertext-policy attribute-based encryption (CP-ABE) is a promising cryptographic tool, where an encryptor can decide the access policy that who can decrypt the data. Thus, the data will be protected from the unauthorized users. However, most of the existing CP-ABE schemes

require huge storage and computational overheads. Moreover, CP-ABE schemes based on bilinear map loose the high efficiency over the elliptic curve cryptography because of the requirement of the security parameters of larger size. These drawbacks prevent the use of ultra-low energy devices in practice. In this paper, we aim to propose a novel expressive AND-gate access structured CP-ABE scheme with constant-size secret keys (CSSK) with the cost efficient solutions for the encryption and decryption using ECC, called the CP-ABE-CSSK scheme. In the proposed CP-ABE-CSSK, the size of secret key is as small as 320 bits. In addition, ECC is efficient and more

suitable for the lightweight devices as compared to the bilinear pairing based cryptosystem. Thus, the proposed CP-ABE-CSSK scheme provides the low computation and storage overheads with an expressive AND-gate access structure as compared to the related existing schemes in the literature. As a result, our scheme is very suitable for CP-ABE key storage and computation cost in the ultra-low energy devices.

Self-blindable credential schemes allow users to anonymously prove ownership of credentials. This is achieved by randomizing the credential before each showing in such a way that it still remains valid. As a result, each time a different version of the same credential is presented. A number of such schemes have been proposed, but unfortunately many of them are broken, in the sense that they are linkable (i.e., failing to protect the privacy of the user), or malleable (i.e., they allow users to create new credentials using one or more valid credentials given to them). In this paper we prove a general theorem that relates linkability and malleability in self-blindable credential schemes, and that can test whether a scheme is linkable or malleable. After that we apply the theorem to a number of self-blindable credential schemes to show that they suffer from one or both of these issues.

Sanitizable signatures, introduced by Ateniese et al. at ESORICS\'05, allow to issue a signature on a message where certain predefined message blocks may later be changed (sanitized) by some dedicated party (the sanitizer) without invalidating the original signature. With sanitizable signatures, replacements for modifiable (admissible) message blocks can be chosen arbitrarily by the sanitizer. However, in various scenarios this makes sanitizers too powerful. To reduce the sanitizers power, Klonowski and Lauks at ICISC\'06 proposed (among others) an extension that enables the signer to limit the allowed modifications per admissible block to a well defined set each. At CT-RSA\'10 Canard and Jambert then extended the formal model of Brzuska et al. from PKC\'09 to additionally include the aforementioned and other extensions. We, however, observe that the privacy guarantees of their model do not capture privacy in the sense of the original definition of sanitizable signatures. That is, if a scheme is private in this model it is not guaranteed that the sets of allowed modifications remain concealed. To this end, we review a stronger notion of privacy, i.e., (strong) unlinkability (defined by Brzuska et al. at EuroPKI\'13), in this context. While unlinkability fixes this problem, no efficient unlinkable scheme supporting the aforementioned extensions exists and it seems to be hard to construct such schemes. As a remedy, in this paper, we propose a notion stronger than privacy, but weaker than unlinkability, which captures privacy in the original sense. Moreover, it allows to easily construct efficient schemes satisfying our notion from secure existing schemes in a black-box fashion.

We give a theoretical description of a new homomorphic encryption scheme DA-Encrypt that is based on (non-archimedean) Diophantine Approximation.

We are looking for research scientists with expertise on cyber-physical security. The candidates should have PhD in infocomm security with track record of strong R&D capability (at least 2 publications at top security conferences - http://icsd.i2r.a-star.edu.sg/staff/jianying/conference-ranking-history.html, in the past 3 years), be able to perform deep system-level investigations of security mechanisms, be a good team player and have the potential to be a team leader, and also have good presentation and communication skills. The candidates are expected to work closely with industry partners, create valuable intellectual properties, and produce project deliverables in time.

Interested candidates please send CV to Jianying Zhou. Fresh PhD is welcome to apply. Review of applications will begin immediately and will continue until the positions are filled. Only short-listed candidates will be contacted for interview.

In this paper, we extend the method of Scott and Barreto and present an explicit and simple algorithm to generate families of generalized MNT elliptic curves. Our algorithm allows us to obtain all families of generalized MNT curves with any given cofactor. Then, we analyze the complex multiplication equations of these families of curves and transform them into generalized Pell equation. As an example, we describe a way to generate Edwards curves with embedding degree 6, that is, elliptic curves having cofactor h = 4.

Broadcasting is a very efficient way to securely transmit information to a large set of geographically scattered receivers, and in practice, it is often the case that these receivers can be grouped in sets sharing common characteristics (or attributes). We describe in this paper an efficient ciphertext-policy attribute-based broadcast encryption scheme (CP-ABBE) supporting negative attributes and able to handle access policies in conjunctive normal form (CNF). Essentially, our scheme is a combination of the Boneh-Gentry-Waters broadcast encryption and of the Lewko-Sahai-Waters revocation schemes; the former is used to express attribute-based access policies while the latter is dedicated to the revocation of individual receivers. Our scheme is the first one that involves a public key and private keys having a size that is independent of the number of receivers registered in the system. Its selective security is proven with respect to the Generalized Diffie-Hellman Exponent (GDHE) problem on bilinear groups.

This paper uses an Instruction Set Architecture (ISA) based statistical energy model of an ARM Cortex-M4 microprocessor to evaluate the energy consumption of an implementation of AES with different side channel attack (SCA) countermeasures and an implementation of lightweight ciphers PRESENT, KLEIN and ZORRO with and without Boolean first order masking. In this way, we assess the additional energy consumption of using different SCA countermeasures and using lightweight block ciphers on 32 bit embedded devices. In addition to this, we provide a methodology for developing an ISA based energy model for cryptographic software with an accuracy of $\\pm5\\%$. In addition to providing our methodology for developing this model, we also show that using variations of instructions that reduce the size of code can reduce the energy consumption by as much as $30\\%-40\\%$ and that memory instructions reduce the predictability of our energy model.

After four decades of public key cryptography, both the industry and academia seek better solutions for the public key infrastructure. A recent proposal, the certificate transparency concept, tries to enable untrusted servers act as public key servers, such that any key owner can verify that her key is kept properly at those servers. Unfortunately, due to high computation and communication requirements, existing certificate transparency proposals fail to address the problem as a whole.

We propose a new efficient key authentication service (KAS). It uses server-side gossiping as the source of trust, and assumes servers are not all colluding. KAS stores all keys of each user in a separate hash chain, and always shares the last ring of the chain among the servers, ensuring the users that all servers provide the same view about them (i.e., no equivocation takes place). Storing users\' keys separately reduces the server and client computation and communication dramatically, making our KAS a very efficient way of public key authentication. The KAS handles a key registration/change operation in O(1) time using only O(1) proof size; independent of the number of users. While the previous best proposal, CONIKS, requires the client to download 100 KB of proof per day, our proposal needs less than 1 KB of proof per key lifetime, while obtaining the same probabilistic guarantees as CONIKS.

Authentication based on cryptographic protocols is a key technology for recent security systems. However, the so-called relay attack where a malicious attacker tries to assume the role of the prover, is known to be a serious threat even for the cryptographically-secure authentication systems. This paper proposes a new authentication method that utilizes the side channel that already exists in many authentication systems. The side channel has been studied intensively from the attacker viewpoint, and it is best known for the key-recovery attack against cryptographic implementations via physical information. Here, reversing our way of thinking, we propose to use the information constructively via the side channel to enhance the existing cryptographic protocols. Using symmetric-key-based authentication as an example, we show based on experiments using an FPGA that each of the side-channel information leaked from provers is unique enough for the purpose of authentication.

From September 11 to September 11
Location: Paris, France
More Information: https://www.cryptoexperts.com/wise2015/

The candidate construction of multilinear maps by Garg, Gentry, and Halevi (Eurocrypt 2013) has lead to an explosion of new cryptographic constructions ranging from attribute-based encryption (ABE) for arbitrary polynomial size circuits, to program obfuscation, and to constrained pseudorandom functions (PRFs). Many of these constructions require k-linear maps for large k. In this work, we focus on the reduction of k in certain constructions of access control primitives that are based on k-linear maps; in particular, we consider the case of constrained PRFs and ABE. We construct the following objects:

- A constrained PRF for arbitrary circuit predicates based on (n+l_{OR}-1)-linear maps (where n is the input length and l_{OR} denotes the OR-depth of the circuit).

- For circuits with a specific structure, we also show how to construct such PRFs based on (n+l_{AND}-1)-linear maps (where l_{AND} denotes the AND-depth of the circuit).

- We then give a black-box construction of a constrained PRF for NC1 predicates, from any bit-fixing constrained PRF that fixes only one of the input bits to 1; we only require that the bit-fixing PRF have certain key homomorphic properties. This gives us a constrained PRF for NC1 predicates that is based only on n-linear maps, with no dependence on the predicate.

In contrast, the previous constructions of constrained PRFs (Boneh and Waters, Asiacrypt 2013) required (n+l+1)-linear maps for circuit predicates (where l is the total depth of the circuit) and n-linear maps even for bit-fixing predicates.

- We also show how to extend our techniques to obtain a similar improvement in the case of ABE and construct ABE for arbitrary circuits based on (l_{OR}+1)-linear (respectively (l_{AND}+1)-linear) maps.

We give a simple and efficient construction of unique signature on groups equipped with bilinear map. In contrast to prior works, our proof of security is based on \\textit{computational Diffie-Hellman} problem in the random oracle model. Meanwhile, the resulting signature consists of only one group element. Due to its simplicity, security and efficiency, our scheme is suitable for those situations that require to overcome communication bottlenecks. Moreover, the unique signature is a building block for designing chosen-ciphertext secure cryptosystems and verifiable random functions, which have found many interesting applications in cryptographic protocol design.

The challenges faced in securing embedded computing systems against multifaceted memory safety vulnerabilities have prompted great interest in the development of memory safety countermeasures. These countermeasures either provide protection only against their corresponding type of vulnerabilities, or incur substantial architectural modifications and overheads in order to provide complete safety, which makes them infeasible for embedded systems. In this paper, we propose M-MAP: a comprehensive system based on multi-factor memory authentication for complete memory safety, inspired by everyday user authentication factors. We examine certain crucial theoretical and practical implications of composing memory integrity verification and bounds checking protection schemes in a comprehensive system. Based on these implications, we implement M-MAP with hardware based memory integrity verification and software based bounds checking to achieve a balance between hardware modifications and performance. We demonstrate that M-MAP implemented on top of a lightweight out-of-order processor delivers complete memory safety with only $32\\%$ performance overhead on average, and incurs minimal hardware modifications and area overhead.

We introduce the notion of asymmetric programmable hash functions

(APHFs, for short), which adapts Programmable Hash Functions,

introduced by Hofheinz and Kiltz at Crypto 2008, with two main

differences. First, an APHF works over bilinear groups, and it

is asymmetric in the sense that, while only {\\em secretly} computable,

it admits an isomorphic copy which is publicly computable.

Second, in addition to the usual programmability, APHFs may have an

alternative property that we call {\\em programmable pseudorandomness}.

In a nutshell, this property states that it is possible to embed a

pseudorandom value as part of the function\'s output, akin to a random

oracle.

In spite of the apparent limitation of being only secretly

computable, APHFs turn out to be surprisingly powerful objects. We

show that they can be used to generically implement both regular and

linearly-homomorphic signature schemes in a simple and elegant way.

More importantly, when instantiating these generic constructions with

our concrete realizations of APHFs, we obtain:

(1) the {\\em first} linearly-homomorphic signature (in the standard

model) whose public key is {\\em sub-linear} in both the dataset size

and the dimension of the signed vectors;

(2) short signatures (in the standard model) whose public key is shorter

than those by Hofheinz-Jager-Kiltz from Asiacrypt 2011, and essentially

the same as those by Yamada, Hannoka, Kunihiro, (CT-RSA 2012).