Cryptanalysis of the SHMW signature scheme.

In recent research, Durandal, a signature scheme based on rank metrics following Schnorr's approach, was introduced to conceal secret key information by selectively manipulating the vector subspace of signatures. Later, an enhancement, namely the SHMW signature scheme, with smaller keys and signatures while maintaining EUF-CMA security, was proposed. Both Durandal and SHMW require adversaries to solve hard problems (i.e., Rank Support Learning, Rank Syndrome Decoding, and Affine Rank Syndrome Decoding) for secret key retrieval, in which the parameters are designed to withstand at least 128-bit computational complexity. The authors claimed that the security of the SHMW scheme is deemed superior to that of the original Durandal scheme. In this paper, we introduce a novel approach to identifying weak keys within the Durandal framework to prove the superiority of the SHMW scheme. This approach exploits the extra information in the signature to compute an intersection space that contains the secret key. Consequently, a cryptanalysis of the SHMW signature scheme was carried out to demonstrate the insecurity of the selected keys within the SHWM scheme. In particular, we proposed an algorithm to recover an extended support that contains the secret key used in the signature schemes. Applying our approach to the SHMW scheme, we can recover its secret key with only 97-bit complexity, although it was claimed that the proposed parameters achieve a 128-bit security level. The results of our proposed approaches show that the security level of the SHMW signature scheme is inferior compared to that of the original Durandal scheme.

A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem.

In 1999, the Polynomial Reconstruction Problem (PRP) was put forward as a new hard mathematics problem. A univariate PRP scheme by Augot and Finiasz was introduced at Eurocrypt in 2003, and this cryptosystem was fully cryptanalyzed in 2004. In 2013, a bivariate PRP cryptosystem was developed, which is a modified version of Augot and Finiasz's original work. This study describes a decryption failure that can occur in both cryptosystems. We demonstrate that when the error has a weight greater than the number of monomials in a secret polynomial, p, decryption failure can occur. The result of this study also determines the upper bound that should be applied to avoid decryption failure.

Digital signature schemes with strong existential unforgeability.

Digital signature schemes (DSS) are ubiquitously used for public authentication in the infrastructure of the internet, in addition to their use as a cryptographic tool to construct even more sophisticated schemes such as those that are identity-based. The security of DSS is analyzed through the existential unforgeability under chosen message attack (EUF-CMA) experiment which promises unforgeability of signatures on new messages even when the attacker has access to an arbitrary set of messages and their corresponding signatures. However, the EUF-CMA model does not account for attacks such as an attacker forging a different signature on an existing message, even though the attack could be devastating in the real world and constitutes a severe breach of the security system. Nonetheless, most of the DSS are not analyzed in this security model, which possibly makes them vulnerable to such an attack. In contrast, a better security notion known as strong EUF-CMA (sEUF-CMA) is designed to be resistant to such attacks. This review aims to identify DSS in the literature that are secure in the sEUF-CMA model. In addition, the article discusses the challenges and future directions of DSS. In our review, we consider the security of existing DSS that fit our criterion in the sEUF-CMA model; our criterion is simple as we only require the DSS to be at least secure against the minimum of existential forgery. Our findings are categorized into two classes: the direct and indirect classes of sEUF-CMA. The former is inherently sEUF-CMA without any modification while the latter requires some transformation. Our comprehensive  review contributes to the security and cryptographic research community by discussing the efficiency and security of DSS that are sEUF-CMA, which aids in selecting robust DSS in future design considerations.