International Association
for Cryptologic Research

Top trading cycles (TTC) is a famous algorithm for trading indivisible goods between a set of agents such that all agents are as happy as possible about the outcome. In this paper, we present a protocol for executing TTC in a privacy preserving way. To the best of our knowledge, it is the first of its kind. As a technical contribution of independent interest, we suggest a new algorithm for determining all nodes in a functional graph that are on a cycle. The algorithm is particularly well suited for secure implementation in that it requires no branching and no random memory access. Finally, we report on a prototype implementation of the protocol based on somewhat homomorphic encryption.

Deterministic broadcast protocols among $n$ parties tolerating $t$ corruptions require $\min\{f+2, t+1\}$ rounds, where $f \le t$ is the actual number of corruptions in an execution of the protocol. We provide the first protocol which is optimally resilient, adaptively secure, and asymptotically matches this lower bound for any $t<(1-\varepsilon)n$. By contrast, the best known algorithm in this regime by Loss and Nielsen (EUROCRYPT'24) always requires $O(\min\{f^2, t\})$ rounds. Our main technical tool is a generalization of the notion of polarizer introduced by Loss and Nielsen, which allows parties to obtain transferable cryptographic evidence of missing messages with fewer rounds of interaction.

Recent advances in differentially private federated learning (DPFL) algorithms have found that using correlated noise across the rounds of federated learning (DP-FTRL) yields provably and empirically better accuracy than using independent noise (DP-SGD). While DP-SGD is well-suited to federated learning with a single untrusted central server using lightweight secure aggregation protocols, secure aggregation is not conducive to implementing modern DP-FTRL techniques without assuming a trusted central server. DP-FTRL based approaches have already seen widespread deployment in industry, albeit with a trusted central curator who provides and applies the correlated noise.

To realize a fully private, single untrusted server DP-FTRL federated learning protocol, we introduce secure stateful aggregation: a simple append-only data structure that allows for the private storage of aggregate values and reading linear functions of the aggregates. Assuming Ring Learning with Errors, we provide a lightweight and scalable realization of this protocol for high-dimensional data in a new security/resource model, Federated MPC: where a powerful persistent server interacts with weak, ephemeral clients. We observe that secure stateful aggregation suffices for realizing DP-FTRL-based private federated learning: improving DPFL utility guarantees over the state of the art while maintaining privacy with an untrusted central party. Our approach has minimal overhead relative to existing techniques which do not yield comparable utility. The secure stateful aggregation primitive and the federated MPC paradigm may be of interest for other practical applications.

The compressed $\Sigma$-protocol theory [AC20, ACF21] presents a standard framework for constructing efficient $\Sigma$-protocols. This approach primarily consists of two phases: amortization to fold multiple instances satisfying a homomorphic relation into one, and Bulletproofs compression [BBB+18] to reduce the communication overhead to a logarithmic scale when verifying the folded instance. For high-degree polynomial (non-homomorphic) relations, a circuit-based linearization technique is employed to convert each instance into a linear relation, resulting in a protocol with at least linear complexity.

In this paper, we provide a direct method to extend the compressed $\Sigma$-protocol theory to polynomial relations. One major objective is to avoid the linear cost of linearization. To achieve this, we employ a sum-check during the amortization phase to ensure a logarithmic communication cost. To the best of our knowledge, this is the first work to achieve a logarithmic amortization for polynomial relations. Nevertheless, without linearization, the amortized relation may not be linear, which hinders us from using Bulletproofs compression. To overcome this problem, we employ another sum-check during the compression phase to effectively manage high-degree relations. This allows us to extend the compressed $\Sigma$-protocol framework to polynomial relations. Furthermore, we introduce several variants of our techniques and adapt them for arithmetic circuit relations. We conclude by showcasing the practicality of our compressed $\Sigma$-protocol theory through applications such as binary proofs, range proofs, and partial knowledge proofs. Our basic protocols are initially based on the Discrete Logarithm (DL) assumption. We have also extended them to incorporate the Strong-RSA assumption and the Generalized Discrete Logarithm Representation (GDLR) assumption. Our work expands the scope of compressed $\Sigma$-protocol theory and provides a robust foundation for real-world cryptographic applications.

Traditional secure multiparty computation (MPC) protocols presuppose a fixed set of participants throughout the computational process. To address this limitation, Fluid MPC [CRYPTO 2021] presents a dynamic MPC model that allows parties to join or exit during circuit evaluation dynamically. However, existing dynamic MPC protocols can guarantee safety but not liveness within asynchronous networks. This paper introduces ΠAD-MPC, a fully asynchronous dynamic MPC protocol. ΠAD-MPC ensures both safety and liveness with optimal resilience, capable of tolerating t (n=3t+1) corrupted participants. To achieve this, we develop a novel asynchronous transfer protocol ΠTrans and a preprocessing protocol ΠAprep specifically tailored for dynamic environments. In contrast to most dynamic MPC protocols that achieve security with abort in synchronous networks, ΠAD-MPC guarantees output delivery in asynchronous networks with optimal resilience, thus enhancing robustness. We provide a formal security proof of ΠAD-MPC under the Universal Composability (UC) framework. Furthermore, an extensive evaluation involving up to 20 geographically distributed nodes demonstrates the protocol’s practical performance and its ability to reliably deliver outputs in asynchronous dynamic settings. Compared to the state-of-the-art Fluid MPC, ΠAD-MPC achieves comparable performance while offering significantly enhanced security guarantees.

The existence of pseudorandom unitaries (PRUs)---efficient quantum circuits that are computationally indistinguishable from Haar-random unitaries---has been a central open question, with significant implications for cryptography, complexity theory, and fundamental physics. In this work, we close this question by proving that PRUs exist, assuming that any quantum-secure one-way function exists. We establish this result for both (1) the standard notion of PRUs, which are secure against any efficient adversary that makes queries to the unitary $U$, and (2) a stronger notion of PRUs, which are secure even against adversaries that can query both the unitary $U$ and its inverse $U^\dagger$. In the process, we prove that any algorithm that makes queries to a Haar-random unitary can be efficiently simulated on a quantum computer, up to inverse-exponential trace distance.

Visa Research conducts both applied and fundamental research while engaging with the company's technology and product teams, business partners, academics, and governments, to explore and develop technologies that are critical to the payments industry in the future.
Currently, we focus on building research teams in key areas: Data Analytics, Cryptography, Security, and Future of Payment (Blockchain), and Artificial Intelligence. We are looking for outstanding researchers and engineers at all levels of experience as part of our growing team!
Visa Research’s goal of security is to enable policy-enforced, full lifecycle protection for data at rest, in transit and during computation for all payment-related scenarios. We accomplish this through fundamental and applied research in the following areas:

Cryptography (MPC, PQC, Foundational)

Systems Security

Identity & Authentication

Security and Privacy in Machine Learning

Please see https://smrtr.io/nhPGH for more information.

Closing date for applications:

Contact: Samuel Cook (scook@visa.com) or Peter Rindal (perindal@visa.com)

More information: https://smrtr.io/nhPGH

The Cryptography Research Group at University College Cork, Ireland is looking for a highly motivated Post-Doctoral or Senior Post-Doctoral Researcher in differential privacy and related privacy preservation techinques. The researchers will be employed on an industry-funded research project sponsored by a major Internet company (get in touch for more details).

Candidates should have a PhD in cryptography or cyber security, with a good track record of publications. Ideally, they will have experience in one or more of the following areas: differential privacy, anonymity, re-identification and/or cryptography-based privacy enhancing technologies. Candidates with a background in other areas of cryptography/privacy/security, but with a strong interest in differential privacy will also be considered. A strong mathematical background is expected, complemented with programming skills. Experience with relevant libraries such as IBM Diffprivlib, Opacus, SecretFlow etc. is an asset (but not required).

The position is until December 2025, with a possibility of extension subject to availability of funding. The successful candidates will be appointed at Post-Doctoral or Senior Post-Doctoral level depending on their experience and qualifications. A budget for travel, equipment, publications and other research expenses is available as part of the project.

The Cryptography Research Group is led by Dr Paolo Palmieri and consists of 8 researchers at doctoral and post-doctoral level. The hired researcher will be encouraged to collaborate with other members of the group, and to take a mentoring role with some of the more junior researchers. There will also be ample opportunities to work with the group’s extensive network of international collaborations.

Closing date for applications:

Contact: Informal inquiries can be made in confidence to Dr. Paolo Palmieri, at: p.palmieri@cs.ucc.ie
Applications should be submitted through the University portal at https://ore.ucc.ie/

More information: https://security.ucc.ie/vacancies.html

We are looking for two PhD students who wish to pursue research in applied cryptography. The positions are fully funded and the starting date is negotiable.

The candidates will work on topics including but not limited to:

• Cryptanalyzing existing cryptographic protocols in the literature and the industry
• Encrypted databases
• Distributed systems

Other research topics are possible upon negotiation.

If interested, please send an email (with a CV and cover letter) to Dr. Zichen Gui (Zichen.Gui@uga.edu).

Closing date for applications:

Contact: Zichen Gui (Zichen dot Gui at uga dot edu)

The cryptography group at the University of Tartu, Estonia, has two openings for tenured lectureships (corresponding to the assistant professorship in the US) in cryptography. The first position is aimed at a person working in modern zero-knowledge proofs, zk-SNARKs, their construction, and security proofs. The person is expected to have a strong cryptography background and several publications in IACR or equivalent conferences. The second position is aimed at a person working at the intersection of coding theory and cryptography, and an interest in hash and code-based zk-SNARKs is appreciated. The person is expected to have a strong background either in coding-theory and cryptography (preferably both) with several publications in IACR or equivalent conferences in cryptography or equivalent venues in coding theory.

Helger Lipmaa leads the cryptography research group, but the department also has a strong coding theory group. Both applicants are expected to collaborate scientifically with the existing groups. Despite the name of the positions, they are research-heavy. We encourage outside activities, like consulting for ZK companies, as long as they are done via the university.

Please contact Helger Lipmaa if you have any questions.

Official application links with other relevant information are at https://ut.ee/en/job-offer/lecturer-cryptography and https://ut.ee/en/job-offer/lecturer-coding-theory-and-cryptography (two separate openings).

Application deadline: 01.11.2024

Closing date for applications:

Contact: Helger Lipmaa (firstname.lastname@gmail.com)

More information: https://crypto.cs.ut.ee/

CISPA is a world-leading research center that focuses on Information Security and Machine Learning at large. To expand and further strengthen our center, we are looking for

Tenure-Track Faculty in Artificial Intelligence and Machine Learning (f/m/d)

All applicants are expected to grow a research team that pursues an internationally visible research agenda. To aid you in achieving this, CISPA provides institutional base funding for three full-time researcher positions and a generous budget for expenditures. Upon successful tenure evaluation, you will hold a position that is equivalent to an endowed full professorship at a top research university.

We invite applications of candidates with excellent track records in Artificial Intelligence and Machine Learning, especially in (but not limited to) the fields of

Accountability and Authenticity

Causality

Fairness

Federated and Decentralized Learning

Foundations of Statistically Sound (Deep) Learning from Data

Human Factors of AI

Interpretability and Explainability,

Neuro-Symbolic Learning

Privacy

Reinforcement Learning

Robustness and Reliability

Sample- and Computationally Efficient Mining and Learning

Secure and Safe AI

CISPA values diversity and is committed to equality. We provide special dual-career support. We explicitly encourage female and diverse researchers to apply.

Closing date for applications:

Contact: scientific-recruiting@cispa.de

More information: https://jobs.cispa.saarland/de_DE/jobs/detail/tenure-track-faculty-in-artificial-intelligence-and-machine-learning-f-m-d-2024-2025-254

CISPA is a world-leading research center that focuses on Information Security and Machine Learning at large. To expand and further strengthen our center, we are looking for

Tenure-Track Faculty in all areas related to Information Security (f/m/d)

All applicants are expected to grow a research team that pursues an internationally visible research agenda.

To aid you in achieving this, CISPA provides institutional base funding for three full-time researcher positions and a generous budget for expenditures. Upon successful tenure evaluation, you will hold a position that is equivalent to an endowed full professorship at a top research university.

We invite applications of candidates with excellent track records in all areas related to Information Security.

CISPA values diversity and is committed to equality. We provide special dual-career support. We explicitly encourage female and diverse researchers to apply.

Closing date for applications:

Contact: scientific-recruiting@cispa.de

More information: https://jobs.cispa.saarland/de_DE/jobs/detail/tenure-track-faculty-in-all-areas-related-to-information-security-f-m-d-2024-2025-255

We are looking for a strong candidate that would be interested in pursuing a PhD on privacy-preserving machine learning at Monash University (a world top 50 university) in the vibrant city of Melbourne, Australia (frequently ranked among the top 10 cities to live in the world).

Closing date for applications:

Contact: rafael.dowsley@monash.edu

Proving non-native operations is still a bottleneck in existing incrementally verifiable computations. Prior attempts to solve this issue either simply improve the efficiency of proofs of non-native operations or require folding instances in each curve of a cycle. This paper shows how to avoid altogether in-circuit proofs of non-native operations in the incre- mental steps, and only record them in some auxiliary proof information. These operations are proved natively at the end of the computation, at the cost of only a small constant number (four or five) of non-native field multiplications to go from a non-native operation record to a native one. To formalise the security guarantees of the scheme, the paper introduces the concept of incrementally verifiable computation with auxiliary proof information, a relaxation of the standard notion of incrementally veri- fiable computation. The knowledge-soundness now guarantees the cor- rectness of a computation only if the piece of information attached to a proof is valid. This new primitive is thus only to be used if there is an efficient mechanism to verify the validity of that information. This relaxation is exactly what enables a construction which does not require in-circuit proofs of non-native operations during the incremental part of the computation. Instantiated in the Plonk arithmetisation, the construction leads to savings in circuit-gate count (compared to standard folding-based constructions) of at least one order of magnitude, and that can go up to a factor of 50.

Oblivious map (OMAP) is an important component in encrypted databases, utilized to safeguard against the server inferring sensitive information about client's encrypted key-value stores based on \emph{access patterns}. Despite its widespread usage and importance, existing OMAP solutions face practical challenges, including the need for a large number of interaction rounds between the client and server, as well as the substantial communication bandwidth requirements. For example, the state-of-the-art protocol named OMIX++ in VLDB 2024 still requires $O(\log{n})$ interaction rounds and $O(\log^2{n})$ communication bandwidth per access, where $n$ denote the total number of key-value pairs stored.

In this work, we introduce more practical and efficient OMAP constructions. Consistent with all prior OMAPs, our proposed constructions also adapt only the \emph{tree-based Oblivious RAM} (ORAM) to achieve OMAP for enhanced practicality. In terms of complexity, our approach needs only $O(\log{n}/\log{\log{n}})$ interaction rounds and $O(\log^2{n}/\log{\log{n}})$ communication bandwidth per data access, achieving the lowest communication volume to the best our of knowledge. This improvement results from our two main contributions. First, unlike prior works that rely solely on search trees, we design a novel framework for OMAP that combines hash table with search trees. Second, we propose a more efficient tree-based ORAM named DAORAM, which is of significant independent interest. This newly developed ORAM noticeably accelerates our constructions. We implement both our proposed constructions and prior methods to experimentally demonstrate that our constructions substantially outperform prior methods in terms of efficiency.

We improve the performance of lattice-based cryptosystems Dilithium on Cortex-M3 with expensive multiplications. Our contribution is two-fold: (i) We generalize Barrett multiplication and show that the resulting shape-independent modular multiplication performs comparably to long multiplication on some platforms without special hardware when precomputation is free. We call a modular multiplication “shape-independent” if its correctness and efficiency depend only on the magnitude of moduli and not the shapes of the moduli. This was unknown in the literature even though modular multiplication has been studied for more than 40 years. In the literature, shape-independent modular multiplications often perform several times slower than long multiplications even if we ignore the cost of the precomputation. (ii) We show that polynomial multiplications based on Nussbaumer fast Fourier transform and Toom–Cook over $\mathbb{Z}_{2^k}$ perform the best when modular multiplications are expensive and $k$ is not very close to the arithmetic precision.

For practical evaluation, we implement assembly programs for the polynomial arithmetic used in the digital signature Dilithium on Cortex-M3. For the modular multiplications in Dilithium, our generalized Barrett multiplications are 1.92 times faster than the state-of-the-art assembly-optimized Montgomery multiplications, leading to 1.38−1.51 times faster Dilithium NTT/iNTT. Along with the improvement in accumulating products, the core polynomial arithmetic matrix-vector multiplications are 1.71−1.77 times faster. We further apply the FFT-based polynomial multiplications over $\mathbb{Z}_{2^k}$ to the challenge polynomial multiplication $c t_0$, leading to 1.31 times faster computation for $c t_0$.

We additionally apply the ideas to Saber on Cortex-M3 and demonstrate their improvement to Dilithium and Saber on our 8-bit AVR environment. For Saber on Cortex-M3, we show that matrix-vector multiplications with FFT-based polynomial multiplications over $\mathbb{Z}_{2^k}$ are 1.42−1.46 faster than the ones with NTT-based polynomial multiplications over NTT-friendly coefficient rings. When moving to a platform with smaller arithmetic precision, such as 8-bit AVR, we improve the matrix-vector multiplication of Dilithium with our Barrett-based NTT/iNTT by a factor of 1.87−1.89. As for Saber on our 8-bit AVR environment, we show that matrix-vector multiplications with NTT-based polynomial multiplications over NTT-friendly coefficient rings are faster than polynomial multiplications over $\mathbb{Z}_{2^k}$ due to the large $k$ in Saber.

This article discusses fully homomorphic encryption and homomorphic sorting. Homomorphic encryption is a special encryption technique that allows all kinds of operations to be performed on ciphertext, and the result is still decryptable, such that when decrypted, the result is the same as that obtained by performing the same operation on the plaintext. Homomorphic sorting is an important problem in homomorphic encryption. Currently, there has been a volume of work on homomorphic sorting. In these works, each integer in a sequence is encrypted in a separate ciphertext, there is a lack of research on sorting sequences of integers encrypted in a single ciphertext. This paper addresses the sorting problem by utilizing Single Instruction Multiple Data (SIMD) technology to provide new algorithms to improve computational efficiency. The content includes the following aspects. For plaintexts encrypted word-wise, this paper studies sorting an integer sequence stored in one or multiple ciphertexts, and proposes a new SIMD-style homomorphic sorting algorithm. On theoretical complexity, compared with three existing sorting algorithms, namely, homomorphic sorting by polynomial computation over a finite field, by TFHE bootstrapping, or by Liu-Wang parallel bootstrapping, the new algorithm achieves a speedup of $O((\log n)^2)$, $O(n(\log n)^3)$, and $O((\log n)^4)$, respectively, for sorting a plaintext integer sequence of length $n$. By experimental results, the new algorithm is 1.7-9.2 times faster than the three sorting algorithms. The third situation involves sorting multiple shorter sequences simultaneously, all of which can be stored in a single ciphertext. For this situation, this paper proposes a method for calculating the ord function, and uses this method to provide a new sorting algorithm. On theoretical complexity, if the total number of numbers to be sorted is $n$ and there are $n^r$ numbers in each sequence, the new algorithm is faster than three existing sorting algorithms, with speed-ups of $O(n^{1-r}(\log n)^2)$, $O(n^{2-r}(\log n)^3)$, and $O(n^{1-r}(\log n)^4)$, respectively. By experimental results, the new algorithm is 2.1-6.4 times faster than existing sorting algorithms.

Zero-knowledge for set membership is a building block at the core of several privacy-aware applications, such as anonymous payments, credentials and whitelists. We propose a new efficient construction for the batching variant of the problem, where a user intends to show knowledge of several elements (a batch) in a set without any leakage on the elements. Our construction is transparent—it does not requires a trusted setup—and based on Curve Trees by Campanelli, Hall-Andersen and Kamp (USENIX 2023). Our first technical contribution consists in techniques to amortize Curve Trees costs in the batching setting for which we crucially exploit its algebraic properties. Even for small batches we obtain $\approx 2\times$ speedups for proving, $\approx3\times$ speedups for verification and $\approx 60\%$ reduction in proof size. Our second contribution is a modifications of a key technical requirement in Curve Trees (related to so called "permissible points") which arguably simplifies its design and obtains a stronger security property. In particular, our construction is secure even for the case where the commitment to the set is provided by the adversary (in contrast to the honest one required by the original Curve Trees).

This paper studies transaction execution mechanisms (TEMs) for blockchains, as the efficient resource allocation across multiple parallel executions queues or "local fee markets." We present a model considering capacity constraints, user valuations, and delay costs in a multi-queue system with an aggregate capacity constraint due to global consensus. We show that revenue maximization tends to allocate capacity to the highest-paying queue, while welfare maximization generally serves all queues. Optimal relative pricing of different queues depends on factors such as market size, demand elasticity, and the balance between local and global congestion. Our results have implications for evolving blockchain architectures, including parallel execution, DAG-based systems, and multiple concurrent proposers, and can help design more efficient TEMs.

This paper investigates the open problem of how to construct non-interactive rational proofs. Rational proofs, introduced by Azar and Micali (STOC 2012), are a model of interactive proofs where a computationally powerful server can be rewarded by a weaker client for running an expensive computation $f(x)$. The honest strategy is enforced by design when the server is rational: any adversary claiming a false output $y \neq f(x)$ will lose money on expectation. Rational proof constructions have appealing properties: they are simple, feature an extremely efficient verifier—reading only a sublinear number of bits of the input $x$—and do not require any collateral from the prover. Currently, all non-trivial constructions of rational proofs are interactive. Developing non-interactive rational protocols would be a game-changer, making them practical for use in smart contracts, one of their most natural applications. Our investigation revolves around the Fiat-Shamir transform, a common approach to compiling interactive proofs into their non-interactive counterparts. We are the first to tackle the question: "Can Fiat-Shamir be successfully applied to rational protocols?" We find negative evidence by showing that, after applying Fiat-Shamir in the random oracle model to two representative protocols in literature (AM13 and CG15) these lose their security guarantees. Our findings point to more general impossibility theorems, which we leave as future work. To achieve our results we first need to address a fundamental technical challenge: the standard Fiat-Shamir transform does not apply to protocols where the verifier has only oracle access to its input $x$ (a core feature of the rational setting). We propose two versions of Fiat-Shamir for this setting, a "vanilla" variant and a "stronger" variant (where the verifier has access to an honestly computed digest of its input). We show that neither variant is sufficient to ensure that AM13 or CG15 are secure in the non-interactive setting. Finally, as an additional contribution, we provide a novel, and arguably simpler, definition for the soundness property of rational proofs (interactive or non-interactive) of independent interest.