pith. sign in

arxiv: 1907.01788 · v1 · pith:K3KI5WQMnew · submitted 2019-07-03 · 🪐 quant-ph · cs.CR

Cryptographic One-way Function Based on Boson Sampling

Georgios M. Nikolopoulos This is my paper

Pith reviewed 2026-05-25 10:23 UTC · model grok-4.3

classification 🪐 quant-ph cs.CR
keywords boson samplingone-way functionsquantum cryptographypost-quantum cryptographylinear optical quantum computingcomputational hardnesscoarse graining
0
0 comments X

The pith

Coarse-grained boson sampling produces a one-way function whose inversion is hard for classical computers but feasible for quantum ones.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes a one-way function built directly from the coarse-grained output probabilities of a boson sampler. Evaluation proceeds by running the sampler and grouping the photon-count outcomes into fewer bins, which remains straightforward on a quantum device. Inversion requires recovering the original input mode configuration from a given coarse-grained result, a task the authors argue is computationally intractable for any classical algorithm. A reader would care because one-way functions form the foundation of asymmetric cryptography, and this construction aims to remain secure even if large-scale quantum computers become available.

Core claim

Coarse-grained boson sampling defines a mathematical one-way function in which the forward map is realized by sampling the linear-optical evolution of indistinguishable photons and then binning the output distribution, while the inverse map—recovering the input state from the binned probabilities—is presumed to lack an efficient classical algorithm. The one-way property therefore rests on the computational asymmetry between quantum sampling and classical inversion of the reduced distribution.

What carries the argument

Coarse-grained boson sampling, the process of grouping the full output photon-number distribution into a smaller number of probability bins to create the function values.

If this is right

  • The function can serve as a primitive for constructing quantum-resistant public-key encryption or digital signatures.
  • Boson sampling devices acquire a direct cryptographic use beyond supremacy demonstrations.
  • Evaluation scales with the number of photons and modes on existing linear-optical hardware, while classical inversion does not.
  • The same coarse-graining step can be applied to other quantum sampling tasks to generate additional one-way functions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the hardness assumption holds, it supplies a concrete link between the complexity of boson sampling and the security of cryptographic protocols.
  • Practical deployment would require experimental confirmation that the coarse-graining does not introduce classical shortcuts.
  • Similar reductions might be explored for other near-term quantum sampling platforms to enlarge the set of post-quantum primitives.

Load-bearing premise

Inverting the coarse-grained output distribution remains computationally intractable for classical computers while remaining feasible for quantum computers.

What would settle it

An efficient classical algorithm that, given only the coarse-grained probabilities, recovers the input configuration for boson sampling instances with more than a few dozen photons.

read the original abstract

The quest for practical cryptographic primitives that are robust against quantum computers is of vital importance for the field of cryptography. Among the abundance of different cryptographic primitives one may consider, one-way functions stand out as fundamental building blocks of more complex cryptographic protocols, and they play a central role in modern asymmetric cryptography. We propose a mathematical one-way function, which relies on coarse-grained boson sampling. The evaluation and the inversion of the function are discussed in the context of classical and quantum computers. The present results suggest that the scope and power of boson sampling may go beyond the proof of quantum supremacy, and pave the way towards cryptographic applications.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper proposes a one-way function based on coarse-grained boson sampling. It claims that this function can be evaluated and inverted in the context of classical and quantum computers, suggesting that boson sampling has cryptographic applications beyond proofs of quantum supremacy.

Significance. If a valid construction existed that satisfied the standard cryptographic definition of a one-way function while leveraging the conjectured hardness of boson sampling, the result would be significant as a potential post-quantum primitive. However, the absence of an efficient classical forward map means the claimed object does not meet the definition, limiting any cryptographic relevance.

major comments (2)
  1. [Abstract] The manuscript provides no mathematical definition of the proposed function, no explicit construction mapping inputs to outputs, and no derivation establishing the one-way property (Abstract).
  2. A one-way function requires a classical polynomial-time algorithm for forward evaluation f(x). The construction relies on (coarse-grained) boson sampling, whose output probabilities are #P-hard to compute classically; no classical poly-time forward procedure is supplied or possible under standard complexity assumptions, so the object fails the definition of an OWF regardless of inversion hardness.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive report. We address the two major comments point-by-point below, providing clarifications on the function definition and the evaluation procedure while acknowledging where revisions are needed to strengthen the presentation.

read point-by-point responses

  1. Referee: [Abstract] The manuscript provides no mathematical definition of the proposed function, no explicit construction mapping inputs to outputs, and no derivation establishing the one-way property (Abstract).

    Authors: The main text defines the function via coarse-grained boson sampling: the input is a unitary matrix U (specified by its entries or circuit description) together with photon number n, and the output is the vector of binned photon-count probabilities (or a sample from that distribution) after applying the linear-optical transformation. The one-way property is argued from the conjectured hardness of recovering the input unitary or exact configuration from the coarse-grained output. We agree that an explicit formal definition and mapping should appear already in the abstract and will add it. revision: yes

  2. Referee: A one-way function requires a classical polynomial-time algorithm for forward evaluation f(x). The construction relies on (coarse-grained) boson sampling, whose output probabilities are #P-hard to compute classically; no classical poly-time forward procedure is supplied or possible under standard complexity assumptions, so the object fails the definition of an OWF regardless of inversion hardness.

    Authors: We accept the referee's statement of the standard cryptographic definition. The manuscript discusses forward evaluation both classically (via approximate sampling methods whose complexity is not proven polynomial) and on a quantum device (where boson sampling is efficient). Because the paper does not supply a classical polynomial-time algorithm for exact forward evaluation, the construction does not satisfy the classical OWF definition. We will revise the manuscript to state this limitation explicitly, reframe the proposal as a candidate one-way function in the quantum-evaluation setting, and remove any implication that it meets the classical definition. revision: yes

Circularity Check

0 steps flagged

No circularity; proposal rests on external hardness conjecture without self-referential reduction

full rationale

The provided abstract and context contain no equations, derivation steps, or load-bearing claims that reduce by construction to the paper's own inputs. The one-way function is proposed by mapping inputs to coarse-grained boson-sampling outputs, with the inversion hardness asserted to follow from the known #P-hardness of boson sampling (an external conjecture). No self-definitional mapping, fitted parameter renamed as prediction, or self-citation chain is exhibited. The text is therefore self-contained against the circularity criteria.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract alone supplies no concrete free parameters, axioms, or invented entities. The proposal implicitly relies on the established properties of boson sampling from prior literature, but no details are extractable.

pith-pipeline@v0.9.0 · 5618 in / 1076 out tokens · 39911 ms · 2026-05-25T10:23:04.881408+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages · 3 internal anchors

  1. [1]

    Menezes, P

    A. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography (CRC Press, 1996)

    work page 1996

  2. [2]

    Goldreich, Foundations of cryptography: Basic Techniques , (Cambridge University Press, Cambridge, UK 2004)

    O. Goldreich, Foundations of cryptography: Basic Techniques , (Cambridge University Press, Cambridge, UK 2004)

    work page 2004

  3. [3]

    M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, London, 2000)

    work page 2000

  4. [4]

    Post-Quantum Cryptography , edited by D. J. Bernstein, J. Buchmann, E. Dahmen (Springer-Verlag Berlin, 2009). Cryptographic One-way Function Based on Boson Sampling 25 10 -4 10 -3 10 -2 Difference of probabilities 0 50 100 150 Number of bins 10 4 10 5 10 6 10 7 10 8 10 9 Sample size 0 50 100 150 Number of bins (a) (c) (b) (d) Fig. 10 (Color online) Perfor...

    work page 2009

  5. [5]

    D. J. Bernstein and T. Lange, Post-Quantum Cryptography, Nature 549, 188 (2017)

    work page 2017

  6. [6]

    Kabashima, T

    Y. Kabashima, T. Murayama, and D. Saad, Cryptographical Properties of Ising Spin Systems, Phys. Rev. Lett. 84, 2030 (2000)

    work page 2030

  7. [7]

    Buhrman, R

    H. Buhrman, R. Cleve, J. W atrous, and R. de W olf, Quantum Fingerprinting , Phys. Rev. Lett. 87, 167902 (2001)

    work page 2001

  8. [8]

    Gottesman and I

    D. Gottesman and I. L. Chuang, Quantum Digital Signatures , e-print qunt-ph/0105032

    work page arXiv

  9. [9]

    Curty, D

    M. Curty, D. J. Santos, Quantum Authentication of Classic al Messages, Phys. Rev. A 64, 062309 (2001)

    work page 2001

  10. [10]

    Kawachi, T

    A. Kawachi, T. Koshiba, H. Nishimura, and T. Yamakami, Computational Indistin- guishability Between Quantum States and Its Cryptographic Application, Lect. Notes on Computer Science 3494, 268 (2005)

    work page 2005

  11. [11]

    Andersson, M

    E. Andersson, M. Curty, and I. Jex, Experimentally Realizable Quantum Comparison of Coherent States and its Applications , Phys. Rev. A 74, 022304 (2006); V. Dunjko, P. W allden, and E. Andersson,Quantum Digital Signatures with Quantum-key-distributio n Components, Phys. Rev. Lett. 112, 040502 (2014)

    work page 2006

  12. [12]

    G. M. Nikolopoulos, Applications of Single-qubit Rotations in Quantum Public- key Cryptography, Phys. Rev. A 77, 032348 (2008); G. M. Nikolopoulos and L. M. Ioannou, Deterministic Quantum-public-key encryption: Forward Se arch Attack and Randomiza- tion, Phys. Rev. A 79, 042327 (2008); U. Seyfarth, G.M. Nikolopoulos, and G. Albe r, Symmetries and security...

    work page 2008

  13. [13]

    S. A. Goorden, M. Horstmann, A. P. Mosk, B. Skor´ic, and P. W. H. Pinkse, Quantum- secure Authentication of a Physical Unclonable Key , Optica 1, 421 (2014)

    work page 2014

  14. [14]

    G. M. Nikolopoulos and E.Diamanti, Continuous-variable Quantum Authentication of Physical Unclonable Keys , Sci. Rep. 7, 46047 (2017); G. M. Nikolopoulos, Continuous- variable Quantum Authentication of Physical Unclonable Ke ys: Security Against an Emulation Attack , Phys. Rev. A 97, 012324 (2018). 26 Georgios M. Nikolopoulos

    work page 2017

  15. [15]

    R. Uppu, T. A. W. W olterink, S. A. Goorden, B. Chen, B. Skor ´ic, A. P. Mosk, P. W. H. Pinkse, Asymmetric Cryptography with Physical Unclonable Keys , arXiv: 1802.07573

    work page arXiv

  16. [16]

    W u and L

    C. W u and L. Yang, Bit-oriented quantum public-key encryption based on quant um perfect encryption, Quantum Inf. Process. 15, 3285 (2016)

    work page 2016

  17. [17]

    Chen, et al

    F.-L. Chen, et al. , Public-key quantum digital signature scheme with one-time pad private-key, Quantum Inf. Process. 17, 10 (2018)

    work page 2018

  18. [18]

    Vlachou, et al

    C. Vlachou, et al. , Quantum walk public-key cryptographic system , Int. J. Quantum Inf. 13 1550050 (2015)

    work page 2015

  19. [19]

    L. M. Ioannou and M. Mosca, Public-key cryptography based on bounded quantum ref- erence frames, Theor. Comput. Science 560, 33 (2014)

    work page 2014

  20. [20]

    Fujita, Quantum McEliece public-key cryptosystem , Quant

    H. Fujita, Quantum McEliece public-key cryptosystem , Quant. Inf. Comput. 12 181 (2012)

    work page 2012

  21. [21]

    Diamanti, H.-K

    E. Diamanti, H.-K. Lo, B. Qi, and Z. Yuan, Practical Challenges in Quantum Key Distribution, npj Quantum Inf. 2, 16025 (2016)

    work page 2016

  22. [22]

    Aaronson and A

    S. Aaronson and A. Arkhipov, The Computational Complexity of Linear Optics , Theory of Computing 9 143 (2013)

    work page 2013

  23. [23]

    B. T. Gard, K. R. Motes, J. P. Olson, P. P. Rohde, and J. P. Do wling, An Introduction to Boson Sampling , From Atomic to Mesoscale: The Role of Quantum Coherence in Systems of Various Complexities (W orld Scientific Publishi ng Co, 2015), Chap. 8

    work page 2015

  24. [24]

    A. P. Lund, M. J. Bremner and T. C. Ralph, Quantum Sampling Problems, BosonSam- pling and Quantum Supremacy , npj Quantum Inf. 3, 15 (2017)

    work page 2017

  25. [25]

    Tillmann, B

    M. Tillmann, B. Daki´ c, R. Heilmann, S. Nolte, A. Szameit, and P. W alther,Experimental Boson Sampling , Nature Photonics 7, 540 (2013)

    work page 2013

  26. [26]

    M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White, Photonic Boson Sampling in a Tunable Circuit , Science 339, 794 (2013)

    work page 2013

  27. [27]

    Spring, B

    B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthamme r, X.-M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Ga tes, B. J. Smith, P. G.R. Smith, I. A. W almsley Boson sampling on a photonic chip , Science 339, 798 (2013)

    work page 2013

  28. [28]

    Crespi, R

    A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galva o, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni and F. Sciarrino, Integrated Multimode Interferometers with Arbitrary Designs for Photonic Boson Sampling , Nature Photonics 7, 545 (2013)

    work page 2013

  29. [29]

    Spagnolo, C

    N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Cre spi, F. Flamini, S. Giaco- mini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. G alvao, F. Sciarrino, Efficient Experimental Validation of Photonic Boson Samplin g Against the Uniform Distribution, Nature Photonics 8, 615 (2014)

    work page 2014

  30. [30]

    Carolan, J

    J. Carolan, J. D. A. Meinecke, P. J. Shadbolt, N. J. Russel l, N. Ismail, K. W¨ orhoff, T. Rudolph, M. G. Thompson, J. L. OBrien, J. C. F. Matthews, an d A. Laing On the Experimental Verification of Quantum Complexity in Linear O ptics, Nature Photonics 8, 621 (2014)

    work page 2014

  31. [31]

    W ang et al

    H. W ang et al. , High-efficiency Multiphoton Boson Sampling , Nat. Photon. 11 361 (2017)

    work page 2017

  32. [32]

    The Classical Complexity of Boson Sampling

    A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Bir chall, A. Montanaro, and A. Laing, Classical Boson Sampling Algorithms with Superior Perform ance to Near-term Experiments, Nat. Phys. 13, 1153 (2017); P. Clifford and R. Clifford, The Classical Complexity of Boson Sampling , arXiv:1706.01260

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  33. [33]

    J. W u, Y. Liu, B. Zhang, X. Jin, Y. W ang, H. W ang, X. Yang, A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer , arXiv:1606.05836

    work page internal anchor Pith review Pith/arXiv arXiv

  34. [34]

    Certification of Boson Sampling Devices with Coarse-Grained Measurements

    S.-T. W ang and L.-M. Duan, Certification of Boson Sampling Devices with Coarse- Grained Measurements, arXiv:1601.02627

    work page internal anchor Pith review Pith/arXiv arXiv

  35. [35]

    V. S. Shchesnovich, Universality of Generalized Bunching and Efficient Assessme nt of Boson Sampling , Phys. Rev. Lett. 116, 123601 (2016)

    work page 2016

  36. [36]

    Agresti, N

    I. Agresti, N. Viggianiello, F. Flamini, N. Spagnolo, A. Crespi, R. Osellame, N. Wiebe, F. Sciarrino, Pattern recognition techniques for Boson Sampling validat ion, Phys. Rev. X 9, 011013 (2019)

    work page 2019

  37. [37]

    G. M. Nikolopoulos and T. Brougham, Decision and Function Problems Based on Boson Sampling, Phys. Rev. A 94, 012315 (2016)

    work page 2016

  38. [38]

    D. C. Montgomery and G. C. Runger, Applied statistics and probability of engineers (John Wiley & Sons, 2005). Cryptographic One-way Function Based on Boson Sampling 27

    work page 2005

  39. [39]

    Baron, Probability and statistics for computer scien tists, (CRC Press, 2014)

    M. Baron, Probability and statistics for computer scien tists, (CRC Press, 2014)

    work page 2014

  40. [40]

    F. J. MacWilliams and N. J. A. Slone, The Theory of Error-Correcting Codes (North- Holland, Amsterdam, 1997)

    work page 1997

  41. [41]

    Boyer, G

    M. Boyer, G. Brassard, P. Høyer, and A. Tapp, Tight Bounds on Quantum Searching , Fortschr. Phys. 46, 493 (1998)

    work page 1998

  42. [42]

    D. R. Stinson and M. B. Paterson, Cryptography : theory and practice (Boca Raton : CRC Press, Taylor & Francis Group, 2018)

    work page 2018

  43. [43]

    K. M. Martin, Everyday Cryptography: Fundamental Principles and Applic ations (Ox- ford University Press, New York, 2012)

    work page 2012