International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

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

09:17 [Pub][ePrint] The Feasibility of Outsourced Database Search in the Plain Model, by Carmit Hazay and Hila Zarosim

  The problem of securely outsourcing computation to an untrusted server gained momentum with the recent penetration of cloud computing services. The ultimate goal in this setting is to design efficient protocols that minimize the computational overhead of the clients and instead rely on the extended resources of the server. In this paper, we focus on the outsourced database search problem which is highly motivated in the context of delegatable computing since it offers storage alternatives for massive databases, that may contain confidential data. This functionality is described in two phases: (1) setup phase and (2) query phase. The main goal is to minimize the parties workload in the query phase so that it is proportional to the query size and its corresponding response.

Our starting point is the semi-honest protocol from FaustHV13 (ICALP 2013) that offers a simulation based secure protocol for outsourced pattern matching in the random oracle setting with optimal workload. In this work we study whether the random oracle is necessary for protocols with minimal interaction that meet the optimal communication/computation bounds in the query phase. We answer this question negatively and demonstrate a lower bound on the communication or the computational overhead in this phase. We further abstract the security properties of the underlying cryptographic primitive that enables to obtain private outsourced database search with minimal interaction. For a large class of search functionalities the communication complexity of our protocol meets the above lower bound.

09:17 [Pub][ePrint] Analysis Of Variance and CPA in SCA, by Sebastien Tiran and Guillaume Reymond and Jean-Baptiste Rigaud and Driss Aboulkassimi and Benedikt Gierlichs and Mathieu Carbone and Gilles Ducharme and Philipp

  This paper introduces Side-Channel Analysis results obtained on an unprotected circuit characterized by a surprisingly non-linear leakage. While in such a case, Correlation Power Analysis is not adapted, we show that a more generic attack, based on the Analysis Of Variance (AOV) outperfoms CPA. It has the advantage of detecting non-linear leakage, unlike Correlation Power Analysis, and of providing similar or much better results in all cases, with a similar computation time.

09:17 [Pub][ePrint] Formal Treatment of Privacy-Enhancing Credential Systems, by Jan Camenisch and Stephan Krenn and Anja Lehmann and Gert Læssøe Mikkelsen and Gregory Neven and Michael Østergaard Pedersen

  Privacy-enhancing attribute-based credentials (PABCs) are the core ingredient to privacy-friendly authentication systems, allowing users to obtain credentials on attributes and prove possession of these credentials in an unlinkable fashion while revealing only a subset of the attributes. To be useful in practice, however, PABCs typically need additional features such as i) revocation, ii) pooling prevention by binding credentials to users\' secret keys, iii) pseudonyms as privacy-friendly user public keys, iv) proving equality of attributes without revealing their values, v) or advanced issuance where attributes can be \"blindly\" carried over into new credentials. Provably secure solutions exist for most of these features in isolation, but it is unclear how they can be securely combined into a full-fledged PABC system, or even which properties such a system would aim to fulfill. We provide a formal treatment of PABC systems supporting the mentioned features by defining their syntax and security properties, resulting in the most comprehensive definitional framework for PABCs so far. Unlike previous efforts, our definitions are not targeted at one specific use-case; rather, we try to capture generic properties that can be useful in a variety of scenarios. We believe that our definitions can also be used as a starting point for diverse application-dependent extensions and variations of PABCs. We present and prove secure a generic and modular construction of a PABC system from simpler building blocks, allowing for a \"plug-and-play\" composition based on different instantiations of the building blocks. Finally, we give secure instantiations for each of the building blocks, including in particular instantiations based on CL- and Brands-signatures which are the core of the Idemix and U-Prove protocols.

09:17 [Pub][ePrint] A Note on Quantum Security for Post-Quantum Cryptography, by Fang Song

  Shor\'s quantum factoring algorithm and a few other efficient quantum algorithms break many classical crypto-systems. In response, people proposed post-quantum cryptography based on computational problems that are believed hard even for quantum computers. However, security of these schemes against \\emph{quantum} attacks is elusive. This is because existing security analysis (almost) only deals with classical attackers and arguing security in the presence of quantum adversaries is challenging due to unique quantum features such as no-cloning.

This work proposes a general framework to study which classical security proofs can be restored in the quantum setting. Basically, we split a security proof into (a sequence of) classical security reductions, and investigate what security reductions are ``quantum-friendly\'\'. We characterize sufficient conditions such that a classical reduction can be ``lifted\'\' to the quantum setting.

We then apply our lifting theorems to post-quantum signature schemes. We are able to show that the classical generic construction of hash-tree based signatures from one-way functions and and a more efficient variant proposed in~\\cite{BDH11} carry over to the quantum setting. Namely, assuming existence of (classical) one-way functions that are resistant to efficient quantum inversion algorithms, there exists a quantum-secure signature scheme. We note that the scheme in~\\cite{BDH11} is a promising (post-quantum) candidate to be implemented in practice and our result further justifies it. Actually, to obtain these results, we formalize a simple criteria, which is motivated by many classical proofs in the literature and is straightforward to check. This makes our lifting theorem easier to apply, and it should be useful elsewhere to prove quantum security of proposed post-quantum cryptographic schemes. Finally we demonstrate the generality of our framework by showing that several existing works (Full-Domain hash in the quantum random-oracle model~\\cite{Zha12ibe} and the simple hybrid arguments framework in~\\cite{HSS11}) can be reformulated under our unified framework.

03:15 [Job][New] Ph.D. student in Theoretical Computer Science, CWI / University of Amsterdam


The Institute for Logic, Language & Computation (ILLC) at the University of Amsterdam, and the Centrum Wiskunde & Informatica (CWI) are looking for a PhD candidate in the area of quantum cryptography.

The aim of the PhD project is to develop new quantum-cryptographic protocols (beyond the task of key distribution) and explore their limitations. An example of an active research is position-based quantum cryptography. Another aspect is to investigate the security of classical cryptographic schemes against quantum adversaries (post-quantum cryptography).

Full-time appointment is on a temporary basis for a period of four years. For the first two years the PhD candidate will be appointed at the ILLC, University of Amsterdam, initially for a period of 18 months and then, on positive evaluation, for a further six months. During the final two years, the PhD candidate will be employed by the Centrum Wiskunde and Informatica (CWI). On the basis of a full-time appointment (38 hours per week), the gross monthly salary amounts to €2,083 during the first year, rising to €2,664 during the fourth year.


  • a Master\'s degree with excellent grades in computer science, mathematics or physics with outstanding results or a comparable degree;
  • candidates with a strong background in cryptography or quantum information are preferred;
  • demonstrated research abilities by completion of an (undergraduate) research project;
  • good academic writing and presentation skills;
  • good social and organisational skills.

01:39 [PhD][Update]


21:17 [Pub][ePrint] A Fully Homomorphic Encryption Scheme with Better Key Size, by Zhigang Chen, Jian Wang, ZengNian Zhang , Xinxia Song

  Fully homomorphic encryption is faced with two problems now. One is candidate fully homomorphic encryption schemes are few. Another is that the efficiency of fully homomorphic encryption is a big question. In this paper, we propose a fully homomorphic encryption scheme based on LWE, which has better key size. Our main contributions are: (1) According to the binary-LWE recently, we choose secret key from binary set and modify the basic encryption scheme proposed in Linder and Peikert in 2010. We propose a fully homomorphic encryption scheme based on the new basic encryption scheme. We analyze the correctness and give the proof of the security of our scheme. The public key, evaluation keys and tensored ciphertext have better size in our scheme. (2) Estimating parameters for fully homomorphic encryption scheme is an important work. We estimate the concert parameters for our scheme. We compare these parameters between our scheme and Bra12 scheme. Our scheme have public key and private key that smaller by a factor of about logq than in Bra12 scheme. Tensored ciphertext in our scheme is smaller by a factor of about log2q than in Bra12 scheme. Key switching matrix in our scheme is smaller by a factor of about log3q than in Bra12 scheme.

21:17 [Pub][ePrint] HIMMO security, by Oscar Garcia-Morchon and Ronald Rietman and Ludo Tolhuizen and Domingo Gomez-Perez and Jaime Gutierrez

  This paper describes HIMMO, an identity-based pairwise symmetric key establishment method. The acronym \"HIMMO\" is derived from two interpolation problems that are essential for the

security of the scheme: the HI problem, which is related to the

well-known noisy interpolation problem, and the apparently novel MMO problem, presented at ISSAC\'14.

HIMMO is non-interactive: nodes in a network can directly generate a common key without exchanging messages. Each node in the network has an identifier, and a trusted third pay (TTP) provides it with secret keying material---linked to the node identifier---in a secure way.

A node that wishes to communicate with another node uses its own secret keying material and the identity of the other node to generate a common pairwise key.

HIMMO allows for efficient operation with respect to both the amount of stored keying material and the key computation time, which is especially relevant for resource-constrained devices.

It has similar operational characteristics as previous ID-based symmetric key establishment methods, but has superior resistance against attacks in which multiple colluding or compromised nodes co-operate to obtain information on keys between other non-colluding or non-compromised nodes.

21:17 [Pub][ePrint] Scrutinizing and Improving Impossible Differential Attacks: Applications to CLEFIA, Camellia, LBlock and Simon (Full Version), by Christina Boura and Mar\\\'ia Naya-Plasencia and Valentin Suder

  Impossible differential cryptanalysis has shown to be a very powerful form of cryptanalysis against block ciphers. These attacks, even if extensively used, remain not fully understood because of their high technicality. Indeed, numerous are the applications where mistakes have been discovered or where the attacks lack optimality. This paper aims in a first step at formalizing and improving this type of attacks and in a second step at applying our work to block ciphers based on the Feistel construction. In this context, we derive generic complexity analysis formulas for mounting such attacks and develop new ideas for optimizing impossible differential cryptanalysis. These ideas include for example the testing of parts of the internal state for reducing the number of involved key bits. We also develop in a more general way the concept of using multiple differential paths, an idea introduced before in a more restrained context. These advances lead to the improvement of previous attacks against well known ciphers such as CLEFIA-128 and Camellia, while also to new attacks against 23-round LBlock and all members of the Simon family.

21:17 [Pub][ePrint] Bounded Pre-Image Awareness and the Security of Hash-Tree Keyless Signatures, by Ahto Buldas and Risto Laanoja and Peeter Laud and Ahto Truu

  We present a new tighter security proof for unbounded hash tree keyless signature (time-stamping) schemes that use Merkle-Damg\\aa rd (MD) hash functions with Preimage Aware (PrA) compression functions. It is known that the PrA assumption alone is insufficient for proving the security of unbounded hash tree schemes against back-dating attacks. We show that many known PrA constructions satisfy a stronger \\emph{Bounded Pre-Image Awareness (BPrA)} condition that assumes the existence of an extractor $\\EXT$ that is bounded in the sense that for any efficiently computable query string $\\alpha$, the number of outputs $y$ for which $\\EXT(y,\\alpha)$ succeeds does not exceed the number of queries in $\\alpha$. We show that blockcipher based MD-hash functions with rate-1 compression functions (such as Davies-Meyer and Miyaguchi-Preneel) of both type I and type II are BPrA.

We also show that the compression function of Shrimpton-Stam that uses non-compressing components is BPrA. The security proof for unbounded hash-tree schemes is very tight under the BPrA assumption. In order to have $2^s$-security against back-dating, the hash function must have $n=2s + 4$ output bits, assuming that the security of the hash function is close to the birthday barrier, i.e. that there are no structural weaknesses in the hash function itself. Note that the previous proofs that assume PrA gave the estimation $n=2s + 2 \\log_2 C + 2$, where $C$ is the maximum allowed size of the hash tree. For example, if $s=100$ ($2^{100}$-security) and $C=2^{50}$, the previous proofs require $n=302$ output bits, while the new proof requires $n=204$ output bits.

21:17 [Pub][ePrint] An Practical Iterative Side Channel Cube Attack on AES-128/256, by Erfan Aghaee and Majid Rahimi and Hamed Yusefi

  The Side Channel Cube Attack (SCCA) is a kind of Algebraic Side Channel Attack (ASCA) consisting of theoretical and practical aspects. This paper presents a general framework for the SCCA (called a Iterative SCCA (ISCCA)) on block ciphers in which these aspects are explained and the requirements are listed. On the theoretical side, we use extracting quadratic equations, recognizing iterated chosen plaintexts, and cube iteration to improve the SCCA on block ciphers. On the experimental side, we define a feasible scenario in which ISCCA can be applied on block ciphers. Then, we implement the ISCCA on AES and verify the results on an ARM micro controller. Finally, we compare the proposed SCCA (ISCCA) with the Simple Power Analysis, the previous SCCAs, and the previous attacks on AES. This comparison is based on the template building and data, time, and memory complexity. We show that the SCCA can recover 128 and 256 key bits of the AES-128/256 only with data complexity 2^{7.3}, time complexity 2^{15.74}, and memory complexity 2^{7.89} on AES-128, and data complexity 2^{7.75}, time complexity 2^{16.2}, and memory complexity 2^{8.21} on AES-256. We show only nine interesting points are needed for template matching phase. This is the most efficient SCCA on AES-128/256.