Polar sampler: A novel Bernoulli sampler using polar codes with application to integer Gaussian sampling
Tóm tắt
Cryptographic constructions based on hard lattice problems have emerged as a front runner for the standardization of post-quantum public-key cryptography. As the standardization process takes place, optimizing specific parts of proposed schemes, e.g., Bernoulli sampling and integer Gaussian sampling, becomes a worthwhile endeavor. In this work, we propose a novel Bernoulli sampler based on polar codes, dubbed “polar sampler”. The polar sampler is information theoretically optimum in the sense that the number of uniformly random bits it consumes approaches the entropy bound asymptotically. It also features quasi-linear complexity and constant-time implementation. An integer Gaussian sampler is developed using multilevel polar samplers. Our algorithm becomes effective when sufficiently many samples are required at each query to the sampler. Security analysis is given based on Kullback–Leibler divergence and Rényi divergence. Experimental and asymptotic comparisons between our integer Gaussian sampler and state-of-the-art samplers verify its efficiency in terms of entropy consumption, running time and memory cost. We envisage that the proposed Bernoulli sampler can find other applications in cryptography in addition to Gaussian sampling.
Tài liệu tham khảo
Alamdar-Yazdi A., Kschischang F.R.: A simplified successive-cancellation decoder for polar codes. IEEE Commun. Lett. 15(12), 1378–1380 (2011).
Andrysco M., Nötzli A., Brown F., Jhala R., Stefan D.: Towards verified, constant-time floating point operations. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 1369–1382. CCS ’18. Association for Computing Machinery, New York (2018).
Arıkan E.: Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Trans. Inf. Theory 55(7), 3051–3073 (2009).
Arıkan E.: Source polarization. In: 2010 IEEE International Symposium on Information Theory, pp. 899–903 (2010).
Bai S., Lepoint T., Roux-Langlois A., Sakzad A., Stehlé D., Steinfeld R.: Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance. J. Cryptol. 31(2), 610–640 (2018).
Barthe G., Belaïd S., Espitau T., Fouque P.A., Rossi M., Tibouchi M.: Galactics: Gaussian sampling for lattice-based constant-time implementation of cryptographic signatures, revisited. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pp. 2147–2164. CCS ’19. Association for Computing Machinery (2019).
Box G.E.P., Muller M.E.: A note on the generation of random normal deviates. Ann. Math. Stat. 29(2), 610–611 (1958).
Bruinderink L.G., Hülsing A., Lange T., Yarom Y.: Flush, Gauss, and reload—a cache attack on the BLISS lattice-based signature scheme. In: International Conference on Cryptographic Hardware and Embedded Systems, pp. 323–345. Springer (2016)
Cover T.M., Thomas J.A.: Elements of Information Theory. Wiley, Hoboken (2012).
Devroye L.: Sample-based non-uniform random variate generation. In: Proceedings of the 18th Conference on Winter Simulation, pp. 260–265. ACM (1986)
Ducas L., Durmus A., Lepoint T., Lyubashevsky V.: Lattice signatures and bimodal Gaussians. In: Annual Cryptology Conference, pp. 40–56. Springer (2013)
Dwarakanath N.C., Galbraith S.D.: Sampling from discret Gaussians for lattice-based cryptography on a constrained device. Appl. Algebra Eng. Commun. Comput. 25(3), 159–180 (2014).
Espitau T., Fouque P.A., Gérard B., Tibouchi M.: Side-channel attacks on BLISS lattice-based signatures: exploiting branch tracing against strongSwan and electromagnetic emanations in microcontrollers. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1857–1874. CCS ’17, Association for Computing Machinery (2017).
Gentry C., Peikert C., Vaikuntanathan V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 197–206. ACM (2008).
Honda J., Yamamoto H.: Polar coding without alphabet extension for asymmetric models. IEEE Trans. Inf. Theory 59(12), 7829–7838 (2013).
Howe J., Khalid A., Rafferty C., Regazzoni F., O’Neill M.: On practical discret Gaussian samplers for lattice-based cryptography. IEEE Trans. Comput. 67(3), 322–334 (2016).
Howe J., Prest T., Ricosset T., Rossi M.: Isochronous Gaussian sampling: from inception to implementation. In: Ding J., Tillich J.P. (eds.) Post-Quantum Cryptography, pp. 53–71. Springer, Cham (2020).
Hülsing A., Lange T., Smeets K.: Rounded Gaussians: fast and secure constant-time sampling for lattice-based crypto. In: Public-Key Cryptography—PKC 2018—21st IACR International Conference on Practice and Theory of Public-Key Cryptography. Proceedings, pp. 728–757. Springer (2018).
Karmakar A., Roy S.S., Reparaz O., Vercauteren F., Verbauwhede I.: Constant-time discret Gaussian sampling. IEEE Trans. Comput. 67(11), 1561–1571 (2018).
Knuth D.: The complexity of nonuniform random number generation. In: Traub J.F. (ed.) Algorithm and Complexity, New Directions and Results, pp. 357–428. Academic Press, Cambridge (1976).
Leroux C., Raymond A.J., Sarkis G., Gross W.J.: A semi-parallel successive-cancellation decoder for polar codes. IEEE Trans. Signal Process. 61(2), 289–299 (2013).
Lyubashevsky V., Peikert C., Regev O.: On ideal lattices and learning with errors over rings. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 1–23. Springer (2010).
Marsaglia G., Tsang W.W., et al.: The Ziggurat method for generating random variables. J. Stat. Softw. 5(8), 1–7 (2000).
Micciancio D., Peikert C.: Hardness of SIS and LWE with small parameters. In: Canetti R., Garay J.A. (eds.) Advances in Cryptology-CRYPTO 2013, pp. 21–39. Springer, Berlin (2013).
Micciancio D., Regev O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007).
Micciancio D., Walter M.: Gaussian sampling over the integers: efficient, generic, constant-time. In: Annual International Cryptology Conference, pp. 455–485. Springer (2017).
Mondelli M., Hashemi S.A., Cioffi J.M., Goldsmith A.: Sublinear latency for simplified successive cancellation decoding of polar codes. IEEE Trans. Wirel. Commun. 20(1), 18–27 (2021).
Peikert C.: An efficient and parallel Gaussian sampler for lattices. In: Annual Cryptology Conference, pp. 80–97. Springer (2010).
Pessl P., Bruinderink L.G., Yarom Y.: To BLISS-B or not to be: attacking strong Swan’s implementation of post-quantum signatures. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, p. 1843–1855. CCS ’17, Association for Computing Machinery (2017).
Pöppelmann T., Ducas L., Güneysu T.: Enhanced lattice-based signatures on reconfigurable hardware. In: International Workshop on Cryptographic Hardware and Embedded Systems, pp. 353–370. Springer (2014).
Prest T.: Gaussian sampling in lattice-based cryptography. Ph.D. thesis, École Normale Supérieure (2015).
Prest T.: Sharper bounds in lattice-based cryptography using the Rényi divergence. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 347–374. Springer (2017).
Prest T., Ricosset T., Rossi M.: Simple, fast and constant-time Gaussian sampling over the integers for falcon. In: Tech. rep., Second PQC Standardization Conference. https://csrc.nist.gov/Presentations/2019/simple-fast-and-constant-time-gaussian (2019).
Regev O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, pp. 84–93. STOC ’05, ACM (2005).
Saarinen M.J.O.: Arithmetic coding and blinding countermeasures for lattice signatures. J. Cryptogr. Eng. 8(1), 71–84 (2018).
Tal I., Vardy A.: How to construct polar codes. IEEE Trans. Inf. Theory 59(10), 6562–6582 (2013).
Tal I., Vardy A.: List decoding of polar codes. IEEE Trans. Inf. Theory 61(5), 2213–2226 (2015).
Wang H.P., Duursma I.M.: Log-logarithmic time pruned polar coding. IEEE Trans. Inf. Theory 67(3), 1509–1521 (2021).
Zhao R.K., Steinfeld R., Sakzad A.: Facct: fast, compact, and constant-time discret Gaussian sampler over integers. IEEE Trans. Comput. 69(1), 126–137 (2019).