Experimental Boson Sampling Enabling Cryptographic One-Way Function

Boson sampling is a computational problem, which is commonly believed to be a representative paradigm for attaining the milestone of quantum advantage. So far, massive efforts have been made to the experimental large-scale boson sampling for demonstrating this milestone, while further applications of the machines remain a largely unexplored area. Here, we investigate experimentally the efficiency and security of a cryptographic one-way function that relies on coarse-grained boson sampling, in the framework of a photonic boson-sampling machine fabricated by a femtosecond laser direct writing technique. Our findings demonstrate that the implementation of the function requires moderate sample sizes, which can be over 4 orders of magnitude smaller than the ones predicted by the Chernoff bound; whereas for numbers of photons $n\ge 3$ and bins $d\sim \mathrm{poly}(m,n)$, the same output of the function cannot be generated by nonboson samplers. Our Letter is the first experimental study that deals with the potential applications of boson sampling in the field of cryptography and paves the way toward additional studies in this direction.

Figure 1

Schematic representation of the BS-based OWF $y=\mathcal{F}(x)$ [37]. An integer $x$ is used as an input to the algorithm $g$, which generates a sequence of $n$ seeds. The $k$th seed ${\mathit{s}}^{(k)}$ defines a boson configuration at the input of the boson sampler, which samples from the corresponding distribution at the output (solid curve), thereby providing information about the label of the MPB ${\mu }^{(k)}$ in a coarse-grained distribution with $d$ bins (red and blue bars). The sequence of labels is possessed by algorithm $G$ to yield the output $y$.

Figure 2

Schematic representation of the BSA [37]. Sampling from an unknown coarse-grained boson distribution, one obtains a sample of size $\mathcal{N}\gg 1$. Given this sample, the algorithm searches for the location of the maximum in the unknown distribution by means of bootstrap analysis. Using a standard computer, one resamples from the original sample data with substitution, to produce $\mathcal{M}\gg 1$ independent empirical bootstrap samples of size $\mathcal{N}$. The sequence of the most frequent bins in the bootstrap samples is recorded ${\mu }_1^{*},\dots ,{\mu }_{\mathcal{M}}^{*}$, and we check whether the frequency ${\mathrm{\Omega }}_{\max }$ associated with the most frequent label $\tilde{\mu }$ satisfies ${\mathrm{\Omega }}_{\max }\ge 1-\xi$, for some $\xi \ll 1$. If ${\mathrm{\Omega }}_{\max }\ge 1-\xi$, our estimate for the MPB in the unknown sampled distribution is $\tilde{\mu }$; otherwise we increase the sample, and the bootstrap analysis is repeated.

Figure 3

Experimental setup. Three-photon Fock state is prepared by successively bumping a collinear and a beamlike $\beta$-barium borate crystal with a frequency doubled 390 nm femtosecond laser pulse. The Hong-Ou-Mandel visibility between the photons in the same pair is about 95% and 80% for different pairs. LBO: lithium triborate, DM: dichromatic mirror, and BPF: band pass filter.

Figure 4

Estimation of the MPB by means of the BSA. (a) Sample sizes required for the reliable identification of the MPB, for different numbers of bins. Squares and circles refer to the identification of the MPB through the establishment of a confidence interval for $P_{\max }$, with and without the bootstrap analysis of the sample data. Diamonds refer to the BSA, which is the sample size required in practice. (b)–(f) Maximum frequency of occurrence ${\mathrm{\Omega }}_{\max }$, as a function of the sample size. The BSA has converged when ${\mathrm{\Omega }}_{\max }\ge 1-\xi$. All of the depicted results pertain to the seed (1,2,5), and similar results hold for all of the two- and three-photon seeds we have investigated in our Letter. Other parameters: $\mathcal{M}={10}^4$, $\xi =0.0001$.

Figure 5

Fraction of inputs for which the OWF returns the same output for distinguishable and indistinguishable photons. (a) and (b) Two- and three-photon case, with $9^2=81$ and $4^3=64$ different input combinations, respectively. The blue and red bars refer to experimental and theoretical results.