7
$\begingroup$

Encryption in the original Rabin scheme took a message $x$ and computed $x(x + b) \bmod n$, where $0 \le b \lt n$ and $n$ is the product of two secret primes $p$ and $q$. The private key is defined as $(p,q)$ and the public key as $(b,n)$. Modern Rabin encryption however is defined as $x^2 \bmod n$, which is equivalent to the original scheme with $b = 0$. Why is $b$ now ignored?

This question is based on another question which I found interesting but which was mysteriously self-deleted.

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ Note: The original scheme was a signature scheme, not an encryption scheme. $\endgroup$ – Squeamish Ossifrage May 22 '19 at 1:42
  • 1
    $\begingroup$ Specifically, in the original scheme as described by Rabin in 1979, a public key is a pair of integers $(n, b)$ with $0 \leq b < n$, and a signature on a message $M$ is a pair $(x, U)$ of an integer $0 \leq x < n$ and a bit string $U$ such that $x(x + b) \equiv H(M, U) \pmod n$, where $H$ is a randomized hash function. The signer knows the secret factors $p$ and $q$ of $n$ by which they can solve for $x$ modulo $p$ and $q$ separately (if it exists, otherwise retry with another $U$). The paper uses the slightly confusing notation $C(MU)$, for ‘compressing function’, where I wrote $H(M, U)$. $\endgroup$ – Squeamish Ossifrage May 22 '19 at 2:49
  • 4
    $\begingroup$ The description on Wikipedia today is bad and misrepresents nearly all of the details from the original paper; obviously it was written by someone—or by a stumbling uncoordinated collective—who never bothered to actually read the paper and instead transcribed a secondhand game of telephone, as is mandated by the priests of Wikipedia who are apparently allergic to primary sources. $\endgroup$ – Squeamish Ossifrage May 22 '19 at 3:05
  • 3
    $\begingroup$ Galbraith's book has a footnote on p. 513 commenting that although the original scheme used $x(x + b)$, setting $b = 0$ improves efficiency with no loss in security, which seems obvious from Rabin's paper. The first edition of Stinson's book uses $x(x + b)$ without saying why; later editions just use $x^2$. Menezes, van Oorschot, and Vanstone (HAC) mention that the original paper used $x(x + b)$, but only describe $x^2$ for encryption and signature. $\endgroup$ – Squeamish Ossifrage May 22 '19 at 3:13
  • 2
    $\begingroup$ You could try emailing Michael Rabin! $\endgroup$ – Squeamish Ossifrage May 22 '19 at 3:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.