In this paper, we treat (k, L, n) ramp secret sharing schemes (SSSs) that can detect impersonation attacks and/or substitution attacks. First, we derive lower bounds on the sizes of the shares and random number used in encoding for given correlation levels, which are measured by the mutual information of shares. We also derive lower bounds on the success probabilities of attacks for given correlation levels and given sizes of shares. Next we propose a strong (k, L, n) ramp SSS against substitution attacks. As far as we know, the proposed scheme is the first strong (k, L, n) ramp SSSs that can detect substitution attacks of at most k-1 shares. Our scheme can be applied to a secret SL uniformly distributed over GF(pm)L, where p is a prime number with p≥L+2. We show that for a certain type of correlation levels, the proposed scheme can achieve the lower bounds on the sizes of the shares and random number, and can reduce the success probability of substitution attacks within nearly L times the lower bound when the number of forged shares is less than k. We also evaluate the success probability of impersonation attack for our schemes. In addition, we give some examples of insecure ramp SSSs to clarify why each component of our scheme is essential to realize the required security.

In 2004, Menezes and Smart left an open problem that is whether there exists a realistic scenario where message and key substitution (MKS) attacks can have damaging consequences. In this letter, we show that MKS attacks can have damaging consequences in practice, by pointing out that a verifiably encrypted signature (VES) scheme is not opaque if MKS attacks are possible.

In this letter, we point out that key substitution attacks should be taken into account for multisignature schemes, which implies that the existing security notions for multisignature schemes are not sufficient. As an example, we show that the multisignature scheme proposed by Boldyreva at PKC'03 is susceptible to key substitution attacks.

At Asiacrypt'2001, Courtois, Finiasz and Sendrier proposed the first coding-based signature scheme which is also known as the CFS signature. The CFS signature is seen as one of the candidates of quantum immune signatures. In this letter, we show that the CFS signature is susceptible to both strong-key substitution attacks and weak-key substitution attacks. We also discuss potential countermeasures.

Recently, Waters proposed a provably secure signature schemes in the standard model. In this letter, we analyse the security of this signature scheme. We found that the signature scheme is subjected to key substitution attack and is malleable.

Recently, Boneh et al. proposed provably secure short signature schemes in the standard model and in the random oracle model respectively. In this letter, we propose strong-key substitution attacks on these signature schemes. In one of the attacks, we show that an adversary can generate a new public key satisfying all legitimate signatures created by the legitimate signer.

Recently, Camenisch et al. and Fischlin proposed provably secure signature schemes in the standard models respectively. In this letter, we propose key substitution attacks on these two signature schemes. We show that an adversary can generate a valid public key corresponding to a legitimate signature.

This paper analyzes a generalized secret-key authentication system from a viewpoint of the information-spectrum methods. In the generalized secret-key authentication system, for each n 1 a legitimate sender transmits a cryptogram Wn to a legitimate receiver sharing a key En in the presence of an opponent who tries to cheat the legitimate receiver. A generalized version of the Simmons' bounds on the success probabilities of the impersonation attack and a certain kind of substitution attack are obtained.

This paper provides the Shannon theoretic coding theorems on the success probabilities of the impersonation attack and the substitution attack against secret-key authentication systems. Though there are many studies that develop lower bounds on the success probabilities, their tight upper bounds are rarely discussed. This paper characterizes the tight upper bounds in an extended secret-key authentication system that includes blocklength K and permits the decoding error probability tending to zero as K . In the extended system an encoder encrypts K source outputs to K cryptograms under K keys and transmits K cryptograms to a decoder through a public channel in the presence of an opponent. The decoder judges whether K cryptograms received from the public channel are legitimate or not under K keys shared with the encoder. It is shown that 2-KI(W;E) is the minimal attainable upper bound of the success probability of the impersonation attack, where I(W;E) denotes the mutual information between a cryptogram W and a key E. In addition, 2-KH(E|W) is proved to be the tight upper bound of the probability that the opponent can correctly guess K keys from transmitted K cryptograms, where H(E|W) denotes the conditional entropy of E given W.