International Association
for Cryptologic Research

The first contribution of this work is a generalisation of Stern's information set decoding (ISD) algorithm. Stern's algorithm, a variant of Stern's algorithm due to Dumer, as well as a recent generalisation of Stern's algorithm due to Bernstein and Chou are obtained as special cases of our generalisation. Our second contribution is to introduce the notion of a set of effective time/memory trade-off (TMTO) points for any ISD algorithm for given ranges of values of parameters of the algorithm. Such a set succinctly and uniquely captures the entire landscape of TMTO points with only a minor loss in precision. We further describe a method to compute a set of effective TMTO points. As an application, we compute sets of effective TMTO points for the five variants of the Classic McEliece cryptosystem corresponding to the new algorithm as well as for Stern's, Dumer's and Bernstein and Chou's algorithms. The results show that while Dumer's and Bernstein and Chou's algorithms do not provide any interesting TMTO points beyond what is achieved by Stern's algorithm, the new generalisation that we propose provide about twice the number of effective TMTO points that is obtained from Stern's algorithm. Consequences of the obtained TMTO points to the classification of the variants of Classic McEliece in appropriate NIST categories are discussed.

The Department of Computer Science in the College of Liberal Arts and Sciences at Iowa State University of Science and Technology in Ames, Iowa, seeks outstanding applicants for a tenure-track faculty position at the rank of Assistant Professor. We are looking for candidates in all areas of Computer Science who expand our current research strengths, in particular, but not limited to, cybersecurity, classical and post-quantum cryptography. The successful candidate will be expected to develop and sustain a strong Computer Science research program; develop collaborative and interdisciplinary research; publish in top venues; provide outstanding graduate student supervision; teach undergraduate and graduate Computer Science courses; and enhance ISU through professional and institutional service. We are interested in exceptional candidates who can expand our research profile in new areas. We are dedicated to work-life balance through an array of flexible policies. We are responsive to the needs of dual-career couples. Required Minimum Qualifications: Ph.D. or equivalent degree by start date in computer science or a closely related field. Evidence of a strong publication record in top-tier conferences or journals. Preferred Qualifications: Scholarship that complements and expands the Computer Science department current research strengths, in particular, but not limited to, cybersecurity, classical and post-quantum cryptography. Application Instructions: To apply for this position, please complete the Employment Application. Please be prepared to enter or attach the following documents (as individual PDF files): Resume/Curriculum Vitae Letter of Application/Cover Letter Contact Information for Three Professional References Statement of Research Interests and Statement of Teaching Interests or Philosophy (one document) To apply: All candidates in Cybersecurity, Classical, and Post-quantum Cryptography should apply to this position: https://isu.wd1.myworkdayjobs.com/IowaStateJobs/job/Ames-IA/Assistant-Professor-of-Computer-Science_R11855. This position has a start date of August 16, 2024.

Closing date for applications:

Contact: Dr. Gianfranco Ciardo

More information: https://www.cs.iastate.edu/open-positions

Artificial intelligence (AI) is a modern technology that allows plenty of advantages in daily life, such as predicting weather, finding directions, classifying images and videos, even automatically generating code, text, and videos. Other essential technologies such as blockchain and cybersecurity also benefit from AI. As a core component used in blockchain and cybersecurity, cryptography can benefit from AI in order to enhance the confidentiality and integrity of cyberspace. In this paper, we review the algorithms underlying four prominent cryptographic cryptosystems, namely the Advanced Encryption Standard, the Rivest--Shamir--Adleman, Learning With Errors, and the Ascon family of cryptographic algorithms for authenticated encryption. Where possible, we pinpoint areas where AI can be used to help improve their security.

Succinctness and zero-knowledge are two fundamental properties in the study of cryptographic proof systems. Several recent works have formalized the connections between these two notions by showing how to realize non-interactive zero-knowledge (NIZK) arguments from succinct non-interactive arguments. Specifically, Champion and Wu (CRYPTO 2023) as well as Bitansky, Kamath, Paneth, Rothblum, and Vasudevan (ePrint 2023) recently showed how to construct a NIZK argument for NP from a (somewhere-sound) non-interactive batch argument (BARG) and a dual-mode commitment scheme (and in the case of the Champion-Wu construction, a local pseudorandom generator). The main open question is whether a BARG suffices for a NIZK (just assuming one-way functions).

In this work, we first show that an adaptively-sound BARG for NP together with an one-way function imply a computational NIZK argument for NP. We then show that the weaker notion of somewhere soundness achieved by existing BARGs from standard algebraic assumptions are also adaptively sound if we assume sub-exponential security. This transformation may also be of independent interest. Taken together, we obtain a NIZK argument for NP from one-way functions and a sub-exponentially-secure somewhere-sound BARG for NP.

If we instead assume plain public-key encryption, we show that a standard polynomially-secure somewhere-sound batch argument for NP suffices for the same implication. As a corollary, this means a somewhere-sound BARG can be used to generically upgrade any semantically-secure public-key encryption scheme into one secure against chosen-ciphertext attacks. More broadly, our results demonstrate that constructing non-interactive batch arguments for NP is essentially no easier than constructing NIZK arguments for NP.

We study digital signatures with revocation capabilities and show two results. First, we define and construct digital signatures with revocable signing keys from the LWE assumption. In this primitive, the signing key is a quantum state which enables a user to sign many messages and yet, the quantum key is also revocable, i.e., it can be collapsed into a classical certificate which can later be verified. Once the key is successfully revoked, we require that the initial recipient of the key loses the ability to sign. We construct digital signatures with revocable signing keys from a newly introduced primitive which we call two-tier one-shot signatures, which may be of independent interest. This is a variant of one-shot signatures, where the verification of a signature for the message ``0'' is done publicly, whereas the verification for the message ``1'' is done in private. We give a construction of two-tier one-shot signatures from the LWE assumption. As a complementary result, we also construct digital signatures with quantum revocation from group actions, where the quantum signing key is simply ``returned'' and then verified as part of revocation.

Second, we define and construct digital signatures with revocable signatures from OWFs. In this primitive, the signer can produce quantum signatures which can later be revoked. Here, the security property requires that, once revocation is successful, the initial recipient of the signature loses the ability to find accepting inputs to the signature verification algorithm. We construct this primitive using a newly introduced two-tier variant of tokenized signatures. For the construction, we show a new lemma which we call the adaptive hardcore bit property for OWFs, which may enable further applications.

This paper introduces LERNA, a new framework for single-server secure aggregation. Our protocols are tailored to the setting where multiple consecutive aggregation phases are performed with the same set of clients, a fraction of which can drop out in some of the phases. We rely on an initial secret sharing setup among the clients which is generated once-and-for-all, and reused in all following aggregation phases. Compared to prior works [Bonawitz et al. CCS’17, Bell et al. CCS’20], the reusable setup eliminates one round of communication between the server and clients per aggregation—i.e., we need two rounds for semi-honest security (instead of three), and three rounds (instead of four) in the malicious model. Our approach also significantly reduces the server’s computational costs by only requiring the reconstruction of a single secret-shared value (per aggregation). Prior work required reconstructing a secret-shared value for each client involved in the computation.

We provide instantiations of LERNA based on both the Decisional Composite Residuosity (DCR) and (Ring) Learning with Rounding ((R)LWR) assumptions respectively and evaluate a version based on the latter assumption. In addition to savings in round-complexity (which result in reduced latency), our experiments show that the server computational costs are reduced by two orders of magnitude in comparison to the state-of-the-art. In settings with a large number of clients, we also reduce the computational costs up to twenty-fold for most clients, while a small set of “heavy clients” is subject to a workload that is still smaller than that of prior work.

The splitting field $F$ of the polynomial $Y^n-2$ is an extension over $\mathbb{Q}$ generated by $\zeta_n=\exp(2 \pi \sqrt{-1} /n)$ and $\sqrt[n]{2}$. When $n$ ($\geq 8$) is a power-of-two integer, the degree of $F$ over $\mathbb{Q}$ is $n^2/4$. In this paper, we lay the foundation for applying the Order-LWE in $\mathcal{R}=\mathbb{Z}[\zeta_n, \sqrt[n]{2}]$ to cryptographic uses. More specifically, We will compute the Galois group $\text{Gal}\left(F/\mathbb{Q} \right)$ and the canonical embedding of $F$ into $\mathbb{C}^{n^2/4}$. Then we study the trace pairings of the integral basis $\zeta_n^{k_0} \sqrt[n]{2}^{k_1}$ and obtain its dual explicitly, which will be crucial when we study the error distributions on the ideal lattices associated with $\mathcal{R}$.

Moreover, we design a Two-Variable Number Theoretic Transform (2NTT) algorithm for the quotient $\mathcal{R}_p=\mathcal{R}/p\mathcal{R}$, where $p$ is a prime number such that $Y^n \equiv 2 \bmod p$ has $n$ distinct solutions. Compared to the one-variable NTT, a crucial advantage of 2NTT is that it enjoys a quadratic saving of twiddle factors. Hence, it is very interesting to see how to leverage this quadratic saving to boost the performance of 2NTT in practical implementations.

In 1982, Yao introduced the problem of comparing two private values, thereby launching the study of protocols for secure multi-party computation (MPC). Since then, comparison protocols have undergone extensive study and found widespread applications.

We survey state-of-the-art comparison protocols for an arbitrary number of parties, decompose them into smaller primitives and analyse their communication complexity under the usual assumption that the underlying MPC protocol does preprocessing and computes linear operations without communication. We then develop two new comparison protocols and explain why they are faster than similar protocols, including those that are commonly used in practice: they reduce the number of online multiplications, without increasing preprocessing or round complexity. More concretely, online bandwidth is reduced by more than half for the standard comparison protocols whose round complexity is logarithmic in the bit-length, whereas for constant round comparison protocols the reduction is two-thirds.

Key Encapsulation Mechanisms (KEMs) are a critical building block for hybrid encryption and modern security protocols, notably in the post-quantum setting. Given the asymmetric public key of a recipient, the primitive establishes a shared secret key between sender and recipient. In recent years, a large number of abstract designs and concrete implementations of KEMs have been proposed, notably in the context of the NIST selection process for post-quantum primitives. The traditional security notion for KEMs has been the IND-CCA notion that was designed for public-key encryption (PKE). In recent work additional properties, such as robustness and anonymity, were lifted from the PKE setting to the KEMs setting.

In this work we introduce several stronger security notions for KEMs. Our new properties formalize in which sense outputs of the KEM uniquely determine, i.e., bind, other values. Our new notions are based on two orthogonal observations: First, unlike PKEs, KEMs establish a unique key, which leads to natural binding properties for the established keys. Our new binding properties can be used, e.g., to prove the absence of attacks that were not captured by prior security notions, such as re-encapsulation attacks. If we regard KEMs as one-pass key exchanges, our key-binding properties correspond to implicit key agreement properties. Second, to prove the absence of weak keys, we have to consider not only honestly generated key pairs but also adversarially-generated key pairs.

We define a hierarchy of security notions for KEMs based on our observations. We position properties from the literature within our hierarchy, provide separating examples, and give examples of real world KEMs in the context of our hierarchy.

In recent years, actively secure SPDZ-like protocols for dishonest majority, like SPD$\mathbb Z_{2^k}$, Overdrive2k, and MHz2k, over base rings $\mathbb Z_{2^k}$ have become more and more efficient. In this paper, we present a new actively secure MPC protocol Multipars that outperforms these state-of-the-art protocols over $\mathbb Z_{2^k}$ by more than a factor of 2 in the two-party setup in terms of communication. Multipars is the first actively secure N-party protocol over $\mathbb Z_{2^k}$ that is based on linear homomorphic encryption (LHE) in the offline phase (instead of oblivious transfer or somewhat homomorphic encryption in previous works). The strong performance of Multipars relies on a new adaptive packing for BGV ciphertexts that allows us to reduce the parameter size of the encryption scheme and the overall communication cost. Additionally, we use modulus switching for further size reduction, a new type of enhanced CPA security over $\mathbb Z_{2^k}$, a truncation protocol for Beaver triples, and a new LHE-based offline protocol without sacrificing over $\mathbb Z_{2^k}$.

We have implemented Multipars and therewith provide the fastest preprocessing phase over $\mathbb Z_{2^k}$. Our evaluation shows that Multipars offers at least a factor of 8 lower communication costs and up to a factor of 15 faster runtime in the WAN setting compared to the currently best available actively secure MPC implementation over $\mathbb Z_{2^k}$.

We present a side-channel attack on CRYSTALS-Dilithium, a post-quantum secure digital signature scheme, with two variants of post-processing. The side-channel attack exploits information leakage in the secret key unpacking procedure of the signing algorithm to recover the coefficients of the polynomials in the secret key vectors ${\bf s}_1$ and ${\bf s}_2$ by profiled deep learning-assisted power analysis. In the first variant, one half of the coefficients of ${\bf s}_1$ and ${\bf s}_2$ is recovered by power analysis and the rest is derived by solving a system of linear equations based on ${\bf t} = {\bf A}{\bf s}_1 + {\bf s}_2$, where ${\bf A}$ and ${\bf t}$ are parts of the public key. This case assumes knowledge of the least significant bits of the vector ${\bf t}$, ${\bf t}_0$. The second variant waives this requirement. However, to succeed, it needs a larger portion of ${\bf s}_1$ to be recovered by power analysis. The remainder of ${\bf s}_1$ is obtained by lattice reduction. Once the full ${\bf s}_1$ is recovered, all the other information necessary for generating valid signatures can be trivially derived from the public key. We evaluate both variants on an ARM Cortex-M4 implementation of Dilithium-2. The profiling stage (trace capture and neural network training) takes less than 10 hours. In the attack assuming that ${\bf t}_0$ is known, the probability of successfully recovering the full vector ${\bf s}_1$ from a single trace captured from a different from profiling device is non-negligible (9%). The success rate approaches 100% if multiple traces are available for the attack. Our results demonstrate the necessity of protecting the secret key of CRYSTALS-Dilithium from single-trace attacks and call for a reassessment of the role of compression of the public key vector ${\bf t}$ in the security of CRYSTALS-Dilithium implementations.

This paper studies a multi-party private set union (mPSU), a fundamental cryptographic problem that allows multiple parties to compute the union of their respective datasets without revealing any additional information. We propose an efficient mPSU protocol which is secure in the presence of any number of colluding semi-honest participants. Our protocol avoids computationally expensive homomorphic operations or generic multi-party computation, thus providing an efficient solution for mPSU.

The crux of our protocol lies in the utilization of new cryptographic tools, namely, Membership Oblivious Transfer (mOT) and Conditional Oblivious Pseudorandom Function (cOPRF). We believe that the mOT and cOPRF may be of independent interest.

We implement our mPSU protocol and evaluate their performance. Our protocol shows an improvement of up to $55\times$ and $776.18\times$ bandwidth cost compared to the existing state-of-the-art protocols.

We study the following broad question about cryptographic primitives: is it possible to achieve security against an arbitrary $\mathsf{poly}(n)$-time adversary with $O(\log n)$-size messages? It is common knowledge that the answer is ``no'' unless information-theoretic security is possible. In this work, we revisit this question by considering the setting of cryptography with public information and computational security.

We obtain the following results, assuming variants of well-studied intractability assumptions:

1) A private simultaneous messages (PSM) protocol for every $f:[n]\times[n]\to\{0, 1\}$ requiring $(1+\epsilon)\log n$-bit messages for most functions and $(2+\epsilon)\log n$-bit messages for the remaining ones. We apply this towards non-interactive secure 3-party computation with similar message size in the preprocessing model, improving over previous 2-round protocols.

2) A secret-sharing scheme for any ``forbidden-graph'' access structure on $n$ nodes with $O(\log n)$ share size.

3) On the negative side, we show that computational threshold secret-sharing schemes with public information require share size $\Omega(\log \log n)$. For arbitrary access structures, we show that computational security does not help with 1-bit shares.

The above positive results guarantee that any adversary of size $n^{o(\log n)}$ achieves an $n^{-\Omega(1)}$ distinguishing advantage. We show how to make the advantage negligible by slightly increasing the asymptotic message size, still improving over all known constructions. The security of our constructions is based on the conjectured hardness of variants of the planted clique problem, which was extensively studied in the algorithms, statistical inference, and complexity theory communities. Our work provides the first applications of such assumptions improving the efficiency of mainstream cryptographic primitives, gives evidence for the necessity of such assumptions, and suggests new questions in this domain that may be of independent interest.

Recently, a novel secure quantum bit commitment (QBC) protocol has been proposed [29]. However, the protocol requires Alice and Bob to share Bell states in advance, making the protocol lacking in practicality. In this paper, we propose two new unconditionally secure quantum bit commitment protocols that do not require pre-shared Bell states based on entangled and non-entangled states, respectively. Their security stems from quantum mechanical properties such as quantum superposition, quantum entanglement, no-cloning theorem, and no-communication theorem. Furthermore, by combining the proposed QBC with Yao's quantum oblivious transfer (QOT) model, we can obtain an unconditionally secure QOT protocol.

A file system provides secure deletion if, after a file is deleted, an attacker with physical possession of the storage device cannot recover any data from the deleted file. Unfortunately, secure deletion is not provided by commodity file systems. Even file systems which explicitly desire to provide secure deletion are challenged by the subtleties of hardware controllers on modern storage devices; those controllers obscure the mappings between logical blocks and physical blocks, silently duplicate physical blocks, and generally make it hard for host-level software to make reliable assumptions about how file data is kept on the device. State-of-the-art frameworks for secure deletion also have no crash consistency, meaning that an ill-timed power outage or software fault will desynchonize keys and the associated encrypted file data, corrupting the file system.

In this paper, we present Holepunch, a new software-level approach for implementing secure deletion. Holepunch treats the storage device as a black box, providing secure deletion via cryptographic erasure. Holepunch uses per-file keys to transparently encrypt outgoing file writes and decrypt incoming file reads, ensuring that all physical data in the storage device is always encrypted. Holepunch uses puncturable pseudorandom functions (PPRFs) to quickly access file keys; upon the deletion of file $f$, Holepunch updates the PPRF so that, even if the PPRF is recovered, the PPRF cannot be used to generate $f$'s key. By using PPRFs instead of the key trees leveraged by prior work, Holepunch reduces both the memory pressure caused by key management and the number of disk IOs needed to access files. Holepunch stores its master key in secure TPM storage, and uses a novel journaling scheme to provide crash consistency between TPM state and on-disk state.

Modern secure messaging protocols typically aim to provide deniability. Achieving this requires that convincing cryptographic transcripts can be forged without the involvement of genuine users. In this work, we observe that parties may wish to revoke deniability and avow a conversation after it has taken place. We propose a new protocol called Not-on-the-Record-Yet (NOTRY) which enables users to prove a prior conversation transcript is genuine. As a key building block we propose avowable designated verifier proofs which may be of independent interest. Our implementation incurs roughly 8× communication and computation overhead over the standard Signal protocol during regular operation. We find it is nonetheless deployable in a realistic setting as key exchanges (the source of the overhead) still complete in just over 1ms on a modern computer. The avowal protocol induces only constant computation and communication performance for the communicating parties and scales linearly in the number of messages avowed for the verifier—in the tens of milliseconds per avowal.

Hard lattice problems are predominant in constructing post-quantum cryptosystems. However, we need to continue developing post-quantum cryptosystems based on other quantum hard problems to prevent a complete collapse of post-quantum cryptography due to a sudden breakthrough in solving hard lattice problems. Solving large multivariate quadratic systems is one such quantum hard problem.

Unbalanced Oil-Vinegar is a signature scheme based on the hardness of solving multivariate equations. In this work, we present a post-quantum digital signature algorithm VDOO (Vinegar-Diagonal-Oil-Oil) based on solving multivariate equations. We introduce a new layer called the diagonal layer over the oil-vinegar-based signature scheme Rainbow. This layer helps to improve the security of our scheme without increasing the parameters considerably. Due to this modification, the complexity of the main computational bottleneck of multivariate quadratic systems i.e. the Gaussian elimination reduces significantly. Thus making our scheme one of the fastest multivariate quadratic signature schemes. Further, we show that our carefully chosen parameters can resist all existing state-of-the-art attacks. The signature sizes of our scheme for the National Institute of Standards and Technology's security level of I, III, and V are 96, 226, and 316 bytes, respectively. This is the smallest signature size among all known post-quantum signature schemes of similar security.

Event date: 10 April to 12 April 2024
Submission deadline: 26 January 2024

Event date: 11 March to 15 March 2024

The Opportunity: The successful candidate will contribute to the formal security specification and design of cryptographic protocols in the Open Finance area. In Open Finance we envision multiple entities, each holding private data, that want to perform joint computation over this data to offer to customers the best possible financial products. The main goal of the project is to investigate what are the security requirements for Open Finance, and then provide a formal security specification (e.g., in the Universal Composable framework) of such a system. The successful candidate will then work on designing a protocol that matches this security definition, and in the final stage of the project, will implement part of the system, focusing on a specific use case. The candidate will be supported by members of the Business School to successfully complete the first phase of the project related to understanding the basic security requirements of an Open Finance system. The majority of the project will be related to the formal design of the system that will be supported by members of the School of Informatics. The project is funded by Input-Output Global. Candidates must have a Ph.D. (or nearing completion) in cryptography or related fields. Evidence of strong research experience as demonstrated through publications at top-tier conferences or high-impact journals is essential. We are looking for a highly motivated candidate with strong initiative and commitment to excellence, and an ability to conduct world-class research. For more info, we refer to the application page.

Application deadline 16/01/2024 23:59 GMT

Closing date for applications:

Contact: Michele Ciampi michele.ciampi@ed.ac.uk

More information: https://elxw.fa.em3.oraclecloud.com/hcmUI/CandidateExperience/en/sites/CX_1001/job/9280