International Association
for Cryptologic Research

Research Internships at Microsoft provide a dynamic environment for research careers with a network of world-class research labs led by globally-recognized scientists and engineers. Our researchers and engineers pursue innovation in a range of scientific and technical disciplines to help solve complex challenges in diverse fields, including computing, healthcare, economics, and the environment.

Digital identities are foundational to the modern web and to the many services enabled by various cloud providers. The Cryptography and Privacy Research Group at Microsoft Research, Redmond, is creating new privacy and transparency technologies for the digital identity ecosystem, with the goal of giving users more control over their identity and visibility into its usage. We are looking for a research intern for the spring of 2022 to work with us on privacy-preserving and auditable data structures and applications to future digital identity ecosystems.

More information and application at https://careers.microsoft.com/us/en/job/1177611/Research-Intern-Privacy-and-Cryptography

Closing date for applications:

Contact: Kim Laine (kim.laine@microsoft.com) or Esha Ghosh (esha.ghosh@microsoft.com)

We are looking for a Research Associate (PostDoc) in Secure & Privacy-preserving AI Models to join our ambitious EnnCore (https://enncore.github.io/) project.

You will enjoy designing, developing and evaluating novel AI models (deep neural networks) that are privacy-preserving and robust against attacks. The project will involve the continuous interaction with experts in explainable AI and formal software verification. You will also have the opportunity to build use cases and to collaborate with domain experts in areas such as cancer research and energy trading. You will design, develop and evaluate new models in the context of their accuracy, privacy-protection and robustness. This position may include research on a diverse set of techniques such as federated learning, homomorphic encryption, multiparty computation and adversarial methods. The post is initially for one year, with the possibility for extensions.

You should have a PhD or equivalent in Computer Science or a closely related field together with a track record of international publications in applied machine learning or secure computation. Examples of fields of interests are:

(1) Federated Learning
(2) Homomorphic Encryption
(3) Secure Multiparty Computation
(4) Differential Privacy
(5) Safety Mechanisms in AI Systems
(6) Adversarial Methods

Closing date for applications:

Contact: Dr Mustafa A. Mustafa
mustafa.mustafa@manchester.ac.uk

More information: https://www.jobs.manchester.ac.uk/displayjob.aspx?jobid=21038

Heliax is looking for a cryptographer & researcher interested in zero-knowledge cryptographic protocols and their application to distributed ledger technology to work with us to design, evaluate, and implement zero-knowledge proof constructions such as zkSNARKs and zkSTARKs, distributed cryptographic protocols such as threshold encryption and distributed key generation, and cryptographic primitives such as elliptic curves and hash functions, then put this cryptography into practice in order to realise privacy and scalability capabilities required by the next generation of blockchain networks. This role offers the chance to work closely with a small team on compelling cross-disciplinary problems in theoretical computer science, cryptography, game theory, economics, and systems design, and enjoy a high degree of independence in working conditions and task prioritization.

Closing date for applications:

Contact: jobs@heliax.dev

More information: https://heliax.dev/jobs/zero-knowledge-cryptographer-protocol-developer/

Shantanu Sharma, Assistant Professor @ Computer Science at NJIT, has multiple fully funded Ph.D. positions in the area of databases, secure data processing, IoT, cloud/edge computing, blockchain, and secure model learning. Webpage: https://web.njit.edu/~ss797/

Details: NJIT is a Rank 1 Research University, situated in New York Metropolitan area, and is about 7 miles away from the beautiful New York City. New York Metropolitan area is a key part of the US and is the hub of several major tech and research companies. The qualified candidates will have opportunities for research internships and joint projects with lead-industrial companies.
The position is looking for highly motivated graduate as well as undergraduate students to explore, design, and implement algorithms for databases, secure computing, IoT, blockchain, and machine learning. Topics are as follows:
1. GDPR compliance trustworthy database systems
a. The implication of privacy laws in database systems
b. Design of new modules for GDPR compliance secure databases
2. Trustworthy data-driven systems
a. Application of blockchains in data-driven systems
b. Applications of security techniques in data-driven system pipeline
3. Scalable and trustworthy database processing
a. Use of encryption and secret-sharing techniques
b. Use of secure hardware
Outcome: The work will expose the student to novel data management algorithms, programming with secure hardware (Intel SGX), cluster computing frameworks such as MapReduce and Spark, and the basics of secure computing using cryptographic techniques.

Requirements:
1. You will need to be highly enthusiastic, learner, and also be interested in coding/prototyping algorithms and systems
2. Adequate knowledge of algorithms, programming, and relational database systems
3. Knowledge of Java, SQL, and C/C++
4. You must be an Undergraduate/Master student in computer science or a related field

Closing date for applications:

Contact: Shantanu Sharma shantanu[DOT]sharma[AT]njit[DOT]edu Please send your CV and other information (e.g., GitHub account, sample projects, etc.) to: Shantanu Sharma

More information: https://web.njit.edu/~ss797/

The Institute of Information Security at University of Stuttgart offers a

fully-funded Postdoc position in formal verification.

The successful candidate is expected to work on tool-supported formal verification of security-critical systems and security protocols.

The position is available immediately with an internationally competitive salary (German public salary scale TV-L E13 or TV-L E14, depending on the candidate's qualification, ranging from about 4.600 Euro to 6.200 Euro monthly gross salary). The appointment period follows the German Wissenschaftszeitvertragsgesetz (WissZeitVg), ranging from one year to up to six years.

The Institute of Information Security offers a creative international environment for top-level international research in Germany's high-tech region.

The successful candidate should have a Ph.D. (or should be very close to completion thereof) in Computer Science, Mathematics, Information Security, or a related field. We value strong analytical skills and

• solid knowledge of logic, proofs and/or formal verification techniques (Theorem Proving, Type Checking, etc.),
• solid programming experience.

Knowledge in security is not required, but a plus. Knowledge of German is not required.

See https://www.sec.uni-stuttgart.de/institute/job-openings/ for details of how to apply.

The deadline for applications is

October 31st, 2021.

Late applications will be considered until the position is filled.

Closing date for applications:

Contact: Prof. Dr. Ralf Küsters
University of Stuttgart
Institute of Information Security
ralf.kuesters@sec.uni-stuttgart.de

More information: https://www.sec.uni-stuttgart.de/institute/job-openings/

The goal of anonymous whistleblowing is to publicly disclose a message while at the same time hiding the identity of the sender in a way that even if suspected of being the sender, this cannot be proven. While many solutions to this problem have been proposed over the years, they all require some form of interaction with trusted or non-colluding parties. In this work, we ask whether this is fundamentally inherent. We put forth the notion of anonymous transfer as a primitive allowing to solve this problem without relying on any participating trusted parties.

We initiate the theoretical study of this question, and derive negative and positive results on the existence of such a protocol. We refute the feasibility of asymptotically secure anonymous transfer, where the message will be received with overwhelming probability while at the same time the identity of the sender remains hidden with overwhelming probability. On the other hand, resorting to fine-grained cryptography, we provide a heuristic instantiation (assuming ideal obfuscation) which guarantees that the message will be correctly received with overwhelming probability and the identity of the sender leaks with vanishing probability. Our results provide strong foundations for the study of the possibility of anonymous communications through authenticated channels, an intriguing goal which we believe to be of fundamental interest.

Leakage-resilient authenticated encryption (AE) schemes received considerable attention during the previous decade. Two core security models of bounded and unbounded leakage have evolved, where the latter has been motivated in a very detailed and practice-oriented manner. In that setting, designers often build schemes based on (tweakable) block ciphers due to the small state size, such as the recent two-pass AE scheme TEDT from TCHES 1/2020. TEDT is interesting due to its high security guarantees of O(n - log(n^2))-bit integrity under leakage and similar AE security in the black-box setting. Though, a detail limited it to provide only n/2-bit privacy under leakage. In this work, we extend TEDT to TEDT2 in three aspects with the help of a tweakable block cipher with a 3n-bit tweakey: we (1) adopt the idea from the design team of Romulus of replacing TEDT's previous internal hash function with Naito's MDPH, (2) move the nonce from the hash to the tag-generation function both for more efficiency, and (3) strengthen the security of the encryption to obtain beyond-birthday-bound security also under leakage.

The NIST selection process for standardizing Post-Quantum Cryptography Mechanisms is currently running. Many papers already studied their theoretical security, but the resistance in deployed device has not been much investigated so far. In particular, fault attack is a serious threat for algorithms implemented in embedded devices. One particularly powerful technique is to use safe-error attacks. Such attacks exploit the fact that a specific fault may or may not lead to a faulty output depending on a secret value. In this paper, we investigate the resistance of various Post-Quantum candidates algorithms against such attacks.

We propose a new hard problem, called the Embedded Multilayer Equations (eMLE) problem in this paper. An example of eMLE, with one secret variable x and three layers, is given below.

6268 = 57240 * x + (1248 * x + (9 * x mod 16) mod 2053) mod 65699

In this example, the eMLE problem is to find x from the above equation. eMLE in this paper has the same number of variables and equations. The hardness of eMLE problem lies in its layered structure. Without knowing the eMLE value of lower layer (i.e., the layer with modulus 2053), the top layer (i.e., the layer with modulus 65699) has many candidate solutions; the adversary has to search the solution space for a few valid ones. A lower-bound for the number of searches has been proven in the paper, together with the expected number of valid solutions. The hardness of eMLE can be increased by adding more layers, without changing the number of variables and equations; no existing NP-complete problems have this feature. Over the hardness of eMLE, a post-quantum signature scheme, eMLE-Sig, is constructed. Compared with all existing signature schemes (conventional and post-quantum), eMLE-Sig might be the simplest to understand, analyze, instantiate, and implement. At the security level above 128 bits, five configurations are provided; all of them have keys and signatures smaller than RSA keys and signatures (above 380 bytes) at the 128-bit security level. The smallest configuration is with two variables and three layers, having 84.1/52.2 bytes for private/public key and 168.4 bytes for signatures.

A comparison of two encrypted numbers is an important operation needed in many machine learning applications, for example, decision tree or neural network inference/training. An efficient instantiation of this operation in the context of fully homomorphic encryption (FHE) can be challenging, especially when a relatively high precision is sought. The conventional FHE way of evaluating the comparison operation, which is based on the sign function evaluation using FHEW/TFHE bootstrapping, can only support very small precision (practically limited to 5 bits or so). For higher precision, the runtime complexity scales linearly with the ciphertext (plaintext) modulus (i.e., exponentially with the modulus bit size). We propose sign function evaluation algorithms that scale logarithmically with the ciphertext (plaintext) modulus, enabling the support of large-precision comparison in practice. Our sign evaluation algorithms are based on an iterative use of homomorphic floor function algorithms, which are also derived in our work. Further, we generalize our procedures for floor function evaluation to arbitrary function evaluation, which can be used to support both small plaintext moduli (directly) and larger plaintext moduli (by using a homomorphic digit decomposition algorithm, also suggested in our work). We implement all these algorithms using the PALISADE lattice cryptography library, introducing several implementation-specific optimizations along the way, and discuss our experimental results.

Recent exciting breakthroughs, starting with the work of Chattopadhyay and Zuckerman (STOC 2016) have achieved the first two-source extractors that operate in the low min-entropy regime. Unfortunately, these constructions suffer from non-negligible error, and reducing the error to negligible remains an important open problem. In recent work, Garg, Kalai, and Khurana (GKK, Eurocrypt 2020) investigated a meaningful relaxation of this problem to the computational setting, in the presence of a common random string (CRS). In this relaxed model, their work built explicit two-source extractors for a restricted class of unbalanced sources with min-entropy $n^{\gamma}$ (for some constant $\gamma$) and negligible error, under the sub-exponential DDH assumption.

In this work, we investigate whether computational extractors in the CRS model be applied to more challenging environments. Specifically, we study network extractor protocols (Kalai et al., FOCS 2008) and extractors for adversarial sources (Chattopadhyay et al., STOC 2020) in the CRS model. We observe that these settings require extractors that work well for balanced sources, making the GKK results inapplicable. We remedy this situation by obtaining the following results, all of which are in the CRS model and assume the sub-exponential hardness of DDH.

- We obtain ``optimal'' computational two-source and non-malleable extractors for balanced sources: requiring both sources to have only poly-logarithmic min-entropy, and achieving negligible error. To obtain this result, we perform a tighter and arguably simpler analysis of the GKK extractor. - We obtain a single-round network extractor protocol for poly-logarithmic min-entropy sources that tolerates an optimal number of adversarial corruptions. Prior work in the information-theoretic setting required sources with high min-entropy rates, and in the computational setting had round complexity that grew with the number of parties, required sources with linear min-entropy, and relied on exponential hardness (albeit without a CRS). - We obtain an ``optimal'' {\em adversarial source extractor} for poly-logarithmic min-entropy sources, where the number of honest sources is only 2 and each corrupted source can depend on either one of the honest sources. Prior work in the information-theoretic setting had to assume a large number of honest sources.

Fully Homomorphic Encryption (FHE) gives the ability to evaluate any function over encrypted data. However, despite numerous improvements during the last decade, the computational overhead caused by homomorphic computations is still very important. As a consequence, optimizing the way of performing the computations homomorphically remains fundamental. Several popular FHE schemes such as BGV and BFV encode their data, and thus perform their computations, in finite fields. In this work, we study and exploit algebraic relations occurring in prime characteristic allowing to speed-up the homomorphic evaluation of several functions over prime fields.

More specifically we give several examples of unary functions: "modulo", "is power of $b$" and "Hamming weight" and "Mod2'" whose homomorphic evaluation complexity over $\mathbb{F}_p$ can be reduced from the generic bound $\sqrt{2p} + \mathcal{O}(\log(p))$ homomorphic multiplications, to $\sqrt{p} + \mathcal{O}(\log(p))$, $\mathcal{O}(\log (p))$, $\mathcal{O}(\sqrt{p/\log (p)})$ and $\mathcal{O}(\sqrt{p/(\log (p))})$ respectively. Additionally we provide a proof of a recent claim regarding the structure of the polynomial interpolation of the "less-than" bivariate function which confirms that this function can be evaluated in $2p-6$ homomorphic multiplications instead of $3p-5$ over $\mathbb{F}_p$ for $p\geq 5$.

In this work, we study what minimal sets of assumptions suffice for constructing indistinguishability obfuscation ($i\mathcal{O}$). We prove:

{\bf Theorem}(Informal): Assume sub-exponential security of the following assumptions:

- the Learning Parity with Noise ($\mathsf{LPN}$) assumption over general prime fields $\mathbb{F}_p$ with polynomially many $\mathsf{LPN}$ samples and error rate $1/k^\delta$, where $k$ is the dimension of the $\mathsf{LPN}$ secret, and $\delta>0$ is any constant;

- the existence of a Boolean Pseudo-Random Generator ($\mathsf{PRG}$) in $\mathsf{NC}^0$ with stretch $n^{1+\tau}$, where $n$ is the length of the $\mathsf{PRG}$ seed, and $\tau>0$ is any constant;

- the Decision Linear ($\mathsf{DLIN}$) assumption on symmetric bilinear groups of prime order.

Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists. Further, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits.}

This removes the reliance on the Learning With Errors (LWE) assumption from the recent work of [Jain, Lin, Sahai STOC'21]. As a consequence, we obtain the first fully homomorphic encryption scheme that does not rely on any lattice-based hardness assumption. Our techniques feature a new notion of randomized encoding called Preprocessing Randomized Encoding (PRE) that, essentially, can be computed in the exponent of pairing groups. When combined with other new techniques, PRE gives a much more streamlined construction of $\iO$ while still maintaining reliance only on well-studied assumptions.

Lossless compression algorithms such as DEFLATE strive to reliably process arbitrary inputs, while achieving compressed sizes as low as possible for commonly encountered data inputs. It is well-known that it is mathematically impossible for a compression algorithm to simultaneously achieve non-trivial compression on some inputs (i.e. compress these inputs into strictly shorter outputs) and to never expand any other input (i.e. guaranteeing that all inputs will be compressed into an output which is no longer than the input); this is a direct application of the "pigeonhole principle". Despite their mathematical impossibility, we show in this paper how to build such paradoxical compression and decompression algorithms, with the aid of some tools from cryptography, notably verifiable delay functions, and, of course, by slightly cheating.

A natural and recurring idea in the knapsack/lattice cryptography literature is to start from a lattice with remarkable decoding capability as your private key, and hide it somehow to make a public key. This is also how the code-based encryption scheme of McEliece (1978) proceeds.

This idea has never worked out very well for lattices: ad-hoc approaches have been proposed, but they have been subject to ad-hoc attacks, using tricks beyond lattice reduction algorithms. On the other hand the framework offered by the Short Integer Solution (SIS) and Learning With Errors (LWE) problems, while convenient and well founded, remains frustrating from a coding perspective: the underlying decoding algorithms are rather trivial, with poor decoding performance.

In this work, we provide generic realizations of this natural idea (independently of the chosen remarkable lattice) by basing cryptography on the lattice isomorphism problem (LIP). More specifically, we provide:

- a worst-case to average-case reduction for search-LIP and distinguish-LIP within an isomorphism class, by extending techniques of Haviv and Regev (SODA 2014). - a zero-knowledge proof of knowledge (ZKPoK) of an isomorphism. This implies an identification scheme based on search-LIP. - a key encapsulation mechanism (KEM) scheme and a hash-then-sign signature scheme, both based on distinguish-LIP.

The purpose of this approach is for remarkable lattices to improve the security and performance of lattice-based cryptography. For example, decoding within poly-logarithmic factor from Minkowski's bound in a remarkable lattice would lead to a KEM resisting lattice attacks down to poly-logarithmic approximation factor, provided that the dual lattice is also close to Minkowski's bound. Recent works have indeed reached such decoders for certain lattices (Chor-Rivest, Barnes-Sloan), but these do not perfectly fit our need as their duals have poor minimal distance.

By exploiting the inherent randomness used by certain digital signature protocols, subliminal channels can subvert these protocols without degrading their security. Due to their nature, these channels cannot be easily detected by an outside observer. Therefore, they pose a severe challenge for protocol designers. More precisely, designers consider certain assumptions implicitly, but in reality these assumptions turn out to be false or cannot be enforced or verified. In this paper we exemplify exactly such a situation by presenting several subliminal channels with a small capacity in Zhang et al. and Dong et al.'s subliminal-free signature protocols.

Two common variations of ECDSA signatures are additive key derivation and presignatures. Additive key derivation is a simple mechanism for deriving many subkeys from a single master key, and is already widely used in cryptocurrency applications with the Hierarchical Deterministic Wallet mechanism standardized in Bitcoin Improvement Proposal 32 (BIP32). Because of its linear nature, additive key derivation is also amenable to efficient implementation in the threshold setting. With presignatures, the secret and public nonces used in the ECDSA signing algorithm are precomputed. In the threshold setting, using presignatures along with other precomputed data allows for an extremely efficient ``online phase'' of the protocol. Recent works have advocated for both of these variations, sometimes combined together. However, somewhat surprisingly, we are aware of no prior security proofs of either of these variations in isolation, let alone in combination with one another.

In this paper, we provide a thorough analysis of these variations, both in isolation and in combination. Our analysis is in the generic group model (GGM). Importantly, we do not modify ECDSA or weaken the standard notion of security in any way. Of independent interest, we also present a version of the GGM that is specific to elliptic curves. This EC-GGM better models some of the idiosyncrasies (such as the conversion function and malleability) of ECDSA. In addition to this analysis, we report security weaknesses in these variations that apparently have not been previously reported. For example, we show that when both variations are combined, there is a cube-root attack on ECDSA, which is much faster than the best known, square-root attack on plain ECDSA. We also present two mitigations against these weaknesses: re-randomized presignatures and homogeneous key derivation. Each of these mitigations is very lightweight, and when used in combination, the security is essentially the same as that of plain ECDSA (in the EC-GGM).

Evaluating a block cipher’s strength against differential or linear cryptanalysis can be a difficult task. Several approaches for finding the best differential or linear trails in a cipher have been proposed, such as using mixed integer linear programming or SAT solvers. Recently a different approach was suggested, modelling the problem as a staged, acyclic graph and exploiting the large number of paths the graph contains. This paper follows up on the graph-based approach and models the prob- lem via compressed right-hand side equations. The graph we build contains paths which represent differential or linear trails in a cipher with few active S-boxes. Our method incorporates control over the memory usage, and the time complexity scales linearly with the number of rounds of the cipher being analysed. The proposed method is made available as a tool, and using it we are able to find differential trails for the Klein and Prince ciphers with higher probabilities than previously published.

The majority of recently demonstrated Deep-Learning Side-Channel Attacks (DLSCAs) use neural networks trained on a segment of traces containing operations only related to the target subkey. However, when the number of training traces are restricted such as in this paper only 5K power traces, deep-learning models always suffer from underfitting since the insufficient training data. One data-level solution is called data augmentation, which is to use the additional synthetically modified traces to act as a regularizer to provide a better generalization capacity for deep-learning models. In this paper, we propose a cross-subkey training approach which acts as a trace augmentation. We train deep-learning models not only on a segment of traces containing the SBox operation of the target subkey of AES-128, but also on segments for other 15 subkeys. Experimental results show that the accuracy of the subkey combination training model is 28.20% higher than that of the individual subkey training model on trajectories captured in the microcontroller implementation of the STM32F3 with AES-128. At the same time, the number of traces that need to be captured when the model is trained is greatly reduced, demonstrating the effectiveness and practicality of the method.

Most cryptography is based on assumptions such as factoring and discrete log, which assume an adversary has bounded computational power. With the recent development in quantum computing as well as concern with everlasting security, there is an interest in coming up with information-theoretic constructions in the bounded storage model. In this model, an adversary is computationally unbounded but has lim- ited space. Past works have constructed schemes such as key exchange and bit commitment in this model. In this work, we expand the function- alities further by building a semi-honest MPC protocol in the bounded storage model. We use the hardness of the parity learning problem (recently shown by Ran Raz (FOCS 16) without any cryptographic assump- tions) to prove the security of our construction, following the work by Guan and Zhandry (EUROCRYPT 19).