International Association
for Cryptologic Research

Indifferentiability is a popular cryptographic paradigm for analyzing the security of ideal objects---both in a classical as well as in a quantum world. It is typically stated in the form of a composable and simulation-based definition, and captures what it means for a construction (e.g., a cryptographic hash function) to be ``as good as'' an ideal object (e.g., a random oracle). Despite its strength, indifferentiability is not known to offer security against pre-processin} attacks in which the adversary gains access to (classical or quantum) advice that is relevant to the particular construction. In this work, we show that indifferentiability is (generically) insufficient for capturing pre-computation. To accommodate this shortcoming, we propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account. As an application, we show that the one-round sponge is indifferentiable (with pre-computation) from a random oracle. This yields the first (and tight) classical/quantum space-time trade-off for one-round sponge inversion.

Liu et al. (ITCS22) initiated the study of designing a secure position verification protocol based on a specific proof of quantumness protocol and classical communication. In this paper, we study this interesting topic further and answer some of the open questions that are left in that paper. We provide a new generic compiler that can convert any single round proof of quantumness-based certified randomness protocol to a secure classical communication-based position verification scheme. Later, we extend our compiler to different kinds of multi-round proof of quantumness-based certified randomness protocols. Moreover, we instantiate our compiler with a random circuit sampling (RCS)-based certified randomness protocol proposed by Aaronson and Hung (STOC 23). RCS-based techniques are within reach of today's NISQ devices; therefore, our design overcomes the limitation of the Liu et al. protocol that would require a fault-tolerant quantum computer to realize. Moreover, this is one of the first cryptographic applications of RCS-based techniques other than certified randomness.

In recent years, urban areas have experienced a rapid increase in vehicle numbers, while the availability of parking spaces has remained largely static, leading to a significant shortage of parking spots. This shortage creates considerable inconvenience for drivers and contributes to traffic congestion. A viable solution is the temporary use of private parking spaces by homeowners during their absence, providing a means to alleviate the parking problem and generate additional income for the owners. However, current systems for sharing parking spaces often neglect security and privacy concerns, exposing users to potential risks. This paper presents PISA, a novel Privacy-Preserving Smart Parking scheme designed to address these issues through a cryptographically secure protocol. PISA enables the anonymous sharing of parking spots and allows vehicle owners to park without revealing any personal identifiers. Our primary contributions include the development of a comprehensive bi-directional anonymity framework that ensures neither party can identify the other, and the use of formal verification methods to substantiate the soundness and reliability of our security measures. Unlike existing solutions, which often lack a security focus, fail to provide formal validation, or are computationally intensive, PISA is designed to be both secure and efficient.

The Fiat-Shamir (FS) transform is the standard approach to compiling interactive proofs into non-interactive ones. However, the fact that knowledge extraction typically requires rewinding limits its applicability without having to rely on further heuristic conjectures. A better alternative is a transform that guarantees straight-line knowledge extraction. Two such transforms were given by Pass (CRYPTO '03) and Fischlin (CRYPTO '05), respectively, with the latter giving the most practical parameters. Pass's approach, which is based on cut-and-choose, was also adapted by Unruh (EUROCRYPT '12, '14, '15) to the quantum setting, where rewinding poses a different set of challenges. All of these transforms are tailored at the case of three-round Sigma protocols, and do not apply to a number of popular paradigms for building succinct proofs (e.g., those based on folding or sumcheck) which rely on multi-round protocols.

This work initiates the study of transforms with straight-line knowledge extraction for multi-round protocols. We give two transforms, which can be thought of as multi-round analogues of those by Fischlin and Pass. Our first transform leads to more efficient proofs, but its usage applies to a smaller class of protocols than the latter one. Our second transform also admits a proof of security in the Quantum Random Oracle Model (QROM), making it the first transform for multi-round protocols which does not incur the super-polynomial security loss affecting the existing QROM analysis of the FS transform (Don et al., CRYPTO '20).

Since designing a dedicated secure symmetric PRF is difficult, various works studied optimally secure PRFs from the sum of independent permutations (SoP). At CRYPTO'20, Gunsing and Mennink proposed the Summation-Truncation Hybrid (STH). While based on SoP, STH releases additional $a \leq n$ bits of the permutation calls and sums $n-a$ bits of them. Thus, it produces $n+a$ bits at $O(n-a/2)$-bit PRF security. Both SoP or STH can be used directly in encryption schemes or MACs in place of permutation calls for higher security. However, simply replacing every call as in GCM-SIV$r$ would demand more calls.

For encryption schemes, Iwata's XORP scheme is long known to provide a better trade-off between efficiency and security. It extends SoP to variable-length-outputs by using $r+1$ calls to a block cipher where the output of one call is added to each of the other $r$ outputs. A similar extension can be conducted for STH that we call XTH, the XORP-Truncation Hybrid. Such an extension was already suggested in the final discussion by Gunsing and Mennink, but left as an open problem. This work fills the gap by formalizing and proving the security of XTH. For a rate of $r/(r+1)$ as in XORP, we show $O(n-a/2-1.5\log(r))$-bit security for XTH.

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.