International Association
for Cryptologic Research

Huawei German Research Center in Munich is responsible for advanced technical research, architecture evolution design and strategic technical planning. The Cyber Security and Privacy Lab is developing cutting-edge technologies, which are designed for supporting data protection and accountability in the Cloud, IoT and cloud-based networks.

To support our research activities, we are looking for an enthusiastic and highly motivated PhD student Security &Trust - Connected, Cooperative, Automated Mobility (m/f/d)

Research Topic

• Perform research and develop new solutions for Trust Management in the Next-Generation CCAM technologies.
• Contribute to new mechanisms for assessing dynamic trust relationship based on Zero Trust and Subjective Logic.
• Define a trust model and trust reasoning framework based on which involved entities can establish trust for cooperatively executing safety-critical functions.

Responsibilities

• Contribute to the research and development of technologies in the upcoming domain of Connected, Cooperative and Automated Mobility (CCAM).
• Being involved in international initiatives including industry groups such as 5GAA, Gaia-X, DIF and Horizon Europe research projects.

Your Profile

• Completed master studies (or equivalent) in computer science, information technology, electrical engineering, or mathematics;
• Exposure and understanding of data protection and security development technologies;
• Good programming skill;
• Must be eligible to work in the European Union to be considered for this position;
• Fluent in English;

Closing date for applications:

Contact: Ioannis Krontiris

More information: https://huaweiresearchcentergermanyaustria.teamtailor.com/jobs/1732783-phd-student-security-trust-connected-cooperative-automated-mobility-m-f-d

We have open positions for a PhD student and a postdoc in the area of symmetric cryptography in the Digital Security group at Radboud University in Nijmegen. The positions cover different topics related to the design of modes of use, and their security analysis in various models.

The Digital Security Group of Radboud University is one of the leading groups in computer security in The Netherlands and Europe, and one of the pioneers in permutation-based crypto and corresponding leakage-resilient modes.

The successful candidate should ideally have a master in Computer Science, Mathematics, or Electrical engineering. Familiarity with symmetric cryptography is required. Applications will be considered until the positions are filled.

Closing date for applications:

Contact: To apply, please send the following documents to b.mennink (at) cs.ru.nl, with the subject "PhD position in cryptography":
- a motivation letter
- your cv
- your master diploma certificate (scanned)
- transcript of the courses you took (including grades)
- up to 3 references

At ASIACRYPT 2012, Sasaki et al. introduced the guess-and-determine approach to extend the meet-in-the-middle (MITM) preimage attack. At CRYPTO 2021, Dong et al. proposed a technique to derive the solution spaces of nonlinear constrained neutral words in the MITM preimage attack. In this paper, we try to combine these two techniques to further improve the MITM preimage attacks. Based on the previous MILP-based automatic tools for MITM attacks, we introduce new constraints due to the combination of guess-and-determine and nonlinearly constrained neutral words to build a new automatic model. As a proof of work, we apply it to the Russian national standard hash function Streebog, which is also an ISO standard. We find the first 8.5-round preimage attack on Streebog-512 compression function and the first 7.5-round preimage attack on Streebog-256 compression function. In addition, we give the 8.5-round preimage attack on Streebog-512 hash function. Our attacks extend the best previous attacks by one round. We also improve the time complexity of the 7.5-round preimage attack on Streebog-512 hash function and 6.5-round preimage attack on Streebog-256 hash function.

In this paper we describe a symmetric key algorithm that offers an unprecedented grade of confidentiality. Based on the uniqueness of the modular multiplicative inverse of a positive integer a modulo n and on its computability in a polynomial time, this non-deterministic cipher can easily and quickly handle keys of millions or billions of bits that an attacker does not even know the length of. The algorithm’s primary key is the modulo, while the ciphertext is given by the concatenation of the modular inverse of blocks of plaintext whose length is randomly chosen within a predetermined range. In addition to the full specification, we present a working implementation of it in Julia Programming Language, accompanied by real examples of encryption and decryption.

Recent works on interactive zero-knowledge (ZK) protocols provide a new paradigm with high efficiency and scalability. However, these protocols suffer from high communication overhead, often linear to the circuit size. In this paper, we proposed two new ZK protocols with communication sublinear to the circuit size, while maintaining a similar level of computational efficiency. -- We designed a ZK protocol that can prove $B$ executions of any circuit $C$ in communication $O(B + |C|)$ field elements (with free addition gates), while the best prior work requires a communication of $O(B|C|)$ field elements. Our protocol is enabled by a new tool called as information-theoretic polynomial authentication code, which may be of independent interest. -- We developed an optimized implementation of this protocol which shows high practicality. For example, with $B=2048$, $|C|=2^{20}$, and under 50 Mbps bandwidth and 16 threads, QuickSilver, a state-of-the-art ZK protocol based on vector oblivious linear evaluation (VOLE), can only prove $0.78$ million MULT gates per second (mgps) and send one field element per gate; our protocol can prove $14$ mgps ($18\times$ improvement) and send $0.0064$ field elements per gate ($156\times$ improvement) under the same hardware configuration. -- Extending the above idea, we constructed a ZK protocol that can prove a single execution of any circuit $C$ in communication $O(|C|^{3/4})$. This is the first ZK protocol with sublinear communication for an arbitrary circuit in the VOLE-based ZK family.

The protection of cryptographic software implementations against power-analysis attacks is critical for applications in embedded systems. A commonly used algorithmic countermeasure against these attacks is masking, a secret-sharing scheme that splits a sensitive computation into computation on multiple random shares. In practice, the security of masking schemes relies on several assumptions that are often violated by microarchitectural side-effects of CPUs. Many past works address this problem by studying these leakage effects and building corresponding leakage models that can then be integrated into a software verification workflow. However, these models have only been derived empirically, putting the otherwise rigorous security statements made with verification in question.

We solve this problem in two steps. First, we introduce a contract layer between the (CPU) hardware and the software that allows the specification of microarchitectural side-effects on masked software in an intuitive language. Second, we present a method for proving the correspondence between contracts and CPU netlists to ensure the completeness of the specified leakage models. Then, any further security proofs only need to happen between software and contract, which brings benefits such as reduced verification runtime, improved user experience, and the possibility of working with vendor-supplied contracts of CPUs whose design is not available on netlist-level due to IP restrictions. We apply our approach to the popular RISC-V IBEX core, provide a corresponding formally verified contract, and describe how this contract could be used to verify masked software implementations.

Fingerprinting is a commonly used technique to provide accurate localization for indoor areas, where global navigation satellite systems, such as GPS and Galileo, cannot function or are not precise enough. Although fingerprint-based indoor localization has gained wide popularity, existing solutions that preserve privacy either rely on non-colluding servers or have high communication which hinder deployment.

In this work we present FAPRIL, a privacy-preserving indoor localization scheme, which takes advantage of the latest secure two-party computation protocol improvements. We can split our scheme into two parts: an input independent setup phase and an online phase. We concentrate on optimizing the online phase for mobile clients who run on a mobile data plan and observe that recurring operands allow to optimize the total communication overhead even further. Our observation can be generalized, e.g., to improve multiplication of Arithmetic secret shared matrices. We implement FAPRIL on mobile devices and our benchmarks over a simulated LTE network show that the online phase of a private localization takes under 0.15 seconds with less than 0.20 megabytes of communication even for large buildings. The setup phase, which can be pre-computed, depends heavily on the setting but stays in the range 0.28 - 4.14 seconds and 0.69 - 16.00 megabytes per localization query. The round complexity of FAPRIL is constant for both phases.

Side-channel resilience is a crucial feature when assessing whether a post-quantum cryptographic proposal is sufficiently mature to be deployed. In this paper, we propose a generic and efficient adaptive approach to improve the sample complexity (i.e., the required number of traces) of plaintext-checking (PC) oracle-based side-channel attacks (SCAs), a major class of key recovery chosen-ciphertext SCAs on lattice-based key encapsulation mechanisms. This new approach is preferable when the constructed PC oracle is imperfect, which is common in practice, and its basic idea is to design new detection codes that can determine erroneous positions in the initially recovered secret key. These secret entries are further corrected with a small number of additional traces. This work benefits from the generality of PC oracle and thus is applicable to various schemes and implementations. We instantiated the proposed generic attack framework on Kyber512 and fully implemented this attack instance. Through extensive computer simulations and also a real-world experiment with electromagnetic (EM) leakages from an ARM-Cortext-M4 platform, we demonstrated that the newly proposed attack could greatly improve the state-of-the-art in terms of the required number of traces. For instance, the new attack requires only 41% of the EM traces needed in a majority-voting attack in our experiments, where the raw oracle accuracy is fixed.

The paper concerns several theoretical aspects of oriented supersingular l-isogeny volcanoes and their relationship to closed walks in the supersingular l-isogeny graph. Our main result is a bijection between the rims of the union of all oriented supersingular l-isogeny volcanoes over $\overline{\mathbb{F}}_p$ (up to conjugation of the orientations), and isogeny cycles (non-backtracking closed walks which are not powers of smaller walks) of the supersingular l-isogeny graph modulo p. The exact proof and statement of this bijection are made more intricate by special behaviours arising from extra automorphisms and the ramification of p in certain quadratic orders. We use the bijection to count isogeny cycles of given length in the supersingular l-isogeny graph exactly as a sum of class numbers, and also give an explicit upper bound by estimating the class numbers.

-

We formalize and study the problem of distributed shuffling in adversarial environments. In this setting, there are $m$ shufflers that have access to a public bulletin board that stores a vector $(c_1, \dots, c_n)$ of re-randomizable commitments. The shufflers repeatedly read $k$ of the $n$ commitments, with $k$ potentially much smaller than $n$, and shuffle them. An adversary has the ability to initially corrupt and then track some of the commitments throughout the shuffles and can adaptively corrupt a bounded number of shufflers in every single round. The goal of the distributed shuffling protocol is to hide the output locations of commitments that are not corrupted by the adversary.

We present and analyze a protocol that solves this problem with essentially optimal shuffling complexity. As an exemplary data point, our protocol can shuffle a list of length $n$ with shuffles of size $k$, where $k \in \Omega(\lg^2 n)$, in the presence of an adversary that can corrupt $4n/5$ many shufflers in each round and can corrupt $4n/5$ commitments in the input vector. Our $m$-party shuffling protocol with $m \in \Omega(n/k)$ terminates in $\mathcal{O}(\lg n)$ rounds. We provide numerical benchmarks that validate our theoretically proven guarantees and in fact show that the number of rounds is not just theoretically, but also concretely small.

Our shuffling protocol can either improve efficiency or lead to more secure solutions in multiple research domains, such as the design of mix-nets, single secret leader election protocols, and electronic voting.

Continuous group key agreement (CGKA) allows a group of users to maintain a continuously updated shared key in an asynchronous setting where parties only come online sporadically and their messages are relayed by an untrusted server. CGKA captures the basic primitive underlying group messaging schemes. Current solutions including TreeKEM (``Message Layer Security'' (MLS) IETF draft) cannot handle concurrent requests while retaining low communication complexity. The exception being CoCoA, which is concurrent while having extremely low communication complexity (in groups of size $n$ and for $m$ concurrent updates the communication per user is $\log(n)$, i.e., independent of $m$). The main downside of CoCoA is that in groups of size $n$, users might have to do up to $\log(n)$ update requests to the server to ensure their (potentially corrupted) key material has been refreshed. We present a new ``fast healing'' concurrent CGKA protocol, called Coffee, where users will heal after at most $\log(t)$ requests, with $t$ being the number of corrupted users. Our new protocol is particularly interesting to realize decentralized group messaging, where protocol messages (add/remove/update) are being posted on a blockchain rather than sent to a server. In this setting, concurrency is crucial once requests are more frequent than blocks. Our new protocol significantly outperforms (the only alternative with sub-linear communication and PCS) CoCoA in this setting: it heals much faster ($\log(t)$ vs. $\log(n)$ rounds). The communication per round and user is $m\cdot\log(n)$, but in this setting -- where there is no server who can craft specific messages to users depending on their position in the tree -- CoCoA requires the same communication.

Pseudorandom number generators with input (PRNGs) are cryptographic algorithms that generate pseudorandom bits from accumulated entropic inputs (e.g., keystrokes, interrupt timings, etc.). This paper studies in particular PRNGs that are secure against premature next attacks (Kelsey et al., FSE '98), a class of attacks leveraging the fact that a PRNG may produce an output (which could be seen by an adversary!) before enough entropy has been accumulated. Practical designs adopt either unsound entropy-estimation methods to prevent such attacks (as in Linux's /dev/random) or sophisticated pool-based approaches as in Yarrow (MacOS/FreeBSD) and Fortuna (Windows). The only prior theoretical study of premature next attacks (Dodis et al., Algorithmica '17) considers either a seeded setting or assumes a constant entropy rate, and thus falls short of providing and validating practical designs. Assuming the availability of random seed is particularly problematic, first because this requires us to somehow generate a random seed without using our PRNG, but also because we must ensure that the entropy inputs to the PRNG remain independent of the seed. Indeed, all practical designs are seedless. However, prior works on seedless PRNGs (Coretti et al., CRYPTO '19; Dodis et al., ITC '21, CRYPTO'21) do not consider premature next attacks. The main goal of this paper is to investigate the feasibility of theoretically sound seedless PRNGs that are secure against premature next attacks. To this end, we make the following contributions: -- We prove that it is impossible to achieve seedless PRNGs that are secure against premature-next attacks, even in a rather weak model. Namely, the impossibility holds even when the entropic inputs to the PRNG are independent. In particular, our impossibility result holds in settings where seedless PRNGs are otherwise possible. -- Given the above impossibility result, we investigate whether existing seedless pool-based approaches meant to overcome premature next attacks in practical designs provide meaningful guarantees in certain settings. Specifically, we show the following. * We introduce a natural condition on the entropic input and prove that it implies security of the round-robin entropy accumulation PRNG used by Windows 10, called Fortuna. Intuitively, our condition requires the input entropy ``not to vary too wildly'' within a given round-robin round. * We prove that the ``root pool'' approach (also used in Windows 10) is secure for general entropy inputs, provided that the system's state is not compromised after system startup.

Interactive arguments, and their (succinct) non-interactive and zero-knowledge counterparts, have seen growing deployment in real world applications in recent years. Unfortunately, for large and complex statements, concrete proof generation costs can still be quite expensive. While recent work has sought to solve this problem by outsourcing proof computation to a group of workers in a privacy preserving manner, current solutions still require each worker to do work on roughly the same order as a single-prover solution.

We introduce the Honest Majority Multi-Prover (HMMP) model for interactive arguments. In these arguments, we distribute prover computation among $M$ collaborating, but distrusting, provers. All provers receive the same inputs and have no private inputs, and we allow any $t < M/2$ provers to be statically corrupted before generation of public parameters, and all communication is done via an authenticated broadcast channel. In contrast with the recent works of Ozdemir and Boneh (USENIX '22) and Dayama et al. (PETS '22), our model targets prover efficiency over privacy.

We show that: (1) any interactive argument where the prover computation is suitably divisible into $M$ sub-computations can be transformed into an interactive argument in the HMMP model; and (2) arguments that are obtained via compiling polynomial interactive oracle proofs with polynomial commitment schemes admit HMMP model constructions that experience a (roughly) $1/M$ speedup over a single-prover solution. The transformation of (1) preserves computational (knowledge) soundness, zero-knowledge, and can be made non-interactive via the Fiat-Shamir transformation. The constructions of (2) showcase that there are efficiency gains in proof distribution when privacy is not a concern.

Consider the scenario that the prover and the verifier perform the zero-knowledge (ZK) proof protocol for the same statement multiple times sequentially, where each proof is modeled as a session. We focus on the problem of how to resume a ZK proof efficiently in such scenario. We introduce a new primitive called resumable honest verifier zero-knowledge proof of knowledge (resumable HVZKPoK) and propose a general construction of the resumable HVZKPoK for circuits based on the ``MPC-in-the-head" paradigm, where the complexity of the resumed session is less than that of the original ZK proofs. To ensure the knowledge soundness for the resumed session, we identify a property called extractable decomposition. Interestingly, most block ciphers satisfy this property and the cost of resuming session can be reduced dramatically when the underlying circuits are implemented with block ciphers. As a direct application of our resumable HVZKPoK, we construct a post quantum secure stateful signature scheme, which makes Picnic3 suitable for blockchain protocol. Using the same parameter setting of Picnic3, the sign/verify time of our subsequent signatures can be reduced to 3.1%/3.3% of Picnic3 and the corresponding signature size can be reduced to 36%. Moreover, by applying a parallel version of our method to the well known Cramer, Damgaard and Schoenmakers (CDS) transformation, we get a compressed one-out-of-$N$ proof for circuits, which can be further used to construct a ring signature from symmetric key primitives only. When the ring size is less than $2^4$, the size of our ring signature scheme is only about 1/3 of Katz et al.'s construction.

The Number Theoretic Transform (NTT) is a major building block in recently introduced lattice based post-quantum (PQ) cryptography. The NTT was target of a number of recently proposed Belief Propagation (BP)-based Side Channel Attacks (SCAs) . These attacks exploit the known structure of the NTT to reduce the guessing entropy after a profiled SCA by modeling the algorithm as a factor graph. Ravi et al. have proposed a number of countermeasures mitigating these attacks. They introduced three shuffling levels and one configurable masking step to counter the influence of the known structure of the NTT.

In 2021, Hamburg et al. presented a chosen-ciphertext enabled SCA improving noise-resistance. Exemplarily, using their setting, we introduce a set of tools, which reveal that a subset of the proposed shuffling countermeasures could lead to a false security perception.

Firstly, we analyze fine shuffling. We introduce a pre-processing step as well as a new factor node which we call shuffle node. Shuffle nodes allow for a modified version of belief propagation when included into a factor graph. The node iteratively learns the shuffling permutation of fine shuffling within a BP run. This allows a more noise resistant inference in the presences of mixed leakage distributions, which model the uncertainty of shuffled input or output nodes of a NTT butterfly.

Secondly, we introduce a set of tools targeting the coarse shuffling countermeasure. We expand our attacker model and describe several matching algorithms to find inter-layer connections based on shuffled measurements. Our matching algorithm allows for either mixing prior distributions according to a doubly stochastic mix matrix or to extract permutations and perform an exact un-matching of layers. We additionally discuss the usage of sub-graph inference to reduce uncertainty and improve un-shuffling of butterflies.

Based on our results, we conclude that the proposed countermeasures of Ravi et al. are powerful and counter Hamburg et al., yet could lead to a false security perception -- a powerful adversary could still launch successful attacks. We discuss on the capabilities needed to defeat shuffling in the setting of Hamburg et al. using our expanded attacker model.

Byzantine reliable broadcast (BRB) is one of the most fundamental primitives in fault-tolerant distributed computing. It is well-known that the best BRB protocol one can hope for has $O(nL+n^2)$ communication. It is unclear if this bound is achievable.

This paper provides a novel BRB protocol---BRB1, which achieves $O(nL + kn + n^2)$ communication, where $n$, $L$, and $k$ are the number of replicas, the message length, and the security parameter, respectively. Our protocol is efficient, because the only building blocks we need are threshold signatures which have been used in various Byzantine fault-tolerant (BFT) protocols (e.g., SBFT, HoneyBadgerBFT, HotStuff). Clearly, our BRB protocol is optimal at least for messages of length larger than $k$. Namely, if the length of the message to be broadcast is no less than the security parameter (e.g., 128 bit), our BRB protocol is optimal.

We describe a new secure storage scheme that facilitates deduplication. The scheme is also proved secure in the universal-composability model. It is a single server scheme, and the basic scheme does not prevent against off-line dictionary attacks if the server is compromised. However, if a global secret key is shared amongst users of the organization, and this key is never stored at the server, we also get protection against off-line dictionary attacks even if the server is compromised. The UC security model for deduplication is based on an earlier work of Liu, Asokan and Pinkas, Proc. CCS 2015. The scheme obtains additional optimization by employing the XTS-AES mode of encryption in the public random permutation model.

Another upshot of the analysis is that one can first MAC and then encrypt using XTS mode and attain authenticated encryption, avoiding the pitfalls cautioned against by Hugo Krawczyk, in the work ``How Secure is SSL?'', CRYPTO 2001.

Recent advances in fast protocols for \textit{vector oblivious linear evaluation} (VOLE) have inspired a family of new VOLE-based lightweight designated-verifier NIZK protocols (Weng et al., S\&P 2021, Baum et al., Crypto 2021, Dittmer et al., ITC 2021, Yang et al., CCS 2021). In particular, the Line-Point Zero Knowledge (LPZK) protocol of Dittmer et al.\ has the advantage of being entirely non-cryptographic given a single instance of a random VOLE correlation.

We present improvements to LPZK through the introduction of additional structure to the correlated randomness. Using an efficiently realizable variant of the VOLE correlation, we reduce the online proof size of LPZK by roughly 2x: from roughly 2 field elements per multiplication gate, or 1 element in the random oracle variant, to only 1 or $\tfrac{1}{2}$ elements respectively. In particular, we get the first practical VOLE-based NIZK that breaks the 1-element-per-multiplication barrier.

We implemented an optimized version of our protocol and compared it with other recent VOLE-based NIZK protocols. In the typical case where communication is the bottleneck, we get at least 2x performance improvement over all previous VOLE-based protocols. When prover computation is the bottleneck, we outperform all non-LPZK protocols by at least $2$-$3$x and (our optimized implementation of) LPZK by roughly 30%, obtaining a $2$-$3$x slowdown factor compared to plain circuit evaluation.

As the first Byzantine fault-tolerant (BFT) protocol with linear communication complexity, HotStuff (PODC 2019) has received significant attention. HotStuff has three round-trips for both normal case operations and view change protocols. Follow-up studies attempt to reduce the number of phases for HotStuff. These protocols, however, all give up of one thing in return for another.

This paper presents Marlin, a BFT protocol with linearity, having two phases for normal case operations and two or three phases for view changes. Marlin uses the same cryptographic tools as in HotStuff and introduces no additional assumptions. We implement a new and efficient Golang library for Marlin and HotStuff, showing Marlin outperforms HotStuff for both the common case and the view change.