International Association
for Cryptologic Research

Recent literature has demonstrated that the security of Physically Unclonable Function (PUF) circuits might be adversely affected by the introduction of faults. In this paper, we propose novel and efficient architectures for a variety of widely used delay-based PUFs which are robust against high precision laser fault attacks proposed by Tajik et al. in FDTC-2015. The proposed architectures can be used to detect run-time modifications in the PUF design due to fault injection. In addition, we propose fault recovery techniques based on either logical reconfiguration or dynamic partial reconfiguration of the PUF design. We validate the robustness of our proposed fault tolerant delay-based PUF designs on Xilinx Artix-7 FPGA platform.

In a functional encryption scheme, secret keys are associated with functions and ciphertexts are associated with messages. Given a secret key for a function f and a ciphertext for a message x, a decryptor learns f(x) and nothing else about x. Inner product encryption is a special case of functional encryption where both secret keys and ciphertexts are associated with vectors. The combination of a secret key for a vector x and a ciphertext for a vector y reveal <x,y> and nothing more about y. An inner product encryption scheme is function-hiding if the keys and ciphertexts reveal no additional information about both x and ybeyond their inner product.

Recently, Bishop, Jain, and Kowalczyk (Asiacrypt 2015) and Datta, Dutta, and Mukhopadhyay (PKC 2016) showed how to construct function-hiding inner product encryption using asymmetric bilinear maps with security in the standard model. In this work, we reduce the parameter sizes and the run-time complexity of the Asiacrypt 2015 and the PKC 2016 constructions by more than a factor of 2 and 4, respectively. We achieve this efficiency by proving security in the generic group model. We then show how function-hiding inner product encryption directly yields single-key two-input functional encryption for general functions over a small message space, which greatly improves upon the parameter sizes of existing constructions from standard assumptions. We validate the practicality of our encryption scheme by implementing both function-hiding inner product encryption and single-key two-input functional encryption. For example, using our construction, encryption and decryption operations for vectors of length 50 complete in a tenth of a second in a standard desktop environment.

Most applicable lattice reduction algorithms used in practice are BKZ (Block-Korkine-Zolotarev) type algorithms as the blockwise generalizations of the LLL algorithm (Lenstra-Lenstra-Lovasz). Its original version was proposed by Schnorr and Euchner in 1991. The quality of reduced lattice bases is measured by the Hermitian factor $\frac{||{\bf b}_1||}{vol({\bf L})^{1/d}}$ and the $d$-th root of this factor which is called root Hermitian factor. In Asiacrypt 2011 paper Y. Chen and Phong Q. Nguyen used BKZ with extreme pruning enumeration subroutine to handle the large block size lattice reduction with the purpose that the better root Hermitian factors can be expected. This BKZ 2.0 algorithm has been served as a base stone for the security evaluation of recent lattice-based cryptosystems such as fully homomorphic encryption and cryptographic multilinear mappings. In this paper we propose a measure version of Gaussian heuristic. This is a strict mathematical proven theorem. It can be used to give a strict mathematical proof for conjectured or simulated root Hermitian factors in BKZ 2.0 type algorithms and BKZ or slide reduction with large block-sizes. The theoretical analysis of these heuristic assumptions in the simulator of BKZ 2.0 type algorithms are also given.

Modern remote electronic voting systems, such as the prominent Helios system, are designed to provide vote privacy and verifiability, where, roughly speaking, the latter means that voters can make sure that their votes were actually counted. In this paper, we propose a new practical voting system called sElect (secure/simple elections). This system, which we implemented as a platform independent web-based application, is meant for low-risk elections and is designed to be particularly simple and lightweight in terms of its structure, the cryptography it uses, and the user experience. One of the unique features of sElect is that it supports fully automated verification, which does not require any user interaction and is triggered as soon as a voter looks at the election result. Despite its simplicity, we prove that this system provides a good level of privacy, verifiability, and accountability for low-risk elections.

In this note we re-evaluate the Eurocrypt'16 paper by Zhang et al. in the area of LPN solving algorithms. We present the history of LPN solving algorithms and give the general description of the algorithm. While this new algorithm claims to improve all the previous results, we have discovered issues in its analysis. We review inconsistencies in complexity estimates and a misconception of some new reduction algorithm. What we show is that the results of Eurocrypt'16 do not provide better performance compared with the results from Asiacrypt'14.

NORX is a second round candidate of the ongoing CAESAR competition for authenticated encryption. It is a nonce based authenticated encryption scheme based on the sponge construction. Its two variants denoted by NORX32 and NORX64 provide a security level of 128 and 256 bits, respectively. In this paper, we present a state/key recovery attack for both variants with the number of rounds of the core permutation reduced to 2 (out of 4) rounds. The time complexity of the attack for NORX32 and NORX64 is $2^{119}$ and $2^{234}$ respectively, while the data complexity is negligible. Furthermore, we show a state recovery attack against NORX in the parallel mode using an internal differential attack for 2 rounds of the permutation. The data, time and memory complexities of the attack for NORX32 are $2^{7.3}$, $2^{124.3}$ and $2^{115}$ respectively and for NORX64 are $2^{6.2}$, $2^{232.8}$ and $2^{225}$ respectively. Finally, we present a practical distinguisher for the keystream of NORX64 based on two rounds of the permutation in the parallel mode using an internal differential-linear attack. To the best of our knowledge, our results are the best known results for NORX in nonce respecting manner.

Authenticated Key Exchange (AKE) is the backbone of internet security protocols such as TLS and IKE. A recent announcement by standardization bodies calling for a shift to quantum-resilient crypto has resulted in several AKE proposals from the research community. Because AKE can be generically constructed by combining a digital signature scheme with public key encryption (or a KEM), most of these proposals focused on optimizing the known KEMs and left the authentication part to the generic combination with digital signatures.\\

In this paper, we show that by simultaneously considering the secrecy and authenticity requirements of an AKE, we can construct a scheme that is more secure and with smaller communication complexity than a scheme created by a generic combination of a KEM with a signature scheme. Our improvement uses particular properties of lattice-based encryption and signature schemes and consists of two parts -- the first part increases security, whereas the second reduces communication complexity. \\

We first observe that parameters for lattice-based encryption schemes are always set so as to avoid decryption errors, since many observations by the adversary of such failures usually leads to him recovering the secret key. But since one of the requirements of an AKE is that it be forward-secure, the public key must change every time. The intuition is therefore that one can set the parameters of the scheme so as to not care about decryption errors and everything should still remain secure. We show that this naive solution is not quite correct, but the intuition can be made to work by a small change in the scheme. Our new AKE, which now remains secure in case of decryption errors, fails to create a shared key with probability around $2^{-30}$, but adds enough security that we are able to instantiate a KEM based on the NTRU assumption with rings of smaller dimension. \\

Our second improvement is showing that certain hash-and-sign lattice signatures can be used in ``message-recovery'' mode. In this mode, the signature size is doubled but this longer signature is enough to recover an even longer message -- thus the signature is longer but the message does not need to be sent. This is advantageous when signing relatively long messages, such as the public keys and ciphertexts generated by a lattice-based KEM. We show how this technique reduces the communication complexity of the generic construction of our AKE by around $20\%$. Using a lattice-based signature in message-recovery mode is quite generic (i.e it does not depend on the structure of the message), and so it may be used in AKE constructions that use a different KEM, or even simply as a way to reduce the transmission length of a message and its digital signature.

In this work, we explore the possibilities for practical Threshold Implementation (TI) with only two shares in order for a smaller design that needs less randomness but is still first-order leakage resistant. We present the first two-share Threshold Implementations of two lightweight block ciphers---Simon and Present. The implementation results show that two-share TI gains in compactness while loses in throughput compared with three-share schemes. Moreover, the leakage analyses show that two-share TI retains perfect first-order resistance but is shadowed by a strong second-order leakage, making it less worthwhile.

Event date: 10 July to 17 July 2016
Submission deadline: 15 May 2016

The proceedings for Eurocrypt 2016 are now available via SpringerLink. Through our agreement with Springer, IACR members can access these proceedings for free by logging into this access page.

Event date: 25 August to 27 August 2016
Submission deadline: 4 June 2016
Notification: 3 July 2016

The successful candidates will join a strong and motivated research team lead by Prof. Alex Biryukov in order to carry out research towards a PhD on one of the following topic:

• Financial Cryptography (security of distributed ledgers, smart contracts, mobile payments)
• Privacy Enhancing Technology (Tor-like networks, privacy for blockchain, code obfuscation)
• Symmetric Cryptography (cryptanalysis and design, lightweight crypto protocols)

Closing date for applications: 1 June 2016

Contact: Prof. Alex Biryukov (e-mail: name dot family name (at) uni.lu)

More information: https://goo.gl/f0CGnb

We present an analysis of key wrapping APIs with generic policies. We prove that certain minimal conditions on policies are sufficient for keys to be indistinguishable from random in any execution of an API.

Our result captures a large class of API policies, including both the hierarchies on keys that are common in the scientific literature and the non-linear dependencies on keys used in PKCS#11. Indeed, we use our result to propose a secure refinement of PKCS#11, assuming that the attributes of keys are transmitted as authenticated associated data when wrapping and that there is an enforced separation between keys used for wrapping and keys used for other cryptographic purposes.

We use the Computationally Complete Symbolic Attacker developed by Bana and Comon. This model enables us to obtain computational guarantees using a simple proof with a high degree of modularity.

Functional encryption is a new paradigm of public-key encryption that allows a user to compute $f(x)$ on encrypted data $CT(x)$ with a private key $SK_f$ to finely control the revealed information. Multi-input functional encryption is an important extension of (single-input) functional encryption that allows the computation $f(x_1, \ldots, x_n)$ on multiple ciphertexts $CT(x_1), \ldots, CT(x_n)$ with a private key $SK_f$. Although multi-input functional encryption has many interesting applications like running SQL queries on encrypted database and computation on encrypted stream, current candidates are not yet practical since many of them are built on indistinguishability obfuscation. To solve this unsatisfactory situation, we show that practical two-input functional encryption schemes for inner products can be built based on bilinear maps.

In this paper, we first propose a two-input functional encryption scheme for inner products in composite-order bilinear groups and prove its selective IND-security under simple assumptions. Next, we propose a two-client functional encryption scheme for inner products where each ciphertext can be associated with a time period and prove its selective IND-security. Furthermore, we show that our two-input functional encryption schemes in composite-order bilinear groups can be converted into schemes in prime-order asymmetric bilinear groups by using the asymmetric property of asymmetric bilinear groups.

The Helios voting scheme is well studied including formal proofs for veriability and ballot privacy, but it does not provide participation privacy (i.e. it reveals who participated in the election). Kulyk, Teague and Volkamer proposed an extension to Helios that is claimed to provide ballot privacy as well as participation privacy while providing stronger veriability than Helios. However, the authors did not prove their claims. Our contribution is to provide a formal denition for participation privacy and to prove that their claims hold.

Homomorphic encryption scheme enables computation in the encrypted domain, which is of great importance because of its wide and growing range of applications. The main issue with the known fully (or partially) homomorphic encryption schemes is the high computational complexity and large communication cost required for their ex- ecution. In this work, we study symmetric partially homomorphic encryption schemes over nite elds, establishing relationships between homomorphisms over nite elds with q-ary functions. Our proposed partially homomorphic encryption schemes have perfect secrecy and resist cipher-only attacks to some extent.

We describe generalized running key ciphers and apply them for analysis of two Shannon's methods. In particular, we suggest some estimation of the cipher equivocation and the probability of correct deciphering without key.

The Lightweight Secure Physically Unclonable Function (LSPUF) was proposed as a secure composition of Arbiter PUFs with additional XOR based input and output networks. But later, researchers proposed a Machine Learning (ML) based modeling attack on $x$-XOR LSPUF, and they also empirically showed that pure ML based modeling is not computationally scalable if the parameter $x$ of $x$-XOR LSPUF is larger than nine. Besides this pure computational attack using only challenge-response pairs (CRPs), there are other proposals for modeling attacks on LSPUF using timing and power side-channel information, reliability information and photonic side-channel information of an LSPUF instance. % In this paper, we proposed another pure computational attack (i.e. without any side-channel information) on multibit output LSPUF variants using both cryptanalysis and ML techniques together. We, first, cryptanalyze the output network of LSPUF to reduce the computational efforts required by previously proposed pure ML based modeling of an $x$-XOR LSPUF. Specifically, we model an LSPUF instance, while its output bit is defined as $x$-XOR PUF, using the ML modeling of $y$-XOR PUF where $y<x$. From the computational complexity view point, our proposed modeling attack is efficient and scalable than previously proposed pure ML based modeling of LSPUFs with respect to both data and time complexities. We demonstrate the effectiveness of our proposed attack using the Matlab based simulation of LSPUFs and LSPUFs implemented on Xilinx Artix-7 Field Programmable Gate Arrays (FPGAs).

Social network analysis as a technique has been applied to diverse set of fields, including, organizational behaviour, sociology, economics and biology. However, for sensitive networks such as hate networks, trust networks and sexual networks, these techniques have been sparsely used. This is majorly attributed to the unavailability of network data. Anonymization is the most commonly used technique for performing privacy preserving network analysis. The process involves the presence of a trusted third party, who is aware of the complete network, and releases a sanitized version of it. In this paper, we propose an alternative, in which, the desired analysis can be performed by the parties who distributedly hold the network, such that : (a) no central third party is required; (b) the topology of the underlying network is kept hidden. We design multiparty protocols for securely performing various social network analysis methods. The network parameters addressed in this paper include degree distribution, clustering coefficient, closeness centrality, pagerank algorithm and K-shell decomposition algorithm. The designed protocols are secure in the malicious adversarial model with less than one third corrupt parties.

Over the last few years, data storage in cloud based services has been very popular due to easy management and monetary advantages of cloud computing. Recent developments showed that such data could be leaked due to various attacks. To address some of these attacks, encrypting sensitive data before sending to cloud emerged as an important protection mechanism. If the data is encrypted with traditional techniques, selective retrieval of encrypted data becomes challenging. To address this challenge, efficient searchable encryption schemes have been developed over the years. Almost all of the existing searchable encryption schemes are developed for keyword searches and require running some code on the cloud servers. However, many of the existing cloud storage services (e.g., Dropbox, Box, Google Drive, etc.) only allow simple data object retrieval and do not provide computational support needed to realize most of the searchable encryption schemes.

In this paper, we address the problem of efficient execution of complex search queries over wide range of encrypted data types (e.g., image files) without requiring customized computational support from the cloud servers. To this end, we provide an extensible framework for supporting complex search queries over encrypted multimedia data. Before any data is uploaded to the cloud, important features are extracted to support different query types (e.g., extracting facial features to support face recognition queries) and complex queries are converted to series of object retrieval tasks for cloud service. Our results show that this framework may support wide range of image retrieval queries on encrypted data with little overhead and without any change to underlying data storage services.