International Association for Cryptologic Research

IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2014-07-02
21:17 [Pub][ePrint]

Most lattice-based cryptographic schemes with a security proof suffer from large key sizes and heavy computations. This is also true for the simpler case of authentication protocols which are used on smart cards, as a very-constrained computing environment.

Recent progress on ideal lattices has significantly improved the efficiency, and made it possible to implement practical lattice-based cryptography on constrained devices. However, to the best of our knowledge, no previous attempts were made to implement lattice-based schemes on smart cards.

In this paper, we provide the results of our implementation of several state-of-the-art lattice-based authentication protocols on smart cards and a microcontroller widely used in smart cards. Our results show that only a few of the proposed lattice-based authentication protocols can be implemented using limited resources of such constrained devices, however, cutting-edge ones are suitably-efficient to be used practically on smart cards.

Moreover, we have implemented fast Fourier transform (FFT) and discrete Gaussian sampling with different typical parameters sets, as well as versatile lattice-based public-key encryptions. These results have noticeable points which help to design or optimize lattice-based schemes for constrained devices.

21:17 [Pub][ePrint]

The concept of social secret sharing (SSS) was introduced in 2010 by Nojoumian et al. [1,2]. In this scheme, the number of shares allocated to each party depends on the players reputation and the way he interacts with other parties. In other words, weights of the players are periodically adjusted such that cooperative participants receive more shares compared to non-cooperative parties. As our contribution, we propose an ideal social secret sharing (Ideal-SSS) in which the size of each player\'s share is equal to the size of the secret. This property will be achieved using hierarchical threshold secret sharing rather than weighted secret sharing. We show that the proposed scheme is secure in a passive adversary model. Compared to SSS, our proposed scheme is more efficient in terms of the share size, communication complexity and computational complexity of the \"sharing\" protocol. However, the \"social tuning\" and \"reconstruction\" protocols of SSS are computationally more efficient than those of the proposed scheme. Depending on the number of execution of social tuning protocol, this might be a reasonable compromise because the reconstruction protocol is executed only once throughout the secret\'s lifetime.

21:17 [Pub][ePrint]

Two parties, $P_1$ and $P_2$, wish to jointly compute some function $f(x,y)$ where $P_1$ only knows $x$, whereas $P_2$ only knows $y$. Furthermore, and most importantly, the parties wish to reveal only what the output suggests. Function $f$ is said to be computable with \\emph{complete fairness} if there exists a protocol computing $f$ such that whenever one of the parties obtains the correct output, then both of them do. The only protocol known to compute functions with complete fairness is the one of Gordon et al (STOC 2008). The functions in question are finite, Boolean, and the output is shared by both parties. The classification of such functions up to fairness may be a first step towards the classification of all functionalities up to fairness. Recently, Asharov (TCC 2014) identifies two families of functions that are computable with fairness using the protocol of Gordon et al and another family for which the protocol (potentially) falls short. Surprisingly, these families account for almost all finite Boolean functions. In this paper, we expand our understanding of what can be computed fairly with the protocol of Gordon et al. In particular, we fully describe which functions the protocol computes fairly and which it (potentially) does not. Furthermore, we present a new class of functions for which fair computation is outright impossible. Finally, we confirm and expand Asharov\'s observation regarding the fairness of finite Boolean functions: almost all functions $f:X\\times Y\\rightarrow \\{0,1\\}$ for which $|X|\\neq |Y|$ are fair, whereas almost all functions for which $|X|= |Y|$ are not.

21:17 [Pub][ePrint]

We revisit the context of leakage-tolerant interactive protocols as

defined by Bitanski, Canetti and Halevi (TCC 2012). Our contributions

can be summarized as follows:

\\begin{enumerate}

\\item

For the purpose of secure message transmission, any encryption

protocol with message space $\\cM$ and secret key space $\\cSK$

tolerating poly-logarithmic leakage on the secret state of the

receiver must satisfy $|\\cSK| \\ge (1-\\epsilon)|\\cM|$, for every $0 2014-07-01 16:01 [Job][New] The Cryptolux team of the Computer Science and Communications research unit of the University of Luxembourg is looking for a postdoc in Cryptography and Information Security. In particular we are interested in candidates who are experts in one of the following topics: • Symmetric Cryptography • Privacy and Anonymity (Tor,I2P, etc.) • Digital Currencies • Reverse engineering, code obfuscation • Network Security Interested candidates are invited to submit their application by email to lacs.application AT gmail.com. The application material should contain a cover letter explaining the candidate\\\'s expertise, motivation and research interests, a CV (including photo, information about the obtained degrees, overall GPA in B.Sc. and M.Sc., transcript of grades for relevant courses). We expect proven expertise in your area of research by publications at top conferences, successful participation in competitions and challenges, etc. 06:17 [Pub][ePrint] We discuss how to recover RSA secret keys from noisy analog data obtained through physical attacks such as cold boot and side channel attacks. Many studies have focused on recovering correct secret keys from noisy binary data. Obtaining noisy binary keys typically involves first observing the analog data and then obtaining the binary data through quantization process that discards much information pertaining to the correct keys. In this paper, we propose two algorithms for recovering correct secret keys from noisy analog data, which are generalized variants of Paterson et al.\'s algorithm. Our algorithms fully exploit the analog information. More precisely, consider observed data which follows the Gaussian distribution with mean$(-1)^b$and variance$\\sigma^2$for a secret key bit$b$. We propose a polynomial time algorithm based on the maximum likelihood approach and show that it can recover secret keys if$\\sigma < 1.767$. The first algorithm works only if the noise distribution is explicitly known. The second algorithm does not need to know the explicit form of the noise distribution. We implement the first algorithm and verify its effectiveness. 2014-06-30 18:17 [Pub][ePrint] A successful detection of the stealthy dopant-level circuit (trojan), proposed by Becker et al. at CHES 2013, is reported. Contrary to an assumption made by Becker et al., dopant types in active region are visible with either scanning electron microscopy (SEM) or focused ion beam (FIB) imaging. The successful measurement is explained by an LSI failure analysis technique called the passive voltage contrast. The experiments are conducted by measuring a dedicated chip. The chip uses the diffusion programmable device: an anti-reverse-engineering technique by the same principle as the stealthy dopant-level trojan. The chip is delayered down to the contact layer, and images are taken with (1) an optical microscope, (2) SEM, and (3) FIB. As a result, the four possible dopant-well combinations, namely (i) p+/n-well, (ii) p+/p-well, (iii) n+/n-well and (iv) n+/p-well are distinguishable in the SEM images. Partial but sufficient detection is also achieved with FIB. Although the stealthy dopant-level circuits are visible, however, they potentially make a detection harder. That is because the contact layer should be measured. We show that imaging the contact layer is at most 16-times expensive than that of a metal layer in terms of the number of images 18:17 [Pub][ePrint] In this paper, we address the problem of privacy preserving delegated word search in the cloud. We consider a scenario where a data owner outsources its data to a cloud server and delegates the search capabilities to a set of third party users. In the face of semi-honest cloud servers, the data owner does not want to disclose any information about the outsourced data; yet it still wants to benefit from the highly parallel cloud environment. In addition, the data owner wants to ensure that delegating the search functionality to third parties does not allow these third parties to jeopardize the confidentiality of the outsourced data, neither does it prevent the data owner from efficiently revoking the access of these authorized parties. To these ends, we propose a word search protocol that builds upon techniques of keyed hash functions, oblivious pseudo-random functions and Cuckoo hashing to construct a searchable index for the outsourced data, and uses private information retrieval of short information to guarantee that word search queries do not reveal any information about the data to the cloud server. Moreover, we combine attribute-based encryption and oblivious pseudo-random functions to achieve an efficient revocation of authorized third parties. The proposed scheme is suitable for the cloud as it can be easily parallelized. 18:17 [Pub][ePrint] In 2005, Hell, Johansson and Meier submitted a stream cipher proposal named Grain v1 to the estream call for stream cipher proposals and it also became one estream nalists in the hardware category. The output function of Grain v1 connects its 160 bits internal state divided equally between an LFSR and an NFSR, using a non-linear lter function in a complex way. Over the last years many cryptanalyst identied several weaknesses in Grain v1. As a result in 2011 the inventors modied Grain v1 and published a new version of Grain named Grain-128a which has a similar structure as Grain v1 but with a 256 bits internal state with an optional authentication is the latest version of Grain family resisting all known attacks on Grain v1. However both these ciphers are quite resistant against the classical algebraic attack due to the rapid growth of the degree of the key-stream equations in subsequent clockings caused by the NFSR. This paper presents a probabilistic algebraic attack on both these Grain versions. The basic idea of our attack is to develop separate probabilistic equations for the LFSR and the NFSR bits from each key-stream equations. Surprisingly it turns out that in case of Grain-128a our proposed equations hold with all most sure probability, which makes the sure retrieval of the LFSR bits. We also outline a technique to reduce the growth of degree of the equations involving the NFSR bits for Grain v1. Further we high light that the concept of probabilistic algebraic attack as proposed in this paper can be considered as a generic attack strategy against any stream cipher having similar structure of the output function as in case of the Grain family. 18:17 [Pub][ePrint] We present a new transformation of chosen-plaintext secure predicate encryption schemes with public index into chosen-ciphertext secure schemes. Our construction requires only a universal one-way hash function and is selectively secure in the standard model. The transformation is not generic but can be applied to various existing schemes constructed from bilinear groups. Using common structural properties of these schemes we provide an efficient and simple transformation without overhead in form of one-time signatures or message authentication codes as required in the known generic transformations. 18:17 [Pub][ePrint] Secure multi-party computation platforms are becoming more and more practical. This has paved the way for privacy-preserving statistical analysis using secure multi-party computation. Simple statistical analysis functions have been emerging here and there in literature, but no comprehensive system has been compiled. We describe and implement the most used statistical analysis functions in the privacy-preserving setting including simple statistics, t-test,$\\chi^{2}\$ test, Wilcoxon tests and linear regression. We give descriptions of the privacy-preserving algorithms and benchmark results that show the feasibility of our solution.