International Association
for Cryptologic Research

This paper introduces zkFFT, a novel zero-knowledge argument designed to efficiently generate proofs for FFT (Fast Fourier Transform) relations. Our approach enables the verification that one committed vector is the FFT of another, addressing an efficiency need in general-purpose non-interactive zero-knowledge proof systems where the proof relation utilizes vector commitments inputs.

We present a concrete enhancement to the Halo2 proving system, demonstrating how zkFFT optimizes proofs in scenarios where the proof relation includes one or more vector commitments. Specifically, zkFFT incorporates streamlined logic within Halo2 and similar systems, augmenting proof and verification complexity by only $O(\text{log}N)$, where $N$ is the vector size. This represents a substantial improvement over conventional approach, which often necessitates specific circuit extensions to validate the integrity of vector commitments and their corresponding private values in the arithmetic framework of the proof relation. The proposed zkFFT method supports multiple vector commitments with only a logarithmic increase in extension costs, making it highly scalable. This capability is pivotal for practical applications involving multiple pre-committed values within proof statements.

Apart from Halo2, our technique can be adapted to any other zero-knowledge proof system that relies on arithmetization, where each column is treated as an evaluation of a polynomial over a specified domain, computes this polynomial via FFT, and subsequently commits to the resulting polynomial using a polynomial commitment scheme based on inner-product arguments. Along with efficient lookup and permutation arguments, zkFFT will streamline and significantly optimize the generation of zero-knowledge proofs for arbitrary relations.

Beyond the applications in augmenting zero-knowledge proof systems, we believe that the formalized zkFFT argument can be of independent interest.

In the Dilithium digital signature scheme, there is an inherent tradeoff between the length of the public key, and the length of the signature. The coefficients of the main part of the public-key, the vector $\mathbf{t}$, are compressed (in a lossy manner), or "quantized", during the key-generation procedure, in order to save on the public-key size. That is, the coefficients are divided by some fixed denominator, and only the quotients are published. However, this results in some "skew" during the verification process, and to fix this, a special signature-dependent "hint" is computed during the signing process. Roughly speaking, stronger compression of $\mathbf{t}$ results in the hint carrying more information, consequently increasing the signature length. Prior to the hint computation, a test is performed to check whether a proper hint can indeed be composed to fix this skew, and if the test fails, the signing process is rerun with a different seed for the (pseudo-)randomness. However, in this short report we observe that this test is not performed optimally: the test calculates a sufficient condition for the hint to work, but not a necessary one. We suggest a new refined test that results in a lower probability for the sign iteration to fail. The new test exhibits some improvement (in terms of expected running time) in certain configurations that are characterized by shorter public-key length on the expense of slightly longer signature length. It is noted that the change does not imply any change in the security of the algorithm.

Collision-resistant hashing (CRH) is a cornerstone of cryptographic protocols. However, despite decades of research, no construction of a CRH based solely on one-way functions has been found. Moreover, there are black-box limitations that separate these two primitives.

Harnik and Naor [HN10] overcame this black-box barrier by introducing the notion of instance compression. Instance compression reduces large NP instances to a size that depends on their witness size while preserving the "correctness" of the instance relative to the language. Shortly thereafter, Fortnow and Santhanam showed that efficient instance compression algorithms are unlikely to exist (as the polynomial hierarchy would collapse). Bronfman and Rothblum defined a computational analog of instance compression, which they called computational instance compression (CIC), and gave a construction of CIC under standard assumptions. Unfortunately, this notion is not strong enough to replace instance compression in Harnik and Naor's CRH construction.

In this work, we revisit the notion of computation instance compression and ask what the "correct" notion for CIC is, in the sense that it is sufficiently strong to achieve useful cryptographic primitives while remaining consistent with common assumptions. First, we give a natural strengthening of the CIC definition that serves as a direct substitute for the instance compression scheme in the Harnik--Naor construction. However, we show that even this notion is unlikely to exist.

We then identify a notion of CIC that gives new hope for constructing CRH from one-way functions via instance compression. We observe that this notion is achievable under standard assumptions and, by revisiting the Harnik--Naor proof, demonstrate that it is sufficiently strong to achieve CRH. In fact, we show that our CIC notion is existentially equivalent to CRH.

Beyond Minicrypt, Harnik and Naor showed that a strengthening of instance compression can be used to construct OT and public-key encryption. We rule out the computational analog of this stronger notion by showing that it contradicts the existence of incompressible public-key encryption, which was recently constructed under standard assumptions.

Distributed point functions (DPF) are increasingly becoming a foundational tool with applications for application-specific and general secure computation. While two-party DPF constructions are readily available for those applications with satisfiable performance, the three-party ones are left behind in both security and efficiency. In this paper we close this gap and propose the first three-party DPF construction that matches the state-of-the-art two-party DPF on all metrics. Namely, it is secure against a malicious adversary corrupting both the dealer and one out of the three evaluators, its function's shares are of the same size and evaluation takes the same time as in the best two-party DPF. Compared to the state-of-the-art three-party DPF, our construction enjoys $40-120\times$ smaller function's share size and shorter evaluation time, for function domains of $2^{16}-2^{40}$, respectively.

Apart from DPFs as a stand-alone tool, our construction finds immediate applications to private information retrieval (PIR), writing (PIW) and oblivious RAM (ORAM). To further showcase its applicability, we design and implement an ORAM with access policy, an extension to ORAMs where a policy is being checked before accessing the underlying database. The policy we plug-in is the one suitable for account-based digital currencies, and in particular to central bank digital currencies (CBDCs). Our protocol offers the first design and implementation of a large scale privacy-preserving account-based digital currency. While previous works supported anonymity sets of 64-256 clients and less than 10 transactions per second (tps), our protocol supports anonymity sets in the millions, performing $\{500,200,58\}$ tps for anonymity sets of $\{2^{16},2^{18},2^{20}\}$, respectively.

Toward that application, we introduce a new primitive called updatable DPF, which enables a direct computation of a dot product between a DPF and a vector; we believe that updatable DPF and the new dot-product protocol will find interest in other applications.

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.