International Association
for Cryptologic Research

This paper addresses the problem of factoring composite numbers by introducing a novel approach to represent their prime divisors. We develop a method to efficiently identify smaller divisors based on the difference between the primes involved in forming the composite number. Building on these insights, we propose an algorithm that significantly reduces the computational complexity of factoring, requiring half as many iterations as traditional quadratic residue-based methods. The presented algorithm offers a more efficient solution for factoring composite numbers, with potential applications in fields such as cryptography and computational number theory.

NTRU is one of the most extensively studied lattice-based schemes. Its flexible design has inspired different proposals constructed over different rings, with some aiming to enhance security and others focusing on improving performance. The literature has introduced a line of noncommutative NTRU-like designs that claim to offer greater resistance to existing attacks. However, most of these proposals are either theoretical or fall short in terms of time and memory requirements when compared to standard NTRU. To our knowledge, DiTRU (Africacrypt 2024) is the first noncommutative analog of NTRU provided as a complete package. Although DiTRU is practical, it operates at two times slower than NTRU with no decryption failure. Additionally, key generation, encryption, and decryption are 1.2, 1.7, and 1.7 times slower, respectively, with negligible decryption failure. In this work, we introduce a noncommutative version of NTRU that offers comparable performance and key sizes to NTRU while improving upon DiTRU. Our cryptosystem is based on the GR-NTRU framework, utilizing the group ring of a semidirect product of cyclic groups over the ring of Eisenstein integers. This design allows for an efficient construction with key generation speeds approximately two (three) times faster than NTRU (DiTRU). Further, the proposed scheme provides roughly a speed-up by a factor of 1.2 (2) while encrypting/decrypting messages of the same length over NTRU (DiTRU). We provide a reference implementation in C for the proposed cryptosystem to prove our claims.

Applications are invited for a PhD student position at the IMDEA Software Institute, Madrid, Spain.

The selected candidate will work under the supervision of Ignacio Cascudo on the research and the development of cryptographic tools for secure computation and threshold cryptography. Topics of interest include homomorphic encryption, secure multiparty computation, zero knowledge proofs, verifiable secret sharing and distributed key generation.

Who should apply?
Applicants should have a MSc in computer science, mathematics or a related discipline. The applicants should in particular have strong background in mathematics and some background and interest in cryptography. Good teamwork and communication skills, including excellent spoken and written English are also required.

Working at IMDEA Software
The position is based in Madrid, Spain, where the IMDEA Software Institute is situated. The institute provides for travel expenses and an internationally competitive stipend. The working language at the institute is English.

Dates
The duration of the position is intended to be for the duration of the doctoral studies and is intended to start in January 2025.

How to apply?
Applicants interested in the position should submit their application at https://careers.software.imdea.org/ using reference code 2024-10-phd-thresholdcrypto. Deadline for applications is November 30th, 2024.

The recruitment process will comply with the IMDEA Software Institute’s OTM-R Policy.

For any questions about this position, please contact Ignacio Cascudo at ignacio.cascudo@imdea.org

Closing date for applications:

Contact: Ignacio Cascudo

More information: https://software.imdea.org/careers/2024-10-phd-thresholdcrypto/

Event date: 27 November to 28 November 2024

Event date: 24 October 2024

Event date: 10 February to 14 February 2025

Event date: 4 August to 6 August 2025
Submission deadline: 10 February 2025
Notification: 10 March 2025

Event date: 26 March to 27 March 2025
Submission deadline: 25 November 2024
Notification: 23 December 2024

We are looking for a Education Technical Coordinator in the University of Amsterdam, to work in our Security and Network Engineering Master's program. The job is educational and involves working in various laboratory settings for courses on network routing, distributed systems, cybersecurity and penetration testing.

Apply using the following link:

https://vacatures.uva.nl/UvA/job/Security-and-Network-Engineering-Education-Technical-Coordinator/798272902/

For more information about the SNE master's programme see:

https://www.uva.nl/shared-content/programmas/en/masters/security-and-network-engineering/security-and-network-engineering.html

Closing date for applications:

Contact: Kostas Papagiannopoulos

More information: https://vacatures.uva.nl/UvA/job/Security-and-Network-Engineering-Education-Technical-Coordinator/798272902/

The University of Birmingham’s Centre for Cyber Security and Privacy is looking for up to three research fellows (postdocs) to work on our EPSRC-funded project on the security analysis of post-quantum cryptography algorithms.

Applicants should have a PhD, or be close to completing a PhD, in a relevant subject (crypto, computer algebra, maths, etc.). Prior track record on post-quantum cryptography and/or cryptanalysis is a plus.

Please contact Christophe Petit for informal enquiries. You can apply online until November 7th:
https://edzz.fa.em3.oraclecloud.com/hcmUI/CandidateExperience/en/sites/CX_6001/job/5764/

Closing date for applications:

Contact: Christophe Petit (C.Petit.1@bham.ac.uk)

More information: https://edzz.fa.em3.oraclecloud.com/hcmUI/CandidateExperience/en/sites/CX_6001/job/5764/

The research team led by Tim Roughgarden at a16z Crypto solicits applications for the summer research internship '25 cohort in all areas pertinent to Web3/blockchains.
Full consideration deadline: Nov 8, 2024.
Details and application form: https://a16z.com/about/jobs/?gh_jid=6242445003

a16z crypto research is a new kind of multidisciplinary lab that bridges the worlds of academic theory and industry practice to advance the science and technology of the next generation of the internet. In addition to fundamental research, we collaborate with portfolio companies to solve hard technical and conceptual problems. Research interns will have the opportunity to learn from the firm’s investment and engineering teams, although this is a research role with no responsibility for investment decisions. We are seeking students with a strong research background and an interest in blockchains and web3 to join the group for the summer. Specific research areas of interest include cryptography, security, distributed computing, economics (both micro and macro), incentives, quantitative finance, political science and governance, and market and mechanism design. This list is not exhaustive and we encourage applicants with different backgrounds who may have unique perspectives on the space to apply.

Preferred Qualifications:

• Enrolled in a PhD program in fields like computer science, economics, maths, operations research, political science, etc. (Exceptional master's and undergrads will also be considered)
• Passionate and knowledgeable about blockchains/Web3 technologies
• Familiar with fundamental research and publishing in peer-reviewed venues

Internship Details:

• Typically a blend of intern's own research (usually with other lab members), portfolio-related research problems, attending seminars, meeting visitors, etc.
• In-person residency in New York, NY
• Duration: May 27–August 15, 2025 (min. 10/max. 12 weeks)
• Anticipated compensation: $4,000/week plus $500/week housing stipend (actual starting pay may vary based on experience/skills/scope/etc.)

Closing date for applications:

Contact: Tim Roughgarden, troughgarden@a16z.com

More information: https://a16z.com/about/jobs/?gh_jid=6242445003

The Computer Science Department at the New Jersey Institute of Technology (NJIT) invites applications for multiple tenure-track faculty positions starting in Fall 2025. Exceptional candidates will be considered in all areas of Computer Science, but priority will be given to those that can build synergies in the following areas, defined broadly:

• Cybersecurity (2 tenure-track positions)
• AI and applications of AI (such as robotics) (2 tenure-track positions)

We aim to hire at the rank of Assistant Professor, but exceptional candidates at higher ranks will also be considered.

NJIT is a Carnegie R1 Doctoral University (Very High Research Activity), with $178M research expenditures in FY23. The Computer Science Department has 31 tenured/tenure track faculty, with nine NSF CAREER, one DARPA Young Investigator, and one DoE Early Career awardees. The Computer Science Department enrolls over 3,200 students at all levels across six programs of study and takes part, alongside the Departments of Informatics and Data Science, in the Ying Wu College of Computing (YWCC). YWCC comprises has an enrollment of more than 4,700 students in computing disciplines, and graduates over 1,000 computing professionals every year; as such, it is the largest producer of computing talent in the tri-state (NY, NJ, CT) area.

To formally apply for the position, please submit your application materials at https://academicjobsonline.org/ajo/jobs/28876. NJIT recognizes the importance of Diversity, Equity, and Inclusion (DEI) in academia and society at large. Candidates who have a track record in DEI are requested to also submit an optional Diversity Statement. Applications received by December 31, 2024 will receive full consideration. However, applications are reviewed until all the positions are filled. Contact address for inquiries: cs-faculty-search@njit.edu.

Closing date for applications:

Contact: cs-faculty-search@njit.edu

More information: https://cs.njit.edu/open-faculty-positions

We construct the first multi-input functional encryption (MIFE) and indistinguishability obfuscation (iO) schemes for pseudorandom functionalities, where the output of the functionality is pseudorandom for every input seen by the adversary. Our MIFE scheme relies on LWE and evasive LWE (Wee, Eurocrypt 2022 and Tsabary, Crypto 2022) for constant arity functions, and a strengthening of evasive LWE for polynomial arity. Thus, we obtain the first MIFE and iO schemes for a nontrivial functionality from conjectured post-quantum assumptions.

Along the way, we identify subtle issues in the proof of witness encryption from evasive LWE by prior work and believe that a similar strengthening of evasive LWE should also be required for their proof, for the same reasons as ours. We demonstrate the power of our new tools via the following applications:

1. Multi Input Predicate Encryption for Constant Arity. Assuming evasive LWE and LWE, we construct a multi-input predicate encryption scheme (MIPE) for P, supporting constant arity. The only prior work to support MIPE for P with constant arity by Agrawal et al. (Crypto, 2023) relies on a strengthening of Tensor LWE in addition to LWE and evasive LWE.

2. Multi Input Predicate Encryption for Polynomial Arity. Assuming a stronger variant of evasive LWE and LWE, we construct MIPE for P for polynomial arity. MIPE for polynomial arity supporting P was not known before, to the best of our knowledge.

3. Two Party ID Based Key Exchange. Assuming a stronger variant of evasive LWE and LWE, along with Decision Bilinear Diffie-Hellman, we provide the first two-party ID based Non-Interactive Key Exchange (ID-NIKE) scheme in the standard model. This leads to the first ID-NIKE in the standard model without using multilinear maps or indistinguishability obfuscation.

4. Instantiating the Random Oracle. We use our pseudorandom iO to instantiate the random oracle in several applications that previously used iO (Hohenberger, Sahai and Waters, Eurocrypt 2014) such as full-domain hash signature based on trapdoor permutations and more.

Our tools of MIFE and iO for pseudorandom functionalities appear quite powerful and yield extremely simple constructions when used in applications. We believe they provide a new pathway for basing “extreme” cryptography, which has so far required full fledged iO, on the presumably weaker evasive LWE in the post quantum regime.

We provide the first construction of compact Functional Encryption (FE) for pseudorandom functionalities from the evasive LWE and LWE assumptions. Intuitively, a pseudorandom functionality means that the output of the circuit is indistinguishable from uniform for every input seen by the adversary. This yields the first compact FE for a nontrivial class of functions which does not rely on pairings.

We demonstrate the power of our new tool by using it to achieve optimal parameters for both key-policy and ciphertext-policy Attribute Based Encryption (ABE) schemes for circuits of unbounded depth, from just the LWE and evasive LWE assumptions. This improves prior work along the twin axes of assumptions and performance. In more detail, this allows to: (i) replace the assumption of circular evasive LWE used in the work of Hseih, Lin and Luo (FOCS 2023) by plain evasive LWE, (ii) remove the need for the circular tensor LWE assumption in the work of Agrawal, Kumari and Yamada (CRYPTO, 2024), (iii) improve parameters obtained by both aforementioned works to achieve asymptotic optimality.

Previously, optimal parameters for ABE schemes were only achieved using compact FE for P (Jain, Lin and Luo, Eurocrypt 2023) – we show that compact FE for a much weaker class (albeit with incomparable security) suffices. Thus we obtain the first optimal ABE schemes for unbounded depth circuits which can be conjectured post-quantum secure. Along the way, we define and construct a new primitive which we term laconic pseudorandom obfuscation from the same assumptions – this may be of independent interest.

There are two security notions for FHE schemes the traditional notion of IND-CPA, and a more stringent notion of IND-CPA$^D$. The notions are equivalent if the FHE schemes are perfectly correct, however for schemes with negligible failure probability the FHE parameters needed to obtain IND-CPA$^D$ security can be much larger than those needed to obtain IND-CPA security. This paper uses the notion of ciphertext drift in order to understand the practical difference between IND-CPA and IND-CPA$^D$ security in schemes such as FHEW, TFHE and FINAL. This notion allows us to define a modulus switching operation (the main culprit for the difference in parameters) such that one does not require adapting IND-CPA cryptographic parameters to meet the IND-CPA$^D$ security level. Further, the extra cost incurred by the new techniques has no noticeable performance impact in practical applications. The paper also formally defines a stronger version for IND-CPA$^D$ security called sIND-CPA$^D$, which is proved to be strictly separated from the IND-CPA$^D$ notion. Criterion for turning an IND-CPA$^D$ secure public-key encryption into an sIND-CPA$^D$ one is also provided.

We present an asynchronous secure multi-party computation (MPC) protocol that is practically efficient. Our protocol can evaluate any arithmetic circuit with linear communication in the number of parties per multiplication gate, while relying solely on computationally lightweight cryptography such as hash function and symmetric encryption. Our protocol is optimally resilient and tolerates $t$ malicious parties among $n = 3t+1$ parties.

At the technical level, we manage to apply the \emph{player-elimination} paradigm to asynchronous MPC. This framework enables the detection and eviction of cheating parties by repeatedly attempting to generate Beaver triples. Once all malicious parties are eliminated, honest parties can proceed with efficient Beaver triple generation. While this approach is standard in synchronous MPC, it presents several technical challenges when adopted in an asynchronous network, which we address in this work.

We give the first construction of a rate-1 statistical non-interactive zero-knowledge argument of knowledge. For the $\mathsf{circuitSAT}$ language, our construction achieves a proof length of $|w| + |w|^\epsilon \cdot \mathsf{poly}(\lambda)$ where $w$ denotes the witness, $\lambda$ is the security parameter, $\epsilon$ is a small constant less than 1, and $\mathsf{poly}(\cdot)$ is a fixed polynomial that is independent of the instance or the witness size. The soundness of our construction follows from either the LWE assumption, or the $O(1)$-$\mathsf{LIN}$ assumption on prime-order groups with efficiently computable bilinear maps, or the sub-exponential DDH assumption. Previously, Gentry et al. (Journal of Cryptology, 2015) achieved NIZKs with statistical soundness and computational zero-knowledge with the aforementioned proof length by relying on the Learning with Errors (LWE) assumption.

In this paper, we introduce OT-PCA, a novel approach for conducting Plaintext-Checking (PC) oracle based side-channel attacks, specifically designed for Hamming Quasi-Cyclic (HQC). By calling the publicly accessible HQC decoder, we build offline templates that enable efficient extraction of soft information for hundreds of secret positions with just a single PC oracle call. Our method addresses critical challenges in optimizing key-related information extraction, including maximizing decryption output entropy and ensuring error pattern independence, through the use of genetic-style algorithms.

Extensive simulations demonstrate that our new attack method significantly reduces the required number of oracle calls, achieving a 2.4-fold decrease for hqc-128 and even greater reductions for hqc-192 and hqc-256 compared to current state-of-the-art methods. Notably, the attack shows strong resilience against inaccuracy in the PC oracle—when the oracle accuracy decreases to 95%, the reduction factor in oracle call requirements increases to 7.6 for hqc-128.

Lastly, a real-world evaluation conducted using power analysis on a platform with an ARM Cortex-M4 microcontroller validates the practical applicability and effectiveness of our approach.

The Shortest Vector Problem (SVP) is a cornerstone of lattice-based cryptography, underpinning the security of numerous cryptographic schemes like NTRU. Given its NP-hardness, efficient solutions to SVP have profound implications for both cryptography and computational complexity theory. This paper presents an innovative framework that integrates concepts from quantum gravity, noncommutative geometry, spectral theory, and post-SUSY particle physics to address SVP. By mapping high-dimensional lattice points to spin foam networks and by means of Hamiltonian engineering, it is theoretically possible to devise new algorithms that leverage the interactions topologically protected Majorana fermion particles have with the gravitational field through the spectral action principle to loop through these spinfoam networks where SVP vectors could then be encoded onto the spectrum of the corresponding Dirac operators within the system. We establish a novel approach that leverages post-SUSY physics and theories of quantum gravity to achieve algorithmic speedups beyond those expected by conventional quantum computers. This interdisciplinary methodology not only proposes potential polynomial-time algorithms for SVP but also bridges gaps between theoretical physics and cryptographic applications, providing further insights into the Riemann Hypothesis (RH) and the Hilbert-Polya Conjecture.

Non-interactive zero-knowledge proofs (NIZK) are essential building blocks in threshold cryptosystems like multiparty signatures, distributed key generation, and verifiable secret sharing, allowing parties to prove correct behavior without revealing secrets. Furthermore, universally composable (UC) NIZKs enable seamless composition in the larger cryptosystems. A popular way to construct NIZKs is to compile interactive protocols using the Fiat-Shamir transform. Unfortunately, Fiat-Shamir transformed NIZK requires rewinding the adversary and is not $\textit{straight-line extractable}$, making it at odds with UC. Using Fischlin's transform gives straight-line extractability, but at the expense of many repetitions of the underlying protocol leading to poor concrete efficiency and difficulty in setting parameters.

In this work, we propose a simple new transform that compiles a Sigma protocol for an algebraic relation into a UC-NIZK protocol $\textit{without any overheads of repetition}$.

- Given a Sigma protocol for proving m algebraic statements over n witnesses, we construct a compiler to transform it into a $\textit{straight-line extractable}$ protocol using an additively homomorphic encryption scheme AHE. Our prover executes the Sigma protocol's prover once and computes 2n encryptions. The verification process involves running the Sigma protocol verifier once and then computing n encryptions, which are homomorphically verified against the prover generated encryptions.

- We apply the Fiat-Shamir transform to the above straight-line extractable Sigma protocol to obtain a UC-NIZK. We instantiate AHE using class group-based encryption where the public key of the encryption scheme is obliviously sampled using a suitable hash function. This yields a UC-NIZK protocol in the random oracle model.