2
$\begingroup$

Given a prime $p$ and positive integer $t \ll \log p$ (say $t = \sqrt{\log p}$), is there an algorithm that is polynomial time in $\log p$ to sample uniform $X, Y \in \mathbb{F}_p$ conditioned on the following constraints:

1) For some $a \in \mathbb{F}_p$, $$X Y = a \mod p.$$ 2) Express $X$ as a bitstring $X_1 \ldots X_{\lceil \log p\rceil}$ using the binary representation. Then the $\lceil \log p\rceil$ binary random variables so obtained lie in a given subspace of $\mathbb{F}_2^{\lceil \log p \rceil}$ of dimension $\lceil\log p\rceil - t$.

3) Same condition as 2) for $Y_i$'s.

I will be happy to get any pointers or reference for this. Even some intuition on why this might or might not be true will be helpful.

$\endgroup$

0

Your Answer

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