International Association for Cryptologic Research

# IACR News Central

Here you can see all recent updates to the IACR webpage. These updates are also available:

Now viewing news items related to:

31 August 2016
MDS matrices are used as building blocks of diffusion layers in block ciphers, and XOR count is a metric that estimates the hardware implementation cost. In this paper we report the minimum value of XOR counts of $4 \times 4$ MDS matrices over $\mathbb{F}_{2^4}$ and $\mathbb{F}_{2^8}$, respectively. We give theoretical constructions of Toeplitz MDS matrices and show that they achieve the minimum XOR count. We also prove that Toeplitz matrices cannot be both MDS and involutory. Further we give theoretical constructions of $4 \times 4$ involutory MDS matrices over $\mathbb{F}_{2^4}$ and $\mathbb{F}_{2^8}$ that have the best known XOR counts so far: for $\mathbb{F}_{2^4}$ our construction gives an involutory MDS matrix that actually improves the existing lower bound of XOR count, whereas for $\mathbb{F}_{2^8}$, it meets the known lower bound.
ePrint Report A Zoo of Homomorphic Signatures: Multi-Key and Key-Homomorphism Russell W. F. Lai, Raymond K. H. Tai, Harry W. H. Wong, Sherman S. M. Chow
Homomorphic signatures (HS) allow evaluation of signed messages by producing a signature on a function of messages signed by the same key. Motivated by the vast potential of applications, we initiate the study of multi-key HS (M-HS) which allows evaluation of signatures under different keys. We also study other multi-key extensions, namely, hierarchical HS (M-HiHS) for delegation of signing power over message sub-spaces, and key-message-HS (M-KMHS) for evaluation of signatures under different keys with respect to both keys and messages. We thus also introduce the concept of key-homomorphism in signatures, which leads to the notion of multi-key key-HS (M-KHS) for evaluation of signatures with respect to keys only.

Notion-wise, our result shows that M-HS can act as a central notion since all its seemingly different extensions are all equivalent. In particular, this suggests that key-homomorphism and message-homomorphism in signatures are identical in nature. As a sample application, we show that M-KHS implies decentralized attribute-based signatures (D-ABS). Our work also provides the first (leveled) fully KHS and the first (D-)ABS for circuits from standard assumptions.

Surprisingly, there is a huge gap between homomorphism in a single space and in two spaces. Indeed all existing (leveled) fully homomorphic signature schemes support only a single signer. In the multi-space setting, we construct M-HS from any adaptive zero-knowledge succinct non-interactive argument of knowledge (ZK-SNARK) (and other standard assumptions). We also show that two-key HS implies functional signatures. Our study equips the literature with a suite of signature schemes allowing different kinds of flexible evaluations.
ePrint Report Multi-Cast Key Distribution: Scalable, Dynamic and Provably Secure Construction Kazuki Yoneyama, Reo Yoshida, Yuto Kawahara, Tetsutaro Kobayashi, Hitoshi Fuji, Tomohide Yamamoto
In this paper, we propose a two-round dynamic multi-cast key distribution (DMKD) protocol under the star topology with a central authentication server. Users can share a common session key without revealing any information of the session key to the server, and can join/leave to/from the group at any time even after establishing the session key. Our protocol is scalable because communication and computation costs of each user are independent from the number of users. Also, our protocol is still secure if either private key or session-specific randomness of a user is exposed. Furthermore, time-based backward secrecy is guaranteed by renewing the session key for every time period even if the session key is exposed. We introduce the first formal security definition for DMKD under the star topology in order to capture such strong exposure resilience and time-based backward secrecy. We prove that our protocol is secure in our security model in the standard model.
Job Posting Research Scientist Temasek Laboratories, National University of Singapore
Temasek Laboratories at National University of Singapore, Singapore is seeking highly motivated professionals interested in conducting research in the area of post-quantum cryptography.

Applicants are expected to have a PhD degree in Mathematics/Computer Science/Engineering and a strong background in algebra or number theory.

Preferred candidates are expected to be proficient in C/C++ language, a team worker and able to conduct independent research.

Interested candidates will kindly email their CV to Dr Chik How Tan tsltch (at) nus.edu.sg.

Review of applications will start immediately until position is filled.

Closing date for applications: 15 October 2016

30 August 2016
The security research team at Visa research has openings for research scientists at all levels with expertise in areas such as, cryptography and cryptanalysis, user and data privacy, payments and cryptocurrencies, and distributed systems/cloud computing security. For more information visit our website: http://research.visa.com/

Interested candidates should kindly email their CV to research (at) visa (dot) com with the subject line Security Research Position.

Closing date for applications: 30 November 2016

AEZ is a parallelizable, AES-based authenticated encryption algorithm that is well suited for software implementations on processors equipped with the AES-NI instruction set. It aims at offering exceptionally strong security properties such as nonce and decryption-misuse resistance and optimal security given the selected ciphertext expansion. AEZ was submitted to the authenticated ciphers competition CAESAR and was selected in 2015 for the second round of the competition.

In this paper, we analyse the resilience of the latest algorithm version, AEZ v4.1 (October 2015), against key-recovery attacks. While AEZ modifications introduced in 2015 were partly motivated by thwarting a key-recovery attack of birthday complexity against AEZ v3 published at Asiacrypt 2015 by Fuhr, Leurent and Suder, we show that AEZ v4.1 remains vulnerable to a key-recovery attack of similar complexity and security impact. Our attack leverages the use, in AEZ, of an underlying tweakable block cipher based on a 4-round version of AES.

Although the presented key-recovery attack does not violate the security claims of AEZ since the designers made no claim for beyond-birthday security, it may be interpreted as an indication that AEZ does not meet in all respects the objective of being a highly conservative and misuse-resilient algorithm.
In recent years, methods to securely mask S-boxes against side-channel attacks by representing them as polynomials over finite binary fields have become quite efficient. A good cost model for this is to count how many non-linear multiplications are needed. In this work we improve on the current state-of-the-art generic method published by Coron-Roy-Vivek at CHES 2014 by working over slightly larger fields than strictly needed. This leads us, for example, to evaluate DES S-boxes with only 3 non-linear multiplications and, as a result, obtain $$25\%$$ improvement in the running time for secure software implementations of DES when using three or more shares.

On the theoretical side, we prove a logarithmic upper bound on the number of non-linear multiplications required to evaluate any $$d$$-bit S-box, when ignoring the cost of working in unreasonably large fields. This upper bound is lower than the previous lower bounds proved under the assumption of working over the field $$\mathbb{F}_{2^d}$$, and we show this bound to be sharp. We also achieve a way to evaluate the AES S-box using only 3 non-linear multiplications over $$\mathbb{F}_{2^{16}}$$.
Free cloud-based services are powerful candidates for deploying ubiquitous encryption for messaging. In the case of email and increasingly chat, users expect the ability to store and search their messages persistently. Using data from one of the top three mail providers, we confirm that for a searchable encryption scheme to scale to millions of users, it should be highly IO-efficient (locality), and handle a very dynamic message corpi. We observe that existing solutions fail to achieve both properties simultaneously. We then design, build, and evaluate a provably secure Dynamic Searchable Symmetric Encryption (DSSE) scheme with significant reduction in IO cost compared to preceding works when used for email or other highly dynamic message corpi.
KDM[$\mathcal F$]-CCA secure public-key encryption (PKE) protects the security of message $f(sk)$, with $f \in \mathcal F$, that is computed directly from the secret key, even if the adversary has access to a decryption oracle. An efficient KDM[$\mathcal F_{aff}$]-CCA secure PKE scheme for affine functions was proposed by Lu, Li and Jia (LLJ, EuroCrypt2015). We point out that their security proof is flawed and cannot go through based on the DDH assumption.

In this paper, we introduce a new concept _Authenticated Encryption with Auxiliary-Input_ AIAE and define for it new security notions dealing with related-key attacks, namely _IND-RKA security_ and _weak INT-RKA security. We also construct such an AIAE w.r.t. a set of restricted affine functions from the DDH assumption. With our AIAE,

-- we construct the first efficient KDM[$\mathcal F_{aff}$]-CCA secure PKE w.r.t. affine functions with compact ciphertexts, which consist only of a constant number of group elements;

-- we construct the first efficient KDM[$\mathcal F_{poly}^d$]-CCA secure PKE w.r.t. polynomials of bounded degree $d$ with almost compact ciphertexts, and the number of group elements in a ciphertext is polynomial in $d$, independent of the security parameter.

Our PKEs are both based on the DDH & DCR assumption, free of NIZK and free of pairing.
We introduce a new technique for doing the key recovery part of an integral or higher order differential attack. This technique speeds up the key recovery phase significantly and can be applied to any block cipher with S-boxes. We show several properties of this technique, then apply it to PRINCE and report on the improvements in complexity from earlier integral and higher order differential attacks on this cipher. Our attacks on 4 and 6 rounds were the fastest and the winner of PRINCE Challenge's last round in the category of chosen plaintext attack.
ePrint Report Security Analysis of BLAKE2's Modes of Operation Atoll Luykx, Bart Manning, Samuel Neves
BLAKE2 is a hash function introduced at ACNS 2013, which has been adopted in many constructions and applications. It is a successor to the SHA-3 finalist BLAKE, which received a significant amount of security analysis. Nevertheless, BLAKE2 introduces sufficient changes so that not all results from BLAKE carry over, meaning new analysis is necessary. To date, all known cryptanalysis done on BLAKE2 has focused on its underlying building blocks, with little focus placed on understanding BLAKE2's generic security. We prove that BLAKE2's compression function is indifferentiable from a random function in a weakly ideal cipher model, which was not the case for BLAKE. This implies that there are no generic attacks against any of the modes that BLAKE2 uses.
Rotational cryptanalysis is a statistical method for attacking ARX constructions. It was previously shown that ARX-C, i.e., ARX with the injection of constants can be used to implement any function. In this paper we investigate how rotational cryptanalysis is affected when constants are injected into the state. We introduce the notion of an RX-difference, generalizing the idea of a rotational difference. We show how RX-differences behave around modular addition, and give a formula to calculate their transition probability. We experimentally verify the for- mula using Speck32/64, and present a 7-round distinguisher based on RX-differences. We then discuss two types of constants: round constants, and constants which are the result of using a fixed key, and provide recommendations to designers for optimal choice of parameters.
Shannon defined an ideal $(\kappa,n)$-blockcipher as a secrecy system consisting of $2^{\kappa}$ independent $n$-bit random permutations.

This work revisits the following question: in the ideal cipher model, can a cascade of several ideal $(\kappa,n)$-blockciphers realize $2^{2\kappa}$ independent $n$-bit random permutations, i.e. an ideal $(2\kappa,n)$-blockcipher? The motivation goes back to Shannon's theory on product secrecy systems, and similar question was considered by Even and Goldreich (CRYPTO '83) in different settings. Towards giving an answer, this work analyzes cascading independent ideal $(\kappa,n)$-blockciphers with two alternated independent keys in the indifferentiability framework of Maurer et al. (TCC 2004), and proves that for such alternating-key cascade, four stages is necessary and sufficient to achieve indifferentiability from an ideal $(2\kappa,n)$-blockcipher. This shows cascade capable of achieving key-length extension in the settings where keys are _not necessarily secret_.
ePrint Report P2P Mixing and Unlinkable Bitcoin Transactions Tim Ruffing, Pedro Moreno-Sanchez, Aniket Kate
Starting with Dining Cryptographers networks (DC-net), several peer-to-peer (P2P) anonymous communication protocols have been proposed. Despite their strong anonymity guarantees none of those has been employed in practice so far: Most fail to simultaneously handle the crucial problems of slot collisions and malicious peers, while the remaining ones handle those with a significant increased latency (communication rounds) linear in the number of participating peers in the best case, and quadratic in the worst case. We conceptualize these P2P anonymous communication protocols as P2P mixing, and present a novel P2P mixing protocol, DiceMix, that only requires constant (i.e., four) communication rounds in the best case, and $4+2f$ rounds in the worst case of $f$ malicious peers. As every individual malicious peer can prevent a protocol run from success by omitting his messages, we find DiceMix with its worst-case linear-round complexity to be an optimal P2P mixing solution.

On the application side, we find DiceMix to be an ideal privacy-enhancing primitive for crypto-currencies such as Bitcoin. The public verifiability of their pseudonymous transactions through publicly available ledgers (or blockchains) makes these systems highly vulnerable to a variety of linkability and deanonymization attacks. DiceMix can allow pseudonymous users to make their transactions unlinkable to each other in a manner fully compatible with the existing systems. We demonstrate the efficiency of DiceMix with a proof-of-concept implementation. In our evaluation, DiceMix requires less than 8 seconds to mix 50 messages (160 bits, i.e., Bitcoin addresses), while the best protocol in the literate requires almost 3 minutes in a very similar setting. As a representative example, we use apply DiceMix to define a protocol for creating unlinkable Bitcoin transactions.

Finally, we discover a generic attack on P2P mixing protocols that exploits the implicit unfairness of a protocol with a dishonest majority to break anonymity. Our attack uses the attacker’s real-world ability to omit some communication from a honest peer to deanonymize her input message. We also discuss how this attack is resolved in our application to crypto-currencies by employing uncorrelated input messages by across different protocol runs.
Attribute based signature schemes (ABS) constitute important and powerful primitives when it comes to protecting the privacy of the user's identity and signing information. More specifically, ABS schemes provide the advantage of anonymously signing a message once a given policy is satisfied. As opposed to other related privacy preserving signatures, the verifier is not able to deduce from the signature, which attributes have been used to satisfy the (public) signing policy. In this work we give new and efficient constructions of lattice-based ABS signature schemes, that are not based on the traditional approach of using span programs or secret sharing schemes as for classical schemes. In fact, our approach is less involved and does not require such complex subroutines. In particular, we first construct a new $(t,B)$-threshold ABS scheme that allows to anonymously generate signatures, if $t$ out of $p=|B|$ attributes are covered by valid credentials. Based on this scheme, we propose a lattice-based ABS scheme for expressive $(\wedge,\vee)$-policies, by use of a new credential aggregation system that is built on top of a modified variant of Boyen's signature scheme. The signature size of the so obtained ABS scheme is linear in the number of disjunctive terms rather than the number of attributes.
Applications are invited for 2 postdoctoral researchers and 1 PhD student in the theory and practice of side-channels. Each post is initially for 3 years, with flexibility for the starting date and any options to extend (depending on funds). Although a background in applied cryptography is a pre-requisite, we are interested in applicants who can demonstrate some experience with one or more of the following:

- side-channel attacks, with particular emphasis on practical aspects (e.g., acquisition and signal processing),

- use, low-level (e.g., processor architecture) understanding and reverse engineering of (e.g., ARM-based) embedded systems,

- the design and implementation of compilers (e.g., LLVM),

- hardware (e.g., FPGA) and software implementation of cryptography,

- use of HPC, experience in developing large scale (research focused) software.

Although a nominal closing date is listed below, this is a rolling advert: we will select applicants until all vacancies are filled.

Closing date for applications: 31 December 2016

Contact: Prof. Elisabeth Oswald, Elisabeth.Oswald (at) bristol.ac.uk

Job Posting Post-Doc University of Luxembourg
The researchers will be working under the supervision of Prof P Y A Ryan, head of the APSIA (Applied Security and Information Assurance) research group, http://wwwde.uni.lu/snt/research/apsia.

Research Associate in Information Assurance (M/F)

Ref: R-STR-5004-00-B

Fixed Term Contract 24 months (CDD), full-time (40 hrs/week), extendable to 36 months

Number of positions: 1

The research will be conducted within the VoteVerif project (Verification of Voter-Verifiable Voting Protocols), in collaboration with Polish Academy of Sciences, Warsaw, Poland. The project aims to develop novel concepts, methodologies, and tools for specification, analysis, and assessment of information security properties. The focus is on voting procedures and protocols, and in particular on their essential features like confidentiality, coercion-resistance, and voter-verifiability. The approach of the project is holistic, in the sense that we plan to develop theoretical concepts (such as strategy- based metrics of information security) not for their own sake, but in order to apply them to an important domain of social life, and come up with guidance on the conduct of elections and novel designs for secure, usable voting systems. To this end, we are going to develop algorithmic tools that help to analyze the level of security and usability. Note also that, while we focus on voting procedures in the project, the concepts and tools being developed can be also applied to other domains where information security is important.

Closing date for applications: 7 October 2016

Contact: Prof Dr Peter Y A Ryan, peter.ryan (at) uni.lu;

or Prof Dr Wojtek Jamroga: w.jamroga (at) ipipan.waw.pl

Job Posting PhD University of Luxembourg
The research will be conducted within the VoteVerif project (Verification of Voter-Verifiable Voting Protocols), in collaboration with Polish Academy of Sciences, Warsaw, Poland. The project aims to develop novel concepts, methodologies, and tools for specification, analysis, and assessment of information security properties. The focus is on voting procedures and protocols, and in particular on their essential features like confidentiality, coercion-resistance, and voter-verifiability. The approach of the project is holistic, in the sense that we plan to develop theoretical concepts (such as strategy- based metrics of information security) not for their own sake, but in order to apply them to an important domain of social life, and come up with guidance on the conduct of elections and novel designs for secure, usable voting systems. To this end, we are going to develop algorithmic tools that help to analyze the level of security and usability. Note also that, while we focus on voting procedures in the project, the concepts and tools being developed can be also applied to other domains where information security is important.

Closing date for applications: 31 October 2016

Contact: Prof Dr Peter Y A Ryan, peter.ryan (at) uni.lu; or

Prof Dr Wojtek Jamroga w.jamroga (at) ipipan.waw.pl

29 August 2016
Event Calendar SG-CRC: Singapore Cyber Security R&D Conference Singapore, Singapore, 21 February - 22 February 2017
Event date: 21 February to 22 February 2017
The Department of Computer Science at the University of Surrey is seeking to recruit a full-time researcher for up to three years.

The position offers the platform for the research fellow to work within a group and develop skills to become an independent researcher. The successful candidate will be expected to work closely with Dr Treharne and Professor Schneider in the development or evaluation of security and safety systems (including IoT based Systems of Systems, distributed ledger technologies, transport systems, cloud architectures and data privacy systems). There is the opportunity for the successful candidate to contribute to setting the research direction within this.

The fellowship allows for flexibility in the profile of applicants:

· Practically-minded applicants who have good programming skills, experience in working in embedded systems, trusted execution environments and platforms, networking protocols and security, cloud security architectures and privacy schemes;

· Applicants with a background in formal verification techniques and security/safety analysis.

Experience in both is preferred but in-depth knowledge of only one is expected. Additionally, an enthusiasm to learn about the other area will be required. We are looking for applicants that demonstrate strong research and analytical skills, have strong communication skills and enthusiasm for developing their own research ideas.

Applicants should have a PhD in a relevant subject or be close to finishing or equivalent professional experience.

The post is available for 36 months, with some flexibility in the start date.

Salary range: £32600 to £34576

Closing date: 13 September, 2016

Interview Date: 26 September, 2016.

Closing date for applications: 13 September 2016

Contact: Dr Helen Treharne (h.treharne (at) surrey.ac.uk) and Professor Steve Schneider (s.schneider (at) surrey.ac.uk)

Job Posting Ph.D Student University College London (UCL)
Fully-funded PhD Position Available

Enabling Progress in Genomic Research via Privacy-Preserving Data Sharing

University College London (UCL)

Closing date for applications: 30 October 2016

Contact: Dr Emiliano De Cristofaro (google me)

Job Posting Ph.D. student University of Bergen, Norway
The Department of Informatics has a vacancy for a PhD position within cryptography. The position is for a fixed-term period of 3 years, starting in the beginning of 2017, and funded by the project “Modern Methods and Tools for Theoretical and Applied Cryptology” (CryptoWorld), awarded by the Research Council of Norway.

About the Department: The Department has 6 research groups, Algorithms, Bioinformatics, Optimization, Programming Theory, Reliable Communication and Visualization. The Department is ranked first in Norway with respect to the quality of its research by the Research Council of Norway. For more information visit our Web pages: http://www.uib.no/en/ii

Develop new methods of algebraic cryptanalysis and apply them to modern cryptographic primitives. Analyse how malicious software can affect the authentication in various applications. Improve the security and efficiency of cloud technologies by designing ciphers with special properties.

Closing date for application: 1 October 2016,

Closing date for applications: 1 October 2016

Contact: Professor Tor Helleseth, Tor.Helleseth (at) uib.no (Department of Informatics), (+47) 55 58 41 60 or Professor Igor Semaev, Igor.Semaev (at) uib.no (Department of Informatics), (+47) 55 58 42 79.

28 August 2016
In vehicular ad hoc networks, message authentication using proxy vehicles was proposed to reduce the computational overhead of roadside unites. In this type of message authentication schemes, proxy vehicles with verifying multiple messages at the same time improve computational efficiency of roadside unites when there are a large number of vehicles in their coverage areas. In this paper, first we show that the only proxy-based authentication scheme presented for this goal by Liu et al. is not resistant against false acceptance of batching invalid signatures and modification attack. Next, we propose an new identitybased message authentication scheme with employing proxy vehicles. Then, unforgeability of underlying signature is proved under Elliptic Curve Discrete Logarithm Problem in the random oracle model to show that it is secure against modification attack. It should be highlighted that our proposed scheme not only is more efficient than Liu et al.’s scheme since it is pairing-free and does not use mapto- point hash functions, but also it satisfies security and privacy requirements of vehicular ad hoc networks.
In this paper, algorithms for multivariate public key cryptography and digital signature are described. Plain messages and encrypted messages are arrays, consisting of elements from a fixed finite ring or field. The encryption and decryption algorithms are based on multivariate mappings. The security of the private key depends on the difficulty of solving a system of parametric simultaneous multivariate equations involving polynomial or exponential mappings. The method is a general purpose utility for most data encryption, digital certificate or digital signature applications.
Differential privacy is a mathematical definition of privacy for statistical data analysis. It guarantees that any (possibly adversarial) data analyst is unable to learn too much information that is specific to an individual. Mironov et al.~(CRYPTO 2009) proposed several computational relaxations of differential privacy (CDP), which relax this guarantee to hold only against computationally bounded adversaries. Their work and subsequent work showed that CDP can yield substantial accuracy improvements in various multiparty privacy problems. However, these works left open whether such improvements are possible in the traditional client-server model of data analysis. In fact, Groce, Katz and Yerukhimovich~(TCC 2011) showed that, in this setting, it is impossible to take advantage of CDP for many natural statistical tasks.

Our main result shows that, assuming the existence of sub-exponentially secure one-way functions and 2-message witness indistinguishable proofs (zaps) for NP, that there is in fact a computational task in the client-server model that can be efficiently performed with CDP, but is infeasible to perform with information-theoretic differential privacy.
26 August 2016
Starting this year, FSE has moved to a new open-access journal/conference hybrid model. Submitted articles undergo a journal-style reviewing process. Accepted papers are published in Gold Open Access (free availability from day one) by the Ruhr University of Bochum in an issue of the newly established journal IACR Transactions on Symmetric Cryptology.