International Association
for Cryptologic Research

Oblivious RAM (ORAM) is a general-purpose technique for hiding memory access patterns. This is a fundamental task underlying many secure computation applications. While known ORAM schemes provide optimal asymptotic complexity, despite extensive efforts, their concrete costs remain prohibitively expensive for many interesting applications. The current state-of-the-art practical ORAM schemes are suitable only for somewhat small memories (Square-Root ORAM or Path ORAM).

This work presents a novel concretely efficient ORAM construction based on recent breakthroughs in asymptotic complexity of ORAM schemes (PanORAMa and OptORAMa). We bring these constructions to the realm of practically useful schemes by relaxing the restriction on constant local memory size. Our design provides a factor of at least $6$ to $8$ improvement over an optimized variant of Path ORAM for a set of reasonable memory sizes (e.g., 1GB, 1TB) and with the same local memory size. To our knowledge, this is the first practical implementation of an ORAM based on the full hierarchical ORAM framework. Prior to our work, the belief was that hierarchical ORAM-based constructions were inherently too expensive in practice. We implement our design and provide extensive evaluation and experimental results.

Differential-Linear (DL) cryptanalysis is a well known cryptanalytic technique that combines differential and linear cryptanalysis. Over the years, multiple techniques were proposed to increase its strength and applicability. Two relatively recent ones are: The partitioning technique by Leurent and the use of neutral bits adapted by Beierle et al. to DL cryptanalysis.

In this paper we compare these techniques and discuss the possibility of using them together to achieve the best possible DL attacks. We study the combination of these two techniques and show that in many cases they are indeed compatible. We demonstrate the strength of the combination in two ways. First, we present the first DL attack on 4-round Xoodyak and an extension to 5-round in the related key model. We show that the attacks are possible only by using these two techniques simultaneously. In addition, using the combination of the two techniques we improve a DL attack on 9-round DES. We show that the partitioning technique mainly reduces the time complexity, and the use of neutral bits mainly reduces the data complexity, while the combination of them reduces both the time and data complexities.

Post-quantum cryptographic (PQC) algorithms, especially those based on the learning with errors (LWE) problem, have been subjected to several physical attacks in the recent past. Although the attacks broadly belong to two classes -- passive side-channel attacks and active fault attacks, the attack strategies vary significantly due to the inherent complexities of such algorithms. Exploring further attack surfaces is, therefore, an important step for eventually securing the deployment of these algorithms. Also, it is important to test the robustness of the already proposed countermeasures in this regard.

In this work, we propose a new fault attack on side-channel secure masked implementation of LWE-based key-encapsulation mechanisms (KEMs) exploiting fault propagation. The attack typically originates due to an algorithmic modification widely used to enable masking, namely the Arithmetic-to-Boolean ($\mathtt{A2B}$) conversion. We exploit the data dependency of the adder carry chain in $\mathtt{A2B}$ and extract sensitive information, albeit masking (of arbitrary order) being present. As a practical demonstration of the exploitability of this information leakage, we show key recovery attacks of Kyber, although the leakage also exists for other schemes like Saber. The attack on Kyber targets the decapsulation module and utilizes Belief Propagation (BP) for key recovery. To the best of our knowledge, it is the first attack exploiting an algorithmic component introduced to ease masking rather than only exploiting the randomness introduced by masking to obtain desired faults (as done by Delvaux). Finally, we performed both simulated and electromagnetic (EM) fault-based practical validation of the attack for an open-source first-order secure Kyber implementation running on an STM32 platform.

Sponge based constructions have gained significant popularity for designing lightweight authenticated encryption modes. Most of the authenticated ciphers following the Sponge paradigm can be viewed as variations of the Transform-then-permute construction. It is known that a construction following the Transform-then-permute paradigm provides security against any adversary having data complexity $D$ and time complexity $T$ as long as $DT \ll 2^{b-r}$. Here, $b$ represents the size of the underlying permutation, while $r$ pertains to the rate at which the message is injected. The above result demonstrates that an increase in the rate leads to a degradation in the security of the constructions, with no security guaranteed to constructions operating at the full rate, where $r=b$. This present study delves into the exploration of whether adding some auxiliary states could potentially improve the security of the Transform-then-permute construction.

Our investigation yields an affirmative response, demonstrating that a special class of full rate Transform-then-permute with additional states, dubbed frTtP+, can indeed attain security when operated under a suitable feedback function and properly initialized additional state. To be precise, we prove that frTtP+ provides security as long as $D \ll 2^{s/2}$ and $T \ll 2^{s}$, where $s$ denotes the size of the auxiliary state in terms of bits. To demonstrate the applicability of this result, we show that the construction $Orange-Zest_{mod}$ belongs to this class, thereby obtaining the desired security. In addition, we propose a family of full-rate Transform-then-permute construction with a Beetle-like feedback function, dubbed \textsf{fr-Beetle}, which also achieves the same level of security.

Recently, Servan-Schreiber et al. (S&P 2023) proposed a new notion called private access control lists (PACL) for function secret sharing (FSS), where the FSS evaluators can ensure that the FSS dealer is authorized to share the given function with privacy assurance. In particular, for the secret sharing of a point function $f_{\alpha, \beta}$, namely distributed point function (DPF), the authors showed how to efficiently restrict the choice of $\alpha$ via a specific PACL scheme from verifiable DPF. In this work, we show their scheme is insecure due to the lack of assessment of $\beta$, and we fix it using an auxiliary output. We then propose more fine-grained policy constraints for DPF. Our schemes allow an attribute-based access control w.r.t. $\alpha$, and a template restriction for $\beta$. Furthermore, we show how to reduce the storage size of the constraint representation from $O(N)$ to $O(\log N)$, where $N$ is the number of constraints. Our benchmarks show that the amortized running time of our attribute-based scheme and logarithmic storage scheme is $2.5\times$ - $3\times$ faster than the state-of-the-art with $2^{15}$ constraints.

We show that the Cherbal-Benchetioui key agreement scheme [Comput. Electr. Eng., 109, 108759 (2023)] fails to keep user anonymity, not as claimed. The scheme simply thinks that user anonymity is equivalent to protecting the user's real identity. But the true anonymity means that the adversary cannot attribute different sessions to target entities, which relates to entity-distinguishable, not just identity-revealable.

Private Set Intersection (PSI) is a well-studied secure two-party computation problem in which a client and a server want to compute the intersection of their input sets without revealing additional information to the other party. With this work, we present nested Cuckoo hashing, a novel hashing approach that can be combined with additively homomorphic encryption (AHE) to construct an efficient PSI protocol for unbalanced input sets. We formally prove the security of our protocol against semi-honest adversaries in the standard model. Our protocol yields client computation and communication complexity that is sublinear in the server’s set size and is thus of interest to clients with limited resources. The implementation and empirical evaluation of our protocol using the exponential ElGamal and BGV/BFV encryption schemes attests to state-of-the-art practical performance.

An $(n, t)$-Non-Interactive Verifiable Secret Sharing (NI-VSS) scheme allows a dealer to share a secret among $n$ parties, s.t. all the parties can verify the validity of their shares and only a set of them, i.e., more than $t$, can access the secret. In this paper, we introduce $\Pi$, as a unified framework for building NI-VSS schemes in the majority honest setting. Notably, $\Pi$ does not rely on homomorphic commitments; instead, builds upon any commitment scheme that extra to its core attributes hiding and binding, it might be homomorphic and/or PQ-secure.

- When employing Discrete Logarithm (DL)-based commitments, $\Pi$ enables the construction of two novel NI-VSS schemes, named $\Pi_P$ and $\Pi_F$. In comparison to the well-known Pedersen and Feldman VSS schemes, both $\Pi_P$ and $\Pi_F$ require $O(1)$ exponentiations in the verification process, as opposed to $O(t)$, albeit at the expense of a slightly slower sharing phase and increased communication. - By instantiating $\Pi$ with a hash-based commitment scheme, we obtain the first PQ-secure NI-VSS scheme in the $\it{plain}$ model, labeled $\Pi_{LA}$ (pronounced [paɪla]). $\Pi_{LA}$ outperforms the recent random oracle-based construction by Atapoor, Baghery, Cozzo, and Pedersen from Asiacrypt'23 by a constant factor in all metrics. $\Pi_{LA}$ can also be viewed as an amplified version of the $\it{simple}$ NI-VSS scheme, proposed by Gennaro, Rabin, and Rabin, at PODC'98. - Building upon $\Pi_F$, we construct a Publicly VSS (PVSS) scheme, labeled $\Pi_S$, that can be seen as a new variant of Schoenmakers' scheme from Crypto'99. To this end, we first define the Polynomial Discrete Logarithm (PDL) problem, as a generalization of DL and then build a variant of the Schnorr Proof of Knowledge (PoK) scheme based on the new hardness assumption. We think the PDL relation and the associated PoK scheme can be independently interesting for Shamir-based threshold protocols.

We believe $\Pi$ is general enough to be employed in various contexts such as lattices, isogenies, and an extensive array of practical use cases.

We design a SNARKs/STARKs-optimized AEAD scheme based on the $\texttt{MonkeySpongeWrap}$ (ToSC 2023(2)) and the RPO permutation (ePrint 2022/1577).

QARMAv2 represents a family of lightweight block ciphers introduced in ToSC 2023. This new iteration, QARMAv2, is an evolution of the original QARMA design, specifically constructed to accommodate more extended tweak values while simultaneously enhancing security measures. This family of ciphers is available in two distinct versions, referred to as QARMAv2-$b$-$s$, where ‘$b$’ signifies the block length, with options for both 64-bit and 128-bit blocks, and ‘$c$’ signifies the key length. In this paper, for the first time, we present differential fault analysis (DFA) of all the QARMAv2 variants- QARMAv2-64, and QARMAv2-128 by introducing an approach to utilize the fault propagation patterns at the nibble level, with the goal of identifying relevant faulty ciphertexts and vulnerable fault positions. This technique highlights a substantial security risk for the practical implementation of QARMAv2. By strategically introducing six random nibble faults into the input of the $(r − 1)$-th and $(r − 2)$-th backward rounds within the $r$-round QARMAv2-64, our attack achieves a significant reduction in the secret key space, diminishing it from the expansive $2^{128}$ to a significantly more smaller set of size $2^{32}$. Additionally, when targeting QARMAv2-128-128, it demands the introduction of six random nibble faults to effectively reduce the secret key space from $2^{128}$ to a remarkably reduced $2^{24}$. To conclude, we also explore the potential extension of our methods to conduct DFA on various other iterations and adaptations of the QARMAv2 cryptographic scheme. To the best of our knowledge, this marks the first instance of a differential fault attack targeting the QARMAv2 tweakable block cipher family, signifying an important direction in cryptographic analysis.

Since 2016’s NIST call for standardization of post-quantum cryptographic primitives, developing efficient post-quantum secure digital signature schemes has become a highly active area of research. The difficulty in constructing such schemes is evidenced by NIST reopening the call in 2022 for digital signature schemes, because of missing diversity in existing proposals. In this work, we introduce the new post-quantum digital signature scheme MiRitH. As direct successor of a scheme recently developed by Adj, Rivera-Zamarripa and Verbel (Africacrypt ’23), it is based on the hardness of the MinRank problem and follows the MPC-in-the-Head paradigm. We revisit the initial proposal, incorporate design-level improvements and provide more efficient parameter sets. We also provide the missing justification for the quantum security of all parameter sets following NIST metrics. In this context we design a novel Grover-amplified quantum search algorithm for solving the MinRank problem that outperforms a naive quantum brute-force search for the solution. MiRitH obtains signatures of size 5.7 kB for NIST category I security and therefore competes for the smallest signatures among any post-quantum signature following the MPCitH paradigm. At the same time MiRitH offers competitive signing and verification timings compared to the state of the art. To substantiate those claims we provide extensive implementations. This includes a reference implementation as well as optimized constant-time implementations for Intel processors (AVX2), and for the ARM (NEON) architecture. The speed-up of our optimized AVX2 implementation relies mostly on a redesign of the finite field arithmetic, improving over existing implementations as well as an improved memory management.

Classic MLaaS solutions suffer from privacy-related risks since the user is required to send unencrypted data to the server hosting the MLaaS. To alleviate this problem, a thriving line of research has emerged called Privacy-Preserving Machine Learning (PPML) or secure MLaaS solutions that use cryptographic techniques to preserve the privacy of both the input of the client and the output of the server. However, these implementations do not take into consideration the possibility of transferability of known attacks in classic MLaaS settings to PPML settings. In this paper, we demonstrate that it is possible to transfer existing model-extraction attacks using adversarial examples to PPML settings due to relaxed constraints on the abilities of the adversary. We show a working example of an end-to-end attack on an image processing application built using a popular FHE-based framework, namely Concrete-ML. We successfully create a cloned model with just 5000 queries, which is, in fact, 10× less than the size of the training set of the victim model, while incurring only a 7% loss in accuracy. Further, we incorporate the well-known defense strategy against such attacks and show that our attack is still able to clone the model. Finally, we evaluate the different defense rationales that exist in literature and observe that such model stealing attacks are difficult to prevent in secure MLaaS settings.

Leader for the US NIST Cryptographic Technology Group. This position formulates and conducts/leads/manages and consults on an exceptionally difficult research program or policy issues of major scope, complexity, importance, and impact in the field of cryptography. Promotes and disseminates wide application of program results through significant publications, presentations, or authoritative reports/analyses and in national and international Standard Development Organizations. Work directly with national and international stakeholders ranging from other federal agencies, other national governments, academia, and industry to gain consensus, communicate organizational value and deconflict mission priorities. Manages a group of researchers, scientists, and support staff. Position open to U.S. Citizens Only.

Closing date for applications:

Contact: tiffani.brown@nist.gov

More information: https://www.usajobs.gov/job/756714700

The Young Investigator Group (YIG) “COSYS - Control Systems and Cyber Security Lab” at the Chair of IT Security at the Brandenburg University of Technology Cottbus-Senftenberg has open PhD/Postdoc positions in the following areas:

• Privacy-enhancing technologies and traffic analysis using AI methods in cyber-physical systems.
• Attack simulators in cyber-physical systems using AI methods, honeypots.
• Network exploration, traffic analysis, and pentesting in modern secure cyber-physical systems.

The available positions are funded as 100% TV-L E13 tariff in Germany and limited until 31.07.2026, with possibility for extension.

Candidates must hold a Master’s degree (PhD degree for Postdocs) or equivalent in Computer Science or related disciplines, or be close to completing it. If you are interested, please send your CV, transcript of records from your Master studies, and an electronic version of your Master's thesis (if possible), as a single pdf file. Applications will be reviewed until the positions are filled.

Closing date for applications:

Contact: Ivan Pryvalov (ivan.pryvalov@b-tu.de)

The Cryptography and Cybersecurity team of Télécom Paris (https://www.telecom-paris.fr/C2) is seeking excellent and motivated candidates who are interested in doing Master internships, PhD thesis, or Post-docs, in cryptography. We have several fundings for 6 months internship, 3-4 years PhD thesis, or 1-2 years Post-Doc, on topics related to Symmetric Cryptography. Candidates with an interest in conducting research in one of the following areas are particularly encouraged to apply:

• Design/analysis of symmetric cryptosystems
• Application of symmetric primitives in fully homomorphic encryption, zero-knowledge proof etc.

Requirements for internships:

• Master program in Math, CS, or relevant fields

Requirements for Ph.D. students:

• Master degree in Math, CS, or relevant fields
  
• Strong mathematics background
  
• Strong ability in at least one programming language
  
• Understanding basic cryptanalysis methods is a plus

Requirements for Post-Docs:

• Holding or finishing a Ph.D. degree in cryptography, IT security, or a related field
• Preference will be given to candidates with a strong publication record at IACR conferences or top security conferences

The review of applications starts immediately and will continue until positions are filled.

Closing date for applications:

Contact: Qingju Wang (qingju.wang@telecom-paris.fr)

These research-focused posts (advertised as "job number" ACAD107178) represent an exciting opportunity to join the Cryptography group at the University of Bristol (UoB), forming part of an Innovate UK funded project whose central focus is development of a RISC-V based micro-processor tailored to the needs of the aerospace industry. Work at UoB relates to cyber-security in general terms, and cryptography more specifically. More specifically still, the posts are aligned with research and engineering (or development) tasks that aim to enhance efficiency and security properties of cryptographic workloads as executed on the micro-processor; such tasks span elements of both software and hardware infrastructure, and demand consideration of both short- and long-term requirements. Given the project remit, a strong background and interest in at least one of the following research fields is therefore desirable:

• instruction set and micro-processor design and implementation (e.g., using HDL- and FPGA-based prototypes),
• cryptography, including lightweight (LWC) and post-quantum (PQC) constructions,
• cryptographic engineering, including high-assurance hardware or software implementation (e.g., formal specification of and verification with respect to security properties) and implementation (e.g., side-channel and fault induction) attacks,
• programming language and compiler design and implementation, ideally including the Jasmin and/or EasyCrypt tools.

Applicants with a purely academic background would ideally have a (completed or near completed) PhD in an appropriate discipline such as Computer Science. However, the project remit means that we view relevant industrial experience as extremely valuable: we therefore equally encourage applicants of this type. Successful applicants will be employed on a full-time, open-ended basis with funding available until 30/04/27; the appointments will be made at the Research Associate upto Research Fellow level depending on experience, implying a full-time starting salary of between £37,099 upto £48,350.

Closing date for applications:

Contact: Daniel Page (Daniel.Page@bristol.ac.uk)

More information: https://www.bristol.ac.uk/jobs/find/details/?jobId=326978

A fully funded position on the DingLab in Cryptography and its applications at the Yanqi Lake Beijing Institute of Mathematical Sciences and Applications (BIMSA).

Ding Lab

The Ding Lab in Public Key Cryptography will be led by Prof. Jintai Ding. It is an international open laboratory with English as the working language. Anyone who works in related areas including (but not restricted to) computational algebra, computational algebraic geometry, number theory, mathematical optimization, quantum algorithms, post-quantum cryptography, multi-party computation, zero-knowledge proof, fully homomorphic encryption, privacy-preserving algorithms, blockchain, high-performance computing, and algorithm implementations are welcome to apply.

Job Requirements

The position requires you to have a doctorate or master's degree in Computer Science, Mathematics, Cryptography, or equivalent practical experience.

Salary

BIMSA offers internationally competitive salary packages and salary will be determined by the applicant's qualifications. Recent PhDs are especially encouraged to apply. A typical appointment for a postdoc of BIMSA is for two years, renewable for the third year with annual salary ranges from 300,000 RMB to 500,000 RMB depending on experience and qualifications.

BIMSA

The BIMSA is a Mathematics research institution co-sponsored by the Beijing Municipal Government and Tsinghua University, and the director of BIMSA is the renowned mathematician, Prof. Shing-Tung Yau. The BIMSA is located in the Huairou District of Beijing and is part of Beijing’s strategic plans to build world-class new-style research & development institutions and national innovation centers for science and technology. The BIMSA aims to develop fundamental scientific research and build a bridge between mathematics and industry applications.

Closing date for applications:

Contact: Prof. Jintai Ding, the dual-appointed Professor at the Yau Mathematical Sciences Center of Tsinghua University and the Beijing Institute of Mathematical Sciences and Applications.

The Joux--Vitse Crossbred algorithm's aim is to efficiently solve a system of semi-regular multivariate polynomials equations. The authors tested their algorithm for polynomials in $\mathbb{F}_2$ and stated that this algorithm also works for other finite fields. In addition. the algorithm is dependent on a set of parameters that control its course. Finding functional parameters for this algorithm is a non-trivial task, so the authors presented a bivariate generating series to test the admissibility of parameters in $\mathbb{F}_2$. However, due to restrictive page limits, the series itself and its derivation are not explained. In this work, the derivation of the bivariate generating series to test the admissibility of parameters in $\mathbb{F}_2$ is explained and from this, a new series for $\mathbb{F}_{q>2}$ is presented. In addition, a complexity estimate of the algorithm is given for both $\mathbb{F}_2$ and $\mathbb{F}_{q>2}$. By obtaining optimal parameters using the previous results, the cost of applying Crossbred to polynomial systems of various sizes, numbers of variables and values of $q$ was plotted. Overall, it was determined that for larger fields, the Crossbred algorithm does not provide an improved asymptotic complexity over FES (Fast Exhaustive Search) and a similar state-of-the-art algorithm, Hybrid-$F_5$.

In the traditional consensus problem (aka Byzantine agreement), parties are required to agree on a common value despite the malicious behavior of some of them, subject to the condition that if all the honest parties start the execution with the same value, then that should be the outcome. This problem has been extensively studied by both the distributed computing and cryptographic protocols communities. With the advent of blockchains, whose main application—a distributed ledger—essentially requires that miners agree on their views, new techniques have been proposed to solve the problem, and in particular in so-called ``permissionless'' environments, where parties are not authenticated or have access to point to point channels and, further, may come and go as they please.

So far, the fastest way to achieve consensus in the proof-of-work (PoW)-based setting of Bitcoin, takes O(polylog $\kappa$) number of rounds, where $\kappa$ is the security parameter. We present the first protocol in this setting that requires expected-constant number of rounds. Further, we show how to apply securely sequential composition in order to yield a fast distributed ledger protocol that settles all transactions in expected-constant time. Our result is based on a novel instantiation of ``m-for-1 PoWs'' on parallel chains that facilitates our basic building block, Chain-King Consensus. The techniques we use, via parallel chains, to port classical protocol design elements (such as Phase-King Consensus, super-phase sequential composition and others) into the permissionless setting may be of independent interest.

This paper presents embedded curves that stem from BLS elliptic curves, providing general formulas derived from the curve’s seed. The mathematical groundwork is laid, and advantages of these embeddings are discussed. Additionally, practical examples are included at the end of the paper.