International Association
for Cryptologic Research

Event date: 5 June to 7 June 2017
Submission deadline: 6 February 2017
Notification: 3 April 2017

Event date: 29 May to 31 May 2017
Submission deadline: 23 December 2016
Notification: 24 February 2017

Responsibilities

As a postdoctoral researcher, you will join the European research project DECODE (DEcentralised Citizens Owned Data Ecosystem) that aims to develop distributed architectures for decentralised data governance. You will conduct research on decentralised identity and reputation management using attribute-based credentials and distributed ledgers. You will communicate your findings through papers in peer-reviewed research journals and at international conferences. You will also be involved in training and teaching PhD and BSc/MSc students.

Work environment

You will join the Digital Security section, headed by Prof. Bart Jacobs. The group works on a broad range of topics in computer security and privacy, including applied cryptography, security protocols, smartcards and RFID, and software security and correctness. We are also interested in societal aspects of digital security, such as privacy and e-voting, and interaction with disciplines outside computer science such as cryptography and law.

The Digital Security section is part of the vibrant and growing Institute for Computing and Information Sciences (iCIS). iCIS is consistently ranked as one of the top Computer Science departments in the Netherlands (National Research Review Computer Science 2002-2008 and 2009-2014).

You will work with Jaap-Henk Hoepman (scientific director of the Privacy & Identity Lab) on the DECODE project. Other partners in this project are Nesta (UK), Institut Municipal d\'Informatica de Barcelona (Spain), Arduino Verkstad (Sweden), University College London (UK), Waag Society (Netherlands), Eurecat (Spain) and CNRS (France).

Closing date for applications: 20 November 2016

Contact: Name: Jaap-Henk Hoepman

Email: jhh (at) cs.ru.nl

More information: http://www.ru.nl/werken/details/details_vacature_0/?taal=uk&recid=590659

If two different secret keys of a stream cipher yield the same internal state after the key scheduling algorithm (KSA) and hence generates the same sequence of keystream bits, they are called a colliding key pair. The number of possible internal states of RC4 stream cipher is very large (approximately $2^{1700}$), which makes finding key collision hard for practical key length (i.e., less than 30 bytes). Matsui [FSE 2009] for the first time reported a 24-byte colliding key pair and one 20-byte near-colliding key pair (i.e., for which the state arrays after the KSA differ in at most two positions) for RC4. Subsequently, Chen and Miyaji [ISC 2011] claimed to design a more efficient search algorithm using Matsui's collision pattern and reported a 22-byte colliding key pair which remains the only shortest known colliding key pair so far. In this paper, we show some limitations of both the above approaches and propose a faster collision search algorithm that overcomes these limitations. Using our algorithm, we are able to find three additional 22-byte colliding key pairs that are different from the one reported by Chen and Miyaji [ISC 2011]. We additionally give 12 new 20-byte near-colliding key pairs different from Matsui's [FSE 2009]. These results are significant, considering the argument by the experts [Biham and Dunkelman, 2007] that for shorter keys there might be no instances of collision at all.

In this paper we present a new attack on cryptosystems based on ideal lattices. We show that, if there is one polynomially large entry in the transformation matrix from trapdoor basis to public basis, then we can obtain the trapdoor basis. The key point is that some class of matrices satisfies multiplication commutative law.

Software implementations of discrete logarithm based cryptosystems over finite fields typically make the assumption that any domain parameters they are presented with are trustworthy, i.e., the parameters implement cyclic groups where the discrete logarithm problem is assumed to be hard. An informal and widespread justification for this seemingly exists that says validating parameters at run time is too computationally expensive relative to the perceived risk of a server sabotaging the privacy of its own connection. In this paper we explore this trust assumption and examine situations where it may not always be justified.

We conducted an investigation of discrete logarithm domain parameters in use across the Internet and discovered evidence of a multitude of potentially backdoored moduli of unknown order in TLS and STARTTLS spanning numerous countries, organizations, and protocols. Although our disclosures resulted in a number of organizations taking down suspicious parameters, we argue the potential for TLS backdoors is systematic and will persist until either until better parameter hygiene is taken up by the community, or finite field based cryptography is eliminated altogether.

We describe new cryptanalytic attacks on the candidate branching-program obfuscator proposed by Garg, Gentry, Halevi, Raykova, Sahai and Waters (GGHRSW) using the GGH13 graded encoding, and its variant using the GGH15 graded encoding as specified by Gentry, Gorbunov and Halevi. All our attacks require very specific structure of the branching programs being obfuscated (which in particular must have some input-partitioning property). Common to all our attacks are techniques to extract information about the ``multiplicative bundling'' scalars that are used in the GGHRSW construction.

For the GGHRSW obfuscator over GGH13, we show how to recover the ideal generating the plaintext space when the branching program has input partitioning. Combined with the information that we extract about the ``multiplicative bundling'' scalars, this lets us extend the annihilation attack of Miles, Sahai and Zhandry, to handle the GGHRSW block-randomization of the branching-program matrices. (We stress that our attack does not break the candidate obfuscators of Miles et al. and Garg et al. (ePrint 2016/588, 2016/817), since their dual-input branching programs are inherently not partitionable.) Alternatively, once we have the ideal we can solve the principle-ideal problem (PIP) in classical subexponential time or quantum polynomial time, hence obtaining a total break.

For the GGH15 variant, we show how to use the left-kernel technique of Coron, Lee, Lepoint and Tibouchi to recover ratios of the bundling scalars. Once we have the ratios of the scalar products, we can use factoring and PIP solvers (in classical subexponential time or quantum polynomial time) to find the scalars themselves, then run mixed-input attacks to break the obfuscation.

We present an additively homomorphic commitment scheme with hardness based on the Ring-SIS problem. Our construction is statistically hiding as well as computationally binding and allows to commit to a vector of ring elements at once. We show how to instantiate efficient zero-knowledge protocols that can be used to prove a number of relations among these commitments, and apply these in the context of lattice-based threshold cryptosystems: we give a generic transformation that can be used with certain (Ring-)LWE-based encryption schemes to make their algorithms actively secure. We show how this transformation can be used to implement distributed decryption with malicious security as well as maliciously secure threshold key generation in an efficient way.

Leakage-resilience and misuse-resistance are two important properties for the deployment of authenticated encryption schemes. They aim at mitigating the impact of implementation flaws due to side-channel leakages and misused randomness. In this paper, we discuss their interactions and incompatibilities. For this purpose, we first show that a generic composition of existing leakage-resilient MAC and encryption schemes leads to a misuse-resistant authenticated encryption mode (without leakage). Next we show that this misuse-resistance does not hold in case the adversary can additionally observe leakages, and that misuse-resistance with leakage may be impossible to achieve with simple primitives such as hash functions and block ciphers. As a result, we formalize a new security notion of ciphertext integrity with misuse and leakage, which seems the best that can be achieved in a symmetric cryptographic setting, and describe first efficient constructions satisfying it.

We have an open position for a post-doctoral researcher (contract duration 2.5 years, salary GBP 31,076.- per annum, starting March/April 2017) at Surrey Centre for Cyber Security (SCCS) within the Department of Computer Science, University of Surrey to work on a new EPSRC-funded project called TAPESTRY that will investigate, develop and demonstrate new cryptographic protocols to enable people, businesses and services to connect safely online.

The successful candidate will be working on the design, security analysis and implementation of privacy-oriented cryptographic protocols that use zero-knowledge proofs, distributed ledger technologies and authentication mechanisms.

More information about the position and the application process is available at https://jobs.surrey.ac.uk/vacancy.aspx?ref=079116

The candidate will be working with Dr Mark Manulis, Deputy Director of SCCS. Applications must be made through the online portal. Questions can be sent to m.manulis AT surrey DOT ac DOT uk

Closing date for applications: 18 November 2016

Fully funded positions for PhD student (3 years) and/or Post-Doc (1 or 2 years) on ID-based Crypto and Advanced Primitives (Broadcast Encryption, Functional Encryption) at XLIM, University of Limoges.

Applicants who have a Master degree (for the PhD position) and a PhD degree (for the post-doc position) in Computer Science / Mathematics or related disciplines are encouraged to apply. Further skills in complexity, coding theory and/or software development will also be very appreciated.

The successful applicant will participate in the project ALAMBIC (AppLicAtions of MalleaBIlity in Cryptography) and IDFIX (IDentity-based cryptography For Identification and eXchange) financed by the French governmental research funding agency ANR (Agence Nationale de la Recherche).

International applicants are welcome but need to be eligible to a proper visa before starting their position.

Applications will be considered until the positions are filled, ideally the positions would start in September October 2017.

Closing date for applications:

Contact: Applications and questions should be directed as soon as possible to:

• Olivier Blazy

  olivier.blazy (at) unilim.fr

• Duong Hieu Phan

  duong-hieu.phan (at) unilim.fr.

The candidate will have the opportunity of carrying out her/his Ph.D. program around the study and development of new advanced cryptographic mechanisms with a view to applications to secure cloud systems and data privacy.

We welcome candidates with an MSc degree in computer science, mathematics, engineering and related areas.

Good analytical skills and familiarity with mathematical reasoning are mandatory. Strong background in theoretical computer science and principles of modern cryptography are an advantage.

The candidate will be supervised by Dr. Vincenzo Iovino and Prof. Peter Ryan, head of the APSIA, a very active and large research group aimed to conduct research in several aspects of information assurance from the mathematical foundations to the usability concerns.

The University offers highly competitive salaries, excellent working conditions and may assist in finding accommodation.

Closing date for applications: 31 December 2016

Contact:

Dr. Vincenzo Iovino, vincenzo.iovino (at) uni.lu

Prof. Peter Ryan, peter.ryan (at) uni.lu

One or more postdoc positions are vacant at the Cryptography and Security Group of Aarhus University (http://aarhuskrypto.dk/).

Applicants should be able to show solid expertise (in the form of scientific publications at major crypto/security venues such as CRYPTO, EUROCRYPT, ASIACRYPT, TCC, PKC, ACM CCS, IEEE S&P, USENIX Security, etc.) in the design and/or implementation of cryptographic protocols. Topics of particular interest include: secure multiparty computation, zero-knowledge, homomorphic encryption, oblivious RAM, differential-privacy, cryptocurrencies, etc.

The closing date is nominal only. Write to Claudio Orlandi (orlandi AT cs au dk) for more information.

(PhD positions are available too, see earlier posting).

Closing date for applications: 31 December 2016

Contact: Claudio Orlandi, Associate Professor,

orlandi AT cs au dk

The Department of Computer Science at the University of Illinois at Urbana-Champaign invites applications for several faculty positions at all levels and in all areas of Computer Science. Applicants from both traditional as well as non-traditional and interdisciplinary areas of computer science are encouraged to apply.

Qualified senior candidates may also be considered for tenured full Professor positions as part of the Grainger Engineering Breakthroughs Initiative, which is backed by a $100-million gift from the Grainger Foundation. Over the next few years, more than 35 new endowed professorships and chairs will be established, which will provide incredible opportunities for world-renowned researchers.

Closing date for applications: 6 January 2017

Contact: Carl A. Gunter

More information: https://cs.illinois.edu/about-us/faculty-positions

Several recent standards, including NIST SP 800- 56A and RFC 5114, advocate the use of “DSA” parameters for Diffie-Hellman key exchange. While it is possible to use such parameters securely, additional validation checks are necessary to prevent well-known and potentially devastating attacks. In this paper, we observe that many Diffie-Hellman implementations do not properly validate key exchange inputs. Combined with other protocol properties and implementation choices, this can radically decrease security. We measure the prevalence of these parameter choices in the wild for HTTPS, POP3S, SMTP with STARTTLS, SSH, IKEv1, and IKEv2, finding millions of hosts using DSA and other non-“safe” primes for Diffie-Hellman key exchange, many of them in combination with potentially vulnerable behaviors. We examine over 20 open-source cryptographic libraries and applications and observe that until January 2016, not a single one validated subgroup orders by default. We found feasible full or partial key recovery vulnerabilities in OpenSSL, the Exim mail server, the Unbound DNS client, and Amazon’s load balancer, as well as susceptibility to weaker attacks in many other applications.

We improve the design and implementation of two-party and three-party authenticated dynamic dictionaries and apply these dictionaries to cryptocurrency ledgers.

A public ledger (blockchain) in a cryptocurrency needs to be easily verifiable. However, maintaining a data structure of all account balances, in order to verify whether a transaction is valid, can be quite burdensome: a verifier who does not have the large amount of RAM required for the data structure will perform slowly because of the need to continually access secondary storage. We use experiments to demonstrate that authenticated dynamic dictionaries can considerably reduce verifier load. On the other hand, per-transaction proofs generated by authenticated dictionaries increase the size of the blockchain, which motivates us to find a solution with most compact proofs.

Our improvements to the design of authenticated dictionaries reduce proof size and speed up verification by 1.4-2.5 times, making them better suited for the cryptocurrency application. We further show that proofs for multiple transactions in a single block can compressed together, reducing their total length by approximately an additional factor of 2.

Side-channel attacks exploit physical characteristics of implementations of cryptographic algorithms in order to extract sensitive information such as the secret key. These physical attacks are among the most powerful attacks against real-world cryptosystems. This paper analyses the non-linear part (called Sboxes) of ciphers, which is often targeted by implementation attacks. We analyse Sboxes of several candidates that were sub- mitted to the competition on authenticated encryption (CAESAR) as well as several other ciphers. We compare theoretical metrics with results from simulations and with real experiments. In this paper, we demonstrate that, in some contexts, the theoretical metrics provide no information on the resiliency of the Sboxes against side-channel attacks.

We investigate the cost of Grover's quantum search algorithm when used in the context of pre-image attacks on the SHA-2 and SHA-3 families of hash functions. Our cost model assumes that the attack is run on a surface code based fault-tolerant quantum computer. Our estimates rely on a time-area metric that costs the number of logical qubits times the depth of the circuit in units of surface code cycles. As a surface code cycle involves a significant classical processing stage, our cost estimates allow for crude, but direct, comparisons of classical and quantum algorithms.

We exhibit a circuit for a pre-image attack on SHA-256 that is approximately $2^{153.8}$ surface code cycles deep and requires approximately $2^{12.6}$ logical qubits. This yields an overall cost of $2^{166.4}$ logical-qubit-cycles. Likewise we exhibit a SHA3-256 circuit that is approximately $2^{146.5}$ surface code cycles deep and requires approximately $2^{20}$ logical qubits for a total cost of, again, $2^{166.5}$ logical-qubit-cycles. Both attacks require on the order of $2^{128}$ queries in a quantum black-box model, hence our results suggest that executing these attacks may be as much as $275$ billion times more expensive than one would expect from the simple query analysis.

The Bitcoin backbone protocol [Eurocrypt 2015] extracts basic properties of Bitcoin's underlying {\em blockchain} data structure, such as ``common prefix'' and ``chain quality,'' and shows how fundamental applications including consensus and a robust public transaction ledger can be built on top of them. The underlying assumptions are ``proofs of work'' (POWs), adversarial hashing power strictly less than $1/2$ {\em and} no adversarial pre-computation---or, alternatively, the existence of an unpredictable ``genesis'' block.

In this paper we show how to remove the latter assumption, presenting a ``bootstrapped'' Bitcoin-like blockchain protocol relying on POWs that builds genesis blocks ``from scratch'' in the presence of adversarial pre-computation. The only known previous result in the same setting (unauthenticated parties, no trusted setup) [Crypto 2015] is indirect in the sense of creating a PKI first and then employing conventional PKI-based authenticated communication.

With our construction we establish that consensus can be solved directly by a blockchain protocol {\em without} trusted setup assuming an honest majority (in terms of computational power). % We also formalize {\em miner unlinkability}, a privacy property for blockchain protocols, and demonstrate that our protocol retains the same level of miner unlinkability as Bitcoin itself.

Linear cryptanalysis can be considered to be one of the strongest techniques in the cryptanalyst's arsenal. In most cases, Matsui's Algorithm 2 is used for the key recovery part of the attack. The success rate analysis of this algorithm is based on an assumption regarding the bias of a linear approximation for a wrong key, known as the wrong-key-randomization hypothesis. This hypothesis was refined by Bogdanov and Tischhauser to take into account the stochastic nature of the bias for a wrong key. We provide further refinements to the analysis of Matsui's algorithm 2 by considering the more natural setting of sampling without replacement. This paper derives the distribution for the observed bias for wrong keys when sampling is done without replacement and shows that less data is required when duplicate pairs are discarded. It also develops formulas for the success probability and the required data complexity when this approach is taken. The formulas predict that the success probability may reach a peak, then decrease as more pairs are considered. We provide a new explanation for this behavior and derive the conditions for encountering it. We empirically verify our results and compare them to previous work.