International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. 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).

2014-09-09
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.

Requirements:

  • 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.




2014-09-08
01:39 [PhD][Update]

 



2014-09-05
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.



21:17 [Pub][ePrint] Defeating ISO9797-1 MAC Algo 3 by Combining Side-Channel and Brute Force Techniques, by Benoit Feix and Hugues Thiebeauld

  Side-channel analysis is a well-known and efficient hardware technique to recover embedded secrets in microprocessors. Over the past years, the state-of-the-art side-channel attacks has significantly increased, leading to a myriad of vulnerability paths that secure codes must withstand. Nowadays most of the attacks target the cryptographic algorithms, but very few exploit the cryptographic protocol. In this paper, we present a new attack that exploits the information exchange at the cryptographic protocol level in order to disclose the secret key. This attack is applicable to the MAC calculations standardized in ISO/IEC 9797-1 especially the MAC algorithm 3 with the DES function. This protocol is spread in secure products nowadays, this is the case typically for some EMV implementations. By using a side-channel technique combined with a reasonable brute force effort, we show that the secret key can be fully retrieved even though the DES implementation seems to be well-protected against side-channel attacks.



21:17 [Pub][ePrint] Linearity Measures for MQ Cryptography, by Simona Samardjiska and Danilo Gligoroski

  We propose a new general framework for the security of multivariate quadratic (\\mathcal{MQ}) schemes with respect to attacks that exploit the existence of linear subspaces. We adopt linearity measures that have been used traditionally to estimate the security of symmetric cryptographic primitives, namely the nonlinearity measure for vectorial functions introduced by Nyberg at Eurocrypt \'92, and the $(s, t)$--linearity measure introduced recently by Boura and Canteaut at FSE\'13. We redefine some properties of \\mathcal{MQ} cryptosystems in terms of these known symmetric cryptography notions, and show that our new framework is a compact generalization of several known attacks in \\mathcal{MQ} cryptography against single field schemes. We use the framework to explain various pitfalls regarding the successfulness of these attacks. Finally, we argue that linearity can be used as a solid measure for the susceptibility of \\mathcal{MQ} schemes to these attacks, and also as a necessary tool for prudent design practice in \\mathcal{MQ} cryptography.