research-article

Free access

Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs

Authors:

Emanuele ViolaAuthors Info & Claims

Journal of the ACM (JACM), Volume 62, Issue 6

Article No.: 46, Pages 1 - 29

https://doi.org/10.1145/2792978

Published: 10 December 2015 Publication History

Abstract

This article takes a new step towards closing the gap between pseudorandom functions (PRF) and their popular, bounded-input-length counterparts. This gap is both quantitative, because these counterparts are more efficient than PRF in various ways, and methodological, because these counterparts usually fit in the substitution-permutation network paradigm (SPN), which has not been used to construct PRF.

We give several candidate PRF F_i that are inspired by the SPN paradigm. Most of our candidates are more efficient than previous ones. Our main candidates are as follows.

—F₁ : {0,1}ⁿ → {0,1}ⁿ is an SPN whose S-box is a random function on b bits given as part of the seed. We prove that F₁ resists attacks that run in time ≤ 2^ϵb.

—F₂ : {0,1}ⁿ → {0,1}ⁿ is an SPN where the S-box is (patched) field inversion, a common choice in practical constructions. We show that F₂ is computable with boolean circuits of size n ⋅ log^O(1) n and that it has exponential security 2^Ω(n) against linear and differential cryptanalysis.

—F₃ : {0,1}ⁿ → {0,1} is a nonstandard variant on the SPN paradigm, where “states” grow in length. We show that F₃ is computable with TC⁰ circuits of size n^{1 + ϵ}, for any ϵ > 0, and that it is almost 3-wise independent.

—F₄ : {0,1}ⁿ → {0,1} uses an extreme setting of the SPN parameters (one round, one S-box, no diffusion matrix). The S-box is again (patched) field inversion. We show that F₄ is computable by circuits of size n ⋅ log^O(1) n and that it fools all parity tests on ≤2^0.9n outputs.

Assuming the security of our candidates, our work narrows the gap between the Natural Proofs barrier and existing lower bounds in three models: circuits, TC⁰ circuits, and Turing machines.

References

[1]

Scott Aaronson and Avi Wigderson. 2009. Algebrization: A new barrier in complexity theory. ACM Trans. Comput. Theory 1, 1 (2009) Article 2. DOI=http://dx.doi.org/10.1145/1490270.1490272

Digital Library

[2]

Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, and Alon Rosen. 2014. Candidate weak pseudorandom functions in AC0 &circ; MOD2. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science (ITCS'14). ACM, New York, NY, 251--260. DOI=http://dx.doi.org/10.1145/2554797.2554821

Digital Library

[3]

Eric Allender and Michal Koucký. 2010. Amplifying lower bounds by means of self-reducibility. J. ACM 57, 3, (2010) Article 14. DOI=http://dx.doi.org/10.1145/1706591.1706594

Digital Library

[4]

Noga Alon, Oded Goldreich, Johan Håastad, and René Peralta. 1992. Simple constructions of almost k-wise independent random variables. Random Struct. Algorith. 3, 3 (1992), 289--304. DOI=http://dx.doi.org/10.1002/rsa.3240030308

Digital Library

[5]

Noga Alon, Oded Goldreich, and Yishay Mansour. 2003. Almost k-wise independence versus k-wise independence. Inf. Process. Lett. 88, 3 (2003), 107--110. DOI=http://dx.doi.org/10.1016/S0020-0190(03)00359-4

Digital Library

[6]

Theodore Baker, John Gill, and Robert Solovay. 1975. Relativizations of the P=?NP question. SIAM J. Comput. 4, 4 (1975), 431--442. DOI=http://dx.doi.org/10.1137/0204037

Digital Library

[7]

Abhishek Banerjee and Chris Peikert. 2014. New and improved key-homomorphic pseudorandom functions. In Proceedings of the 34th Annual Cryptology Conference (CRYPTO), Part I. 353--370. DOI=http://dx.doi.org/10.1007/978-3-662-44371-2_20

[8]

Abhishek Banerjee, Chris Peikert, and Alon Rosen. 2012. Pseudorandom functions and lattices. In Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). 719--737. DOI=http://dx.doi.org/10.1007/978-3-642-29011-4_42

Digital Library

[9]

Louay M. J. Bazzi. 2009. Polylogarithmic independence can fool DNF formulas. SIAM J. Comput. 38, 6 (2009), 2220--2272. DOI=http://dx.doi.org/10.1137/070691954

Digital Library

[10]

Mihir Bellare, Joe Kilian, and Phillip Rogaway. 2000. The security of the cipher block chaining message authentication code. J. Comput. Syst. Sci. 61, 3 (Dec. 2000), 362--399. DOI=http://dx.doi.org/10.1006/jcss.1999.1694

Digital Library

[11]

E. Biham and A. Shamir. 1991. Differential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4, 1 (1991), 3--72. DOI=http://10.1007/BF00630563

Digital Library

[12]

Mark Braverman. 2009. Poly-logarithmic independence fools AC⁰ circuits. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC'09). IEEE Computer Society, 3--8. http://dx.doi.org/10.1109/CCC.2009.35

Digital Library

[13]

Alex Brodsky and Shlomo Hoory. 2008. Simple permutations mix even better. Random Struct. Algorith. 32, 3 (May 2008), 274--289. DOI=http://dx.doi.org/10.1002/rsa.v32:3

Digital Library

[14]

Hong-Su Cho, Soo Hak Sung, Daesung Kwon, Jung-Keun Lee, Jung Hwan Song, and Jongin Lim. 2004. New method for bounding the maximum differential probability for SPNs and ARIA. In Proceedings of the 7th International Conference on Information Security and Cryptology (ICISC'04), Choon-sik Park and Seongtaek Chee (Eds.), Springer-Verlag, Berlin, Heidelberg, 21--32. DOI=http://dx.doi.org/10.1007/11496618_4

Digital Library

[15]

Joan Daemen. 1995. Cipher and hash function design strategies based on linear and differential cryptanalysis. Ph.D. Dissertation, K.U. Leuven, Leuven, Flanders, Belgium.

[16]

Joan Daemen and Vincent Rijmen. 2002. The Design of Rijndael: AES - The Advanced Encryption Standard. Springer Verlag, New York, Inc., Secaucus, NJ.

Digital Library

[17]

Shimon Even and Yishay Mansour. 1997. A construction of a cipher from a single pseudorandom permutation. J. Cryptol. 10, 3 (June 1997), 151--162. DOI=http://dx.doi.org/10.1007/s001459900025

Digital Library

[18]

Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, and Emanuele Viola. 2013. Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. IEEE Trans. Inform. Theory 59, 10 (2013), 6611--6627. DOI=http://dx.doi.org/10.1109/TIT.2013.2270275

Digital Library

[19]

Shuhong Gao, Joachim von zur Gathen, Daniel Panario, and Victor Shoup. 2000. Algorithms for exponentiation in finite fields. J. Symb. Comput. 29, 6 (June 2000), 879--889. DOI=http://dx.doi.org/10.1006/jsco.1999.0309

Digital Library

[20]

Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, and Søren S. Thomsen. 2011. Grøstl: A SHA-3 candidate. http://www.groestl.info.

[21]

Craig Gentry and Zulfikar Ramzan. 2004. Eliminating random permutation oracles in the Even-Mansour Cipher. In Proceedings of the 10th International Conference on the Theory and Application of Cryptology and Information security (ASIACRYPT). 32--47. DOI=http://dx.doi.org/10.1007/978-3-540-30539-2_3

[22]

A. Gerasoulis. 1988. A fast algorithm for the multiplication of generalized Hilbert matrices with vectors. Math. Comp. 50 (1988), 179--188. DOI=http://dx.doi.org/10.1090/S0025-5718-1988-0917825-9

[23]

Oded Goldreich. 2001. Foundations of Cryptography: Volume 1. Cambridge University Press, New York, NY.

Digital Library

[24]

Oded Goldreich, Shafi Goldwasser, and Silvio Micali. 1986. How to construct random functions. J. ACM 33, 4 (August 1986), 792--807. DOI=http://dx.doi.org/10.1145/6490.6503

Digital Library

[25]

Oded Goldreich and Leonid Levin. 1989. A hard-core predicate for all one-way functions. In Proceedings of the 21st annual ACM Symposium on Theory of Computing (STOC'89), D. S. Johnson (Ed.), ACM, New York, NY, 25--32. DOI=http://dx.doi.org/10.1145/73007.73010

Digital Library

[26]

W. T. Gowers. 1996. An almost m-wise independent random permutation of the cube. Combinatorics, Probab. Comput. 5, 2 (1996), 119--130. DOI=http://dx.doi.org/10.1017/S0963548300001917

[27]

Iftach Haitner, Omer Reingold, and Salil P. Vadhan. 2010. Efficiency improvements in constructing pseudorandom generators from one-way functions. In Proceedings of the ACM Symposium on Theory of Computing (STOC'10). ACM, New York, NY, 437--446. DOI=http://dx.doi.org/10.1145/1806689.1806750

Digital Library

[28]

Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. 1999. A pseudorandom generator from any one-way function. SIAM J. Comput. 28, 4 (March 1999), 1364--1396. DOI=http://dx.doi.org/10.1137/S0097539793244708

Digital Library

[29]

Alexander Healy and Emanuele Viola. 2006. Constant-depth circuits for arithmetic in finite fields of characteristic two. In Proceedings of the 23rd Annual Conference on Theoretical Aspects of Computer Science (STACS'06). Bruno Durand and Wolfgang Thomas (Eds.), Springer-Verlag, Berlin, Heidelberg, 672--683. DOI=http://dx.doi.org/10.1007/11672142_55

Digital Library

[30]

William Hesse, Eric Allender, and David A. Mix Barrington. 2002. Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. 65, 4 (December 2002), 695--716. DOI=http://dx.doi.org/10.1016/S0022-0000(02)00025-9

Digital Library

[31]

Shlomo Hoory, Avner Magen, Steven Myers, and Charles Rackoff. 2005. Simple permutations mix well. Theor. Comput. Sci. 348, 2 (December 2005), 251--261. DOI=http://dx.doi.org/10.1016/j.tcs.2005.09.016

Digital Library

[32]

T. Jakobsen and L. R. Knudsen. 2001. Attacks on block ciphers of low algebraic degree. J. Cryptol. 14, 3 (January 2001), 197--210. DOI=http://dx.doi.org/10.1007/s00145-001-0003-x

Digital Library

[33]

Ju-Sung Kang, Seokhie Hong, Sangjin Lee, Okyeon Yi, Choonsik Park, and Jongin Lim. 2001. Practical and provable security against differential and linear cryptanalysis for substitution-permutation networks. ETRI J. 23, 4 (Dec. 2001), 158--167. DOI=http://dx.doi.org/10.4218/etrij.01.0101.0402

[34]

Liam Keliher, Henk Meijer, and Stafford E. Tavares. 2001. New method for upper bounding the maximum average linear hull probability for SPNs. In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology (EUROCRYPT'01). Birgit Pfitzmann (Ed.), Springer-Verlag, London, 420--436.

Digital Library

[35]

Lars R. Knudsen. 1994. Truncated and higher order differentials. In Proceedings of the 2nd Internatinal Workshop on Fast Software Encryption (FSE). 196--211. DOI=http://dx.doi.org/10.1007/3-540-60590-8_16

[36]

Swastik Kopparty. 2011. On the complexity of powering in finite fields. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC'11). ACM, New York, NY, 489--498. DOI=http://dx.doi.org/10.1145/1993636.1993702

Digital Library

[37]

Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press, New York, NY.

Digital Library

[38]

Michael Luby and Charles Rackoff. 1988. How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17, 2 (April 1988), 373--386. DOI=http://dx.doi.org/10.1137/0217022

Digital Library

[39]

M. Matsui. 1994. Linear cryptanalysis method for DES cipher. In Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology (EUROCRYPT'93), Tor Helleseth (Ed.). Springer-Verlag New York, Inc., Secaucus, NJ, 386--397.

Digital Library

[40]

Eric Miles and Emanuele Viola. 2012. Substitution-permutation networks, pseudorandom functions, and natural proofs. In Proceedings of the 32nd Annual Cryptology Conference (CRYPTO). 68--85. DOI=http://dx.doi.org/10.1007/978-3-642-32009-5_5

Digital Library

[41]

Joseph Naor and Moni Naor. 1993. Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput. 22, 4 (August 1993), 838--856. DOI=http://dx.doi.org/10.1137/0222053

Digital Library

[42]

Moni Naor and Omer Reingold. 1999. On the construction of pseudorandom permutations: Luby-Rackoff revisited. J. Cryptol. 12, 1 (January 1999), 29--66. DOI=http://dx.doi.org/10.1007/PL00003817

Digital Library

[43]

Moni Naor and Omer Reingold. 2004. Number-theoretic constructions of efficient pseudo-random functions. J. ACM 51, 2 (March 2004), 231--262. DOI=http://dx.doi.org/10.1145/972639.972643

Digital Library

[44]

Moni Naor, Omer Reingold, and Alon Rosen. 2002. Pseudorandom functions and factoring. SIAM J. Comput. 31, 5 (May 2002), 1383--1404. DOI=http://dx.doi.org/10.1137/S0097539701389257

Digital Library

[45]

Kaisa Nyberg. 1993. Differentially uniform mappings for cryptography. In Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology (EUROCRYPT'93). Tor Helleseth (Ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 55--64.

Digital Library

[46]

Josef Pieprzyk. 1991. On bent permutations. In Proceedings of the International Conference on Finite Fields, Coding Theory, and Advances in Communications and Computing. Lecture Notes in Pure and Applied Math, Vol. 141. Marcel Dekker, Inc.

[47]

Zulfikar Ramzan and Leonid Reyzin. 2000. On the round security of symmetric-key cryptographic primitives. In Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO'00), Mihir Bellare (Ed.)., Springer-Verlag, London, 376--393.

Digital Library

[48]

Alexander Razborov and Steven Rudich. 1997. Natural proofs. J. Comput. Syst. Sci. 55, 1 (August 1997), 24--35. DOI=http://dx.doi.org/10.1006/jcss.1997.1494

Digital Library

[49]

Alexander A. Razborov. 2009. A simple proof of Bazzi's theorem. ACM Trans. Comput. Theory 1, 1 (February 2009). Article 3. DOI=http://dx.doi.org/10.1145/1490270.1490273

Digital Library

[50]

Ron M. Roth and Gadiel Seroussi. 1985. On generator matrices of MDS codes. IEEE Trans. Inf. Theor. 31, 6 (November 1985), 826--830. DOI=http://dx.doi.org/10.1109/TIT.1985.1057113

Digital Library

[51]

Claude Shannon. 1949. Communication theory of secrecy systems. Bell Syst. Tech. J. 28, 4 (1949), 656--715. DOI=http://dx.doi.org/10.1002/j.1538-7305.1949.tb00928.x

[52]

Salil P. Vadhan and Colin Jia Zheng. 2012. Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC'12). ACM, New York, NY, 817--836. DOI=http://dx.doi.org/10.1145/2213977.2214051

Digital Library

[53]

Joachim von zur Gathen and Jürgen Gerhard. 2003. Modern Computer Algebra (2nd ed.). Cambridge University Press, New York, NY.

Digital Library

[54]

Ryan Williams. 2011. Non-uniform ACC circuit lower bounds. In Proceedings of the IEEE Conference on Computational Complexity (CCC). 115--125. DOI=http://dx.doi.org/10.1109/CCC.2011.36

Digital Library

[55]

Hongjun Wu. 2011. The hash function JH. http://www3.ntu.edu.sg/home/wuhj/research/jh/index.html.

Cited By

Bhaumik RNandi MPaul SSaha A(2024)Indifferentiability of 3-Round Confusion-Diffusion NetworksSecurity and Cryptography for Networks10.1007/978-3-031-71073-5_7(140-161)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71073-5_7
Boubaker SAlsubaei FSaid YAhmed H(2023)Lightweight Cryptography for Connected Vehicles Communication Security on Edge DevicesElectronics10.3390/electronics1219409012:19(4090)Online publication date: 29-Sep-2023
https://doi.org/10.3390/electronics12194090
Ghosal RIshai YKorb AKushilevitz ELou PSahai ASaha BServedio R(2023)Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured HardnessProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585119(1243-1256)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585119
Show More Cited By

Index Terms

Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs
1. Theory of computation
  1. Computational complexity and cryptography
    1. Cryptographic primitives

Recommendations

Substitution-permutation networks resistant to differential and linear cryptanalysis

In this paper we examine a class of product ciphers referred to as substitution-permutation networks. We investigate the resistance of these cryptographic networks to two important attacks: differential cryptanalysis and linear cryptanalysis. In ...
Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs
Proceedings of the 32nd Annual Cryptology Conference on Advances in Cryptology --- CRYPTO 2012 - Volume 7417

This paper takes a new step towards closing the troubling gap between pseudorandom functions PRF and their popular, bounded-input-length counterparts. This gap is both quantitative, because these counterparts are more efficient than PRF in various ways, ...
Linear cryptanalysis of substitution-permutation networks

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 62, Issue 6

December 2015

304 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2856350

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 December 2015

Accepted: 01 September 2015

Revised: 01 August 2015

Received: 01 September 2012

Published in JACM Volume 62, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
916
Total Downloads

Downloads (Last 12 months)215
Downloads (Last 6 weeks)74

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bhaumik RNandi MPaul SSaha A(2024)Indifferentiability of 3-Round Confusion-Diffusion NetworksSecurity and Cryptography for Networks10.1007/978-3-031-71073-5_7(140-161)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71073-5_7
Boubaker SAlsubaei FSaid YAhmed H(2023)Lightweight Cryptography for Connected Vehicles Communication Security on Edge DevicesElectronics10.3390/electronics1219409012:19(4090)Online publication date: 29-Sep-2023
https://doi.org/10.3390/electronics12194090
Ghosal RIshai YKorb AKushilevitz ELou PSahai ASaha BServedio R(2023)Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured HardnessProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585119(1243-1256)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585119
Khan SLee WKarmakar AMera JMajeed AHwang S(2023)Area–Time Efficient Implementation of NIST Lightweight Hash Functions Targeting IoT ApplicationsIEEE Internet of Things Journal10.1109/JIOT.2022.322951610:9(8083-8095)Online publication date: 1-May-2023
https://doi.org/10.1109/JIOT.2022.3229516
Chen LLi JYang T(2022)Extremely efficient constructions of hash functions, with applications to hardness magnification and PRFsProceedings of the 37th Computational Complexity Conference10.4230/LIPIcs.CCC.2022.23(1-37)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2022.23
Fan ZLi JYang TLeonardi SGupta A(2022)The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexityProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520010(962-975)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520010
Nguyen CTran NNguyen L(2022)FLC: A New Secure and Efficient SPN-Based Scheme for Block Ciphers2022 9th NAFOSTED Conference on Information and Computer Science (NICS)10.1109/NICS56915.2022.10013379(75-80)Online publication date: 31-Oct-2022
https://doi.org/10.1109/NICS56915.2022.10013379
Nguyen CNguyen ANguyen LTrieu PTran L(2022)Analysis of a New Practical SPN-Based Scheme in the Luby-Rackoff ModelFuture Data and Security Engineering. Big Data, Security and Privacy, Smart City and Industry 4.0 Applications10.1007/978-981-19-8069-5_14(210-224)Online publication date: 20-Nov-2022
https://doi.org/10.1007/978-981-19-8069-5_14
de Castro LHazay CIshai YVaikuntanathan VVenkitasubramaniam M(2022)Asymptotically Quasi-Optimal CryptographyAdvances in Cryptology – EUROCRYPT 202210.1007/978-3-031-06944-4_11(303-334)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-06944-4_11
Dinur IGoldfeder SHalevi TIshai YKelkar MSharma VZaverucha G(2021)MPC-Friendly Symmetric Cryptography from Alternating Moduli: Candidates, Protocols, and ApplicationsAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84259-8_18(517-547)Online publication date: 16-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-84259-8_18
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents