International Association
for Cryptologic Research

The Luxembourg Institute of Science and Technology (LIST) is a Research and Technology Organization (RTO) active in the fields of materials, environment and IT. By transforming scientific knowledge into technologies, smart data and tools, LIST empowers citizens in their choices, public authorities in their decisions and businesses in their strategies.

How will you contribute? Your specific mission includes, but is not limited to, participating into the following activities along with the project partners:

• To design and develop privacy-preserving federated data management technologies
• To prototype privacy-preserving technologies for cyberthreat intelligence, data analysis or cybersecurity
• To develop open-source software
• To validate the effectiveness of developed technologies You are in charge of disseminating and promoting the research activities that will be carried out, whether through publications, prototype development or technical reports

You’re highly motivated and have proven skills in federated data processing such as applying simple statistics or advanced machine learning tools, to improve the utility of the obtained information. You have already good experience in collaborative cyber threat intelligence systems that use advanced analytics solutions an can offer significant advantages over the local systems by detecting cyberattacks early and promptly responding to them. And last, but not least, you’re a great practitioner of privacy-enhancing techniques such as secure multiparty computation, homomorphic encryption, and anonymization. Is Your profile described below? Are you our future colleague? Apply now! As to join us, you:

• Hold a PhD. degree in Computer Science or related disciplines
• Have good programming skills (particularly experience on Python and C++)
• Have good track record on applied cryptography, such as secure multiparty computation and homomorphic encryption. Knowledge on secure aggregation techniques or zero-knowledge proofs is a plus.
• Demonstrate strong interest and experience in anonymization techniques such as differential privacy, Google’s RAPPOR

Closing date for applications:

Contact: Orhan Ermis

More information: https://app.skeeled.com/offer/6554879c69ccf56b0c1432df?utm_id=60fed4c509c80d16d1bbe536&utm_medium=OFFERS_PORTAL&language=en&show_description=true

Salary: GBP 36,024 to 41,732 per annum depending on experience

Fixed Term Contract until 30th September 2025

Closing Date: Monday 15th January

This post will work on challenges around decentralized identity and personal data, and approaches across distributed platforms such as Distributed Ledgers.

The Computer Science Research Centre at the University of Surrey is seeking to recruit a full-time researcher to the Surrey Centre for Cyber Security (SCCS). The successful candidate will join the DECaDE Next Stage Digital Economy Centre for the Decentralised Digital Economy (http://decade.ac.uk), a multidisciplinary UKRI-funded Centre with the University of Surrey, the University of Edinburgh, and the Digital Catapult.

The Centre is initially focused on three themes: value co-creation in the digital economy, data trusts for identity and data, and the world of work and the gig economy.

Surrey is recognized by the National Cyber Security Centre as an Academic Centre of Excellence in Cyber Security Research, and offers a thriving research environment with world leading researchers. We were also recognised as Cyber University of the Year 2023 in the National Cyber Awards. Our research includes security and privacy, verification, cryptography, distributed systems, and networked systems.

The position offers the platform for the research fellow to develop skills to become an independent researcher and to contribute to the DECaDE vision. The successful candidate will work within a team under the direction of Professor Steve Schneider. Significant interaction with project partners is encouraged, and the dissemination strategy may involve national and international travel, with many personal development opportunities.

Closing date for applications:

Contact: Contact: Professor Steve Schneider: s.schneider@surrey.ac.uk

More information: https://jobs.surrey.ac.uk/Vacancy.aspx?id=13775

The existence of "unstructured" hard languages in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether $\mathsf{P}$ is separated from $\mathsf{NP} \cap \mathsf{coNP}$ relative to a random oracle, a question that remained open ever since. While a hard language in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ can be constructed in a black-box way from a one-way permutation, for which only few (structured) candidates exist, Bitansky et al. (SICOMP, 2021) ruled out such a construction based on an injective one-way function, an unstructured primitive that is easy to instantiate heuristically. In fact, the latter holds even with a black-box use of indistinguishability obfuscation.

We give the first evidence for the existence of unstructured hard languages in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ by showing that if $\mathsf{UP} \not \subseteq \mathsf{RP}$, which follows from the existence of injective one-way functions, the answer to Bennett and Gill's question is affirmative: with probability 1 over a random oracle $\cal O$, we have that $\mathsf{P}^{\cal O} \neq \mathsf{NP}^{\cal O} \cap \mathsf{coNP}^{\cal O}$. Our proof gives a constructive non-black-box approach for obtaining candidate hard languages in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ from cryptographic hash functions.

The above conditional separation builds on a new construction of non-interactive zero-knowledge (NIZK) proofs, with a computationally unbounded prover, to convert a hard promise problem into a hard language. We obtain such NIZK proofs for $\mathsf{NP}$, with a uniformly random reference string, from a special kind of hash function which is implied by (an unstructured) random oracle. This should be contrasted with previous constructions of such NIZK proofs that are based on one-way permutations or other structured primitives, as well as with (computationally sound) NIZK arguments in the random oracle model.

Quantum Fourier Transformation (QFT) plays a key role in quantum computation theory. But its transform size has never discussed. In practice, the Xilinx LogiCORE IP Fast Fourier Transform core has the maximum transform size $N=2^{16}$. Taking into account the Planck constant $\hbar=6.62607015\times 10^{-34}$ and the difficulty to physically implement basic operator {\footnotesize $\left[ \begin{array}{cc} 1& 0\\ 0 & \exp(-2\pi\,i/N)\\ \end{array} \right]$} on some qubits, we think $N=2^{120}$ could be an upper bound for the transform size of QFT.

Maiorana--McFarland type constructions are basically concatenating the truth tables of linear functions on a smaller number of variables to obtain highly nonlinear ones on larger inputs. Such functions and their different variants have significant applications in cryptology and coding theory. Straightforward hardware implementation of such functions may require exponential resources on the number of inputs. In this paper, we study such constructions in detail and provide implementation strategies for a selected subset of this class with polynomial many gates over the number of inputs. We demonstrate that such implementations cover the requirement of cryptographic primitives to a great extent. Several existing constructions are revisited in this direction and exact implementations are provided with specific depth and gate counts in the hardware implementation. Related combinatorial as well as circuit complexity-related results of theoretical nature are also analyzed in this regard. Finally we present a novel construction of a new class of balanced Boolean functions having very low absolute indicator and very high nonlinearity that can be implemented in polynomial circuit size over the number of inputs. In conclusion, we present that these constructions have immediate applications to resist the signature generation in Differential Fault Attack (DFA) and to implement functions on large number of variables in designing ciphers for the paradigm of Fully Homomorphic Encryption (FHE).

The popularity of cloud computing has made outsourced databases prevalent in real-world applications. To protect data security, numerous encrypted outsourced databases have been proposed for this paradigm. However, the maintenance of encrypted databases has scarcely been addressed. In this paper, we focus on a typical maintenance task --- functional dependency (FD) discovery. We develop novel FD protocols in encrypted databases while guaranteeing minimal leakages: nothing is revealed besides the database size and the actual discovered FDs. As far as we know, we are the first to formally define secure FD discovery with minimal leakage.

We present two oblivious FD protocols and prove them secure in the presence of the persistent adversary (monitoring processes on the server). The first protocol leverages Oblivious RAM (ORAM) and is suitable for dynamic databases. The second protocol relies on oblivious sorting and is more practical in static databases due to high parallelism. We also present a thorough experimental evaluation of the proposed methods.

In the wake of recent progress on quantum computing hardware, the National Institute of Standards and Technology (NIST) is standardizing cryptographic protocols that are resistant to attacks by quantum adversaries. The primary digital signature scheme that NIST has chosen is CRYSTALS-Dilithium. The hardness of this scheme is based on the hardness of three computational problems: Module Learning with Errors (MLWE), Module Short Integer Solution (MSIS), and SelfTargetMSIS. MLWE and MSIS have been well-studied and are widely believed to be secure. However, SelfTargetMSIS is novel and, though classically as hard as MSIS, its quantum hardness is unclear. In this paper, we provide the first proof of the hardness of SelfTargetMSIS via a reduction from MLWE in the Quantum Random Oracle Model (QROM). Our proof uses recently developed techniques in quantum reprogramming and rewinding. A central part of our approach is a proof that a certain hash function, derived from the MSIS problem, is collapsing. From this approach, we deduce a new security proof for Dilithium under appropriate parameter settings. Compared to the only other rigorous security proof for a variant of Dilithium, Dilithium-QROM, our proof has the advantage of being applicable under the condition q = 1 mod 2n, where q denotes the modulus and n the dimension of the underlying algebraic ring. This condition is part of the original Dilithium proposal and is crucial for the efficient implementation of the scheme. We provide new secure parameter sets for Dilithium under the condition q = 1 mod 2n, finding that our public key sizes and signature sizes are about 2.5 to 2.8 times larger than those of Dilithium-QROM for the same security levels

A monotone policy batch $\mathsf{NP}$ language $\mathcal{L}_{\mathcal{R}, P}$ is parameterized by a monotone policy $P \colon \{0,1\}^k \to \{0,1\}$ and an $\mathsf{NP}$ relation $\mathcal{R}$. A statement $(x_1, \ldots, x_k)$ is a YES instance if there exists $w_1, \ldots, w_k$ where $P(\mathcal{R}(x_1, w_1), \ldots, \mathcal{R}(x_k, w_k)) = 1$. For example, we might say that an instance $(x_1, \ldots, x_k)$ is a YES instance if a majority of the statements are true. A monotone policy batch argument (BARG) for $\mathsf{NP}$ allows a prover to prove that $(x_1, \ldots, x_k) \in \mathcal{L}_{\mathcal{R}, P}$ with a proof of size $\mathsf{poly}(\lambda, |\mathcal{R}|, \log k)$, where $\lambda$ is the security parameter, $|\mathcal{R}|$ is the size of the Boolean circuit that computes $\mathcal{R}$, and $k$ is the number of instances. Recently, Brakerski, Brodsky, Kalai, Lombardi, and Paneth (CRYPTO 2023) gave the first monotone policy BARG for $\mathsf{NP}$ from the learning with errors (LWE) assumption.

In this work, we describe a generic approach for constructing monotone policy BARGs from any BARG for $\mathsf{NP}$ together with an additively homomorphic encryption scheme. This yields the first constructions of monotone policy BARGs from the $k$-Lin assumption in prime-order pairing groups as well as the (subexponential) DDH assumption in pairing-free groups. Central to our construction is a notion of a zero-fixing hash function, which is a relaxed version of a predicate-extractable hash function from the work of Brakerski et al. Our relaxation enables a direct realization of zero-fixing hash functions from standard BARGs for $\mathsf{NP}$ and additively homomorphic encryption, whereas the previous notion relied on leveled homomorphic encryption, and by extension, the LWE assumption.

We investigate proof systems where security holds against rational parties instead of malicious ones. Our starting point is the notion of rational arguments}, a variant of rational proofs (Azar and Micali, STOC 2012) where security holds against rational adversaries that are also computationally bounded.

Rational arguments are an interesting primitive because they allow for sublinear verification and a more efficient protocol in general. In this paper we aim at narrowing the gap between literature on rational schemes and real world applications. Our contribution is two-fold.

We provide the first construction of rational arguments for the class of polynomial computations that is practical (i.e., it can be applied to real-world computations on reasonably common hardware) and with logarithmic communication. Techniques-wise, we obtain this result through a compiler from information-theoretic protocols and rational proofs for polynomial evaluation. The latter could be of independent interest.

As a second contribution, we propose a new notion of extractability for rational arguments. Through this notion we can obtain arguments where knowledge of a witness is incentivized (rather than incentivizing mere soundness). We show how our aforementioned compiler can also be applied to obtain efficient extractable rational arguments for $\mathsf{NP}$.

In this paper, we study the design of efficient signature and public-key encryption (PKE) schemes in the presence of both leakage and tampering attacks.

Firstly, we formalize the strong leakage and tamper-resilient (sLTR) security model for signature, which provides strong existential unforgeability, and deals with bounded leakage and restricted tampering attacks, as a counterpart to the sLTR security introduced by Sun et al. (ACNS 2019) for PKE.

Then, we present direct constructions of signature and chosen-ciphertext attack (CCA) secure PKE schemes in the sLTR model, based on the matrix decisional Diffie-Hellman (MDDH) assumptions (which covers the standard symmetric external DH (SXDH) and k-Linear assumptions) over asymmetric pairing groups. Our schemes avoid the use of heavy building blocks such as the true-simulation extractable non-interactive zero-knowledge proofs (tSE-NIZK) proposed by Dodis et al. (ASIACRYPT 2010), which are usually needed in constructing schemes with leakage and tamper-resilience. Especially, our SXDH-based signature and PKE schemes are more efficient than the existing schemes in the leakage and tamper-resilient setting: our signature scheme has only 4 group elements in the signature, which is about 5×~8× shorter, and our PKE scheme has only 6 group elements in the ciphertext, which is about 1.3×~3.3× shorter.

Finally, we note that our signature scheme is the {\it first} one achieving strong existential unforgeability in the leakage and tamper-resilient setting, where strong existential unforgeability has important applications in building more complex primitives such as signcryption and authenticated key exchange.

The Lightning Network (LN) is a second layer solution built on top of Bitcoin, aimed to solve Bitcoin's long transaction waiting times and high transaction fees. Empirical and theoretical studies show that the LN is tending towards the hub and spoke network topology. In this topology most of the nodes, the spokes, open a single channel to one of the few well-connected nodes, the hubs. This topology is known to be prone to failures, attacks, and privacy issues. In this work we introduce the Maypoles protocol in which most nodes open two channels instead of one. We show that this protocol benefits the network significantly by enhancing its stability, privacy, and resilience to attacks. We also examine the economic incentives of nodes to take part in Maypoles.

We find an efficient method to solve the semidirect discrete logarithm problem (SDLP) over finite nonabelian groups of order $p^3$ and exponent $p^2$ for certain exponentially large parameters. This implies an attack on SPDH-Sign, a signature scheme based on the SDLP, for such parameters. We also take a step toward proving the quantum polynomial time equivalence of SDLP and SCDH.

We survey various mathematical tools used in software works multiplying polynomials in $\mathbb{Z}_q [x] / ⟨x^n −αx−β⟩$. In particular, we survey implementation works targeting polynomial multiplications in lattice-based cryptosystems Dilithium, Kyber, NTRU, NTRU Prime, and Saber with instruction set architectures/extensions Armv7-M, Armv7E-M, Armv8-A, and AVX2.

There are three emphases in this paper: (i) modular arithmetic, (ii) homomorphisms, and (iii) vectorization. For modular arithmetic, we survey Montgomery, Barrett, and Plantard multiplications. For homomorphisms, we survey (a) various homomorphisms such as Cooley–Tukey FFT, Bruun’s FFT, Rader’s FFT, Karatsuba, and Toom– Cook; (b) various algebraic techniques for adjoining nice properties to the coefficient rings, including injections, Schönhage’s FFT, Nussbaumer’s FFT, and localization; and (c) various algebraic techniques related to the polynomial moduli, including twisting, composed multiplication, evaluation at ∞, Good–Thomas FFT, truncation, incomplete transformation, and Toeplitz matrix-vector product. For vectorization, we survey the relations between homomorphisms and the support of vector arithmetic. We then go through several case studies: We compare the implementations of modular multiplications used in Dilithium and Kyber, explain how the matrix-to-vector structure was exploited in Saber, and review the design choices of transformations for NTRU and NTRU Prime with vectorization. Finally, we outline several interesting implementation projects.

The Fiat-Shamir transform is a classical technique for turning any zero-knowledge $\Sigma$-protocol into a signature scheme.

In essence, the idea underlying this transform is that deriving the challenge from the digest of the commitment suppresses simulatability and hence provides non-interactive proofs of interaction.

It follows from that observation that if one wishes to preserve deniability the challenge size (per round) must be kept low. For instance in the original Fiat-Shamir protocol the authors recommend 18 bits but suggest that the challenge size can be made larger to reduce communication overhead, e.g. the value of 20 is proposed in \cite{micali}.

We show that even with relatively small challenge sizes \textsl{practical} deniability can be destroyed by having the verifier artificially impose upon himself the use of slowed-down hash function or by resorting to a trusted agency proposing an on-line deniability enforcement service against the provers community's will.

This paper presents 'KEM Sphinx', an enhanced version of the Sphinx packet format, designed to improve performance through modifications that increase packet header size. Unlike its predecessor, KEM Sphinx addresses performance limitations inherent in the original design, offering a solution that doubles processing speed. Our analysis extends to the adaptation of KEM Sphinx in a post-quantum cryptographic context, showing a transition with minimal performance degradation. The study concludes that the trade-off between increased size and improved speed and security is justifiable, especially in scenarios demanding higher performance. These findings suggest KEM Sphinx as a promising direction for efficient, secure communication protocols in an increasingly post-quantum cryptographic landscape.

Applying the pothole method on the factors of numbers of the form $2^n-1$, we prove that if $2^n-1$ has carries of degree at most $$\kappa(2^n-1)=\frac{1}{2(1+c)}\lfloor \frac{\log n}{\log 2}\rfloor-1$$ for $c>0$ fixed, then the inequality $$\iota(2^n-1)\leq n-1+(1+\frac{1}{1+c})\lfloor\frac{\log n}{\log 2}\rfloor$$ holds for all $n\in \mathbb{N}$ with $n\geq 4$, where $\iota(\cdot)$ denotes the length of the shortest addition chain producing $\cdot$. In general, we show that all numbers of the form $2^n-1$ with carries of degree $$\kappa(2^n-1):=(\frac{1}{1+f(n)})\lfloor \frac{\log n}{\log 2}\rfloor-1$$ with $f(n)=o(\log n)$ and $f(n)\longrightarrow \infty$ as $n\longrightarrow \infty$ for $n\geq 4$ then the inequality $$\iota(2^n-1)\leq n-1+(1+\frac{2}{1+f(n)})\lfloor\frac{\log n}{\log 2}\rfloor$$ holds.

Since 2015, there has been a significant decrease in the asymptotic complexity of computing discrete logarithms in finite fields. As a result, the key sizes of many mainstream pairing-friendly curves have to be updated to maintain the desired security level. In PKC'20, Guillevic conducted a comprehensive assessment of the security of a series of pairing-friendly curves with embedding degrees ranging from $9$ to $17$. In this paper, we focus on pairing-friendly curves with embedding degrees of 10 and 14. First, we extend the optimized formula of the optimal pairing on BW13-310, a 128-bit secure curve with a prime $p$ in 310 bits and embedding degree $13$, to our target curves. This generalization allows us to compute the optimal pairing in approximately $\log r/2\varphi(k)$ Miller iterations, where $r$ and $k$ are the order of pairing groups and the embedding degree respectively. Second, we develop optimized algorithms for cofactor multiplication for $\mathbb{G}_1$ and $\mathbb{G}_2$, as well as subgroup membership testing for $\mathbb{G}_2$ on these curves. Based on these theoretical results a new 128-bit secure curve emerges: BW14-351. Finally, we provide detailed performance comparisons between BW14-351 and other popular curves on a 64-bit platform in terms of pairing computation, hashing to $\mathbb{G}_1$ and $\mathbb{G}_2$, group exponentiations and subgroup membership testings. Our results demonstrate that BW14-351 is a strong candidate for building pairing-based cryptographic protocols.

In this paper, we show a new set of cryptographic primitives that generically leads to chosen ciphertext secure (CCA secure) public-key encryption (PKE). Specifically, we show how a (non-interactive, publicly verifiable) batch argument (BARG) for NP can be combined with a chosen plaintext secure PKE scheme to achieve a CCA secure one. The requirement of the succinctness of the proof size of a BARG in our result is rather mild: The proof size is $O(k^{\epsilon})$ for some non-negative constant $\epsilon < 1$ when the correctness of $k$ statements is simultaneously proved.

In this paper we propose a new hash-and-sign digital signature scheme whose security against existential forgery under adaptive chosen message attack is based on the hardness of full-distance syndrome decoding. We propose parameter sets for three security levels (128-bits, 192-bits, and 256-bits) based on concrete estimations for hardness of the syndrome decoding problem and estimate the corresponding sizes of the keys and the signature for each level. The scheme has large public and private keys but very small signatures.

We optimize the number-theoretic transforms (NTTs) in Dilithium — a digital signature scheme recently standardized by the National Institute of Standards and Technology (NIST) — on Cortex-M3 and 8-bit AVR. The core novelty is the exploration of micro-architectural insights for modular multiplications. Recent work [Becker, Hwang, Kannwischer, Yang and Yang, Volume 2022 (1), Transactions on Cryptographic Hardware and Embedded Systems, 2022] found a correspondence between Montgomery and Barrett multiplications by relating modular reductions to integer approximations and demonstrated that Barrett multiplication is more favorable than Montgomery multiplication by absorbing the subtraction to the low multiplication. We first point out the benefit of Barrett multiplication when long and high multiplication instructions are unavailable, unusable, or slow. We then generalize the notion of integer approximations and improve the emulation of high multiplications used in Barrett multiplication.

Compared to the state-of-the-art assembly-optimized implementations on Cortex-M3, our constant-time NTT/iNTT are 1.38−1.51 times faster and our variable-time NTT/iNTT are 1.10−1.21 times faster. On our 8-bit AVR, we outperform Montgomery-based C implementations of NTT/iNTT by 6.37−7.27 times by simply switching to the proposed Barrett-based implementation. We additionally implement Barrett-based NTT/iNTT in assembly and obtain 14.10− 14.42 times faster code.

For the overall scheme, we provide speed-optimized implementations for Dilithium parameter sets dilithium2 and dilithium3 on Cortex-M3, and stack-optimized implementations for all parameter sets on Cortex-M3 and 8-bit AVR. We briefly compare the performance of speed-optimized dilithium3. Compared to the state-of-the-art assembly implementation on Cortex-M3, our assembly implementation reduces the key generation, signature generation, and signature verification cycles by 2.30%, 23.29%, and 0.69%. In the 8-bit AVR environment, our Barrett-based C implementation reduces the key generation, signature generation, and signature verification cycles by 45.09%, 56.80%, and 50.40%, respectively, and our assembly-optimized implementation reduces the cycles of each operation by 48.85%, 61.70%, and 55.08%, respectively.