International Association
for Cryptologic Research

We sketch a method for creating a zero-knowledge proof of knowledge for the correct execution of a program within a model of higher-order, recursive, purely functional programming by leveraging Halo 2. To our knowledge, this is the first ZKP for general purpose computation based on purely functional computation. This is an attractive alternative to using a von Neumann architecture based zero-knowledge virtual machine for verified computing of functional programs, as compilation will be more direct, making it more easily verifiable and potentially more efficient. Interaction nets are a natural setting for recursive, higher-order functional programming where all computation steps are linear and local. Interaction nets are graphs and traces for such programs are hyper-graphs. Correctness of a trace is a simple syntactic check over the structure of the trace represented as a hyper-graph. We reformulate this syntactic check as a Halo 2 circuit which is universal over all traces.

Recent practical applications using advanced cryptographic protocols such as multi-party computations (MPC) and zero-knowledge proofs (ZKP) have prompted a range of novel symmetric primitives described over large finite fields, characterized as arithmetization-oriented AO ciphers. Such designs, aiming to minimize the number of multiplications over fields, have a high risk of being vulnerable to algebraic attacks, especially to the higher-order differential attack. Thus, it is significant to carefully evaluate the growth of their algebraic degree. However, the degree estimation for AO ciphers has been a challenge for cryptanalysts due to the lack of general and accurate methods.

In this paper, we extend the division property, a state-of-the-art framework for finding the upper bound of the algebraic degree over binary fields, to the scope of $\mathbb{F}_{2^n}$. It is a generic method to detect the algebraic degree for AO ciphers, even applicable to Feistel ciphers which have no better bounds than the trivial exponential one. In this general division property, our idea is to evaluate whether the polynomial representation of a block cipher contains some specific monomials. With a deep investigation of the arithmetical feature, we introduce the propagation rules of monomials for field-based operations, which can be efficiently modeled using the bit-vector theory of SMT. Then the new searching tool for degree estimation can be constructed due to the relationship between the algebraic degree and the exponents of monomials.

We apply our new framework to some important AO ciphers, including Feistel MiMC, GMiMC, and MiMC. For Feistel MiMC, we show that the algebraic degree grows significantly slower than the native exponential bound. For the first time, we present a secret-key higher-order differential distinguisher for up to 124 rounds, much better than the 83-round distinguisher for Feistel MiMC permutation proposed at CRYPTO 2020. We also exhibit a full-round zero-sum distinguisher with a data complexity of $2^{251}$. Our method can be further extended for the general Feistel structure with more branches and exhibit higher-order differential distinguishers against the practical instance of GMiMC for up to 50 rounds. For MiMC in SP-networks, our results correspond to the exact algebraic degree proved by Bouvier et al. We also point out that the number of rounds in MiMC's specification is not sufficient to guarantee the security against the higher-order differential attack for MiMC-like schemes with different exponents. The investigation of different exponents provides some guidance on the cipher design.

We introduce puncturable key wrapping (PKW), a new cryptographic primitive that supports fine-grained forward security properties in symmetric key hierarchies. We develop syntax and security definitions, along with provably secure constructions for PKW from simpler components (AEAD schemes and puncturable PRFs). We show how PKW can be applied in two distinct scenarios. First, we show how to use PKW to achieve forward security for TLS 1.3 0-RTT session resumption, even when the server's long-term key for generating session tickets gets compromised. This extends and corrects a recent work of Aviram, Gellert, and Jager (Journal of Cryptology, 2021). Second, we show how to use PKW to build a protected file storage system with file shredding, wherein a client can outsource encrypted files to a potentially malicious or corrupted cloud server whilst achieving strong forward-security guarantees, relying only on local key updates.

Garbling is a cryptographic primitive which has many applications. It is mainly used for scenes of limited authority, such as multi-party computation (MPC), attribute-based encryption (ABE), functional encryption (FE), indistinguishability obfuscation (IO), etc. Garbling schemes before 2013 are of one-time garbling. Goldwasser et al and Agrawal presented a reusable garbling scheme, which made use of a symmetric encryption scheme and an FE scheme as the components.

In this paper we discuss the validity and the efficiency of reusable garbling scheme. We present the following three notes on the scheme.

(1) Reusable garbling scheme does not provide new applications, and it is still a one-time garbling scheme.

(2) Even reusable garbling scheme is taken as a one-time garbling scheme, sometimes it is not usable. More detailedly, it can only be used for Basic Scene 2, and cannot be used for Basic Scene 1. For example, it cannot be used for MPC.

(3) Even reusable garbling scheme is taken as a one-time garbling scheme used for Basic Scene 2, there is no evidence to show that its efficiency is better than a former one-time garbling scheme.

In the classical notion of multiparty computation (MPC), an honest party learning private inputs of others, either as a part of protocol specification or due to a malicious party's unspecified messages, is not considered a potential breach. Several works in the literature exploit this seemingly minor loophole to achieve the strongest security of guaranteed output delivery via a trusted third party, which nullifies the purpose of MPC. Alon et al. (CRYPTO 2020) presented the notion of Friends and Foes ($\mathtt{FaF}$) security, which accounts for such undesired leakage towards honest parties by modelling them as semi-honest (friends) who do not collude with malicious parties (foes). With real-world applications in mind, it's more realistic to assume parties are semi-honest rather than completely honest, hence it is imperative to design efficient protocols conforming to the $\mathtt{FaF}$ security model.

Our contributions are not only motivated by the practical viewpoint, but also consider the theoretical aspects of $\mathtt{FaF}$ security. We prove the necessity of semi-honest oblivious transfer for $\mathtt{FaF}$-secure protocols with optimal resiliency. On the practical side, we present QuadSquad, a ring-based 4PC protocol, which achieves fairness and GOD in the $\mathtt{FaF}$ model, with an optimal corruption of $1$ malicious and $1$ semi-honest party. QuadSquad is, to the best of our knowledge, the first practically efficient $\mathtt{FaF}$ secure protocol with optimal resiliency. Its performance is comparable to the state-of-the-art dishonest majority protocols while improving the security guarantee from abort to fairness and GOD. Further, QuadSquad elevates the security by tackling a stronger adversarial model over the state-of-the-art honest-majority protocols, while offering a comparable performance for the input-dependent computation. We corroborate these claims by benchmarking the performance of QuadSquad. We also consider the application of liquidity matching that deals with highly sensitive financial transaction data, where $\mathtt{FaF}$ security is apt. We design a range of $\mathtt{FaF}$ secure building blocks to securely realize liquidity matching as well as other popular applications such as privacy-preserving machine learning (PPML). Inclusion of these blocks makes QuadSquad a comprehensive framework.

An $\ell$-server Private Information Retrieval (PIR) scheme enables a client to retrieve a data item from a database replicated among $\ell$ servers while hiding the identity of the item. It is called $b$-error-correcting if a client can correctly compute the data item even in the presence of $b$ malicious servers. It is known that $b$-error correction is possible if and only if $\ell>2b$. In this paper, we first prove that if error correction is perfect, i.e., the client always corrects errors, the minimum communication cost of $b$-error-correcting $\ell$-server PIR is asymptotically equal to that of regular $(\ell-2b)$-server PIR as a function of the database size $n$. Secondly, we formalize a relaxed notion of statistical $b$-error-correcting PIR, which allows non-zero failure probability. We show that as a function of $n$, the minimum communication cost of statistical $b$-error-correcting $\ell$-server PIR is asymptotically equal to that of regular $(\ell-b)$-server one, which is at most that of $(\ell-2b)$-server one. Our main technical contribution is a generic construction of statistical $b$-error-correcting $\ell$-server PIR for any $\ell>2b$ from regular $(\ell-b)$-server PIR. We can therefore reduce the problem of determining the optimal communication complexity of error-correcting PIR to determining that of regular PIR. In particular, our construction instantiated with the state-of-the-art PIR schemes and the previous lower bound for single-server PIR result in a separation in terms of communication cost between perfect and statistical error correction for any $\ell>2b$.

A major challenge for blockchain interoperability is having an on-chain light client protocol that is both efficient and secure. We present a protocol that provides short proofs about the state of a decentralised consensus protocol while being able to detect misbehaving parties. To do this naively, a verifier would need to maintain an updated list of all participants' public keys which makes the corresponding proofs long. In general, existing solutions either lack accountability or are not efficient. We define and design a committee key scheme with short proofs that do not include any of the individual participants' public keys in plain. Our committee key scheme, in turn, uses a custom designed SNARK which has a fast prover time. Moreover, using our committee key scheme, we define and design an accountable light client system as the main cryptographic core for building bridges between proof of stake blockchains. Finally, we implement a prototype of our custom SNARK for which we provide benchmarks.

Doctoral student Position at School of Computer Science, University College Dublin, Ireland, focusing on Blockchain and Federated Learning for CONFIDENTIAL6G Project. We are looking for a candidate for a four-year direct Ph.D. position at the School of Computer Science, University College Dublin, Ireland, focusing on Blockchain uses for radio spectrum sharing and learning data integrity assurance for AI/ML approaches. This PhD position is attached to the project CONFIDENTIAL6G; a HORIZON EUROPE project funded by the EU commission. This project emphasizes privacy preservation and security of sensitive data focusing on the protection of data in use, in transit, and processed or stored at the edge. The selected student will work on a topic related to the CONFIDENTIAL6G project. #Funding The student will receive a four-year scholarship (where university tuition fees are fully covered along with living allowances of 18,500 Euros per annum) for the total duration of the Ph.D. program. Start Date By January 2023 Requirements for the doctoral student - Candidates should have a B.Sc (with a first-class) or a M.Sc. in one of the following fields: computer science, software engineering, or any other relevant subject by the time of the start date; - Proven DLT software (e.g., Blockchain, Ethereum, hyperledger…etc.) development skills with at least one relevant programming language such as Python, or Java; - Proven ability to document and publish the research findings in top conference proceedings and journals; - Motivation and dedication to pursue doctoral degree studies and research work that has the potential to be published in high-ranking publications; - Formidable communication skills to enable networking and knowledge dissemination plausible. Applying If you are interested, please contact me with the following documen

Closing date for applications:

Contact: The position is supervised by Asst. Prof. Dr. Madhusanka Liyanage (https://scholar.google.fi/citations?user=p1n0ioUAAAAJ&hl=en) and Asst. Prof. Dr. Shen Wang (https://scholar.google.com/citations?user=rPAOzIwAAAAJ&h).

This is an opportunity for a high-achieving postdoctoral researcher to join a world-leading research group within the area of computer security and cryptography. In this role you will design, develop, implement, and assess tools and procedures for secure implementation of cryptographic primitives. The position will support our research program to improve hardware and software security and promote secure designs.

This is a fixed term (18 months) position with a flexible start date up to January 2023.

Apply at: https://careers.adelaide.edu.au/cw/en/job/510702

Closing date for applications:

Contact: Yuval Yarom yval(at)cs.adelaide.edu.au

Job Description
The Cryptography Architect will be responsible for guiding how advanced and innovative cryptography is leveraged at JPMorgan Chase. As an experienced member of the Emerging Technologies Security group within the Cybersecurity & Technology Controls organization, you will interact with like-minded cryptographers and a group of passionate security engineers to work on concrete applications of advanced cryptography schemes. You will also have the opportunity to collaborate with other cryptographers on research projects.
The position requires strong academic knowledge as well as some industry experience in vetting and applying advanced cryptography schemes to secure complex IT infrastructure, customer-facing services, and sensitive customer and enterprise data.
Knowledge, experience, and capability required for the role include:

• Expertise in both mainstream encryption schemes and key exchange protocols as well as quantum-safe cryptography
• Strong familiarity with NIST post-quantum cryptography standardization & migration efforts
• Hands-on experience with implementing, testing and deploying advanced cryptographic schemes
• Familiarity with NIST Cryptographic Standards and Guidelines
• Proficiency in multiple programming languages, e.g., Java, C#, JavaScript, C/C++
• Ability to convey complex concepts in a clear & concise manner to a wide range of audience
• Proven track record in publishing papers (academia, whitepaper, position paper etc.)
• Proven track record in working with diverse teams to achieve goals
• Driving enterprise-wide transformative security technology initiatives
• PhD (preferred) or MS in computer science

Closing date for applications:

Contact: Hubert Le Van Gong, Ph.D. | Managing Director | Cybersecurity & Technology Controls

More information: https://jpmc.fa.oraclecloud.com/hcmUI/CandidateExperience/en/sites/CX_1001/job/210337824/?utm_medium=jobshare

Job Description

The Applied Cryptography Architect will be responsible for leveraging innovative cryptography at JPMorgan Chase. As a member of the Emerging Technologies Security group within the Cybersecurity & Technology Controls organization, you will work alongside cryptographers and a group of passionate security engineers to solve complex security problems and support the deployment of cryptography-based solutions.

The position requires extensive knowledge and industry experience in combining cryptography and security best-practices to secure complex IT infrastructure, customer-facing services, and sensitive customer and enterprise data.

Knowledge, experience, and capability required for the role include:

• Expertise in applying mainstream cryptographic primitives, including digital signatures, public-key ciphers, block ciphers Good understanding and hands-on experience of network security protocols (TLS etc.)
• Familiarity with NIST post-quantum cryptography standardization & migration efforts
• Security solution development utilizing cryptographic agility principles and elements
• Proficiency in multiple programming languages, e.g., Java, C#, JavaScript, C/C++
• Hands-on data protection solution development utilizing industry standard security protocol and best-practices
• Application knowledge of public key infrastructure (PKI) and digital certificates (e.g., X.509)
• Ability to convey complex concepts and ideas in a clear and concise manner to a wide range of audience
• Proven track record in working with diverse teams to achieve goals
• Driving enterprise-wide transformative security technology initiatives
• MS (preferred) or BS in computer science

Closing date for applications:

Contact: Hubert Le Van Gong, Ph.D. | Managing Director | Cybersecurity & Technology Controls

More information: https://jpmc.fa.oraclecloud.com/hcmUI/CandidateExperience/en/sites/CX_1001/job/210337262/?utm_medium=jobshare

Oxford University’s Computer Science Department is hiring four new faculty. The positions are open to all areas of computer science and the closing date is 12 noon on 14 December 2022. For more information, see https://www.cs.ox.ac.uk/aboutus/vacancies/vacancy-faculty-hiring.html

Closing date for applications:

Contact: James Worrell

We introduce a new idealized model of hash functions, which we refer to as the *pseudorandom oracle* (PrO) model. Intuitively, it allows us to model cryptosystems that use the code of a hash function in a non-black-box way. Formally, we model hash functions via a combination of a pseudorandom function (PRF) family and an ideal oracle. A user can initialize the hash function by choosing a PRF key $k$ and the oracle maps it to a public handle $h$. Given the handle $h$ and some input $x$, the oracle will recover the PRF key $k$ and evaluate the PRF on $x$. A user who chooses the PRF key $k$ therefore has a complete description of the hash function and can use its code in non-black-box constructions, while an adversary, who just gets the handle $h$, only has black-box access to the hash function via the oracle.

As our main result, we show how to construct ideal obfuscation in the PrO model, starting from functional encryption (FE), which in turn can be based on well-studied polynomial hardness assumptions. In contrast, we know that ideal obfuscation cannot be instantiated in the basic random oracle model under any assumptions. We believe our result gives a heuristic justification for the following: (1) most natural security goals implied by ideal obfuscation are achievable in the real world; (2) we can construct obfuscation from FE with polynomial security loss.

We also discuss how to interpret our result in the PrO model as a construction of ideal obfuscation using simple hardware tokens or as a way to bootstrap ideal obfuscation for PRFs to that for all functions.

The NTRU problem can be viewed as an instance of finding a short non-zero vector in a lattice, under the promise that it contains an exceptionally short vector. Further, the lattice under scope has the structure of a rank-2 module over the ring of integers of a number field. Let us refer to this problem as the module unique Shortest Vector Problem,or mod-uSVP for short. We exhibit two reductions that together provide evidence the NTRU problem is not just a particular case of mod-uSVP, but representative of it from a computational perspective.

First, we reduce worst-case mod-uSVP to worst-case NTRU. For this, we rely on an oracle for id-SVP, the problem of finding short non-zero vectors in ideal lattices. Using the worst-case id-SVP to worst-case NTRU reduction from Pellet-Mary and Stehlé [ASIACRYPT'21],this shows that worst-case NTRU is equivalent to worst-case mod-uSVP.

Second, we give a random self-reduction for mod-uSVP. We put forward a distribution D over mod-uSVP instances such that solving mod-uSVP with a non-negligible probability for samples from D allows to solve mod-uSVP in the worst-case. With the first result, this gives a reduction from worst-case mod-uSVP to an average-case version of NTRU where the NTRU instance distribution is inherited from D. This worst-case to average-case reduction requires an oracle for id-SVP.

We investigate a new class of fault-injection attacks against the CSIDH family of cryptographic group actions. Our disorientation attacks effectively flip the direction of some isogeny steps. We achieve this by faulting a specific subroutine, connected to the Legendre symbol or Elligator computations performed during the evaluation of the group action. These subroutines are present in almost all known CSIDH implementations. Post-processing a set of faulty samples allows us to infer constraints on the secret key. The details are implementation specific, but we show that in many cases, it is possible to recover the full secret key with only a modest number of successful fault injections and modest computational resources. We provide full details for attacking the original CSIDH proof-of-concept software as well as the CTIDH constant-time implementation. Finally, we present a set of lightweight countermeasures against the attack and discuss their security.

The mutual information between the observable device leakage and the unknown key is a key metric in the context of side channel attacks, evaluations, and countermeasures. Estimating this mutual information has been a problem and was addressed in several recent contributions. We explain why previous work has ended up in a "catch-22'' and we show how to avoid this situation by using a leakage model free estimation approach based on a recently discovered, consistent mutual information estimator. Our work demonstrates that mutual information estimation in the side channel setting can be done extremely efficiently (even in a multivariate setting), with strong mathematical guarantees, without the need for an explicit device leakage model, discretisation, or assumptions about the nature of the device leakage.

Security concerns about a machine learning model used in a prediction-as-a-service include the privacy of the model, the query and the result. Secure inference solutions based on homomorphic encryption (HE) and/or multiparty computation (MPC) have been developed to protect all the sensitive information. One of the most efficient type of solution utilizes HE for linear layers, and MPC for non-linear layers. However, for such hybrid protocols with semi-honest security, an adversary can malleate the intermediate features in the inference process, and extract model information more effectively than methods against inference service in plaintext. In this paper, we propose SEEK, a general extraction method for hybrid secure inference services outputing only class labels. This method can extract each layer of the target model independently, and is not affected by the depth of the model. For ResNet-18, SEEK can extract a parameter with less than 50 queries on average, with average error less than $0.03\%$.

In ASIACRYPT 2017, Rønjom et al. analyzed AES with yoyo attack. Inspired by their 4-round AES distinguisher, Grassi proposed the mixture differential cryptanalysis as well as a key recovery attack on 5-round AES, which was shown to be better than the classical square attack in computation complexity. After that, Bardeh et al. combined the exchange attack with the 4-round mixture differential distinguisher of AES, leading to the first secret-key chosen plaintext distinguisher for 6-round AES. Unlike the attack on 5-round AES, the result of 6-round key-recovery attack on AES has extremely large complexity, which implies the weakness of mixture difference to a certain extent. Our work aims at evaluating the security of AES-like ciphers against mixture differential cryptanalysis. We propose a new structure called a boomerang struncture and illustrate that a differential distinguisher of a boomerang struncture just corresponds to a mixture differential distinguisher for AES-like ciphers. Based on the boomerang structure, it is shown that the mixture differential cryptanalysis is not suitable to be applied to AES-like ciphers with high round number. In specific, we associate the primitive index with our framework built on the boomerang structure and give the upper bound for the length of mixture differentials with probability 1 on AES-like ciphers. It can be directly deduced from our framework that there is no mixture differential distinguisher for 6-round AES.

While research in post-quantum cryptography (PQC) has gained significant momentum, it is only slowly adopted for real-world products. This is largely due to concerns about practicability and maturity. The secure boot process of embedded devices is one s- cenario where such restraints can result in fundamental security problems. In this work, we present a flexible hardware/software co-design for hash-based signature (HBS) schemes which enables the move to a post-quantum secure boot today. These signature schemes stand out due to their straightforward security proofs and are on the fast track to standardisation. In contrast to previous works, we exploit the performance intensive similarities of the s- tateful LMS and XMSS schemes as well as the stateless SPHINCS+ scheme. Thus, we enable designers to use a stateful or stateless scheme depending on the constraints of each individual application. To show the feasibility of our approach, we compare our results with hardware accelerated implementations of classical asymmetric algorithms. Further, we lay out the usage of different HBS schemes during the boot process. We compare different schemes, show the importance of parameter choices, and demonstrate the performance gain with different levels of hardware acceleration.

During the design of a new primitive inspired by Squash we accidentally stumbled on the observation described in this note.

Let $n$ be a $k$-bit Mersenne number whose factors are unknown. Consider an $\ell$-bit secret number $x=2^{k/2}a+b$. We observe that there are parameter configurations where a chunk of the value $b^2$ is leaked even if $k<2\ell$.

This observation does not endanger any known scheme and in particular not Squash.