Abstract A partial key exposure attack is a key recovery attack where an adversary obtains a priori partial knowledge of the secret key, e.g., through side-channel leakage. While for a long time post-quantum cryptosystems, unlike RSA, have been believed to be resistant to such attacks, recent results by Esser, May, Verbel, and Wen (CRYPTO ’22), and by Kirshanova and May (SCN ’22), have refuted this belief. In this work, we focus on partial key exposure attacks in the context of rank-metric-based schemes, particularly targeting the RYDE, MIRA, and MiRitH digital signatures schemes, which are active candidates in the NIST post-quantum cryptography standardization process. We demonstrate that, similar to the RSA case, the secret key in RYDE can be recovered from a constant fraction of its bits. Specifically, for NIST category I parameters, our attacks remain efficient even when less than 25% of the key material is leaked. Interestingly, our attacks lead to a natural improvement of the best generic attack on RYDE without partial knowledge , reducing security levels by up to 9 bits. For MIRA and MiRitH our attacks remain efficient as long as roughly 57–60% of the secret key material is leaked. Additionally, we initiate the study of partial exposure of the witness in constructions following the popular MPCitH (MPC-in-the-Head) paradigm. We show a generic reduction from recovering RYDE and MIRA’s witness to the MinRank problem, which again leads to efficient key recovery from constant fractions of the secret witness in both cases.

Abstract Cryptographic group actions have gained significant attention in recent years for their application on post-quantum Sigma protocols and digital signatures. In NIST’s recent additional call for post-quantum signatures, three relevant proposals are based on group actions: LESS, MEDS, and ALTEQ. This work explores signature optimisations leveraging a group’s factorisation. We show that if the group admits a factorisation as a semidirect product of subgroups, the group action can be restricted on a quotient space under the equivalence relation induced by the factorisation. If the relation is efficiently decidable, we show that it is possible to construct an equivalent Sigma protocol for a relationship that depends only on one of the subgroups. Moreover, if a special class of representative of the quotient space is efficiently computable via a canonical form, the restricted action is effective and does not incur in security loss. Finally, we apply these techniques to the group actions underlying LESS and MEDS, showing how they will affect the length of signatures and public keys.

Verifiable Credentials (VCs) can play a crucial role for the identity layer of the Internet. VCs allow Holders to share cryptographically verifiable claims issued by trusted Issuers for authentication purposes. However, plaintext VCs can compromise the privacy of the Holder, as they must disclose entire VCs even when only partial information is required. To address this growing concern, the concept of anonymous credentials has been introduced. In addition, with the advent of Cryptographically Relevant Quantum Computers, many cryptography fields, including that of anonymous credentials, face significant security challenges. This threat urge the design, development, and the implementation of Post-Quantum Anonymous Verifiable Credential frameworks. This paper contributes to this challenge by presenting the analysis and selection of a practical PQ Anonymous Credential framework, the adaptation of the framework to the VC concept introduced by the Self-Sovereign Identity Model, and the software implementation with 128 bit security with the initial performance evaluation.

Abstract Starting from the problem of d-tensor isomorphism (d- $$\textsf {TI}$$ TI ), we study the relation between various code equivalence problems in different metrics. In particular, we show a reduction from the sum-rank metric ( $$\textsf {CE}_{\textsf {sr}}$$ CE sr ) to the rank metric ( $$\textsf {CE}_{\textsf {rk}}$$ CE rk ). To obtain this result, we investigate reductions between tensor problems. We define the monomial isomorphism problem for d-tensors (d- $$\textsf {TI}^*$$ TI ∗ ), where, given two d-tensors, we ask if there are $$d-1$$ d - 1 invertible matrices and a monomial matrix sending one tensor into the other. We link this problem to the well-studied d- $$\textsf {TI}$$ TI and the $$\textsf {TI}$$ TI -completeness of d- $$\textsf {TI}^*$$ TI ∗ is shown. Due to this result, we obtain a reduction from $$\textsf {CE}_{\textsf {sr}}$$ CE sr to $$\textsf {CE}_{\textsf {rk}}$$ CE rk . In the literature, a similar result was known, but it needs an additional assumption on the automorphisms of matrix codes. Since many constructions based on the hardness of Code Equivalence problems are emerging in cryptography, we analyze how such reductions can be taken into account in the design of cryptosystems based on $$\textsf {CE}_{\textsf {sr}}$$ CE sr .