Rabin-Williams signature and it's reduction to factorization

Question

Rabin signature is rightly celebrated as a signature scheme with provable reduction to factorization. How do we show that for Rabin-Williams signature as standardized, under the common and realistic hypothesis that the adversary has access to a signature oracle?

---

I'll describe in detail the standardized modular arithmetic in Rabin-Williams signature, per ISO/IEC 9796-2:2010 appendix B, or almost equivalently ISO/IEC 14888-2:2008 RW or IEEE P1363-2000 IFSP-RW/IFVP-RW¹. I assume signature with appendix per Full Domain Hash because I don't want to dive into padding and message recovery, but the reasoning also applies to deterministic paddings in these standards.

Security parameter $k$ is the public modulus size in bits. For the padding, we assume a hash function $H_k:\{0,1\}^*\to\{0,1\}^{k-5}$ with result assimilated to an integer in $[0,2^{k-5})$, and that this hash is undistinguishable from a Random Oracle.

• Key generation $\mathsf{Gen}$: on input $1^k$

  1. draw random primes $p,q\in[2^{(k-1)/2},2^{k/2}]$ with $p\equiv3\pmod8$ and $q\equiv7\pmod8$, which turns out to be possible $\forall k>10$
  2. compute $n\gets p\,q$, which is exactly $k$-bit
  3. set $e\gets2$ and compute $d\gets e^{-1}\bmod(\operatorname{lcm}(p-1,q-1)/2)$
  4. output $\mathrm{Pub}=(n,e)$ and $\mathrm{Priv}=(n,d)$.

• Signature $\mathsf{Sign}$: on input $\mathrm{Priv}=(n,d)$ and message $M$

  1. compute $k\gets\left\lceil\,\log_2(n)\right\rceil$
  2. compute message representative $m\gets16\,H_k(M)+12$ [with thus $m\in[0,2^{k-1})$ and $m\equiv12\pmod{16}$ ]
  3. compute² the Jacobi symbol $j\gets\left(\frac m n\right)$
  4. compute $g\gets\begin{cases}m/2&\text{if }\,j=-1\\m&\text{otherwise}\end{cases}\quad$[with thus $\left(\frac g n\right)\ge0$ ]
  5. compute $r\gets g^d\bmod n$
  6. compute and output the signature $s\gets\min(r,n-r)$.

• Verification $\mathsf{Ver}$: on input $\mathrm{Pub}=(n,e)$, message $M$ and signature $s$

  1. set $k\gets\left\lceil\,\log_2(n)\right\rceil$
  2. compute message representative $m\gets16\,H_k(M)+12$ [with thus $m\in[0,2^{k-1})$ and $m\equiv12\pmod{16}$ ]
  3. if $s\not\in[0,(n+1)/2)$ then output $\mathtt{Invalid}$ and stop
  4. compute $t\gets s^e\bmod n$ and $u\gets t\bmod8$
  5. if $u\not\in\{1,4,6,7\}$ then output $\mathtt{Invalid}$ and stop
  6. set $v\gets\begin{cases}t&\text{if }\,u=4\\n-t&\text{if }\,u=1\\ 2\,t&\text{if }\,u=6\\2\,(n-t)&\text{if }\,u=7\end{cases}$
  7. if $m\ne v$ then output $\mathtt{Invalid}$ and stop
  8. output $\mathtt{Valid}$.

Soundness can be proved using that for all $x\in\mathbb Z,\,x^2\equiv{\left({\left(x^2\right)}^d\right)}^e\pmod n$.

The values of $u$ allowed at $\mathsf{Ver}_5$ and cases at $\mathsf{Ver}_6$ correspond to $m\equiv12\pmod{16}$ after $\mathsf{Sign}_2$ and $\mathsf{Ver}_2$, per this table (where for large $k$ it's impossible in practice to find $M$ that triggers any of the four right cases):

$$\begin{array}{c|rrrr|rrrr} \left(\frac m p\right)&+1&-1&-1&+1&+1& 0&-1& 0\\ \left(\frac m q\right)&+1&-1&+1&-1& 0&+1& 0&-1\\ \hline \left(\frac m n\right)&+1&+1&-1&-1& 0& 0& 0& 0\\ u & 4& 1& 6& 7& 4& 4& 1& 1 \end{array}$$

Observation: adversaries with access to signatures of known arbitrary messages can compute $u\gets (s^e\bmod n)\bmod 8$, thus deduce $\left(\frac m p\right)$ and $\left(\frac m q\right)$ for known pseudo-random $m\equiv12\pmod{16}$. When without access to these signatures I only see they could get at the lesser information $\left(\frac m n\right)=\left(\frac m p\right)\,\left(\frac m q\right)$.

---

Questions [please ignore 1 and 3, I got them solved!]

1. _{Is there an argument that the above observation can't give an adversary with access to signatures (or a signature oracle) some insight on the factorization of $n$?}
2. How do we prove that this Rabin-Williams signature is sEF-CMA (Strongly secure against Existential Forgery under Chosen-Message Attack), assuming factorization of $n$ as output by $\mathsf{Gen}$ is hard?
3. _{Are these reductions to factorization all towards the security of the scheme, or do they somewhat go against it (leaving out side-channels and other implementation-specific attacks)? My concern is that existential break with signature oracle ⟹ factorization ⟹ total break is not intuitively reassuring.}

---

Update: perhaps the answer to 2 is in Bernstein's Proving tight security for Rabin-Williams signatures, originally in proceedings of Eurocrypt 2008, but I have a hard time following that paper³, or even ascertain the question's scheme is his α-|principal| with B=0 (thus fixed).

---

¹ IEEE P1363-2000 cites ISO/IEC 9796:1991 and Hugh C. Williams' A modification of the RSA public-key encryption procedure (in IEEE TIT, 1980) as it's origin. ISO/IEC 9796:1991 uses $m\equiv6\pmod{16}$ at $\mathsf{Sign}_2$ and $\mathsf{Ver}_2$, which requires minor adjustments at $\mathsf{Ver}_5$ and $\mathsf{Ver}_6$, see the Handbook of Applied Cryptography's Modified-Rabin signature scheme (starting page marked 439 following 11.27).

² One can compute $j\gets\left(\frac m n\right)$ per algorithm 2.149 in the Handbook of Applied Cryptography. Bernstein gives a method avoiding Jacobi symbols by making $p$ and $q$ part of the private key, reusing computations needed when using the Chinese Reminder Theorem to speed-up private-key operation, and other optimizations using precomputed values.

³ And I respectfully disagree on one count: the motivation of the $\min$ step in $\mathsf{Sign}_6$ is stated as:

the point is that ($s$) takes a bit less space than ($r$)

but that's missing another objective: having sEF-CMA rather than EF-CMA, by allowing the check in $\mathsf{Ver}_3$, which prevent an adversary from changing $s$ into an equally valid signature $n-s$, which would break sEF-CMA.

Answer 1

I'm still piecing things together, so bear with me as this may be revised.

1. Access to a signature oracle is either a zero-knowledge resource or breaks the random oracle model for $H_k$. To see this we observe that anyone can generate valid $(m,s)$ pairs for random values of $H_k$. They do this by picking arbitrary $s$ in the required range, squaring to get a $t$ and either discarding or going through verification step 6 to get a $m$ value. The only thing that they don't know is the $M$ that generated $H_k$, but the random oracle means that this information does not help in factoring $n$.

2. There is no special forgery to produce a separate signature for a given $M$ as the process is deterministic. It suffices therefore to show EUF-CMA. Suppose that an attacker can exhibit a forgery $(M,s)$ then their method must either produce $s$ before $M$ is fully specified or $M$ before $s$ is fully specified. If the former, they could have reconstructed $H_k(M)$ before knowing $M$ (it can't be a repeated message) and so have an improved chance of finding $M$ given $H_k(M)$ which violates our random oracle. If $M$ is fully specified before $s$, then the attacker has a means to construct one of $\sqrt m$, $\sqrt{-1}\sqrt m$, $\sqrt 2\sqrt m$ or $\sqrt{-2}\sqrt m$ (according to the choice in step 6) for a $m=16H_k+12$ with random $H_k$ with improved chances. We choose many random $x$, square them and see if the form matches a $u$ and then ask our attacker to construct the corresponding square root. In case 1 we get a random square root which gives us a pair of congruent squares and we have a chance to factor per the usual method. In case 2 we can compute a value for $\sqrt{-1}$ and future instances of case 2 will give us another instance of $\sqrt{-1}$ and a pair of congruent squares. Likewise case 3 and 4 give us values for $\sqrt{2}$ and $\sqrt{-2}$ and further instances again give us congruent squares. This with an expected $O(1)$ calls to the $\sqrt{u}$ extractor we will factor $n$.

3. The zero-knowledge nature of the signature oracle does provide assurance that the factoring problem is equivalent.

Answer 2

This answers my own Q1 and Q3. Q2 still flies above my head, but getting closer.

Q1 asked an argument why it can't help factoring $n$ that by examining Rabin-Williams signatures for known or chosen messages $M$, an adversary can find loads of pseudo-random $m=16\,H_k(M)+12$ with known $\left(\frac m p\right)$ and $\left(\frac m q\right)$; when for a given $m$, there is no known way to find these two quantities (only their product).

An argument is that adversaries have efficient alternate ways, requiring no signature or queries to a signature oracle, to find pseudo-random $m$ with whatever combination of non-zero $\left(\frac m p\right)$ and $\left(\frac m q\right)$ they see fit (see below). Thus having the same ability using signatures (or a signature oracle using a random oracle to prepare $m$) can't be of sizable usefulness in factoring.

Start from a random $x\in[1,n)$. Unless $\gcd(n,x)$ was a factor of $n$ $$\begin{array}{llclcl} m_0&\gets x^2\bmod n&\text{verifies}&\left(\frac{m_0}p\right)=+1&\text{and}&\left(\frac{m_0}q\right)=+1\\ m_1&\gets n-m_0&\text{verifies}&\left(\frac{m_1}p\right)=-1&\text{and}&\left(\frac{m_1}q\right)=-1\\ m_2&\gets2\,m_0\bmod n&\text{verifies}&\left(\frac{m_2}p\right)=-1&\text{and}&\left(\frac{m_2}q\right)=+1\\ m_3&\gets-2\,m_0\bmod n&\text{verifies}&\left(\frac{m_3}p\right)=+1&\text{and}&\left(\frac{m_3}q\right)=-1\\ \end{array}$$

Having one such $m_i$ of the appropriate kind, it's easy to make more: just multiply by a square and reduce modulo $n$. After pre-computation of a few squares, we can produce nearly one new $m\equiv12\pmod{16}$ per modular multiplication, by choosing which square we use this time according to a few high-order bits of the previous $m$.

---

Q3 asked why we consider arguments on the tune of if we could exhibit existential signature forgeries with access to a signature oracle, then we could factor it's $n$ as a good reason to trust a signature system.

I was making a rather basic confusion between

1. if adversaries with access to a signature oracle could exhibit existential signature forgeries, they could also factor $n$ (and make a total break)
2. if adversaries with access to a signature oracle could exhibit existential signature forgeries, they could also factor $n$ without access to the signature oracle (and make a total break with only the public key).

1 states [break (s)EUF-CMA for $n$ ] ⟹ [factor $n$ given $n$ and signatures under $n$ aplenty]. 2 states [break EUF-CMA for $n$ ] ⟹ [factor $n$ given $n$ ]. Thus 2 is a strictly better guarantee.

The difference is subtle. I was pointed literature that (rightly) states that 1 holds but is not reassuring, and does not point that 2 holds and is reassuring. That was my mistake when I asked Q3.

A proof of 2 (that, I'm convinced, holds for $H_k$ per FDH) is an excellent reason (beyond faster public-key operations) to use Rabin rather than RSA, if we disregard the potential for side channels, for implementation errors due to the added complexity, and for total break due to improper choice of $H_k$. The later issue has occurred for ISO/IEC 9796(-1):1991 where an attack causes a total break from the signature of 4 chosen messages, and ISO/IEC 9796-2:1997 where another does so for feasibly many messages and hashes of practical size.