International Association
for Cryptologic Research

Bottleneck complexity is an efficiency measure of secure multiparty computation (MPC) protocols introduced to achieve load-balancing in large-scale networks, which is defined as the maximum communication complexity required by any one player within the protocol execution. Towards the goal of achieving low bottleneck complexity, prior works proposed MPC protocols for computing symmetric functions in the correlated randomness model, where players are given input-independent correlated randomness in advance. However, the previous protocols with polylogarithmic bottleneck complexity in the number of players $n$ require a large amount of correlated randomness that is linear in $n$, which limits the per-party efficiency as receiving and storing correlated randomness are the bottleneck for efficiency. In this work, we present for the first time MPC protocols for symmetric functions such that bottleneck complexity and the amount of correlated randomness are both polylogarithmic in $n$, assuming collusion of size at most $n-o(n)$ players. Furthermore, one of our protocols is even computationally efficient in that each player performs only $\mathrm{polylog}(n)$ arithmetic operations while the computational complexity of the previous protocols is $O(n)$. Technically, our efficiency improvements come from novel protocols based on ramp secret sharing to realize basic functionalities with low bottleneck complexity, which we believe may be of interest beyond their applications to secure computation of symmetric functions.

Deduplication is a vital preprocessing step that enhances machine learning model performance and saves training time and energy. However, enhancing federated learning through deduplication poses challenges, especially regarding scalability and potential privacy violations if deduplication involves sharing all clients’ data. In this paper, we address the problem of deduplication in a federated setup by introducing a pioneering protocol, Efficient Privacy-Preserving Multi-Party Deduplication (EP-MPD). It efficiently removes duplicates from multiple clients’ datasets without compromising data privacy. EP-MPD is constructed in a modular fashion, utilizing two novel variants of the Private Set Intersection protocol. Our extensive experiments demonstrate the significant benefits of deduplication in federated learning of large language models. For instance, we observe up to 19.61% improvement in perplexity and up to 27.95% reduction in running time. EP-MPD effectively balances privacy and performance in federated learning, making it a valuable solution for large-scale applications.

Isogeny-based schemes often come with special requirements on the field of definition of the involved elliptic curves. For instance, the efficiency of SQIsign, a promising candidate in the NIST signature standardisation process, requires a large power of two and a large smooth integer $T$ to divide $p^2-1$ for its prime parameter $p$.

We present two new methods that combine previous techniques for finding suitable primes: sieve-and-boost and XGCD-and-boost. We use these methods to find primes for the NIST submission of SQIsign. Furthermore, we show that our methods are flexible and can be adapted to find suitable parameters for other isogeny-based schemes such as AprèsSQI or POKE. For all three schemes, the parameters we present offer the best performance among all parameters proposed in the literature.

In this work, we introduce enhanced high-order masking techniques tailored for Dilithium, the post-quantum signature scheme recently standardized by NIST. We improve the masked generation of the masking vector $\vec{y}$, based on a fast Boolean-to-arithmetic conversion modulo $q$. We also describe an optimized gadget for the high-order masked rejection sampling, with a complexity independent from the size of the modulus $q$. We prove the security of our gadgets in the classical ISW $t$-probing model. Finally, we detail our open-source C implementation of these gadgets integrated into a fully masked Dilithium implementation, and provide an efficiency comparison with previous works.

In this short note, we introduce a specific class of rank two lattices over CM fields endowed with additional symmetries, which are involved in the decomposition of algebraic integers in Hermitian squares. As an application, we show an elementary reduction from the module-LIP problem in rank 2 over a CM or totally real number field to the finding of a square basis in such lattices.

In this article we present a non-uniform reduction from rank-2 module-LIP over Complex Multiplication fields, to a variant of the Principal Ideal Problem, in some fitting quaternion algebra. This reduction is classical deterministic polynomial-time in the size of the inputs. The quaternion algebra in which we need to solve the variant of the principal ideal problem depends on the parameters of the module-LIP problem, but not on the problem’s instance. Our reduction requires the knowledge of some special elements of this quaternion algebras, which is why it is non-uniform.

In some particular cases, these elements can be computed in polynomial time, making the reduction uniform. This is in particular the case for the Hawk signature scheme: we show that breaking Hawk is no harder than solving a variant of the principal ideal problem in a fixed quaternion algebra (and this reduction is uniform).

Event date: 18 October 2024
Submission deadline: 22 July 2024
Notification: 26 August 2024

The research group for Cryptographic Protocols located at the University of Luxembourg and the KASTEL Security Research Labs (Germany) is looking for a PhD student working on cryptographic primitives and protocols enabling privacy, accountability, and transparency. A background in provable security (e.g., successfully attended courses or a master’s thesis on the subject) is expected.

The candidate will be based at the University of Luxembourg but also profit from regular visits at and joint research projects with the KASTEL Security Research Labs at KIT, Germany. The candidate’s research will be dealing with privacy-enhancing cryptographic building blocks and protocols for important application scenarios and result in both theoretical contributions (protocol designs, security models and proofs, etc.) and their efficient implementation. Privacy-preserving payments and data analytics, misuse-resistant lawful interception, and anonymous communication are research topics of particular interest to us.

If you are interested in joining our group, please send an email including your CV, transcripts, and two references to andy.rupp@uni.lu. As the position should be filled as soon as possible, your application will be considered promptly.

Closing date for applications:

Contact: Andy Rupp (andy.rupp@uni.lu)

More information: https://www.uni.lu/fstm-en/research-groups/cryptographic-protocols/

Are you fascinated by the theoretical underpinnings of security that allow for protecting privacy in an ever more interconnected world? Are you willing to take on the challenge of upgrading cryptography to deal with the threat posed by quantum computation? Do you enjoy working in a team of young and motivated researchers? The TCS Group from the Informatics Institute of the University of Amsterdam is seeking a PhD student to carry out cutting-edge research in theoretical computer science, with an expected focus on code-based cryptography.

Closing date for applications:

Contact: Nicolas Resch

More information: https://vacatures.uva.nl/UvA/job/PhD-Position-in-Code-Based-Cryptography/777741202/

We are seeking two highly motivated and talented students to join our research group to pursue a Ph.D in the field of cryptography at School of Computer Science, University of Sydney. The student will work on cutting-edge research in topics such as

security and fairness in multi-party computation

distributed payment protocols

privacy-preserving blockchains and cryptocurrencies

Security and game-theoretic aspects in blockchains

and other topics in cryptographic theory and applications.

Qualifications:

An UG or Master’s degree in CS, Mathematics, Electrical Engineering, or a related field, with one year of research experience (For eg., research-based thesis).

Strong background in theoretical computer science, number theory, probability.

Proficiency in English, both written and spoken

Good communication and teamwork skills.

Optional skills:

Excellent programming skills and experience with cryptographic libraries is a plus.

Benefits:

Competitive salary and benefits package.

Work in a dynamic and international research environment.

Support for international collaborations and travel.

About University of Sydney:

The University of Sydney is one of the world's leading universities, known for its outstanding research and teaching excellence (ranked 18 in the world - QS rankings 2025 ). Our vibrant campus is located in the heart of Sydney (one of the top livable cities of the world), offering an exceptional environment for both academic and personal growth and the perfect work-life balance. The School of Computer Science is among the top ranked in the world ( ranked 22 in the world for CS - US news and world report 2024-25 ) constantly expanding year-on-year with strong faculty and students.

Application Process: Interested candidates should contact via email with

a detailed CV, including list of publications (if any)

Transcript, degree certificate

Contact of two references

Closing date for applications:

Contact: Sri AravindaKrishnan Thyagarajan aravind.thyagarajan@sydney.edu.au

More information: https://www.sydney.edu.au/courses/courses/pr/doctor-of-philosophy-engineering.html

We are looking for a bright, ambitious, and motivated PhD student to join the cryptography group in the Cybersecurity Engineering Section at DTU Compute in the Copenhagen region of Denmark. The 3-year PhD position will preferably start on 1 November 2024 (or according to mutual agreement). The goal of the PhD project is to improve the state of threshold post-quantum cryptography. You will join the growing cryptography team at DTU and be able to work with researchers in- and outside of the Copenhagen region and Denmark.

Responsibilities and qualifications
Your main task will be to design new threshold cryptographic algorithms with post-quantum security.
You will investigate distributed alternatives to existing post-quantum algorithms such as Dilithium, Falcon and Picnic, and the long-term security of threshold cryptography, in particular with respect to proactive and post-quantum security. To succeed in this research effort, you will gain familiarity with:

• post-quantum cryptographic primitives such as signatures or OPRFs
• threshold cryptographic techniques such as secret sharing and multiparty computation
• cryptographic foundations of post-quantum cryptography such as lattices, MPC-in-the-head, FHE and similar tools

In addition to the research project, you will conduct a limited amount of small-class teaching during your PhD period.

As formal qualification, you must have a two-year master's degree (120 ECTS points) or a similar degree with an academic level equivalent to a two-year master's degree. Furthermore, to ensure a smooth start into the project, it is preferable that you have previous experience with either threshold or post-quantum cryptography.

Salary and appointment terms
The appointment will be based on the collective agreement with the Danish Confederation of Professional Associations. The allowance will be agreed upon with the relevant union. The period of employment is 3 years. The position is a full-time position and the starting date is 1 November 2024 (or according to mutual agreement).

Closing date for applications:

Contact: Carsten Baum (cabau@dtu.dk)

More information: https://efzu.fa.em2.oraclecloud.com/hcmUI/CandidateExperience/da/sites/CX_1/job/2872/

We are looking for a person to extend our team as postdoc in the Horizon Europe Next Generation Internet pilot NGI TALER. Your task will be to carry out foundational research in the context of the payment system GNU Taler. More precisely, you will be tasked with proving the security of post-quantum replacements for the cryptography used to secure GNU Taler. The position is initially 1 year with funding for a 1-year extension available.

GNU Taler is a privacy-preserving payment system. Customers can stay anonymous, but merchants cannot hide their income through payments with GNU Taler. This helps to avoid tax evasion and money laundering while providing users with a privacy-preserving way of electronic payment. As part of a Next Generation Internet pilot, the cryptography used in GNU Taler will be future-proofed by developing post-quantum secure variants of the involved protocols. Your task will be to prove these new protocols secure against quantum adversaries, closely collaborating with the team that develops the protocols.

If you have a PhD in cryptography or a related area, please apply online via the TU/e website.

Closing date for applications:

Contact: Andreas Hülsing a.t.huelsing [put at here] tue.nl and Kathrin Hövelmanns k.hovelmanns [put at here] tue.nl

More information: https://jobs.tue.nl/en/vacancy/postdoc-in-postquantum-cryptography-1094802.html

https://aztec.network/

We’re creating a general-purpose private smart contract layer for Ethereum, affectionately dubbed ‘Aztec 3’.

We utilise bleeding-edge cryptography in our tech stack to realise private transactions on a public blockchain network, particularly in the realm of zero-knowledge cryptography.

As a result we possess a world-class R&D team that has co-authored the Plonk, Plookup and Zeromorph protocols. Plonk in particular is rapidly becoming an industry standard ZK-SNARK technology.

We are looking for experienced cryptographers to expand our R&D team and allow us to further enhance the state-of-the-art when it comes to generating proofs of private computation.

Role focus:

* Research techniques to improve both the constant and asymptotic performance of our cryptographic protocols

* Perform literature reviews to identify new developments that could improve the Prover/Verifier efficiency of our cryptographic protocols (or replace them entirely)

* Develop security proofs for our ZK-SNARK circuit architectures

* Liaise with our applied cryptographers to assist them with implementing our cryptographic protocols in software

Required experience:

* PhD-level qualification in cryptography or a related field

* Named author in one or more papers in the field of zero-knowledge cryptography

* Ability to read and understand software implementations of cryptographic protocols written in C++

* Familiarity with algorithms, data structures and basic programming concepts

* Able to provide clear and constructive feedback for more junior cryptographers / applied cryptographers, mentoring where necessary

What we offer:

* A highly competitive compensation package (including equity)

* Flexible and remote work environment

* 25 days holiday + bank holidays annually

* An opportunity to work at the cutting edge of blockchain and FinTech with a world class cryptography and engineering team

Closing date for applications:

Contact: travis@aztecprotocol.com

More information: https://boards.eu.greenhouse.io/aztec/jobs/4098527101

Full Time =nil; Foundation has been at the forefront of Ethereum scalability solutions since 2018. With a mission to overcome the Ethereum scalability challenge, the team has been working on cutting-edge products such as =nil;’s native Proof Market, zkLLVM, and Placeholder, combining advanced cryptography, zero-knowledge technology, and database management systems. Now we are looking for an experienced Cryptographer, who has an experience or a strong interest in developing zkProof systems. Responsibilities - Developing cryptography algorithms design including proof system design. - Design circuits for protocols’ state proofs for a proof system. - Academic writing. - Security analysis. - Research other solutions related to proof-system\circuits\other cryptography tasks. Qualifications - MS with major in Applied Math or equivalent experience. - Deep expertise in cryptographic algorithms and primitives. - Peer-reviewed publications in cryptography, distributed systems, proof systems. - Proven experience in ZK proof techniques (for example, Groth16, Plonk, STARKs, Marlin). - The language is English, so you’re supposed to be at least B2 level. As part of our hiring process, one of the key stages involves completing a test assignment. You can familiarize yourself with it by following this link https://nilfoundation.notion.site/Applicant-Challenge-Cryptography-Researcher-at-nil-Foundation-2dd2b4535ac14847a69ea46091b78442?pvs=74 Should you be interested, you are welcome to undertake this task and submit the link to your completed assignment along with your application. Alternatively, you may respond with your resume and opt to commence the assignment after engaging with our team. Benefits Apply to discuss your benefit package, including health insurance, language courses, relocation support or other care the company may provide.

Closing date for applications:

Contact: Alex Aristides - Alexisaristdes@nil.foundation

More information: https://nil.foundation/careers/jobs?jobId=eKBawSyO9EDP

We are seeking a highly motivated candidate for a PhD in Cybersecurity. This project aims to advance the field of healthcare cybersecurity through innovative and scalable solutions. The candidate will focus on the security and privacy of healthcare systems, including but not limited to developing decentralized, secure, and privacy-preserving methods for sharing health data.

Starting date: The position is available from January 1, 2025. An earlier commencement might be possible.

Application deadline: October 7, 2024.

We offer:

• Fully funded position for three years
• No teaching obligations
• Stimulating research environment
• Competitive salary and benefits, starting salary from NOK 532,200

More information is available at bit.ly/phd25

Closing date for applications:

Contact: Mohsen Toorani (mohsen.toorani@usn.no)

More information: https://bit.ly/phd25

Multi-party private set union (MPSU) protocol enables $m$ $(m > 2)$ parties, each holding a set, to collectively compute the union of their sets without revealing any additional information to other parties. There are two main categories of MPSU protocols: The first builds on public-key techniques. All existing works in this category involve a super-linear number of public-key operations, resulting in poor practical efficiency. The second builds on oblivious transfer and symmetric-key techniques. The only existing work in this category is proposed by Liu and Gao (ASIACRYPT 2023), which features the best concrete performance among all existing protocols, despite its super-linear computation and communication. Unfortunately, it does not achieve the standard semi-honest security, as it inherently relies on a non-collusion assumption, which is unlikely to hold in practice. Therefore, the problem of constructing a practical MPSU protocol based on oblivious transfer and symmetric-key techniques in standard semi-honest model remains open. Furthermore, there is no MPSU protocol achieving both linear computation and linear communication complexity, which leaves another unresolved problem. In this work, we resolve these two open problems.

- We propose the first MPSU protocol based on oblivious transfer and symmetric-key techniques in the standard semi-honest model. This protocol is $4.9-9.3 \times$ faster than Liu and Gao in the LAN setting. Concretely, our protocol requires only $3.6$ seconds in online phase for 3 parties with sets of $2^{20}$ items each. - We propose the first MPSU protocol achieving both linear computation and linear communication complexity, based on public-key operations. This protocol has the lowest overall communication costs and shows a factor of $3.0-36.5\times$ improvement in terms of overall communication compared to Liu and Gao.

We implement our protocols and conduct an extensive experiment to compare the performance of our protocols and the state-of-the-art. To the best of our knowledge, our implementation is the first correct and secure implementation of MPSU that reports on large-size experiments.

The one-time pad cipher is renowned for its theoretical perfect security, yet its practical deployment is primarily hindered by the key-size and distribution challenge. This paper introduces a novel approach to key distribution called q-stream, designed to make symmetric-key cryptography, and the one-time pad cipher in particular, a viable option for contemporary secure communications, and specifically, post-quantum cryptography, leveraging quantum noise and combinatorics to ensure secure and efficient key-distribution between communicating parties. We demonstrate that our key-distribution mechanism has a variable, yet quantifiable hardness of at least 504 bits, established from immutable mathematical laws, rather than conjectured-intractability, and how we overcome the one-time pad key-size issue with a localised quantum-noise seeded key-generation function, having a system hardness of at least 2304 bits, while introducing sender authentication and message integrity. Whilst the proposed solution has potential applications in fields requiring very high levels of security, such as military communications and large financial transactions, we show from our research with a prototype of q-stream, that it is sufficiently practical and scaleable for use in common browser-based web-applications, without any modification to the browser (i.e. plug-ins), running above SSL/TLS at the application level, where in tests, it achieved a key-distribution rate of around 7 million keys over a 5 minute surge-window, in a single (multi-threaded) instance of q-stream.

We show that the data storage scheme [IEEE/ACM Trans. Netw., 2023, 31(4), 1550-1565] is flawed due to the false secret sharing protocol, which requires that some random $4\times 4$ matrixes over the finite field $F_p$ (a prime $p$) are invertible. But we find its mathematical proof for invertibility is incorrect. To fix this flaw, one needs to check the invertibility of all 35 matrixes so as to generate the proper 7 secret shares.

Oblivious Transfer (OT) is a fundamental cryptographic primitive, becoming a crucial component of a practical secure protocol. OT is typically implemented in software, and one way to accelerate its running time is by using hardware implementations. However, such implementations are vulnerable to side-channel attacks (SCAs). On the other hand, protecting interactive protocols against SCA is highly challenging because of their longer secrets (which include inputs and randomness), more complicated design, and running multiple instances. Consequently, there are no truly practical leakage-resistant OT protocols yet.

In this paper, we introduce two tailored indistinguishability-based security definitions for leakage-resilient OT, focusing on protecting the sender's state. Second, we propose a practical semi-honest secure OT protocol that achieves these security levels while minimizing the assumptions on the protocol's building blocks and the use of a secret state. Finally, we extend our protocol to support sequential composition and explore efficiency-security tradeoffs.

Matrix congruential generators is an important class of pseudorandom number generators. In this paper we show how to predict a class of Matrix congruential generators matrix congruential generators with unknown parameters. Given a few truncated digits of high-order bits output by a matrix congruential generator, we give a method based on lattice reduction to recover the parameters and the initial state of the generator.