International Association
for Cryptologic Research

Event date: 6 September to 10 December 2021

The positions are available within a recently funded project ERC Advanced Grant “PROCONTRA: Smart-Contract Protocols: Theory for Applications” (see here for more). The project is led by Stefan Dziembowski. ​

We offer:

• very interesting research problems (ranging from theory of cryptography to more applied topics),
• membership in an active and vibrant research team with several international collaborators,
• budget for conference travel and research visits,
• attractive salary: approximately 6,500 PLN per month (gross), and
• an employment contract.

The ideal candidates should have an MSc degree in computer science or mathematics from a leading university and have a good background in probability theory, computational complexity, algebra, and number theory. The knowledge of cryptography, information theory, and game theory is a significant plus, but is not a prerequisite. The candidates must be fluent in written and spoken English. ​

Other details:

• Starting date: January 2021
• Duration: 2 years

​

The successful candidates will have to enroll in the PhD program at the University of Warsaw (Poland).

Application deadline: Dec 2nd, 2020.

To apply please follow this link: https://www.crypto.edu.pl/research-assistants.

Closing date for applications:

Contact: Stefan Dziembowski

More information: https://www.crypto.edu.pl/research-assistants

Located at the heart of the future Green City of Benguerir, Mohammed VI Polytechnic University (UM6P), a higher education institution with an international standard, is established to serve Morocco and the African continent. Its vision is honed around research and innovation at the service of education and development. This unique nascent university, with its state-of-the-art campus and infrastructure, has woven a sound academic and research network, and its recruitment process is seeking high quality academics and professionals in order to boost its quality-oriented research environment in the metropolitan area of Marrakech.

The School of Computer and Communication Sciences at Mohammed VI Polytechnic University (UM6P), Benguerir, Morocco is currently looking for motivated and talented Postdoctoral researchers in the area of applied cryptography, and Information security. The successful candidates will primarily be working on the following topics (but not limited to):

• Blockchains and Cryptocurrencies
• Secure Multi Party Computation

The ideal candidates should have a PhD degree in cryptography (or related field) from a leading university, and a proven record of publications in top cryptography/security/TCS venues. We offer competitive salary (the net salary per month is 2000 USD), a budget for conference travel and research visit, and membership in a young and vibrant team with several international contacts (for more see: https://www.um6p.ma/en).

Submit your application via email including

• full CV,
• sample publications,
• a detailed research proposal,
• and 2-3 reference letters sent directly by the referees.

There is no specific deadline for this call, but we will start looking at the applications from Oct 15th, 2020.

Closing date for applications:

Contact: Assoc. Prof. Mustapha Hedabou (mustapha.hedabou@um6p.ma) https://career2.successfactors.eu/sfcareer/jobreqcareer?jobId=1339&company=ump

More information: https://career2.successfactors.eu/sfcareer/jobreqcareer?jobId=1339&company=ump

Event date: 6 December to 10 December 2021
Submission deadline: 1 December 2020
Notification: 28 February 2021

Improved filter permutators are designed to build stream ciphers that can be efficiently evaluated homomorphically. So far the transciphering with such ciphers has been implemented with homomorphic schemes from the second generation. In theory the third generation is more adapted for the particular design of these ciphers. In this article we study how suitable it is in practice. We implement the transciphering of different instances of the stream cipher family FiLIP with homomorphic encryption schemes of the third generation using the TFHE library. We focus on two kinds of filter for FiLIP. First we consider the direct sum of monomials, already evaluated using HElib and we show the improvements on these results. Then we focus on the XOR-threshold filter, we develop strategies to efficiently evaluate any symmetric Boolean function in an homomorphic way, allowing us to give the first timings for such filters. We investigate different approaches for the homomorphic evaluation: using the leveled homomorphic scheme TGSW, an hybrid approach combining TGSW and TLWE schemes, and the gate boostrapping approach. We discuss the costs in time and memory and the impact on delegation of computation of these different approaches, and we perform a comparison with others transciphering schemes.

Searchable Symmetric Encryption(SSE) remains to be one of the hot topics in the field of cloud storage technology. However, malicious servers may return incorrect search results intentionally, which will bring significant security risks to users. Therefore, verifiable searchable encryption emerged. In the meantime, single-keyword query limits the applications of searchable encryption. Accordingly, more expressive searchable encryption schemes are desirable. In this paper, we propose a verifiable conjunctive keyword search scheme based on Cuckoo filter (VCKSCF), which significantly reduces verification and storage overhead. Security analysis indicates that the proposed scheme achieves security in the face of indistinguishability under chosen keyword attack and the unforgeability of proofs and search tokens. Meanwhile, the experimental evaluation demonstrates that it achieves preferable performance in real-world settings.

We study two-source non-malleable extractors, which extract randomness from weak sources even when an adversary is allowed to learn the output of the extractor on correlated inputs. First, we study consequences of improving the best known constructions of such objects. We show that even small improvements to these constructions lead to explicit low-error two-source extractors for very low linear min-entropy, a longstanding open problem in pseudorandomness. Moreover, we show the resulting extractor can be made non-malleable for samplable sources in the computational CRS model introduced by Garg, Kalai, and Khurana (Eurocrypt 2020) under standard hardness assumptions, against an unbounded distinguisher. Remarkably, previous constructions of similar extractors require much stronger assumptions.

To complement the above, we study unconditional explicit constructions of computational two-source non-malleable extractors for samplable sources in the CRS model with significantly better parameters than their information-theoretic counterparts by exploiting stronger hardness assumptions. Under a quasipolynomial hardness assumption, we achieve security against bounded distinguishers, while assuming the existence of nearly optimal collision-resistant hash functions allows us to achieve security against unbounded distinguishers.

Finally, we introduce the setting of privacy amplification resilient against memory-tampering active adversaries. Here, we aim to design privacy amplification protocols that are resilient against an active adversary that can additionally choose one honest party at will and arbitrarily corrupt its memory (i.e., its shared secret and randomness tape) before the execution of the protocol. We show how to design such protocols using two-source non-malleable extractors.

This paper presents an attack against common procedures for comparing the size-security tradeoffs of proposed cryptosystems. The attack begins with size-security tradeoff data, and then manipulates the presentation of the data in a way that favors a proposal selected by the attacker, while maintaining plausible deniability for the attacker.

As concrete examples, this paper shows two manipulated comparisons of size-security tradeoffs of lattice-based encryption proposals submitted to the NIST Post-Quantum Cryptography Standardization Project. One of these manipulated comparisons appears to match public claims made by NIST, while the other does not, and the underlying facts do not. This raises the question of whether NIST has been subjected to this attack.

This paper also considers a weak defense and a strong defense that can be applied by standards-development organizations and by other people comparing cryptographic algorithms. The weak defense does not protect the integrity of comparisons, although it does force this type of attack to begin early. The strong defense stops this attack.

New Number Field Sieves (NFS) attacks on the discrete logarithm problem have led to increase the key size of pairing-based cryptography and more precisely pairings on most popular curves like BN. To ensure 128-bit security level, recent costs estimations recommand to switch for BLS24 curves. However, using BLS24 curves for pairing requires to have an efficient arithmetic in Fp4.

In this paper, we transposed previous work on multiplication over extesnsion fields using Newton's interpolation to construct a new formula for multiplication in Fp4 and propose time x area efficient hardware implementation of this operation.

This co-processor is implemented on Kintex-7 Xilinx FPGA. The efficiency of our design in terms of time x area is almost 3 times better than previous specific architecture for multiplication in Fp4. Our architecture is used to estimate the efficiency of hardware implementations of full pairings on BLS12 and BLS24 curves with a 128-bit security level. This co-processeur can be easily modified to anticipate further curve changes.

Point randomization is an important countermeasure to protect Elliptic Curve Cryptography (ECC) implementations against side-channel attacks. In this paper, we revisit its worst-case security in front of advanced side-channel adversaries taking advantage of analytical techniques in order to exploit all the leakage samples of an implementation. Our main contributions in this respect are the following: first, we show that due to the nature of the attacks against the point randomization (which can be viewed as Simple Power Analyses), the gain of using analytical techniques over simpler divide-and-conquer attacks is limited. Second, we take advantage of this observation to evaluate the theoretical noise levels necessary for the point randomization to provide strong security guarantees and compare different elliptic curve coordinates systems. Then, we turn this simulated analysis into actual experiments and show that reasonable security levels can be achieved by implementations even on low-cost (e.g. 8-bit) embedded devices. Finally, we are able to bound the security on 32-bit devices against worst-case adversaries.

Bitcoin is a blockchain whose immutability relies on Proof-of-Work: Before appending a new block, some so-called miner has to solve a cryptographic challenge by brute force. The blockchain is spread over a network of faithful miners, whose cumulated computing power is assumed to be so large that, among other things, it should be too expensive for an attacker to mine a secret fork $n$ blocks longer than the main blockchain, provided that $n$ is big enough. For a given targeted advance of $n$ blocks, we investigate the expected time for the attacker to mine such a secret fork, the underlying cumulative distribution function, and some related optimization problems.

By design, TLS (Transport Layer Security) is a 2-party, end-to-end protocol. Yet, in practice, TLS delegation is often deployed: that is, middlebox proxies inspect and even modify TLS traffic between the endpoints. Recently, industry-leaders (e.g., Akamai, Cloudflare, Telefonica, Ericcson), standardization bodies (e.g., IETF, ETSI), and academic researchers have proposed numerous ways of achieving safer TLS delegation. We present LURK the LURK (Limited Use of Remote Keys) extension for TLS~1.2, a suite of designs for TLS delegation, where the TLS-server is aware of the middlebox. We implement and test LURK. We also cryptographically prove and formally verify, in Proverif, the security of LURK. Finally, we comprehensively analyze how our designs balance (provable) security and competitive performance.

The security of cryptosystems based on Chebyshev recursive relation, T_n(x)=2xT_{n-1}(x)-T_{n-2}(x), relies on the difficulty of finding the large degree of Chebyshev polynomials from given parameters. The relation cannot be used to evaluate T_n(x) if n is very large. We will investigate other three methods: matrix-multiplication-based evaluation, halve-and-square evaluation, and root-extraction-based evaluation. Though they have the same theoretical complexity O(\log n\log^2p), we find in some cases the root-extraction-based method is more efficient than the others, which is as fast as the general modular exponentiation. The result indicates that the hardness of some cryptosystems based on modular Chebyshev polynomials is almost equivalent to that of solving general discrete logarithm.

In a hybrid key encapsulation construction, multiple independent key encapsulation mechanisms are combined in a way that ensures the resulting key is secure according to the strongest mechanism. Such constructions can combine mechanisms that are secure in different settings and achieve the combined security of all mechanisms. For example classical and post-quantum mechanisms can be combined in order to secure communication against current threats as well as future quantum adversaries. This paper contains proofs of security for two hybrid key encapsulation mechanisms along with the relevant security definitions. Practical interpretation of these results is also provided in order to guide the use of these mechanisms in applications and standards.

We use biometrics like fingerprints and facial images to identify ourselves to our mobile devices and log on to applications everyday. Such authentication is internal-facing: we provide measurement on the same device where the template is stored. If our personal devices could participate in external-facing authentication too, where biometric measurement is captured by a nearby external sensor, then we could also enjoy a frictionless authentication experience in a variety of physical spaces like grocery stores, convention centers, ATMs, etc. The open setting of a physical space brings forth important privacy concerns though.

We design a suite of secure protocols for external-facing authentication based on the cosine similarity metric which provide privacy for both user templates stored on their devices and the biometric measurement captured by external sensors in this open setting. The protocols provide different levels of security, ranging from passive security with some leakage to active security with no leakage at all. With the help of new packing techniques and zero-knowledge proofs for Paillier encryption - and careful protocol design, our protocols achieve very practical performance numbers. For templates of length 256 with elements of size 16 bits each, our fastest protocol takes merely 0.024 seconds to compute a match, but even the slowest one takes no more than 0.12 seconds. The communication overhead of our protocols is very small too. The passive and actively secure protocols (with some leakage) need to exchange just 16.5KB and 27.8KB of data, respectively. The first message is designed to be reusable and, if sent in advance, would cut the overhead down to just 0.5KB and 0.8KB, respectively.

Event date: 7 June to 11 June 2021
Submission deadline: 8 January 2021
Notification: 22 February 2021

Proof of Work (PoW) protocols, originally proposed to circumvent DoS and email spam attacks, are now at the heart of the majority of recent cryptocurrencies. Current popular PoW protocols are based on hash puzzles. These puzzles are solved via a brute force search for a hash output with particular properties, such as a certain number of leading zeros. By considering the hash as a random function, and fixing a priori a sufficiently large search space, Grover's search algorithm gives an asymptotic quadratic advantage to quantum machines over classical machines. In this paper, as a step towards a fuller understanding of post quantum blockchains, we propose a PoW protocol for which quantum machines have a smaller asymptotic advantage. Specifically, for a lattice of rank \(n\) sampled from a particular class, our protocol provides as the PoW an instance of the Hermite Shortest Vector Problem (Hermite-SVP) in the Euclidean norm, to a small approximation factor. Asymptotically, the best known classical and quantum algorithms that directly solve SVP type problems are heuristic lattice sieves, which run in time \(2^{0.292n + o(n)}\) and \(2^{0.265n + o(n)}\) respectively. We discuss recent advances in SVP type problem solvers and give examples of where the impetus provided by a lattice based PoW would help explore often complex optimization spaces.

The random oracle model (ROM) enjoys widespread popularity, mostly because it tends to allow for tight and conceptually simple proofs where provable security in the standard model is elusive or costly. While being the adequate replacement of the ROM in the post-quantum security setting, the quantum-accessible random oracle model (QROM) has thus far failed to provide these advantages in many settings. In this work, we focus on adaptive reprogrammability, a feature of the ROM enabling tight and simple proofs in many settings. We show that the straightforward quantum-accessible generalization of adaptive reprogramming is feasible by proving a bound on the adversarial advantage in distinguishing whether a random oracle has been reprogrammed or not. We show that our bound is tight by providing a matching attack. We go on to demonstrate that our technique recovers the mentioned advantages of the ROM in three QROM applications:

1) We give a tighter proof of security of the message compression routine as used by XMSS. 2) We show that the standard ROM proof of chosen-message security for Fiat-Shamir signatures can be lifted to the QROM, straightforwardly, achieving a tighter reduction than previously known. 3) We give the first QROM proof of security against fault injection and nonce attacks for the hedged Fiat-Shamir transform.

This paper gives the first definitions and constructions for incremental pseudo-random functions (IPRFs). The syntax is nonce based. (Algorithms are deterministic but may take as input a non-repeating quantity called a nonce.) The design approach is modular. First, given a scheme secure only in the single-document setting (there is just one document on which incremental updates are being performed) we show how to generically build a scheme that is secure in the more realistic multi-document setting (there are many documents, and they are simultaneously being incrementally updated). Then we give a general way to build an IPRF from (1) an incremental hash function with weak collision resistance properties and (2) a symmetric encryption scheme. (This adapts the classic Carter-Wegman paradigm used to build message authentication schemes in the non-incremental setting.) This leads to many particular IPRFs. Our work has both practical and theoretical motivation and value: Incremental PRFs bring the benefits of incrementality to new applications (such as incremental key derivation), and the movement from randomized or stateful schemes to nonce based ones, and from UF (unforgeability) to PRF security, bring incremental symmetric cryptography up to speed with the broader field of symmetric cryptography itself.

The six infinite families of power APN functions are among the oldest known instances of APN functions, and it has been conjectured in 2000 that they exhaust all possible power APN functions. Another long-standing open problem is that of the Walsh spectrum of the Dobbertin power family, which is the only one among the six families for which it remains unknown. In this paper, we derive alternative representations for functions from the infinite APN monomial families, with the hope that this will pave the way for further progress in this area. More concretely, we show how the Niho, Welch, and Dobbertin functions can be represented as the composition $x^i \circ x^{1/j}$ of two power functions, and prove that our representations are the simplest possible in the sense that no two power functions of lesser algebraic degree can produce the same composition. We also investigate compositions of the form $x^i \circ L \circ x^{1/j}$ for a linear polynomial $L$, and computationally determine all APN functions of this form for $n \le 9$ and for $L$ with coefficients in $\mathbb{F}_2$ in order to confirm that our theoretical constructions exhaust all possible cases. We present some observations and computational data on power functions with exponent of the form $\sum_{i = 1}^{k-1} 2^{2ni} - 1$, which can be seen as generalizations of both the inverse and the Dobbertin APN families. Finally, we present our computational data on the Walsh coefficients of the Dobbertin function over $\F$ for $n \le 35$, and conjecture the exact form of its Walsh spectrum.