  Based on binary inquiries, we developed an algorithm to estimate population
quantiles under Local Differential Privacy (LDP). By self-normalizing, our
algorithm provides asymptotically normal estimation with valid inference,
resulting in tight confidence intervals without the need for nuisance
parameters to be estimated. Our proposed method can be conducted fully online,
leading to high computational efficiency and minimal storage requirements with
$\mathcal{O}(1)$ space. We also proved an optimality result by an elegant
application of one central limit theorem of Gaussian Differential Privacy (GDP)
when targeting the frequently encountered median estimation problem. With
mathematical proof and extensive numerical testing, we demonstrate the validity
of our algorithm both theoretically and experimentally.
