# How to simplify a the signing process in an elliptic curve signature scheme that involves a quadratic verification equation?

Cryptography Asked by Columbida on January 26, 2021

I am looking at a proprietary signature scheme used in production. It involves a short Weierstrass curve $$E_{mathcal{W}}:y^2=x^3+ax+b$$ in the prime field $$mathbb{F}_p$$. The parameters are set up such that $$E_{mathcal{W}}$$ is always expressible as a Montgomery curve $$E_{mathcal{M}}:y^2=x^3+x$$ (i.e. $$a_{mathcal{W}}=1$$, $$b_{mathcal{W}}=0$$, $$A_{mathcal{M}}=0$$, and $$B_{mathcal{M}}=1$$). As far as I know, the Montgomery form is never used for verification. The curve has highly composite order $$n$$, with a base point $$B$$ having prime order $$ell$$.

The verification process given a hash function $$H$$, a keyed hash function built from $$H$$ with (namely $$H$$ in HMAC mode, $$H_k$$), a message $$M$$, a public key $$K$$ and a signature consisting of a scalar $$s$$ and a hash $$h$$ is performed as follows:

1. $$h_1=H_{c_1}(M||h)$$.
2. $$R=scdot(sB+h_1K)$$
3. $$h_2=H_{c_2}(M || R_x || R_y)$$, where $$R_x$$ is the $$x$$ coordinate of $$R$$ and accordingly $$R_y$$ is the $$y$$ coordinate of $$R$$
4. If $$h_2=h$$, the signature is valid; else, it is invalid.

$$c_1$$ and $$c_2$$ are static HMAC keys known both to the signer and the verifier. My conjecture is that they act as domain separation strings.

I am trying to determine if there is an efficient way of creating a signature that does not involve taking a square root in $$mathbb{F}_p$$. Square roots are not trivially found in $$p$$ because $$p$$ it may be that $$pequiv1pmod{4}$$ and $$pequiv1pmod{8}$$.
Currently, I reach the following signing process:

1. Choose a nonce $$r$$ such that $$0.
2. $$R=rB$$
3. $$h_2=H_{c_2}(M||R_x||R_y)$$
4. $$h_1=H_{c_1}(M||h_2)$$
5. $$s=frac{-Hkpmsqrt{(h_1k)^2+4r}}{2}pmod{ell}$$, where $$k$$ is the secret key corresponding to $$K$$ in the verification process
6. If $$sqrt{(h_1k)^2+4r}$$ has no solution in $$mathbb{F}_p$$, restart from the beginning.
7. Output signature $$(s, h_2)$$.

Is there a way to create a signature passing the above verification process that does not involve a square root in $$mathbb{F}_p$$?

Ignoring the case of $$R$$ being the point at infinity, I have found a patent that seems to describe the system you outline to a T: US 7,512,232 B2, which also makes me suspect that your "commercial" system ends up being Microsoft's in particular. It specifically notes that taking the square root modulo $$ell$$ is a requirement. In other words, no, there is no way to simplify.

Answered by asnfkjsdx on January 26, 2021

Is there a way to create a signature passing the above verification process that does not involve a square root in $$mathbb{F}_p$$?

Well, one obvious thing to try is setting $$R=0$$ (the point at infinity); assuming the code doesn't have any protection against that (and the pseudocode doesn't), you compute $$h = H_{c_2}(M || R_x || R_y )$$ (where $$R_x, R_y$$ is whatever representation the point-at-infinity has), set $$s=0$$, and you're done...

Answered by poncho on January 26, 2021

## Related Questions

### Binomial distribution sampling – concrete example

0  Asked on January 4, 2022

### Using xor encryption in the following use case

1  Asked on December 31, 2021 by kaa

### How to justify the lightweight symmetric PRESENT encryption algorithm is more secure?

0  Asked on December 31, 2021 by sunitha-tappari

### Difference Between an Authentication Token and an OTP (One Time Password)

0  Asked on December 28, 2021 by dawnforce

### Using XOR to derive a data key for ECIES

2  Asked on December 26, 2021 by maarten-bodewes

### Digital Signature or MAC Yielding Non-Binary Verification Predicate

0  Asked on December 24, 2021

### Computing PGP ed25519 and curve25519 keygrips?

2  Asked on December 21, 2021 by skaht

### Find Consecutive X-Coordinate algorithm

1  Asked on December 21, 2021 by kmart875

### Is there any proof for ECDSA signature algorithm?

1  Asked on December 19, 2021 by sanket1729

### What basic knowledge is required to understand SIKE?

1  Asked on December 19, 2021 by vivekanand-v

### Why we can’t implement AES 512 key size?

3  Asked on December 17, 2021 by hamedb71

### MD5 – Chosen Prefix Collision Attack

1  Asked on December 17, 2021

### Does selectively generating keypairs with particular public-key hash prefix weaken the security?

2  Asked on December 17, 2021

### Difference between polynomial embedding and canonical embedding

0  Asked on December 17, 2021

### How can Cipher Block Chaining (CBC) in SSL be attacked?

3  Asked on December 14, 2021 by antonpug

### Subset Sum Hashes

1  Asked on December 14, 2021 by lev-knoblock

### Why is this authenticated Diffie–Hellman key exchange insecure?

1  Asked on December 14, 2021 by beroal

### Homomorphic encryption scheme for modulo reduction

0  Asked on December 8, 2021

### Can we say that password authentication contains registration phase, authentication phase and authenticated key exchange phase?

0  Asked on December 6, 2021 by z-p

### LWR parameter estimation

0  Asked on December 4, 2021 by mev