International Association
for Cryptologic Research

Division property is a generalized integral property proposed by Todo at Eurocrypt 2015. Previous tools for automatic searching are mainly based on the Mixed Integer Linear Programming (MILP) method and trace the division property propagation at the bit level. In this paper, we propose automatic tools to detect ARX ciphers' division property at the bit level and some specific ciphers' division property at the word level. For ARX ciphers, we construct the automatic searching tool relying on Boolean Satisfiability Problem (SAT) instead of MILP, since SAT method is more suitable in the search of ARX ciphers' differential/linear characteristics. The propagation of division property is translated into a system of logical equations in Conjunctive Normal Form (CNF). Some logical equations can be dynamically adjusted according to different initial division properties and stopping rule, while the others corresponding to r-round propagations remain the same. Moreover, our approach can efficiently identify some optimized distinguishers with lower data complexity. As a result, we obtain a 17-round distinguisher for SHACAL-2, which gains four more rounds than previous work, and an 8-round distinguisher for LEA, which covers one more round than the former one. For word-based division property, we develop the automatic search based on Satisfiability Modulo Theories (SMT), which is a generalization of SAT. We model division property propagations of basic operations and S-boxes by logical formulas, and turn the searching problem into an SMT problem. With some available solvers, we achieve some new distinguishers. For CLEFIA, 10-round distinguishers are obtained, which cover one more round than the previous work. For the internal block cipher of Whirlpool, the data complexities of 4/5-round distinguishers are improved. For Rijndael-192 and Rijndael-256, 6-round distinguishers are presented, which attain two more rounds than the published ones. Besides, the integral attacks for CLEFIA are improved by one round with the newly obtained distinguishers.

Among all existing identity-based encryption (IBE) schemes in the bilinear group, Wat-IBE proposed by Waters [CRYPTO, 2009] and JR-IBE proposed by Jutla and Roy [AsiaCrypt, 2013] are quite special. A secret key and/or ciphertext in these two schemes consist of several group elements and an integer which is usually called tag. A series of prior work was devoted to extending them towards more advanced attribute-based encryption (ABE) including inner-product encryption (IPE), hierarchical IBE (HIBE). Recently, Kim et al. [SCN, 2016] introduced the notion of tag-based encoding and presented a generic framework for extending Wat-IBE. We may call these ABE schemes ABE with tag or tag-based ABE. Typically, a tag-based ABE construction is more efficient than its counterpart without tag. However the research on tag-based ABE severely lags---We do not know how to extend JR-IBE in a systematic way and there is no tag-based ABE for boolean span program even with Kim et al.'s generic framework.

In this work, we proposed a generic framework for tag-based ABE which is based on JR-IBE and compatible with Chen et al.'s (attribute-hiding) predicate encoding [EuroCrypt, 2015]. The adaptive security in the standard model relies on the k-linear assumption in the asymmetric prime-order bilinear group. This is the first framework showing how to extend JR-IBE systematically. In fact our framework and its simple extension are able to cover most concrete tag-based ABE constructions in previous literature. Furthermore, since Chen et al.'s predicate encoding supports a large number of predicates including boolean span program, we can now give the first (both key-policy and ciphertext-policy) tag-based ABE for boolean span program in the standard model. Technically our framework is based on a simplified version of JR-IBE. Both the description and its proof are quite similar to the prime-order IBE derived from Chen et al.'s framework. This not only allows us to work with Chen et al.'s predicate encoding but also provides us with a clear explanation of JR-IBE and its proof technique.

Keccak-based algorithms such as Secure Hash Algorithm-3 (SHA-3) will be widely used in crypto systems, and evaluating their security against different kinds of attacks is vitally important. This paper presents an efficient differential fault analysis (DFA) method on all four modes of SHA-3 to recover an entire internal state, which leads to message recovery in the regular hashing mode and key retrieval in the message authentication code (MAC) mode. We adopt relaxed fault models in this paper, assuming the attacker can inject random single-byte faults into the penultimate round input of SHA-3. We also propose algorithms to find the lower bound on the number of fault injections needed to recover an entire internal state for the proposed attacks. Results show that on average the attacker needs about 120 random faults to recover an internal state, while he needs 17 faults at best if he has control of the faults injected. The proposed attack method is further extended for systems with input messages longer than the bitrate.

In image processing, algorithms for object classification are typically based around machine learning. From the algorithm developer's perspective, these can involve a considerable amount of effort and expertise to develop, which makes them commercially valuable. On the other hand, other parties may want to make use of these algorithms to classify their images, while protecting the privacy of their data. In this paper, we show how non-linear Support Vector Machines (SVMs) can be practically used for image classification on data encrypted with a Somewhat Homomorphic Encryption (SHE) scheme. Previous work has shown how an SVM with a linear kernel can be computed on encrypted data, but this only has limited applicability. By enabling SVMs with polynomial kernels, a much larger class of applications are possible with more accuracy in classification results.

Beyond their security guarantees under well-studied assumptions, algebraic pseudo-random functions are motivated by their compatibility with efficient zero-knowledge proof systems, which is useful in a number of privacy applications like digital cash. We consider the problem of proving the correct evaluation of lattice-based PRFs based on the Learning-With-Rounding (LWR) problem introduced by Banerjee et al. (Eurocrypt'12). Namely, we are interested zero-knowledge arguments of knowledge of triples $(y,k,x)$ such that $y=F_k(x)$ is the correct evaluation of a PRF for a secret input $x$ and a committed key $k$. While analogous statements admit efficient zero-knowledge protocols in the discrete logarithm setting, they have never been addressed in lattices so far. We provide such arguments for the key homomorphic PRF of Boneh et al. (Crypto'13) and the generic PRF implied by the LWR-based pseudo-random generator. As an application of our ZK arguments, we design the first compact e-cash system based on lattice assumptions. By ``compact'', we mean that the complexity is at most logarithmic in the value of withdrawn wallets. Our system can be seen as a lattice-based analogue of the first compact e-cash construction due to Camenisch, Hohenberger and Lysyanskaya (Eurocrypt'05).

Fault attack is one of the most efficient side channel attacks and has attracted much attention in recent public cryptographic literatures. In this work we introduce a fault attack on the authenticated cipher ACORN v3. Our attack is done under the assumption that a fault is injected into an initial state of ACORN v3 randomly, and contains two main steps: fault locating and equation solving. At the first step, we introduce concepts of unique set and non-unique set, where differential strings belonging to unique sets can determine the fault location uniquely. For strings belonging to non-unique sets, we use some strategies to increase the probability of determining the fault location uniquely to almost 1. At the second step, we demonstrate several ways of retrieving equations, and then obtain the initial state by solving equations with the guess-and-determine method. With $n$ fault experiments, we can recover the initial state with time complexity $c \cdot2^{146.5-3.52\cdot n}$, where $c$ is the time complexity of solving linear equations and $26<n<43$. We also apply the attack to ACORN v2, which shows that, comparing with ACORN v2, the tweaked version ACORN v3 is more vulnerable against the fault attack.

Passwords are ubiquitous and most commonly used to authenticate users when logging into online services. Using high entropy passwords is critical to prevent unauthorized access and password policies emerged to enforce this requirement on passwords. However, with current methods of password storage, poor practices and server breaches have leaked many passwords to the public. To protect one's sensitive information in case of such events, passwords should be hidden from servers. Verifier-based password authenticated key exchange, proposed by Bellovin and Merrit (IEEE S\&P, 1992), allows authenticated secure channels to be established with a hash of a password (verifier). Unfortunately, this restricts password policies as passwords cannot be checked from their verifier. To address this issue, Kiefer and Manulis (ESORICS 2014) proposed zero-knowledge password policy check (ZKPPC). A ZKPPC protocol allows users to prove in zero knowledge that a hash of the user's password satisfies the password policy required by the server. Unfortunately, their proposal is not quantum resistant with the use of discrete logarithm-based cryptographic tools and there are currently no other viable alternatives. In this work, we construct the first post-quantum ZKPPC using lattice-based tools. To this end, we introduce a new randomised password hashing scheme for ASCII-based passwords and design an accompanying zero-knowledge protocol for policy compliance. Interestingly, our proposal does not follow the framework established by Kiefer and Manulis and offers an alternate construction without homomorphic commitments. Although our protocol is not ready to be used in practice, we think it is an important first step towards a quantum-resistant privacy-preserving password-based authentication and key exchange system.

We present a generic, yet simple and efficient transformation to obtain a forward secure authenticated key exchange protocol from a two-move passively secure unauthenticated key agreement scheme (such as standard Diffie--Hellman or Frodo or NewHope). Our construction requires only an IND-CCA public key encryption scheme (such as RSA-OAEP or a method based on ring-LWE), and a message authentication code. Particularly relevant in the context of the state-of-the-art of postquantum secu re primitives, we avoid the use of digital signature schemes: practical candidate post-quantum signature schemes are less accepted (and require more bandwidth) than candidate post-quantum public key encryption schemes. An additional feature of our proposal is that it helps avoid the bad practice of using long term keys certified for encryption to produce digital signatures. We prove the security of our transformation in the random oracle model.

We present blockcipher-based MACs (Message Authentication Codes) that have beyond the birthday bound security without message length in the sense of PRF (Pseudo-Random Function) security. Achieving such security is important in constructing MACs using blockciphers with short block sizes (e.g., 64 bit).

Luykx et al. (FSE2016) proposed LightMAC, the first blockcipher-based MAC with such security and a variant of PMAC, where for each $n$-bit blockcipher call, an $m$-bit counter and an $(n-m)$-bit message block are input. By the presence of counters, LightMAC becomes a secure PRF up to $O(2^{n/2})$ tagging queries. Iwata and Minematsu (TOSC2016, Issue1) proposed F_t, a keyed hash function-based MAC, where a message is input to $t$ keyed hash functions (the hash function is performed $t$ times) and the $t$ outputs are input to the xor of $t$ keyed blockciphers. Using the LightMAC's hash function, F_t becomes a secure PRF up to $O(2^{t n/(t+1)})$ tagging queries. However, for each message block of $(n-m)$ bits, it requires $t$ blockcipher calls.

In this paper, we improve F_t so that a blockcipher is performed only once for each message block of $(n-m)$ bits. We prove that our MACs with $t \leq 7$ are secure PRFs up to $O(2^{t n/(t+1)})$ tagging queries. Hence, our MACs with $t \leq 7$ are more efficient than F_t while keeping the same level of PRF-security.

The ultimate goal of designing a symmetric-key cryptographic primitive often can be formulated as an optimization problem. So far, these problems mainly have been solved with trivial algorithms such as brute force or random search. We show that a more advanced and equally versatile class of search algorithms, called metaheuristics, can help to tackle optimization problems related to design of symmetric-key primitives. We use two nature-inspired metaheuristics, simulated annealing and genetic algorithm, to optimize in terms of security the components of two recent cryptographic designs, SKINNY and AES-round based constructions. The positive outputs of the optimization suggest that metaheuristics are non-trivial tools, well suited for automatic design of primitives.

Computing similarity between data is a fundamental problem in information retrieval and data mining. To address the relevant performance and scalability challenges, approximation methods are employed for large-scale similarity computation. A common characteristic among all privacy- preserving approximation protocols based on sketching is that the sketching is performed locally and is based on common randomness.

In the semi-honest model the input to the sketching algorithm is independent of the common randomness. We, however, consider a new threat model where a party is allowed to use the common randomness to perturb her input 1) offline, and 2) before the execution of any secure protocol so as to steer the approximation result to a maliciously chosen output. We formally define perturbation attacks under this adversarial model and propose two attacks on the well-studied techniques of minhash and cosine sketching. We demonstrate the power of perturbation attacks by measuring their success on synthetic and real data.

To mitigate such perturbation attacks we propose a server- aided architecture, where an additional party, the server, assists in the secure similarity approximation by handling the common randomness as private data. We revise and introduce the necessary secure protocols so as to apply minhash and cosine sketching techniques in the server-aided architecture. Our implementation demonstrates that this new design can mitigate offline perturbation attacks without sacrificing the efficiency and scalability of the reconstruction protocol.

Event date: 29 November to 1 December 2017
Submission deadline: 15 September 2017
Notification: 20 October 2017

This work describes a new family of cryptographic constructions called FAST. Several instantiations of FAST are described. These are targeted towards two goals, the specific task of disk encryption on one hand and a more general scheme suitable for a wide variety of applications on the other. Formally, FAST is a new family of tweakable enciphering schemes. It is built as a mode of operation of a fixed input length pseudo-random function and an appropriate hash function. FAST uses a single-block key, is parallelisable and can be instantiated using only the encryption function of an appropriate block cipher. The hash function can be instantiated using either the Horner's rule based usual polynomial hashing or the more efficient Bernstein-Rabin-Winograd polynomials. Security is rigorously analysed using the standard provable security approach and concrete security bounds are derived. Detailed and careful implementations of FAST in both software and hardware are presented. The results from the implementations show that FAST compares favourably to all previous schemes. Based on these results, we put forward FAST as a serious candidate for standardisation and deployment.

In CRYPTO 2011, Yasuda proposed PMAC_Plus message authentication code based on an $n$-bit block cipher. Its design principle inherits the well known PMAC parallel network with a low additional cost. PMAC_Plus is a rate-$1$ construction like PMAC (i.e., one block cipher call per $n$-bit message block) but provides security against all adversaries making queries altogether consisting of roughly upto $2^{2n/3}$ blocks (strings of $n$-bits). Even though PMAC_Plus gives higher security than the standard birthday bound security, with currently available best bound, it provides weaker security than PMAC for certain choices of adversaries. Moreover, unlike PMAC, PMAC_Plus operates with three independent block cipher keys. In this paper, we propose 1k-PMAC_Plus, the first rate-$1$ single keyed block cipher based BBB (Beyond Birthday Bound) secure (in standard model) deterministic MAC construction without arbitrary field multiplications. Our construction is a simple one-key variant of PMAC_Plus. Moreover, we show higher security guarantee than what was proved originally for PMAC_Plus. Our proven bound shows that PMAC_Plus and 1k-PMAC_Plus always provide higher security guarantee than what was promised by PMAC against all types of adversaries.

Job Description

Cryptography Architect will lead and contribute to our core technology. This senior engineering position requires demonstrated capabilities in cryptography, encryption, programming, and the associated computational sciences, while also serving the role of cryptography lead for the product teams. The position also requires leading associated research and patent activities and staging of foundational cryptographic technologies for security products.

DESIRED SKILLS & EXPERIENCE

• MS or PhD with at least few credits in advanced cryptography, mathematics and computer science combined with at least 2 years of software development experience in a related discipline is required

• In-depth hands-on implementation experience of at least few cryptography algorithms from scratch is required

• A very good understanding of symmetric and asymmetric key cryptography, key management techniques, PKI, SSL, X.509 Certificates and all the related technologies is needed

• Strong theoretical bend and academic connections is a plus

• Understanding of latest cryptographic techniques such as as Homomorphic and Split Key Encryption, Function and Format preserving Encryption techniques is a big plus

• Experience with various character sets and character encoding techniques is required

• Hands-on programming experience in C or Java. Java development experience is a plus

• Entrepreneurial drive and work ethic, self-motivated, results oriented and demonstrated ability to add value and succeed in a fast paced environment.

• Team player with strong communications and writing skills.

Closing date for applications: 1 November 2017

Contact: Harshiika Upadhyay Sahu

Mananger - Recruitment

husahu (at) ciphercloud.com

More information: https://ciphercloud.com/

The University of York is one of the UK\'s leading higher education institutions and a member of the prestigious Russell Group of universities. The Department is renowned internationally for its high impact research, combined with a dedication to high-quality teaching and excellent student satisfaction, as well as strong industrial links, making us one of the UK\'s top Computer Science departments.

We welcome applications from researchers with a track record as an international leader in Cybersecurity, with some emphasis on pragmatic aspects of Cybersecurity. You will actively engage and collaborate with colleagues leading the development of Cybersecurity research and teaching. You’ll develop relationships across the wider University and beyond, to help build a distinctive and positive working environment that emphasises excellence.

To support this appointment we are appointing up to 10 lectureships within the department to further grow Cybersecurity research and our other core themes. Our intentions is to build our Cybersecurity research into an accredited centre. We would offer the appointed candidate support through these additional appointment and reduced teaching load in the first instance.

Closing date for applications: 8 October 2017

Contact: Professor Neil Audsley

Head of Department - Computer Science

neil.audsley (at) york.ac.uk

More information: https://jobs.york.ac.uk/wd/plsql/wd_portal.show_job?p_web_site_id=3885&p_web_page_id=325060

York\'s Computer Science Department is building for the future. We wish to attract early career academics with the potential to shape the discipline, and the broader community, over the next ten to twenty years. We want your strengths to become our strengths!

Ten posts are available over the next two years and will be phased according to the quality of applications. The posts are at the lecturer (Research and Teaching) grade, equivalent to Assistant Professor.

We are looking to the new staff to reinforce our existing strengths, e.g. in Human Computer Interaction and Real-Time Systems, to expand in areas such as Cybersecurity, and to enable us to build up our range of interdisciplinary themes and research centres.

Closing date for applications: 1 October 2017

Contact: Candidates are invited to email cs-lectureships (at) york.ac.uk for confidential informal enquiries.

More information: https://www.york.ac.uk/professorial-jobs/computer-science

Event date: 11 February to 15 February 2018

The cryptographic community has widely acknowledged that the emergence of large quantum computers will pose a threat to most current public-key cryptography. Primitives that rely on order-finding problems, such as factoring and computing Discrete Logarithms, can be broken by Shor's algorithm (Shor, 1994).

Symmetric primitives, at first sight, seem less impacted by the arrival of quantum computers: Grover's algorithm (Grover, 1996) for searching in an unstructured database finds a marked element among $2^{n}$ in time $\widetilde{O}(2^{n / 2})$, providing a quadratic speedup compared to the classical exhaustive search, essentially optimal. Cryptographers then commonly consider that doubling the length of the keys used will be enough to maintain the same level of security.

From similar techniques, quantum collision search is known to attain $\widetilde{O}(2^{n / 3})$ query complexity (Brassard et al., 1998), compared to the classical $O(2^{n / 2})$. However, as Bernstein pointed out (Bernstein, 2009), this quantum speedup is illusory: the actual quantum computation performed is actually more expensive than in the classical algorithm.

In this paper, we investigate quantum collision and multi-target preimage search and present a new algorithm, that uses the amplitude amplification technique. As such, it relies on the same principle as Grover's search.

Our algorithm is the first to propose a time complexity that improves upon $O(2^{n/2})$, in a simple setting with a single processor. This time complexity is $\widetilde{O}(2^{2n/5})$ (equal to its query complexity), with a polynomial quantum memory needed ($O(n)$), and a small classical memory complexity of $\widetilde{O}(2^{n/5})$. For multi-target preimage attacks, these complexities become $\widetilde{O}(2^{3n/7})$, $O(n)$ and $\widetilde{O}(2^{n/7})$ respectively. To the best of our knowledge, this is the first proof of an actual quantum time speedup for collision search. We also propose a parallelization of these algorithms.

This result has an impact on several symmetric cryptography scenarios: we detail how to improve upon previous attacks for hash function collisions and multi-target preimages, how to perform an improved key recovery in the multi-user setting, how to improve the collision attacks on operation modes, and point out that these improved algorithms can serve as basic tools for some families of cryptanalytic techniques.

In the end, we discuss the implications of these new attacks on post-quantum security.

We propose the first provably secure zero-knowledge (ZK) argument of knowledge (AoK) protocol running at close to 1 megabyte per second (MBps) on commodity hardware -- about an order of magnitude faster than relevant current protocols. It is a post-quantum, (efficient-prover) honest-verifier (HV) statistical zero-knowledge (SZK) sigma protocol in the standard model under a hardness assumption on ideal lattices. We further propose an overhead-efficient low-latency amortization yielding a witness indistinguishable (WI) and witness hiding (WH) AoK protocol running at $> 100$ MBps. Both protocols have absolute soundness slack 1, or zero for small completeness error, and an argument size growing linearly, where amortization has slope 2 and latency 1 microsecond. Non-interactive (NI), non-HV, resettable ZK (rZK) and resettable WI (rWI) variations of the protocols are obtained using standard transforms. Choices of parameters with concrete security $\ge 2^{100}$ against known attacks are given along with experimental results showing practicality.