International Association
for Cryptologic Research

Number-Theoretic-Transform (NTT) is a variation of Fast-Fourier-Transform (FFT) on finite fields. NTT is being increasingly used in blockchain and zero-knowledge proof applications. Although FFT and NTT are widely studied for FPGA implementation, we believe CycloneNTT is the first to solve this problem for large data sets ($\ge2^{24}$, 64-bit numbers) that would not fit in the on-chip RAM. CycloneNTT uses a state-of-the-art butterfly network and maps the dataflow to hybrid FIFOs composed of on-chip SRAM and external memory. This manifests into a quasi-streaming data access pattern minimizing external memory access latency and maximizing throughput. We implement two variants of CycloneNTT optimized for DDR and HBM external memories. Although historically this problem has been shown to be memory-bound, CycloneNTT's quasi-streaming access pattern is optimized to the point that when using HBM (Xilinx C1100), the architecture becomes compute-bound. On the DDR-based platform (AWS F1), the latency of the application is equal to the streaming of the entire dataset $\log N$ times to/from external memory. Moreover, exploiting HBM's larger number of channels, and following a series of additional optimizations, CycloneNTT only requires $\frac{1}{6}\log N$ passes.

An accountable threshold signature (ATS) is a threshold signature scheme where every signature identifies the quorum of signers who generated that signature. They are widely used in financial settings where signers need to be held accountable for threshold signatures they generate. In this paper we initiate the study of proactive refresh for accountable threshold signatures. Proactive refresh is a protocol that lets the group of signers refresh their shares of the secret key, without changing the public key or the threshold. We give several definitions for this notion achieving different levels of security. We observe that certain natural constructions for an ATS cannot be proactively refreshed because the secret key generated at setup is needed for accountability. We then construct three types of ATS schemes with proactive refresh. The first is a generic construction that is efficient when the number of signers is small. The second is a hybrid construction that performs well for a large number of signers and satisfies a strong security definition. The third is a collection of very practical constructions derived from ATS versions of the Schnorr and BLS signature schemes; however these practical constructions only satisfy our weaker notion of security.

Fitzi, Garay, Maurer, and Ostrovsky (J. Cryptology 2005) showed that in the presence of a dishonest majority, no primitive of cardinality $n - 1$ is complete for realizing an arbitrary $n$-party functionality with guaranteed output delivery. In this work, we show that in the presence of $n - 1$ corrupt parties, no unreactive primitive of cardinality $n - 1$ is complete for realizing an arbitrary $n$-party functionality with fairness. We show more generally that for $t > \frac{n}{2}$, in the presence of $t$ malicious parties, no unreactive primitive of cardinality $t$ is complete for realizing an arbitrary $n$-party functionality with fairness. We complement this result by noting that $(t+1)$-wise fair exchange is complete for realizing an arbitrary $n$-party functionality with fairness. In order to prove our results, we utilize the primitive of fair coin tossing and introduce the notion of predictability in coin tossing protocols, which we believe is of independent interest.

The Fujisaki-Okamoto (FO) transform (CRYPTO 1999 and JoC 2013) turns any weakly (i.e., IND-CPA) secure public-key encryption (PKE) scheme into a strongly (i.e., IND-CCA) secure key encapsulation method (KEM) in the random oracle model (ROM). Recently, the FO transform re-gained momentum as part of CRISTAL-Kyber, selected by the NIST as the PKE winner of the post-quantum cryptography standardization project.

Following Fischlin (ICALP 2005), we study the complete non-malleability of KEMs obtained via the FO transform. Intuitively, a KEM is completely non-malleable if no adversary can maul a given public key and ciphertext into a new public key and ciphertext encapsulating a related key for the underlying blockcipher.

On the negative side, we find that KEMs derived via FO are not completely non-malleable in general. On the positive side, we show that complete non-malleability holds in the ROM by assuming the underlying PKE scheme meets an additional property, or by a slight tweak of the transformation.

We conduct a security analysis of the e-voting protocol used for the largest political election using e-voting in the world, the 2022 French legislative election for the citizens overseas. Due to a lack of system and threat model specifications, we built and contributed such specifications by studying the French legal framework and by reverse-engineering the code base accessible to the voters. Our analysis reveals that this protocol is affected by two design-level and implementation-level vulnerabilities. We show how those allow a standard voting server attacker and even more so a channel attacker to defeat the election integrity and ballot privacy due to 6 attack variants. We propose and discuss 5 fixes to prevent those attacks. Our specifications, the attacks, and the fixes were acknowledged by the relevant stakeholders during our responsible disclosure. Our attacks are in the process of being prevented with our fixes for future elections. Beyond this specific protocol, we draw general conclusions and lessons from this instructive experience where an e-voting protocol meets the real-world constraints of a large-scale and political election.

A Universal Circuit (UC) is a Boolean circuit of size $\Theta(n \log n)$ that can simulate any Boolean function up to a certain size $n$. Valiant (STOC'76) provided the first two UC constructions of asymptotic sizes $\sim5 n\log n$ and $\sim4.75 n\log n$, and today's most efficient construction of Liu et al. (CRYPTO'21) has size $\sim3n\log n$. Evaluating a public UC with a secure Multi-Party Computation (MPC) protocol allows efficient Private Function Evaluation (PFE), where a private function is evaluated on private data. Most existing UC constructions simulate circuits consisting of 2-input gates.

In this work, we study UCs that simulate circuits consisting of ($\rho \rightarrow \omega$)-Lookup Tables (LUTs) that map $\rho$ inputs to $\omega$ outputs. Existing UC constructions can be easily extend to ($\rho \rightarrow$ 1)-LUTs (we call this the fixed UC construction). We further extend this to ($\rho \rightarrow \omega$)-LUTs. Unfortunately, the size of the fixed UC construction is linear in the largest input size $\rho$ of the LUT, i.e., even if only a single LUT in the circuit has a large input size, the size of the whole UC is dominated by this LUT size. To circumvent this, we design a \emph{dynamic} UC construction, where the dimensions of the individual LUTs are public. We implement the fixed and dynamic UC constructions based on the UC construction by Liu et al., which also is the first implementation of their construction. We show that the concrete size of our dynamic UC construction improves by at least $2\times$ over Liu et al.'s UC for all benchmark circuits, that are representative for many PFE applications.

The quantum resistance Key Encapsulation Mechanism (PQC-KEM) design aims to replace cryptography in legacy security protocols. It would be nice if PQC-KEM were faster and lighter than ECDH or DH for easy migration to legacy security protocols. However, it seems impossible due to the temperament of the secure underlying problems in a quantum environment. Therefore, it makes reason to determine the threshold of the scheme by analyzing the maximum bandwidth the legacy security protocol can adapt. We specified the bandwidth threshold at 1,244 bytes based on IKEv2 (RFC7296), a security protocol with strict constraints on payload size in the initial exchange for secret key sharing. We propose TiGER that is an IND-CCA secure KEM based on RLWE(R). TiGER has a ciphertext (1,152bytes) and a public key (928 bytes) smaller than 1,244 bytes, even at the AES256 security level. To our knowledge, TiGER is the only scheme with such an achievement. Also, TiGER satisfies security levels 1, 3, and 5 of NIST competition. Based on reference implementation, TiGER is 1.7-2.6x faster than Kyber and 2.2-4.4x faster than LAC.

Security and privacy issues with centralized exchange services have motivated the design of atomic swap protocols for decentralized trading across currencies. These protocols follow a standard blueprint similar to the 2-phase commit in databases: (i) both users first lock their coins under a certain (cryptographic) condition and a timeout; (ii-a) the coins are swapped if the condition is fulfilled; or (ii-b) coins are released after the timeout. The quest for these protocols is to minimize the requirements from the scripting language supported by the swapped coins, thereby supporting a larger range of cryptocurrencies. The recently proposed universal atomic swap protocol [IEEE S&P’22] demonstrates how to swap coins whose scripting language only supports the verification of a digital signature on a transaction. However, the timeout functionality is cryptographically simulated with verifiable timelock puzzles, a computationally expensive primitive that hinders its use in battery-constrained devices such as mobile phones. In this state of affairs, we question whether the 2-phase commit paradigm is necessary for atomic swaps in the first place. In other words, is it possible to design a secure atomic swap protocol where the timeout is not used by (at least one of the two) users? In this work, we present LightSwap, the first secure atomic swap protocol that does not require the timeout functionality (not even in the form of a cryptographic puzzle) by one of the two users. LightSwap is thus better suited for scenarios where a user, running an instance of LightSwap on her mobile phone, wants to exchange coins with an online exchange service running an instance of LightSwap on a computer. We show how LightSwap can be used to swap Bitcoin and Monero, an interesting use case since Monero does not provide any scripting functionality support other than linkable ring signature verification.

A Feistel Network (FN) based block cipher relies on a Substitution Box (S-Box) for achieving the non-linearity. S-Box is carefully designed to achieve optimal cryptographic security bounds. The research of the last three decades shows that considerable efforts are being made on the mathematical design of an S-Box. To import the exact cryptographic profile of an S-Box, the designer focuses on the Affine Equivalent (AE) or Extended Affine (EA) equivalent S-Box. In this research, we argue that the Robustness of surjective mappings is invariant under AE and not invariant under EA transformation. It is proved that the EA equivalent of a surjective mapping does not necessarily contribute to the Robustness against the Differential Cryptanalysis (DC) in the light of Seberry's criteria. The generated EA equivalent S-Box(es) of DES and other $6 \times 4$ mappings do not show a good robustness profile compared to the original mappings. This article concludes that a careful selection of affine permutation parameters is significant during the design phase to achieve high Robustness against DC and Differential Power Analysis (DPA) attacks.

Traditional notions of secure multiparty computation (MPC) allow mutually distrusting parties to jointly compute a function over their private inputs, but typically do not specify how these inputs are chosen. Motivated by real-world applications where corrupt inputs could adversely impact privacy and operational legitimacy, we consider a notion of authenticated MPC where the inputs are authenticated, e.g., signed using a digital signature by some trusted authority. We propose a generic and efficient compiler that transforms any linear secret sharing based MPC protocol into one with input authentication.

Our compiler incurs significantly lower computational costs and competitive communication overheads when compared to the best existing solutions, while entirely avoiding the (potentially expensive) protocol-specific techniques and pre-processing requirements that are inherent to these solutions. For $n$-party MPC protocols with abort security where each party has $\ell$ inputs, our compiler incurs $O(n\log \ell)$ communication overall and a computational overhead of $O(\ell)$ group exponentiations per party (the corresponding overheads for the most efficient existing solution are $O(n^2)$ and $O(\ell n)$). Finally, for a corruption threshold $t
Along the way, we make several technical contributions that are of independent interest. This includes the notion of distributed proofs of knowledge and concrete realizations of the same for several relations of interest, such as proving knowledge of many popularly used digital signature schemes, and proving knowledge of opening of a Pedersen commitment. We also illustrate the practicality of our approach by extending the well-known MP-SPDZ library with our compiler, thus yielding prototype authenticated MPC protocols.

In 1993 Bernstein and Vazirani proposed a quantum algorithm for the Bernstein-Vazirani problem, which is given oracle access to the function $f(a_1,\dots,a_n) = a_1x_1+\cdots + a_nx_n \pmod 2$ with respect to a secret string $x = x_1\dots x_n \in \{0,1\}^n$, where $a_1,\dots,a_n \in \{0,1\}$, find $x$. We give a quantum algorithm for a new problem called the oracle subset product problem, which is given oracle access to the function $f(a_1,\dots,a_n) = a_1^{x_1}\cdots a_n^{x_n}$ with respect to a secret string $x = x_1\dots x_n\in\{0,1\}^n$, where $a_1,\dots,a_n\in \mathbb Z$, find $x$. Similar to the Bernstein-Vazirani algorithm, it is a quantum algorithm for a problem that is originally polynomial time solvable by classical algorithms; and that the advantage of the algorithm over classical algorithms is that it only makes one call to the function instead of $n$ calls.

The tech industry is currently making the transition from Web 2.0 to Web 3.0, and with this transition, authentication and authorization have been reimag- ined. Users can now sign in to websites with their unique public/private key pair rather than generating a username and password for every site. How- ever, many useful features, like role-based access control, dynamic resource owner privileges, and expiration tokens, currently don’t have efficient Web 3.0 solutions. Our solution aims to provide a flexible foundation for resource providers to implement the aforementioned features on any blockchain through a two-step process. The first step, authorization, creates an on-chain asset which is to be presented as an access token when interacting with a resource. The second step, authentication, verifies ownership of an asset through querying the blockchain and cryptographic digital signatures. Our solution also aims to be a multi-chain standard, whereas current Web 3.0 sign-in standards are limited to a single blockchain.

This paper presents a code-based signature scheme based on the well-known syndrome decoding (SD) problem. The scheme builds upon a recent line of research which uses the Multi-Party-Computation-in-the-Head (MPCitH) approach to construct efficient zero-knowledge proofs, such as Syndrome Decoding in the Head (SDitH), and builds signature schemes from them using the Fiat-Shamir transform.

At the heart of our proposal is a new approach to amplify the soundness of any MPC protocol that uses additive secret sharing. An MPCitH protocol with $N$ parties can be repeated $D$ times using parallel composition to reach the same soundness as a protocol run with $N^D$ parties. However, the former comes with $D$ times higher communication costs, often mainly contributed by the usage of $D$ `auxiliary' states (which in general have a significantly bigger impact on size than random states). Instead of that, we begin by generating $N^D$ shares, arranged into a $D$-dimensional hypercube of side $N$ containing only one `auxiliary' state. We derive from this hypercube $D$ sharings of size $N$ which are used to run $D$ instances of an $N$ party MPC protocol. This approach leads to an MPCitH protocol with $1/N^D$ soundness error, requiring $N^D$ offline computation, only $ND$ online computation, and only $1$ `auxiliary'. As the, potentially offline, share generation phase is generally inexpensive, this leads to trade-offs that are superior to just using parallel composition.

Our novel method of share generation and aggregation not only improves certain MPCitH protocols in general but also shows in concrete improvements of signature schemes. Specifically, we apply it to the work of Feneuil, Joux, and Rivain (CRYPTO'22) on code-based signatures, and obtain a new signature scheme that achieves a 3.3x improvement in global runtime, and a 15x improvement in online runtime for their shortest signatures size (8.5 kB). It is also possible to leverage the fact that most computations are offline to define parameter sets leading to smaller signatures: 6.7 kB for 60 ms offline, or 5.6 kB for 700 ms offline. For NIST security level 1, online signature cost is around 3 million cycles (1 ms on commodity processors), regardless of signature size.

In this paper, we examine one of the public key exchange protocols proposed in [M. I. Durcheva. An application of different dioids in public key cryptography. In AIP Conference Proceedings, vol. 1631, pp 336-343. AIP, 2014] which uses max-times and min-times algebras. We discuss properties of powers of matrices over these algebras and introduce a fast attack on this protocol.

As end-to-end encrypted messaging services become widely adopted, law enforcement agencies have increasingly expressed concern that such services interfere with their ability to maintain public safety. Indeed, there is a direct tension between preserving user privacy and enabling content moderation on these platforms. Recent research has begun to address this tension, proposing systems that purport to strike a balance between the privacy of ''honest'' users and traceability of ''malicious'' users. Unfortunately, these systems suffer from a lack of protection against malicious or coerced service providers.

In this work, we address the privacy vs. content moderation question through the lens of pre-constrained cryptography [Ananth et al., ITCS 2022]. We introduce the notion of set pre-constrained (SPC) group signatures that guarantees security against malicious key generators. SPC group signatures offer the ability to trace users in messaging systems who originate pre-defined illegal content (such as child sexual abuse material), while providing security against malicious service providers.

We construct concretely efficient protocols for SPC group signatures, and demonstrate the real-world feasibility of our approach via an implementation. The starting point for our solution is the recently introduced Apple PSI system, which we significantly modify to improve security and expand functionality.

Technology Innovation Institute (TII) is a recently-established publicly-funded research institute in Abu Dhabi (UAE). It is home to a diverse community of leading scientists and engineers from across the globe.

Job Description

We are looking for permanent researchers to join the Cryptographic Protocols team within the Cryptography Research Center (CRC) at TII. The main aim of the team is to conduct applied academic research in areas relating to cryptographic protocols, such as: TLS, QUIC, Tor, Key Exchange, Secure Channels, Cryptographic Primitives, Privacy Enhancing Technologies, MLS and Secure Messaging, and Probabilistic Data Structures in Adversarial Environments. The nature of the research spans both theory and practice, covering aspects such as provable security, security models, efficient designs, implementation aspects, and attacks.

Applicants should have completed (or be close to completing) their PhD in a related area, and postdoctoral research experience will be valued. Preference will be given to applicants with publications in top-tier venues such as CRYPTO, EUROCRYPT, ASIACRYPT, ACM CCS, IEEE S&P, and USENIX.

Required Skills:

• Fluency in English (verbal and written) and an ability to communicate research effectively.
• Good problem-solving skills and an ability to conduct research independently.
• Good interpersonal and collaborative skills.
• Solid knowledge in cryptography.

Valuable Skills:

• Research experience in Key Exchange, Signatures, Onion Routing, Privacy-Enhancing Technologies, and Zero Knowledge.
• Programming, Software Engineering, experience in implementing cryptographic primitives and attacks on real-world cryptosystems, reverse engineering of closed-source protocols.

What we offer:

• Vibrant working environment, flexible working conditions, and travel funding.
• Industry-competitive tax-free salary.
• Family-wide health insurance and children’s education allowance.
• Sunshine all year round.

Closing date for applications:

Contact: Jean Paul Degabriele (jeanpaul.degabriele@tii.ae).

The Centre for Doctoral Training (CDT) at Royal Holloway, University of London seeks to recruit PhD students to work in the area of cryptography. Examples for potential topics include:

• Foundations of Witness Encryption and Smart Encryption (supervised by Saqib Kakvi)
• Secure Coded Caching (supervised by Siaw-Lynn Ng)
• Applications of Time and Delay in Cryptographic Protocols (supervised by Elizabeth Quaglia)
• Privacy-Preserving Applications based on Secure Multi-Party Computation (supervised by Christian Weinert)

You can find more details for these and other project proposals on FindAPhD.com [1].

The crypto team at Royal Holloway, as part of the Information Security Group (ISG), has a strong track record in cryptographic research, including algorithm design and analysis, post-quantum cryptography, homomorphic encryption, and applications of secure computation.

Applicants are expected to have a background in mathematics, computer science, or a related discipline. Prospective applicants are welcome to contact CDT administrator Claire Hudson (CyberSecurityCDT@rhul.ac.uk) or any member of staff they might be interested to work with. For more information about the crypto team, please visit our website [2].

The CDT can offer approximately ten studentships per year, three of which can be awarded to international students (including EU and EEA). Please ensure you are familiar with the eligibility criteria set by UKRI and their terms and conditions. In order to apply, please visit the CDT website [3] and follow the application instructions. The studentship includes a (tax-free) maintenance of £23,668.00 for each academic year.

[1] https://www.findaphd.com/phds/information-security-group/?c0MPwk50
[2] https://cryptography.isg.rhul.ac.uk
[3] https://www.royalholloway.ac.uk/cdt

Closing date for applications:

Contact: CyberSecurityCDT@rhul.ac.uk

Applications are invited for one Postdoctoral Research Fellow position at Eötvös Loránd University, Budapest. The candidate is expected to carry out research in the topic of post-quantum cryptography (lattice-based, multivariate, code-based or isogeny -based cyrptography). The research will be conducted as part of the Quantum Information National Laboratory, which is a collaboration between several universities and research institutes in Budapest. The applicant is supposed to hold a Phd in Computer Science or Mathematics (the degree should be obtained by the starting date). The position is for two years and expected starting date is April 2023, however the starting date is negotiable (but not later than September 2023). If you want to apply for this position please send the following documents to Péter Kutas (kuppabt@inf.elte.hu):

• CV
• Motivation Letter
• Two recommendation letters (these should be sent by the recommending person directly to the above e-mail address)

Please send your applications by 31st January 2023.

Closing date for applications:

Contact: Péter Kutas (kuppabt@inf.elte.hu)

The School of Engineering at the Universidad Católica de Chile, one of the leading engineering academic institutions in Latin America and ranked among the top four emerging leaders for engineering education worldwide, invites outstanding candidates for a full-time faculty position in the area of cybersecurity. Duties: High-quality teaching (at undergraduate and graduate levels), and conducting independent research. Additional duties include knowledge transfer, outreach, and university administrative tasks. The new position should conduct teaching, research, and technological innovation activities in cybersecurity and cryptography, including but not limited to privacy, data protection, computer network security, information technology security, software and application security, blockchain, computer forensics, smart contracts, data integrity, among others. The selected candidate is expected to develop a strong externally funded research program, support doctoral programs, and teach three courses per year, at least two of these courses should belong to the bachelor of science in computer science program, and another course according to their expertise. Requirements: Applicants must hold a Ph.D., preferably in Computer Science, and/or have demonstrable expertise in the fields. Due to the nature of our School, the applicant will have the opportunity and should be willing to work collaboratively with other Departments in the School of Engineering. Previous postdoctoral or international academic experience should be stated in the application. Candidates do not need to be fluent in Spanish at the time of application, but should be prepared to learn the language well enough to teach in this language in the short term (two years maximum). English is a requirement.

Closing date for applications:

Contact: Marcelo Arenas, marenas@ing.puc.cl

More information: https://www.ing.uc.cl/trabaja-con-nosotros/areas-to-apply-2/

A postdoctoral position is available in the APSIA research group (led by Prof. Peter Y. A. Ryan) in the Department of computer Science at the University of Luxembourg. The successful candidate is expected to do research in line with ‘’quantum safe proofs’’ (QSP) project funded by Luxembourg National Research Fund. The successful candidate will conduct the QSP project in collaboration with Prof. Peter Y. A. Ryan, Prof. Anne Broadbent (University of Ottawa, Canada) and Dr. Ehsan Ebrahimi (PI, University of Luxemburg).

The duration of the position is two years. The yearly gross salary for every Postdoctoral researcher at the UL is around EUR 77167 (full time) . The starting date would be as early as 02.01.2023 (Feb 2023).

The successful candidate will conduct the following tasks:

• Research on post-quantum security of proof systems and its impact to applications like cryptocurrencies and electronic voting systems.
• Research on Quantum Proof Systems: for instance, complexity classes QMA, QIP, etc.
• Participate in teaching tasks and Ph.D. and M.Sc. students supervisions
• Collaboration with writing progress reports

we expect:

• A Ph.D. degree in Computer Science, Mathematics or Physics with the focus on Cryptography and its intersection with Quantum Computation & Information.
• Experience working on quantum-secure proof systems or quantum proof systems is a plus
• Competitive research record in cryptography or quantum computation & information
• Strong mathematical CS background
• Fluent written and verbal communication skills in English are required

Applications should include a short letter of motivation, a CV, a publication list with short summery for each publication, and names of at least 2 reference letter writers . Early application is highly encouraged, as the applications will be processed upon reception.

Closing date for applications:

Contact: Ehsan Ebrahimi, ehsan.ebrahimi@uni.lu