International Association
for Cryptologic Research

SHA3 and its extendable output variant SHAKE belong to the family of sponge functions. In this work, we present formal security arguments for the quantum preimage, $2^{\text{nd}}$-preimage, and collision resistance of any sponge function. We just assume that the internally used transformation behaves like a random transformation. These are the first formal arguments that sponge functions (incl. SHA3 and SHAKE) are secure in the post-quantum setting.

We even go one step further and prove that sponges are collapsing (Unruh, EUROCRYPT'16). Thereby, we can also derive the applicability of sponge functions for collapse-binding commitments.

In addition to the security arguments, we also present a quantum collision attack against sponges. The complexity of our attack asymptotically matches the proven lower bound up to a square root.

Lin and Tessaro (Eprint 2017/250) recently proposed indistinguishability obfuscation and functional encryption candidates and proved their security based on a standard assumption on bilinear maps and a non-standard assumption on ``Goldreich-like'' pseudorandom generators (PRG). In a nutshell, they require the existence of pseudo-random generators $G:\Sigma^n \rightarrow \{0,1\}^m$ for some $\mathsf{poly}(n)$-size alphabet $\Sigma$ where each output bit depends on at most two input alphabet symbols, and which achieve sufficiently large stretch. We show a polynomial-time attack against such generators.

Our attack uses tools from the literature on two-source extractors (Chor and Goldreich, SICOMP 1988) and efficient refutation of 2-CSPs over large alphabets (Allen, O'Donnell and Witmer, FOCS 2015). Finally, we propose new ways to instantiate the Lin-Tessaro construction that do not immediately fall to our attacks. While we cannot say with any confidence that these modifications are secure, they certainly deserve further cryptanalysis.

Event date: 13 November to 15 November 2017
Submission deadline: 21 July 2017
Notification: 12 September 2017

The Quantum Information and Applications (IQA) group of Telecom Paristech is conducting a research activity centered on quantum information, quantum communication and cryptography. This research combines theoretical work on quantum information, communication and quantum cryptographic protocols.

The IQA group is part of several active networks of researchers in quantum information, which provides a dynamic context for scientific exchange, collaboration and opportunities for financial support: the Paris Centre for Quantum Computing” http://www.pcqc.fr/, the “Domaine d’Intérêt Majeur” project called SIRTEQ (regional cluster) and the project IQUPS : quantum information at university Paris –Saclay.

The IQA group is also involved in master courses in Paris-Saclay, in Quantum communications and quantum cryptography, as well as a specialized master program on quantum information and post-quantum cryptography.

The IQA group is part of the Network & Computer Sc. departement (INFRES Dpt.) and the Laboratoire Traitement et Communication de l’information l’Information (LTCI).

The recruited associate professor will contribute to the research and teaching activities, as detailed in the official announcement (in French) http://www.telecom-paristech.fr/nc/telecom-paristech/offres-emploi-stages-theses/fiche-offre- demploi.html?offre_emploi=181

The successful candidate will take part in the research projects lead in the team, and will also initiate new research projects, in particular on quantum information and post-quantum cryptography. Research results will be published in leading journals and conferences. Activities in scientific bodies, organization of special sessions, workshops as well as involvements in committees of scientific conferences will also be encouraged, as they contribute to the visibility.

Teaching can be done at bachelor level, in computer science and maths, and also at master level in more specialized courses, such as information theory, algebra, quantum physics, quantum information, cryptography.

Closing date for applications: 5 May 2017

Contact: Isabelle Zaquine

Département Informatique et Réseaux

Télécom ParisTech, LTCI

Université Paris-Saclay

46 rue Barrault Paris 13e , Bureau C234-5

+33 1 45 81 78 39

isabelle.zaquine (at) telecom-paristech.fr

More information: http://www.telecom-paristech.fr/telecom-paristech/offres-emploi-stages-theses.html

Role

Use elliptic curve cryptography, digital signatures, and commitments in an established codebase to help the world securely interact in a way that preserves privacy.

Write code in python and possibly a system language or two (C, Rust, Go) that invokes c-callable crypto libraries to exchange anonymous credentials (see http://www.research.ibm.com/labs/zurich/idemix/ and https://www.microsoft.com/en-us/research/project/u-prove/) and build zero-knowledge proofs. Integrate with technologies like zkSNARKS and Ethereum.

Build byzantine fault tolerant protocols for distributed consensus.

Work on specific federal government contracts.*

Requirements

Master’s degree or PhD in cryptography or a closely related field--or active enrollment in such a program.

At least 5 years of experience with software engineering

Familiarity with applied cryptography, cryptanalysis, and similar topics; the stronger the math background, the better. Familiarity with networking and cryptocurrencies. Good competence as a coder (python preferred, but strengths in other languages may be considered). Comfort on Linux (though we also work on Mac and Windows).

Flexibility to work with remote colleagues in different time zones.

Strongly preferred: Ability to work in our Utah office (Lehi/American Fork). Some remote work possible.

This is a regular full-time position.

*Federal Government project requires US Citizenship.

Closing date for applications: 4 July 2017

Contact: Steve Tolman

careers (at) evernym.com

We propose Meshcash, a new framework for cryptocurrency protocols that combines a novel, proof-of-work based, permissionless byzantine consensus protocol (the tortoise) that guarantees eventual consensus and irreversibility, with a possibly-faulty but quick consensus protocol (the hare). The construction is modular, allowing any suitable ``hare'' protocol to be plugged in. The combined protocol enjoys best of both worlds properties: consensus is quick if the hare protocol succeeds, but guaranteed even if it is faulty. Unlike most existing proof-of-work based consensus protocols, our tortoise protocol does not rely on leader-election (e.g., the single miner who managed to extend the longest chain). Rather, we use ideas from asynchronous byzantine agreement protocols to gradually converge to a consensus.

Meshcash, is designed to be race-free: there is no ``race'' to generate the next block, hence honestly-generated blocks are always rewarded. This property, which we define formally as a game-theoretic notion, turns out to be useful in analyzing rational miners' behavior: we prove (using a generalization of the blockchain mining games of Kiayias et al.) that race-free blockchain protocols are incentive-compatible and satisfy linearity of rewards (i.e., a party receives rewards proportional to its computational power).

Because Meshcash can tolerate a high block rate regardless of network propagation delays (which will only affect latency), it allows us to lower both the variance and the expected time between blocks for honest miners; together with linearity of rewards, this makes pooled mining far less attractive. Moreover, race-free protocols scale more easily (in terms of transaction rate). This is because the race-free property implies that the network propagation delays are not a factor in terms of rewards, which removes the main impediment to accommodating a larger volume of transactions.

We formally prove that all of our guarantees hold in the asynchronous communication model of Pass, Seeman and shelat, and against a constant fraction of byzantine (malicious) miners; not just rational ones.

Private Set Intersection (PSI) is a cryptographic technique that allows two parties to compute the intersection of their sets without revealing anything except the intersection. We use fully homomorphic encryption to construct a fast PSI protocol with a small communication overhead that works particularly well when one of the two sets is much smaller than the other.

The most computationally efficient PSI protocols have been constructed using tools such as hash functions and oblivious transfer, but a potential limitation with these approaches is the communication complexity, which scales linearly with the size of the larger set. This is of particular concern when performing PSI between a constrained device (cellphone) holding a small set, and a large service provider (e.g. WhatsApp), such as in the Private Contact Discovery application.

Our protocol has communication complexity linear in the size of the smaller set, and logarithmic in the larger set. More precisely, if the set sizes are Nx for the sender, and Ny for the receiver, we achieve a communication overhead of O(NylogNx). Our benchmarks show that it takes 36 seconds of online-computation, 71 seconds of non-interactive (receiver-independent) pre-processing, and only 12.5MB of round trip communication to intersect five thousand 32-bit strings with 16 million 32-bit strings. Compared to prior works, this is roughly a 38 times reduction in communication, with minimal increase in computation.

This paper presents a performance and statistical analysis of random number generators and discrete Gaussian samplers implemented in software. Most Lattice-based cryptographic schemes utilise discrete Gaussian sampling and will require a quality random source. We examine a range of candidates for this purpose, including NIST DRBGs, stream ciphers and well-known PRNGs. The performance of these random sources is analysed within 64-bit implementations of Bernoulli, CDT and Ziggurat sampling. In addition we perform initial statistical testing of these samplers and include an investigation into improper seeding issues and their effect on the Gaussian samplers. Of the NIST approved Deterministic Random Bit Generators (DRBG), the AES based CTR-DRBG produced the best balanced performance in our tests.

Distance-bounding protocols have been introduced to thwart relay attacks against contactless authentication protocols. In this context, verifiers have to authenticate the credentials of untrusted provers. Unfortunately, these protocols are themselves subject to complex threats such as terrorist-fraud attacks, in which a malicious prover helps an accomplice to authenticate. Provably guaranteeing the resistance of distance-bounding protocols to these attacks is a complex task. The classical countermeasures usually assume that rational provers want to protect their long-term authentication credentials, even with respect to their accomplices. Thus, terrorist-fraud resistant protocols generally rely on artificial extraction mechanisms, ensuring that an accomplice can retrieve the credential of his partnering prover.

In this paper, we propose a novel approach to obtain provable terrorist-fraud resistant protocols without assuming that provers have any long-term secret key. Instead, the attacker simply has to replay the information that he has received from his accomplice. Based on this, we present a generic construction for provably secure distance-bounding protocols, and give three instances: (1) an efficient symmetric-key protocol, (2) a public-key protocol protecting the identities of the provers against external eavesdroppers, and finally (3) a fully anonymous protocol protecting the identities of the provers even against malicious verifiers trying to profile them.

Event date: 10 August to 11 August 2017
Submission deadline: 23 April 2017
Notification: 9 June 2017

Event date: 23 October to 24 October 2017
Submission deadline: 12 July 2017
Notification: 20 August 2017

We put forward a generalization of lossy trapdoor functions (LTFs). Namely, all-but-many lossy trapdoor functions (ABM-LTFs) are LTFs that are parametrized with tags. Each tag can either be injective or lossy, which leads to an invertible or a lossy function. The interesting property of ABM-LTFs is that it is possible to generate an arbitrary number of lossy tags by means of a special trapdoor, while it is not feasible to produce lossy tags without this trapdoor.

Our definition and construction can be seen as generalizations of all-but-one LTFs (due to Peikert and Waters) and all-but-N LTFs (due to Hemenway et al.). However, to achieve ABM-LTFs (and thus a number of lossy tags which is not bounded by any polynomial), we have to employ some new tricks. Concretely, we give two constructions that employ ``disguised'' variants of the Waters, resp. Boneh-Boyen signature schemes to make the generation of lossy tags hard without trapdoor. In a nutshell, lossy tags simply correspond to valid signatures. At the same time, tags are disguised (i.e., suitably blinded) to keep lossy tags indistinguishable from injective tags.

ABM-LTFs are useful in settings in which there are a polynomial number of adversarial challenges (e.g., challenge ciphertexts). Specifically, building on work by Hemenway et al., we show that ABM-LTFs can be used to achieve selective opening security against chosen-ciphertext attacks. One of our ABM-LTF constructions thus yields the first SO-CCA secure encryption scheme with compact ciphertexts (O(1) group elements) whose efficiency does not depend on the number of challenges. Our second ABM-LTF construction yields an IND-CCA (and in fact SO-CCA) secure encryption scheme whose security reduction is independent of the number of challenges and decryption queries.

The Swedish NCSA, a function within the Swedish Military Intelligence and Security Directorate of the Swedish Armed Forces, has an open position for a cryptographer. Further details about this job opportunity is provided in Swedish via the reference below.

Please note that a Swedish citizenship is a mandatory requirement to apply for this position. Applicants considered for employment will be required to undergo security vetting.

Closing date for applications: 30 April 2017

More information: http://jobb.forsvarsmakten.se/sv/lediga-tjanster/13088

The Swedish NCSA, a function within the Swedish Military Intelligence and Security Directorate of the Swedish Armed Forces, has an open position for a junior cryptographer. Further details about this job opportunity is available in Swedish via the reference below.

Please note that a Swedish citizenship is a mandatory requirement to apply for this position. Applicants considered for employment will be required to undergo security vetting procedures.

Closing date for applications: 30 April 2017

More information: http://jobb.forsvarsmakten.se/sv/lediga-tjanster/13085

The Security and Privacy Group at the TU Wien is offering a full-time position (40 hours/week) for a post-doc university assistant for 2 years. The estimated starting date is October 2, 2017.

The salary as a postdoctoral researcher is covered by level B1 of the Austrian

Collective Agreement for university staff, and is currently EUR 3.626,60 per month/gross (14 times a year).

The successful applicant will carry out his/her research activity in one of the following areas:

- Formal Methods for Security and Privacy

- Web Security

- Mobile Security

- Cryptocurrencies

- Privacy-Enhancing Technologies

- Applied Cryptography

Outstanding candidates in other security domains are also encouraged to apply.

The specific requirements for this postdoc position are the following:

- Scientific excellence, as witnessed by publications in top-tier security venues

- PhD in Computer Science

- Very good English skills (writing, speaking)

The TU Wien is committed to increasing female employment in leading scientific positions. Female applicants are explicitly encouraged to apply. Preference will be given to female applicants when equally qualified.

Only applications received by April 26, 2017 will receive consideration.

Applications should be submitted by e-mail to veronika.korn (at) tuwien.ac.at and include

A cover letter stating the candidate\'s motivation to apply, and the reason(s) why they should be selected for the position

- A CV

- A short research statement

- Three most significant publications

- The contact details of two referees

For informal inquiries, please contact

Univ. Prof. Matteo Maffei (matteo.maffei (at) tuwien.ac.at)

Closing date for applications: 26 April 2017

A distributed computation in which nodes are connected by a partial communication graph is called topology-hiding if it does not reveal information about the graph beyond what is revealed by the output of the function. Previous results have shown that topology-hiding computation protocols exist for graphs of constant degree and logarithmic diameter in the number of nodes [Moran-Orlov-Richelson, TCC'15; Hirt et.al., Crypto'16] as well as for other graph families, such as cycles, trees, and low circumference graphs [Akavia-Moran, Eurocrypt'17], but the feasibility question for general graphs was open. In this work we positively resolve the above open problem: we prove that topology-hiding computation is feasible for all graphs under the Decisional Diffie-Hellman assumption.

Our techniques employ random-walks to generate paths covering the graph, upon which we apply the Akavia-Moran topology-hiding broadcast for chain-graphs (paths). To prevent topology information revealed by the random-walk, we design multiple random-walks that, together, are locally identical to receiving at each round a message from each neighbors and sending back processed messages in a randomly permuted order.

At PQ Crypto 2014, Peikert proposed efficient and practical lattice-based protocols for key transport, encryption and authenticated key exchange. One of the main technical innovations of this work is a reconciliation technique that allows two parties who "approximately agree" on a secret value to reach exact agreement, a setting common to essentially all lattice-based encryption schemes. Peikert's reconciliation technique has been extended in the Frodo key exchange scheme, allowing for agreement on more than one bit. In both cases, only one reconciliation bit is required to reach exact agreement. As symmetric keys typically require many bits, say 128 or more, the parties compute multiple secret values, and reach exact agreement on each of those values individually. In this paper, we propose a reconciliation method that sends more than one reconciliation bit. In this way, the parties can agree on the same number of bits as with Peikert's method with less stringent conditions on "how approximate" the approximate agreement must be. An instance of our method allows the two parties on a secret value that is one bit longer than with the previous methods, with virtually the same approximation requirements (i.e., with virtually the same security guarantees) as before. We numerically illustrate the advantages of our method with the impact to the instantiations of the Frodo scheme.

As genome sequencing technology develops rapidly, there has lately been an increasing need to keep genomic data secure even when stored in the cloud and still used for research. In this paper, we are interested in designing a protocol for the secure outsourcing matching problem on encrypted data. We propose an efficient method to securely search a matching position with the query data and extract some information at the position. After decryption, we only perform a small amount of comparison with the query information in plaintext. We apply this method to find a set of biomarkers in encrypted genomes.

The important feature of our method is to encode a genomic database as a single element of polynomial ring. It also requires only a single homomorphic multiplication for query computation. Thus this method has the advantage over the previous methods in parameter size, computational complexity, and communication cost.

We evaluate the performance of our method and verify that computation on large-scale personal data can be securely and practically outsourced to a cloud environment during data analysis. It takes about 3.9 seconds to search-and-extract the reference and alternate sequences of the queried position in a database of size 4M.

The Montgomery ladder is a remarkably simple method of computing scalar multiples of points on a broad class of elliptic curves. This article surveys a wide range of topics related to the Montgomery ladder, both from the historical perspective of Weierstrass curves and from the modern perspective of Edwards curves. New material includes a full proof of a complete constant-time ladder algorithm suitable for cryptographic applications.

Substitution box (S-box) is an important component of block ciphers for providing confusion into the cryptosystems. The functions used as S-boxes should have low differential uniformity, high nonlinearity and high algebraic degree. Due to the lack of knowledge on the existence of APN permutations over $\mathbb{F}_{2^{2k}}$, which have the lowest differential uniformity, when $k>3$, they are often constructed from differentially 4-uniform permutations. Up to now, many infinite families of such functions have been constructed. Besides, the less cost of hardware implementation of S-boxes is also an important criterion in the design of block ciphers. If the S-box is an involution, which means that the compositional inverse of the permutation is itself, then the implementation cost for its inverse is saved. The same hardware circuit can be used for both encryption and decryption, which is an advantage in hardware implementation. In this paper, we investigate all the differentially 4-uniform permutations that are known in the literature and determine whether they can be involutory. We found that some involutory differential 4-uniform permutations with high nonlinearity and algebraic degree can be given from these known constructions.