6

This answer is assuming you are not removing the private key $a$ from the computation of $S$, and instead actually meant what is said in the title of the question: $S = r + a H(A, M)$ Removing $a$ from the computation would be terrible. The first issue that comes to mind is malleability, on top of collision resistance. The signature process for EdDSA ...


5

would using S = r + H(A, M) be a secure variant? Actually, it would become trivial to generate a signature for an abitrary message with just the public key. The verification check would be: $$2^h s G = 2^h R + 2^h H(A, M) A$$ where $h$ is the curve cofactor, $G$ is the curve generator, $A$ is the public key, $M$ is the message and $(R, s)$ is the signature. ...


5

It does contribute to the security. In particular, the hash function $H$ must be “random prefix preimage resistant” in order to be safe from Key Only forgeries and “random prefix second preimage resistant” in order to be safe from Known Message forgeries. By “random prefix preimage resistant”, we mean that given an output value $e$ and a random $r$, it is ...


3

why were signing and encryption schemes based only on the discrete-log problem not more popular? Well, I expect any answer is somewhat opinion based; however, my perspective: RSA didn't have many significant disadvantages compared to discrete-log-based solutions. You mentioned that RSA required a "complicated padding scheme"; many discrete-log ...


3

As long as the public key is in the elliptic curve group, there is no such thing as being "of the correct form" or not. For any point $P$ in the group, there exists a value $x$ such that $P=x\cdot G$. Thus, all that is necessary is to check that $P$ is indeed in the group. This is carried out by checking (1) that $P=(x,y)$ is on the elliptic curve ...


2

I believe this is the 'Rewinding Lemma' part of Schoor identification security proof, and very well explained in the Boneh and Shoup book "A Graduate Course in Applied Cryptography", pgs 727-728. An important aspect here is that we have to consider another adversary B, who emulates (grab a digital compiled version of A) and plays/interacts with A. (...


2

Yes it can be tested if a given $Y$ is of the form $x\cdot G$ (for some $x\ne0\bmod n$ ), even though it is not possible to find $x$. How depends on the Elliptic Curve (but I don't see that also possessing a matching signature helps). For an Elliptic Curve with $h=1$ (meaning $G$ generates the full curve), it's enough to check if the point $Y$ is on the ...


2

Both models have the same "computational power" : You can build $Mult$, and $Inv$ routines with $mexp$, and you can build $mexp$ with $Mult$ (by using square-and-multiply algorithm). We can think that in the second model the adversary has access to the real value of the element, but it can use it to have a better efficiency because the coefficients ...


2

Here, $k$ bits of security means that the advantage is at most $O\left(\frac{T^\alpha}{2^{\alpha k}}\right)$, after doing $T$ operations (of all types) made by the adversary. With this formalism, it allows us to conclude that the adversary need to do $O(2^k)$ "operations" to break the system ($T^\alpha \approx2^{\alpha k}\implies T \approx 2^k$). ...


2

Reduction from multi-user to single-user First, please notice that there is a reduction between the multi-user security and the standard single-user security for signature scheme: it was proven in 2002 by Galbraith, Malone-Lee, and Smart (GSM) that for any signature system, attacking the scheme in the multi-user setting with $N$ public-keys cannot increase ...


1

There is none. Schnorr's signature had only ever been academically described, so no standard for it there is all variaty of potentially incompatible specifications for it, lacking a uniform standard. There was standard for ElGamel encryption when NIST was running the OSI Implementor's Workshop, but it wasn't widely used. There is however, EdDSA, which is a ...


1

@Maher's comments guided me to understanding. To prove security of short Schnorr signature from security of «regular» Schnorr signature with the same hash $H$, we hypothesizes a PPT algorithm $\mathcal A$ that breaks short Schnorr signature, and use it to build algorithm $\mathcal A'$ that breaks regular Schnorr signature, as follows. $\mathcal A'$ does as $\...


1

No, unless I'm misunderstanding something in your question. $Y = z \cdot g = (2^{-1}y)\cdot g + y\cdot (2^{-1}g) = x\cdot g +x' \cdot g'$ That is even a "valid" $Y$ can be expressed as a sum of points. If you recognize that elliptic curves are a group, this should be apparent.


Only top voted, non community-wiki answers of a minimum length are eligible