I read the description of 1-2 oblivious transfer algorithm in wikipedia. In the algorithm described Alice has two messages $m_0, m_1$. Bob picks value $b \in {0,1}$, and the protocol allows Bob to obtain $m_b$, while Alice does not know which value was sent to Bob.

The protocol requires that Alice creates an RSA private,public key pair, and also a value for e. I was wondering if Bob has to perform any verification over there values. It seems to me that Alice can craft special values for N=pq, and e such that it is easier for Alice to find out what was the value of Bob's b.

An edge case would be for Alice to pick e=0. In that case, $k^e = 1$, and therefore the blinding performed by Bob does nothing, and Alice can always discover b.

What if Alice chooses an N that is not really a multiplication of two large primes, with a combination of a specially crafted value of e?

Is there a way for Bob to defend himself against such behavior from Alice?


1 Answer 1


There are many proof systems achieving this goal, i.e. Alice can prove to Bob, that her public parameters were chosen in a "right way". What does "right way" mean?

Typically, what we want for public parameters $(N,e)$ is that the map $x\rightarrow x^e$ over $\mathbb{Z}^{*}_{N}$ defines a permutation to deter certain attacks, for example the attack mentioned in OP's question. The state of the art for such a proof system is proposed by Goldberg et al. It is a non-interactive Honest-Verifier Zero-knowledge proof system allowing one to certify that public RSA parameters were generated in a non-adversarial manner without leaking any information about the factors of $N$. Such a certification contains $\lambda/\log_{2} e'$ group elements from $\mathbb{Z}^{*}_{N}$, where $\lambda$ is the bit-security one wants for the soundness of the certificate proof and $e'$ is the smallest prime which divides the public exponent $e$. In a typical parameter setting, where $e=e'=65537$, with $\lambda=128$, the proof consists of $9$ integers from $\mathbb{Z}^{*}_{N}$ and also proof generation and verification is super lightweight. For more details, see the paper linked above.

There are also many proof systems allowing one to prove that an integer is a product of two primes. This is quite an old paper by van de Graaf and Peralta but might suffice for your needs. One could even prove more about a semiprime! For instance one could prove that a (committed) number is a product of two safe primes due to Camenisch and Michels. Additionally, one could prove that a number is a product of two primes AND also a Blum-integer. Lastly, there is an efficient, non-interactive, statistical zero-knowledge proof system for quasi-safe prime products by Gennaro, Micciancio and Rabin.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.