International Association
for Cryptologic Research

We present a general framework for polynomial-time lattice Gaussian sampling. It revolves around a systematic study of the discrete Gaussian measure and its samplers under extensions of lattices; we first show that given lattices $\Lambda'\subset \Lambda$ we can sample efficiently in $\Lambda$ if we know how to do so in $\Lambda'$ and the quotient $\Lambda/\Lambda'$, \emph{regardless} of the primitivity of $\Lambda'$. As a direct application, we tackle the problem of domain extension and restriction for sampling and propose a sampler tailored for lattice \emph{filtrations}, which can be seen as a broad generalization of the celebrated Klein's sampler. Then, we demonstrate how to sample using a change of bases, or even switching the ambient space, even when the target lattice is not represented as full-rank in the ambient space. We show how to correct the induced distortion with the ``convolution-like'' technique of Peikert (Crypto 2010) (which we encompass as a byproduct). Since our framework aims at modularity and leverage the combinations of smaller samplers to build new ones, we also propose ad-hoc samplers for the so-called \emph{root lattices} $\mathsf{A}_n, \mathsf{D}_n, \mathsf{E}_n$ as base cases, extending the state-of-the-art for root lattice sampling, which was limited to $\mathbb{Z}^n$. We also show how our framework blends with the so-called $k$ing construction and provides a sampler for the remarkable Leech and Barnes-Wall lattices.

As a by-product, we obtain novel, quasi-linear samplers for prime and smooth conductor (as $2^\ell 3^k$) cyclotomic rings, achieving essentially optimal Gaussian width. In a practice-oriented application, we showcase the impact of our work on hash-and-sign signatures over \textsc{ntru} lattices. In the best case, we can gain around 200 bytes (which corresponds to an improvement greater than 20\%) on the signature size. We also improve the new gadget-based constructions (Yu, Jia, Wang, Crypto 2023) and gain up to 110 bytes for the resulting signatures.

Lastly, we sprinkle our exposition with several new estimates for the smoothing parameter of lattices, stemming from our algorithmic constructions and by novel methods based on series reversion.

QCB is a proposal for a post-quantum secure, rate-one authenticated encryption with associated data scheme (AEAD) based on classical OCB3 and \(\Theta\)CB, which are vulnerable against a quantum adversary in the Q2 setting. The authors of QCB prove integrity under plus-one unforgeability, whereas the proof of the stronger definition of blind unforgeability has been left as an open problem. After a short overview of QCB and the current state of security definitions for authentication, this work proves blind unforgeability of QCB. Finally, the strategy of using tweakable block ciphers in authenticated encryption is generalised to a generic blindly unforgeable AEAD model.

$\Sigma$-protocols are a widely utilized, relatively simple and well understood type of zero-knowledge proofs. However, the well known Schnorr $\Sigma$-protocol for proving knowledge of discrete logarithm in a cyclic group of known prime order, and similar protocols working over this type of groups, are hard to generalize to dealing with other groups. In particular with hidden order groups, due to the inability of the knowledge extractor to invert elements modulo the order.

In this paper, we introduce a universal construction of $\Sigma$-protocols designed to prove knowledge of preimages of group homomorphisms for any abelian finite group. In order to do this, we first establish a general construction of a $\Sigma$-protocol for $\mathfrak{R}$-module homomorphism given only a linear secret sharing scheme over the ring $\mathfrak{R}$, where zero knowledge and special soundness can be related to the privacy and reconstruction properties of the secret sharing scheme. Then, we introduce a new construction of 2-out-of-$n$ packed black-box secret sharing scheme capable of sharing $k$ elements of an arbitrary (abelian, finite) group where each share consists of $k+\log n-3$ group elements. From these two elements we obtain a generic ``batch'' $\Sigma$-protocol for proving knowledge of $k$ preimages of elements via the same group homomorphism, which communicates $k+\lambda-3$ elements of the group to achieve $2^{-\lambda}$ knowledge error.

For the case of class groups, we show that our $\Sigma$-protocol improves in several aspects on existing proofs for knowledge of discrete logarithm and other related statements that have been used in a number of works.

Finally, we extend our constructions from group homomorphisms to the case of ZK-ready functions, introduced by Cramer and Damg\aa rd in Crypto 09, which in particular include the case of proofs of knowledge of plaintext (and randomness) for some linearly homomorphic encryption schemes such as Joye-Libert encryption. However, in the case of Joye-Libert, we show an even better alternative, using Shamir secret sharing over Galois rings, which achieves $2^{-k}$ knowledge soundness by communicating $k$ ciphertexts to prove $k$ statements.

Publicly Verifiable Secret Sharing (PVSS) allows a dealer to publish encrypted shares of a secret so that parties holding the corresponding decryption keys may later reconstruct it. Both dealing and reconstruction are non-interactive and any verifier can check their validity. PVSS finds applications in randomness beacons, distributed key generation (DKG) and in YOSO MPC (Gentry et al. CRYPTO'21), when endowed with suitable publicly verifiable re-sharing as in YOLO YOSO (Cascudo et al. ASIACRYPT'22).

We introduce a PVSS scheme over class groups that achieves similar efficiency to state-of-the art schemes that only allow for reconstructing a function of the secret, while our scheme allows the reconstruction of the original secret. Our construction generalizes the DDH-based scheme of YOLO YOSO to operate over class groups, which poses technical challenges in adapting the necessary NIZKs in face of the unknown group order and the fact that efficient NIZKs of knowledge are not as simple to construct in this setting.

Building on our PVSS scheme's ability to recover the original secret, we propose two DKG protocols for discrete logarithm key pairs: a biasable 1-round protocol, which improves on the concrete communication/computational complexities of previous works; and a 2-round unbiasable protocol, which improves on the round complexity of previous works. We also add publicly verifiable resharing towards anonymous committees to our PVSS, so that it can be used to efficiently transfer state among committees in the YOSO setting. Together with a recent construction of MPC in the YOSO model based on class groups (Braun et al. CRYPTO'23), this results in the most efficient full realization (i.e without assuming receiver anonymous channels) of YOSO MPC based on the CDN framework with transparent setup.

The security of multivariate polynomial cryptography depends on the computational complexity of solving a multivariate quadratic polynomial system (MQ problem). One of the fastest algorithms for solving the MQ problem is F4, which computes a Groebner basis but requires numerous calculations of zero reduction that do not affect the output.The Hilbert-driven algorithm evaluates the number of generators in the Groebner basis of degree $d$ using Hilbert series, then it reduces the number of zero reduction computations. In this paper, we propose a high-speed algorithm designed for randomly generated semi-regular MQ problems. Although the Hilbert-driven algorithm is limited to computing homogeneous ideals, we demonstrate its applicability to semi-regular non-homogeneous ideals in this work. Furthermore, when using the Hilbert-driven algorithm to solve non-homogeneous MQ problems with F4, we demonstrate the efficient achievement of reducing zero reduction for F4. We implemented the proposed algorithm in C++ and report successful decryption of a new record $m=21$ Type VI equations. This was achieved using an AMD EPYC 7742 processor and 2TB RAM, and the decryption process was completed within approximately 9 h.

Homomorphic Encryption (HE) is one of the mainstream cryptographic tools used to enable secure outsourced computation. A typical task is secure matrix computation. Popular HE schemes are all based on the problem of Ring Learning with Errors (RLWE), where the messages are encrypted in a ring. In general, the ring dimension should be large to ensure security, which is often larger than the matrix size. Hence, exploiting the ring structure to make fast homomorphic matrix computation has been an important topic in HE. In this paper, we present a new framework for encoding a matrix and performing multiplication on encrypted matrices. The new framework requires fewer basic homomorphic operations for matrix multiplication. Suppose that the ring dimension is $n$ and the matrix size is $d\times d$ with $d= n^{\rho}$. (1) In the compact case where $\rho \leq \frac{1}{3}$, the multiplication of two encrypted matrices requires $\tilde{O}(1)$ basic homomorphic operations, which include plaintext-ciphertext multiplications, ciphertext-ciphertext multiplications, and homomorphic Galois automorphisms. (2) In the large sized case where $\rho> \frac{1}{3}$, our new method requires $O\big(d^{(1 - \frac{1}{3\rho})\cdot \log_2 7 }\big)$ basic homomorphic operations, which is better than all existing methods. In addition, the new framework reduces the communication cost, since it requires fewer key-switching keys. The number of key-switching keys is reduced from $O(d)$ to $O(\log d)$.

When Satoshi Nakamoto introduced Bitcoin, a central tenet was that the blockchain functions as a timestamping server. In the Ethereum era, smart contracts widely assume on-chain timestamps are mostly accurate. In this paper, we prove this is indeed the case, namely that recorded timestamps do not wildly deviate from real-world time, a property we call timeliness. Assuming a global clock, we prove that all popular mechanisms for constructing blockchains (proof-of-work, longest chain proof-of-stake, and quorum-based proof-of-stake) are timely under honest majority, but a synchronous network is a necessary condition. Next we show that all timely blockchains can be suitably modified, in a black-box fashion, such that all honest parties output exactly the same ledgers at the same round, achieving a property we call supersafety, which may be of independent interest. Conversely, we also show that supersafety implies (perfect) timeliness, completing the circle.

Over the last decades, fault injection attacks have been demonstrated to be an effective method for breaking the security of electronic devices. Some types of fault injection attacks, like clock and voltage glitching, require very few resources by the attacker and are practical and simple to execute. A cost-effective countermeasure against these attacks is the use of a detector circuit which detects timing violations - the underlying effect that glitch attacks rely on. In this paper, we take a closer look at three examples of such detectors that have been presented in the literature. We demonstrate four high-speed clock glitching attacks, which successfully inject faults in systems, where detectors have been implemented to protect. The attacks remain unnoticed by the glitch detectors. We verify our attacks with practical experiments on an FPGA.

Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Applications of PCD have sparked keen interest within the applied community and industry.

Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. Unfortunately, these constructions do not come with security analyses that yield useful concrete security bounds, leaving practitioners in the dark about how to securely instantiate PCD constructions.

In this work we study the concrete security of recursive composition, with the goal of enabling practitioners to set efficient parameters for certain PCD constructions of practical interest. Our main result is that PCD obtained from SNARKs with \emph{straightline knowledge soundness} has essentially the same security as the underlying SNARK. In this setting, recursive composition incurs no security loss.

We describe how straightline knowledge soundness is achieved by SNARKs in several oracle models, including SNARKs that are deployed in practice. Crucially, SNARKs in these settings can be \emph{relativized}, allowing us to construct PCD without instantiating the SNARK's oracle explicitly. This results in a highly efficient security analysis of PCD that makes black-box use of the SNARK's oracle.

As a notable application, our work offers an idealized model that provides useful, albeit heuristic, guidance for setting the security parameters of \emph{recursive STARKs} currently used in blockchain systems.

In 2019, Wan, Liao, Yan and Tsai proposed an article ``Discrete Sliding Mode Control for Chaos Synchronization and Its Application to an Improved ElGamal Cryptosystem''. However, Wan et al. just renamed the variable names without modified the core algorithm. Their paper passed review phase and then published. For this case, it is difficult to detect this situation by computer/digital forensics techniques. In this paper the authors would like to point out this dilemmas.

Domain Generation Algorithms (DGAs) are used by malware to generate pseudorandom domain names to establish communication between infected bots and Command and Control servers. While DGAs can be detected by machine learning (ML) models with great accuracy, offering DGA detection as a service raises privacy concerns when requiring network administrators to disclose their DNS traffic to the service provider. We propose the first end-to-end framework for privacy-preserving classification as a service of domain names into DGA (malicious) or non-DGA (benign) domains. We achieve this through a combination of two privacy-enhancing technologies (PETs), namely secure multi-party computation (MPC) and differential privacy (DP). Through MPC, our framework enables an enterprise network administrator to outsource the problem of classifying a DNS domain as DGA or non-DGA to an external organization without revealing any information about the domain name. Moreover, the service provider's ML model used for DGA detection is never revealed to the network administrator. Furthermore, by using DP, we also ensure that the classification result cannot be used to learn information about individual entries of the training data. Finally, we leverage the benefits of quantization of deep learning models in the context of MPC to achieve efficient, secure DGA detection. We demonstrate that we achieve a significant speed-up resulting in a 15% reduction in detection runtime without reducing accuracy.

In the ever-evolving landscape of Information Technologies, private decentralized computing on an honest yet curious server has emerged as a prominent paradigm. While numerous schemes exist to safeguard data during computation, the focus has primarily been on protecting the confidentiality of the data itself, often overlooking the potential information leakage arising from the function evaluated by the server. Recognizing this gap, this article aims to address the issue by presenting and implementing an innovative solution for ensuring the privacy of both the data and the program. We introduce a novel approach that combines the power of Fully Homomorphic Encryption with the concept of the Turing Machine model, resulting in the first fully secure practical, non-interactive oblivious Turing Machine. Our Oblivious Turing Machine construction is based on only three hypothesis, the hardness of the Ring Learning With Error problem, the ability to homomorphically evaluate non-linear functions and the capacity to blindly rotate elements of a data structure. Only based on those three assumptions, we propose an implementation of an Oblivious Turing Machine relying on the TFHE cryptosystem and present some implementation results.

Fully homomorphic encryption is a promising solution for privacy-preserving computation. For BFV, BGV, and CKKS, three state-of-the-art fully homomorphic encryption schemes, the so-called key switching is one of the primary bottlenecks when evaluating homomorphic circuits. While a large body of work explores optimal selection for scheme parameters such as the polynomial degree or the ciphertext modulus, the realm of key switching parameters is relatively unexplored.

This work closes this gap, formally exploring the parameter space for BGV-like key switching. We introduce a new asymptotic bound for key switching complexity, thereby providing a new perspective on this crucial operation. We also explore the parameter space for the recently proposed double-decomposition technique by Kim et al. [24], which outperforms current state-of-the-art only in very specific circumstances. Furthermore, we revisit an idea by Gentry, Halevi, and Smart [19] switching primes in and out of the ciphertext and find novel opportunities for constant folding, speeding up key switching by up to 50% and up to 11.6%, respectively.

Symmetric Private Information Retrieval (SPIR) is a protocol that protects privacy during data transmission. However, the existing SPIR focuses only on the privacy of the data to be requested on the server, without considering practical factors such as the payload that may be present during data transmission. This could seriously prevent SPIR from being applied to many complex data scenarios and hinder its further expansion. To solve such problems, we propose a primitive (PSKPIR) for symmetric private keyword information retrieval based on private set intersection (PSI) that supports payload transmission and batch keyword search. Specifically, we combine probe-and-XOR of strings (PaXoS) and Oblivious Programmable PRF (OPPRF) to construct PSI with payload (PSI-Payload) not only satisfies client privacy and server privacy, but also facilitates efficient payload transmission. The client can efficiently generate symmetric keys locally using keywords in the intersection, and receive payloads with matching labels in batches. In addition, we provide security definitions for PSKPIR and use the framework of universal composability (UC) to prove security. Finally, we implement PSKPIR with sublinear communication costs in both LAN and WAN settings. Experimental results show that our payload transfer speed is 10× faster than previous work on sufficiently large data sets.

Event date: 12 June to 14 June 2024
Submission deadline: 19 January 2024
Notification: 15 March 2024

Event date: 24 March 2024

Event date: 17 January to 19 January 2024

Event date: 18 August to 22 August 2024

Event date: 5 March to 8 March 2024
Submission deadline: 11 November 2023
Notification: 10 December 2023

Two assistant professor (maître de conférences) positions in computer science will open at University of Lorraine in Spring 2024, with the common topic of security and safety. Hired persons will conduct their research on these topics within one of the teams of the Loria research lab [1] (Nancy). Teaching will take place at Mines Nancy for one of the two positions, and Polytech Nancy for the other one. At Mines Nancy, the hired person may choose to teach entirely in English.

All relevant detailed information about these positions will be posted online in due time.

Potential applicants are encouraged to reach out well in advance.

IMPORTANT (in particular for foreign applicants) Applicants must enter the "qualification" process [2] before Nov. 10, 4pm, in order to apply. The application deadline is in March 2024.

Newly hired assistant professors typically have a reduced teaching load for at least the first year.

Links:

• [1] https://www.loria.fr/
• [2] https://www.galaxie.enseignementsup-recherche.gouv.fr/ensup/cand_qualification_droit_commun.htm

Closing date for applications:

Contact: Emmanuel.Thome@loria.fr