International Association
for Cryptologic Research

We propose an efficient technique called coefficient grouping to evaluate the algebraic degree of the FHE-friendly cipher Chaghri, which has been accepted for ACM CCS 2022. It is found that the algebraic degree increases linearly rather than exponentially. As a consequence, we can construct a 13-round distinguisher with time and data complexity of $2^{63}$ and mount a 13.5-round key-recovery attack with time complexity of about $2^{119.6}$. In particular, a higher-order differential attack on 8 rounds of Chaghri can be achieved with time and data complexity of $2^{38}$. Hence, it indicates that the full 8 rounds are far from being secure. Furthermore, we also demonstrate the application of our coefficient grouping technique to the design of secure cryptographic components. As a result, a countermeasure is found for Chaghri and it has little overhead compared with the original design. Since more and more symmetric primitives defined over a large finite field are emerging, we believe our new technique can have more applications in the future research.

Elliptic curves are abelian varieties of dimension one; the two-dimensional analogue are abelian surfaces. In this work we present an algorithm to compute $(2^n,2^n)$-isogenies of abelian surfaces defined over finite fields. These isogenies are the natural generalization of $2^n$-isogenies of elliptic curves. Our algorithm is designed to be used in higher-dimensional variants of isogeny-based cryptographic protocols such as G2SIDH which is a genus-$2$ version of the Supersingular Isogeny Diffie-Hellman (SIDH) key exchange. We analyze the performance of our algorithm in cryptographically relevant settings and show that it significantly improves upon previous implementations.

Different results deduced in the development of our algorithm are also interesting beyond this application. For instance, we derive a formula for the evaluation of $(2,2)$-isogenies. Given an element in Mumford coordinates, this formula outputs the (unreduced) Mumford coordinates of its image under the $(2,2)$-isogeny. Furthermore, we study $4$-torsion points on Jacobians of hyperelliptic curves and explain how to extract square-roots of coefficients of $2$-torsion points from these points.

Passwords are the most prevalent authentication mechanism and proliferate on nearly every new web service. As users are overloaded with the tasks of managing dozens even hundreds of passwords, accordingly password-based single-sign-on (SSO) schemes have been proposed. In password-based SSO schemes, the authentication server needs to maintain a sensitive password file, which is an attractive target for compromise and poses a single point of failure. Hence, the notion of password-based threshold authentication (PTA) system has been proposed. However, a static PTA system is threatened by perpetual leakage (e.g., the adversary perpetually compromises servers). In addition, most of the existing PTA schemes are built on the intractability of conventional hard problems and become insecure in the quantum era.

In this work, we first propose a threshold oblivious pseudorandom function (TOPRF) to harden the password so that PTA schemes can resist offline password guessing attacks. Then, we employ the threshold homomorphic aggregate signature (THAS) over lattices to construct the first quantum-resistant password-based threshold single-sign-on authentication scheme with the updatable server private key. Our scheme resolves various issues arising from user corruption and server compromise, and it is formally proved secure against the quantum adversary. Comparison results show that our scheme is superior to its counterparts.

The Learning with Errors (LWE) problem receives much attention in cryptography, mainly due to its fundamental significance in post-quantum cryptography. Among its solving algorithms, the Blum-Kalai-Wasserman (BKW) algorithm, originally proposed for solving the Learning Parity with Noise (LPN) problem, performs well, especially for certain parameter settings with cryptographic importance. The BKW algorithm consists of two phases, the reduction phase and the solving phase. In this work, we study the performance of distinguishers used in the solving phase. We show that the Fast Fourier Transform (FFT) distinguisher from Eurocrypt’15 has the same sample complexity as the optimal distinguisher, when making the same number of hypotheses. We also show via simulation that it performs much better than previous theory predicts and develop a sample complexity model that matches the simulations better. We also introduce an improved, pruned version of the FFT distinguisher. Finally, we indicate, via extensive experiments, that the sample dependency due to both LF2 and sample amplification is limited.

Gröbner bases are an important tool in computational algebra and, especially in cryptography, often serve as a boilerplate for solving systems of polynomial equations. Research regarding (efficient) algorithms for computing Gröbner bases spans a large body of dedicated work that stretches over the last six decades. The pioneering work of Bruno Buchberger in 1965 can be considered as the blueprint for all subsequent Gröbner basis algorithms to date. Among the most efficient algorithms in this line of work are signature-based Gröbner basis algorithms, with the first of its kind published in the late 1990s by Jean-Charles Faugère under the name $\texttt{F5}$. In addition to signature-based approaches, Rusydi Makarim and Marc Stevens investigated a different direction to efficiently compute Gröbner bases, which they published in 2017 with their algorithm $\texttt{M4GB}$. The ideas behind $\texttt{M4GB}$ and signature-based approaches are conceptually orthogonal to each other because each approach addresses a different source of inefficiency in Buchberger's initial algorithm by different means.

We amalgamate those orthogonal ideas and devise a new Gröbner basis algorithm, called $\texttt{M5GB}$, that combines the concepts of both worlds. In that capacity, $\texttt{M5GB}$ merges strong signature-criteria to eliminate redundant S-pairs with concepts for fast polynomial reductions borrowed from $\texttt{M4GB}$. We provide proofs of termination and correctness and a proof-of-concept implementation in C++ by means of the Mathic library. The comparison with a state-of-the-art signature-based Gröbner basis algorithm (implemented via the same library) validates our expectations of an overall faster runtime for quadratic overdefined polynomial systems that have been used in comparisons before in the literature and are also part of cryptanalytic challenges.

Aaram Yun et al. considered that Lai-Massey structure has the same security as Feistel structure. However, Luo et al. showed that 3-round Lai-Massey structure can resist quantum attacks of Simon's algorithm, which is different from Feistel structure. We give quantum attacks against a typical Lai-Massey structure. The result shows that there exists a quantum CPA distinguisher against 3-round Lai-Massey structure and a quantum CCA distinguisher against 4-round Lai-Massey Structure, which is the same as Feistel structure. We extend the attack on Lai-Massey structure to quasi-Feistel structure. We show that if the combiner of quasi-Feistel structure is linear, there exists a quantum CPA distinguisher against 3-round balanced quasi-Feistel structure and a quantum CCA distinguisher against 4-round balanced quasi-Feistel Structure.

Blockchain technologies rely on a public ledger, where typically all transactions are pseudoanonymous and fully traceable. This poses a major flaw in its large scale adoption of cryptocurrencies, the primary application of blockchain technologies, as most individuals do not want to disclose their finances to the pub- lic. Motivated by the explosive growth in private-Blockchain research, this Statement-of-Knowledge (SOK) explores the ways to obtain privacy in this public ledger ecosystem. The authors first look at the underly- ing technology underling all zero-knowledge applications on the blockchain: zk-SNARKs (zero-knowledge Succinct Non-interactive ARguments of Knowledge). We then explore the two largest privacy coins as of today, ZCash and Monero, as well as TornadoCash, a popular Ethereum Tumbler solution. Finally, we look at the opposing incentives behind privacy solutions and de-anonymization techniques, and the future of privacy on the blockchain.

The semiconductor industry is entering a new age in which device scaling and cost reduction will no longer follow the decades-long pattern. Packing more transistors on a monolithic IC at each node becomes more difficult and expensive. Companies in the semiconductor industry are increasingly seeking technological solutions to close the gap and enhance cost-performance while providing more functionality through integration. Putting all of the operations on a single chip (known as a system on a chip, or SoC) presents several issues, including increased prices and greater design complexity. Heterogeneous integration (HI), which uses advanced packaging technology to merge components that might be designed and manufactured independently using the best process technology, is an attractive alternative. However, although the industry is motivated to move towards HI, many design and security challenges must be addressed. This paper presents a three-tier security approach for secure heterogeneous integration by investigating supply chain security risks, threats, and vulnerabilities at the chiplet, interposer, and system-in-package levels. Furthermore, various possible trust validation methods and attack mitigation were proposed for every level of heterogeneous integration. Finally, we shared our vision as a roadmap toward developing security solutions for a secure heterogeneous integration.

Misuse resilience is an important security criterion in the evaluation of the NIST Post-quantum cryptography standardization process. In this paper, we propose new key mismatch attacks against Kyber and Saber, NIST's selected scheme for encryption and one of the finalists in the third round of the NIST competition, respectively. Our novel idea is to recover partial information of multiple secret entries in each mismatch oracle call. These multi-positional attacks greatly reduce the expected number of oracle calls needed to fully recover the secret key. They also have significance in side-channel analysis. From the perspective of lower bounds, our new attacks falsify the Huffman bounds proposed in [Qin et al. ASIACRYPT 2021], where a one- positional mismatch adversary is assumed. Our new attacks can be bounded by the Shannon lower bounds, i.e., the entropy of the distribution generating each secret coefficient times the number of secret entries. We call the new attacks "near-optimal" since their query complexities are close to the Shannon lower bounds.

We study the notion of Random-index ORAM (RORAM), which is a weak form of ORAM where the Client is limited to asking for (and possibly modifying) random elements of the $N$-items memory, rather than specific ones. That is, whenever the client issues a request, it gets in return a pair $(r,x_r)$ where $r\in_R[N]$ is a random index and $x_r$ is the content of the $r$-th memory item. Then, the client can also modify the content to some new value $x'_r$.

We first argue that the limited functionality of RORAM still suffices for certain applications. These include various applications of sampling (or sub-sampling), and in particular the very-large-scale MPC application in the setting of~ Benhamouda et al. (TCC 2020). Clearly, RORAM can be implemented using any ORAM scheme (by the Client selecting the random $r$'s by himself), but the hope is that the limited functionality of RORAM can make it faster and easier to implement than ORAM. Indeed, our main contributions are several RORAM schemes (both of the hierarchical-type and the tree-type) of lighter complexity than that of ORAM.

We design \textbf{\textsf{FrodoPIR}}~---~a highly configurable, \emph{stateful}, single-server Private Information Retrieval (PIR) scheme that involves an offline phase that is completely \emph{client-independent}. Coupled with small online overheads, it leads to much smaller amortized financial costs on the server-side than previous approaches. In terms of performance for a database of $1$ million $1$KB elements, \textsf{FrodoPIR} requires $< 1$ second for responding to a client query, has a server response size blow-up factor of $< 3.6\times$, and financial costs are $\sim \$1$ for answering $100,000$ client queries. Our experimental analysis is built upon a simple, non-optimized Rust implementation, illustrating that \textsf{FrodoPIR} is eminently suitable for large practical deployments.

This paper presents a fast method to compute algebraic norms of integral elements of smooth-degree cyclotomic fields, and, more generally, smooth-degree Galois number fields with commutative Galois groups. The typical scenario arising in $S$-unit searches (for, e.g., class-group computation) is computing a $\Theta(n\log n)$-bit norm of an element of weight $n^{1/2+o(1)}$ in a degree-$n$ field; this method then uses $n(\log n)^{3+o(1)}$ bit operations.

An $n(\log n)^{O(1)}$ operation count was already known in two easier special cases: norms from power-of-2 cyclotomic fields via towers of power-of-2 cyclotomic subfields, and norms from multiquadratic fields via towers of multiquadratic subfields. This paper handles more general Abelian fields by identifying tower-compatible integral bases supporting fast multiplication; in particular, there is a synergy between tower-compatible Gauss-period integral bases and a fast-multiplication idea from Rader.

As a baseline, this paper also analyzes various standard norm-computation techniques that apply to arbitrary number fields, concluding that all of these techniques use at least $n^2(\log n)^{2+o(1)}$ bit operations in the same scenario, even with fast subroutines for continued fractions and for complex FFTs. Compared to this baseline, algorithms dedicated to smooth-degree Abelian fields find each norm $n/(\log n)^{1+o(1)}$ times faster, and finish norm computations inside $S$-unit searches $n^2/(\log n)^{1+o(1)}$ times faster.

The cloud-aided Internet of Things (IoT) overcomes the resource-constrained nature of the traditional IoT and develops rapidly in such fields as smart grid and intelligent transportation. In a cloud-aided IoT system, users can remotely control the IoT devices or send specific instructions to them. When the user's identity is not verified and an adversary delivers malicious instructions to IoT devices, the system's security may be compromised. Besides, the real-time data stored in IoT devices can also be exposed to illegal users, causing security issues. Thus, the authentication mechanism is indispensable. Furthermore, with the exponential growth of interconnected devices, a gateway may connect to mass IoT devices. The efficiency of authentication schemes is easily affected by the computation power of the gateway. Although recent research has proposed many user authentication schemes for IoT, only a dozen schemes are designed for cloud-aided IoT. Therefore, we take a typical scheme (presented at IEEE TDSC 2020) as an example to capture user authentication schemes' common weaknesses and design challenges for cloud-aided IoT. Then, we propose a new secure user authentication scheme for cloud-aided IoT with lightweight computation on gateways. The proposed scheme provides secure access between the remote user and IoT devices with many ideal attributions, such as forward secrecy and multi-factor security. Meanwhile, the security of this scheme is proved under the random oracle model, heuristic analysis, the ProVerif tool and BAN logic. Finally, we compare the proposed scheme with eleven state-of-the-art schemes in security and performance. The results show that the proposed scheme achieves all listed twelve security requirements with minimum computation and storage costs on gateways.

We study a tamper-tolerant implementation security notion for general purpose Multi-Party Computation (MPC) protocols, as an analogue of the leakage-tolerant notion in the MPC literature. An MPC protocol is tamper-tolerant, or more specifically, non-malleable (with respect to a certain type of tampering) if the processing of the protocol under corruption of parties (and tampering of some ideal resource assumed by the protocol) can be simulated by an ideal world adversary who, after the trusted party spit out the output, further decides how the output for honest parties should be tampered with. Intuitively, we relax the correctness of secure computation in a privacy-preserving way, decoupling the two entangled properties that define secure computation. The rationale behind this relaxation is that even the strongest notion of correctness in MPC allows corrupt parties to substitute wrong inputs to the trusted party and the output is incorrect anyway, maybe the importance of insisting on that the adversary does not further tamper with the incorrect output is overrated, at least for some applications. Various weak privacy notions against malicious adversary play an important role in the study of two-party computation, where full security is hard to achieve efficiently.

We begin with the honest majority setting, where efficient constructions for general purpose MPC protocols with full security are well understood assuming secure point-to-point channels. We then focus on non-malleability with respect to tampered secure point-to-point channels. (1) We show achievability of non-malleable MPC against the bounded state tampering adversary in the joint tampering model through a naive compiler approach, exploiting a known construction of interactive non-malleable codes. The construction is currently not efficient and should be understood as showing feasibility in a rather strong tampering model. (2) We show efficient constructions of non-malleable MPC protocols against weaker variants of bounded state tampering adversary in the independent tampering model, where the protocol obtained have the same asymptotic communication complexity as best MPC protocols against honest-but-curious adversary. These are all information-theoretic results and are to be contrasted against impossibility of secure MPC when secure point-to-point channels are compromised.

Though general non-malleable MPC in no honest majority setting is beyond the scope of this work, we discuss interesting applications of honest majority non-malleable MPC in the celebrated MPC-in-the-head paradigm. Other than an abstract result concerning non-malleability, we also derive, in standard model where there is no tampering, that strong (ideal/real world) privacy against malicious adversary can be achieved in a conceptually very simple way.

In this paper, we aim to present a quantum setting oriented preimage attack against 4-round Keccak-224. An important technique we called the allocating rotational cryptanalysis takes the preimage attack into the situation of 2-block preimage recovery. With the conditions on the middle state proposed by Li et al., we use the generic quantum preimage attack to deal with the finding of first preimage block. By using the newly explored propagation of rotational relations, we significantly increase the number of eigenpoints at the end of 4-round modified Keccak-f from 0 to 32, and therefore improving the accuracy of determining the rotational number for a certain rotational counterpart in the quantum setting by more than 10 orders of magnitude. On the basis of the above, we design an efficient unitary oracle operator with only twice calling of the 4-round modified Keccak-f, which costs half of previous results, to mark a rotational counterpart of the second preimage block in order that the second preimage block can be found indirectly from a quickly generated specified search space. As a result on the 4-round Keccak-224: In the classical setting, the preimage attack with the complexity decreased to 2^218 is better than the result based on the pioneered rotational cryptanalysis. In the quantum setting, the amplitude amplification driven preimage attack with a complexity of 2^110 is by far the best dedicated quantum preimage attack. Additionally, the SKW algorithm is applied to the dedicated quantum preimage attack against the 4-round Keccak-224 for the first time, which is exponentially easier to implement in quantum circuit than the former, with a complexity of 2^111.

Non-fungible tokens (NFTs) are a blockchain application that has recently witnessed significant success. However, NFT marketplaces are majorly built on popular blockchain platforms that do not provide privacy tools. As a result, NFTs are easily visible to everyone. This has naturally given rise to various issues, including stolen/duplicate NFTs and attacks like shill trading. Furthermore, this architecture fails to reflect the real-life privacy notion as it digitizes unique physical goods. In this project, we build Paras - a blockchain-agnostic protocol that offers privacy to NFTs. Specifically, one may hide the real NFTs and only display a reference to them on marketplaces, hide seller and bidder identities, hide bid values and user wallet balances.

Paras is based on cryptographic primitives, such as, threshold encryption and robust secret sharing. It does not rely on any trusted execution environments for security, unlike some existing protocols in this direction.

The School of Computing and Information Technology (SCIT) is one of six Schools within the Faculty of Engineering and Information Sciences at the University of Wollongong. The SCIT aims to be a world class Research School, and this position is expected to contribute towards this aim. The Senior Lecturer/Lecturer, Cryptography will provide development, teaching and research within the Bachelor of Computer Science (majoring Cybersecurity and Digital Systems Security). The candidate is expected to be research active in the area of cryptography and other relevant topics, and be equipped with sufficient experience for teaching undergraduate and postgraduate studies. The successful candidate will have a national reputation in cryptography and/or cyber security research, innovative teaching experience, an established research profile and a demonstrable commitment to positive change. The candidate should demonstrate research excellence and potential to become an effective teacher in the area of Computer Science and Information Technology. As women are underrepresented in this area, women are strongly encouraged for these positions. You will be prompted to respond to a selection criteria questionnaire as part of the application process.

Closing date for applications:

Contact: Prof Willy Susilo

More information: https://www.seek.com.au/job/57956072

As a FHE Researcher, you will:

• Conduct research on state-of-the-art FHE schemes.
• Conduct Research on new Verifiable Computation (VC) schemes applied to FHE
• Design and implementation of new FHE and VC schemes.

Skills required for the job

• Knowledge of fully homomorphic encryption
• Deep understanding of lattice-based cryptography
• Knowledge on Verifiable Computation schemes is advisable
• Experience in C desired, C++, Rust or Go relevant as well
• Familiarity with hardware languages is a plus
• Solid engineering practices and processes, such as development and testing methodology and documentation
• Quick learner, geared towards implementation
• Eager to develop new skills and willing to take ownership of projects

Qualifications:

Ph.D. degree in Cryptography, Applied Cryptography, Cybersecurity, Mathematics, Computer Science or Engineering

Closing date for applications:

Contact: Dr. Najwa Aaraj, naaraj@alumni.princeton.edu

As a MPC Researcher, you will:

• Conduct research on state-of-the-art secure Multi Party Computation.
• Work on MPC building blocks such as,
  • Secret Sharing schemes
  • FHE
  • Garbled Circuits
• Design and implementation of building blocks to utilize privacy-preserving cryptographic techniques to cloud computing and machine learning applications.

Skills required for the job

• Knowledge on secure Multi Party Computation.
• Knowledge in some of the following is valuable:
  • Secret Sharing schemes
  • Garbled Circuits
  • FHE schemes
  • Zero-Knowledge proofs
• Experience in C desired, C++, Rust and Python relevant as well.
• Solid engineering practices and processes, such as development and testing methodology and documentation.
• Quick learner, geared towards implementation. Eager to develop new skills and willing to take ownership of projects.
• Knowledge on machine learning would be valuable.

Qualifications:

Ph.D. degree in Cryptography, Applied Cryptography, Cybersecurity, Mathematics or Computer Science or Engineering

Closing date for applications:

Contact: Dr. Najwa Aaraj, naaraj@alumni.princeton.edu

As a Post-Quantum Protocol expert, you will

• Work on security protocols based on post-quantum primitives such as Public Key Encryption, Key Encapsulation Mechanism, Key Exchange, and Digital Signatures schemes
• Analyze existing and propose new protocol designs, with special focus on post-quantum IPSec, VPNs, SSL, TLS, etc.
• Focus on protocols for lightweight environment
• Test and benchmark optimized and secure implementations of different protocols and study the impact on real life applications
• Investigate security properties and performance-security trade-offs
• Conduct research on new and/or state-of-the-art attacks
• Design and implementation of hybrid (post quantum – classical) solutions

Skills required for the job

• Knowledge on cryptography and cybersecurity, in particular a solid background in network security, especially protocol design and evaluation
• Excellent with C, C++, Python, (JAVA and Rust will be valuable as well)
• Hard and organized worker, quick learner, geared towards implementation. Eager to develop new skills and willing to take ownership of projects

Qualifications

• Ph.D. degree in Cryptography, Applied Cryptography, Cybersecurity, Mathematics or Computer Science or Engineering

Closing date for applications:

Contact: Najwa Aaraj, naaraj@alumni.Princeton.edu