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.

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.

The Permuted Kernel Problem (PKP) is a problem in linear algebra that was first introduced by Shamir in 1989. Roughly speaking, given an ℓ × m matrix A and an m × 1 vector b over a finite field of q elements F q , the PKP asks to find an m × m permutation matrix π such that π b belongs to the kernel of A . In recent years, several post-quantum digital signature schemes whose security can be provably reduced to the hardness of solving random instances of the PKP have been proposed. In this regard, it is important to know the expected number of solutions to a random instance of the PKP in terms of the parameters q , ℓ , m . Previous works have heuristically estimated the expected number of solutions to be m ! / q ℓ . We provide, and rigorously prove, exact formulas for the expected number of solutions to a random instance of the PKP and the related Inhomogeneous Permuted Kernel Problem (IPKP), considering two natural ways of generating random instances.