{"entities":{"Q1100894":{"pageid":1111646,"ns":120,"title":"Item:Q1100894","lastrevid":69641502,"modified":"2026-04-13T08:24:02Z","type":"item","id":"Q1100894","labels":{"en":{"language":"en","value":"One way functions and pseudorandom generators"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4045145"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100894$EA6D085E-C998-4B88-A7DA-60EF95091FDB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d51ba293d95c9b77cf7409bc616c949ca4358083","datavalue":{"value":{"text":"One way functions and pseudorandom generators","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1100894$4725A284-6316-4F88-9C37-B22BF0121389","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"11b248f9bf1c0a2e16e7001d568b05c4309290b4","datavalue":{"value":"0641.68061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100894$85D7F6D0-D5F6-4B1C-A511-7E19333C0E75","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"16acd3c2172e021a4e4d6f62bca7243cb1cce0a5","datavalue":{"value":"10.1007/BF02579323","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100894$2CB95090-0569-459E-818D-FA186FFE667E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100894$B83AC90B-8AD8-4545-9092-1BF6D9676F3A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1100894$0B0E913B-C164-45F8-8738-6810F65F0E83","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e8e8aa6b32c801e92d521de3aeabe03f0cdc6c28","datavalue":{"value":"Pseudorandom generators transform in polynomial time a short random ``seed'' into a long ``pseudorandom'' string. This string cannot be random in the classical sense of \\textit{A. N. Kolmogorov} [Probl. Peredachi Inf. 1, No.1, 3-11 (1965; Zbl 0271.94018)], but testing that requires an unrealistic amount of time (say, exhaustive search for the seed). Such pseudorandom generators were first discovered by \\textit{M. Blum} and \\textit{S. Micali} [SIAM J. Comput. 13, 850-864 (1984; Zbl 0547.68046)] assuming that the function \\((a^ x mod b)\\) is one-way, i.e., easy to compute, but hard to invert on a noticeable fraction of instances. By \\textit{A. C. Yao} [``Theory and application of trapdoor functions'', Proc. 23rd Annu. IEEE Symp. Found. Comput. Sci., 80-91 (1982)] this assumption was generalized to the existence of any one-way permutation. The permutation requirement is sufficient but still very strong. It is unlikely to be proven necessary, unless something crucial, like \\(P=NP\\), is discovered. Below, among other observations, a weaker assumption about one-way functions is proposed, which is not only sufficient, but also necessary for the existence of pseudorandom generators.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100894$6F9C1D62-1625-41C3-AF16-27C3C9E05057","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100894$0F98FD0B-DEDF-4F51-AF86-77A55FF23913","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100894$02C94525-59ED-4699-8E2B-A14A111827BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c6dc32161cfbbc0543faafed5e6c564351d5db2f","datavalue":{"value":"65C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100894$8B4C5141-DD52-4B43-A56E-A17F481D17EE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0ad0f6d8fd3fc74704e41f436d8c5cbc885f2685","datavalue":{"value":"4045145","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100894$0270C136-0B3A-4E7C-8B5F-BF1AB0EF47AA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9751e40fc64b559f097ced67cd2c8f328b9f12c","datavalue":{"value":"one-way function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100894$BB14D56E-BB3E-4A03-84CF-FBC14A5796CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80cf7c741247b42b3496c01a3938e39f37d9f0e4","datavalue":{"value":"one-way permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100894$9AD37E52-C269-46CB-A3BE-411991F6D444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"797ca31b1acf5bf389b0a92a7ae49cb449b952fa","datavalue":{"value":"pseudorandom generators","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100894$C7413801-056D-4806-BB71-FD82E70D80CE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2dfa45ae252af4578203ecdec33c184e104945f2","datavalue":{"value":{"entity-type":"item","numeric-id":638489,"id":"Q638489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100894$DCFE012D-7813-41D7-84B8-98A2EE1328EE","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100894$9F6217D1-EF13-4C99-BA5A-497AF97BBE36","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a581f96e8cabd60b98280dbc93b840cb31eb7421","datavalue":{"value":{"entity-type":"item","numeric-id":3339289,"id":"Q3339289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100894$9B4C20EC-2A29-4D7C-B1FA-DACD9177C0E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abf7100910029c95c58ccfecde6ed402cda7095b","datavalue":{"value":{"entity-type":"item","numeric-id":5671907,"id":"Q5671907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100894$06E4CC13-2BF7-4219-8080-2BCD168C131B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2c5f4a456f9910b4c4f2a1d73e4561be8a5dbc2","datavalue":{"value":{"entity-type":"item","numeric-id":3214803,"id":"Q3214803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100894$37B8305A-32EE-4D04-B85F-530D52C95BC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04533b5e4f54e7a61c4fc1c55a4a47c19e20f43a","datavalue":{"value":{"entity-type":"item","numeric-id":3718151,"id":"Q3718151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100894$489EF0AD-F07F-43B5-AAE2-993BBE9BBD32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef9a9393e2f03a4575fecf9399e9efba5fa39c9e","datavalue":{"value":{"entity-type":"item","numeric-id":4077885,"id":"Q4077885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100894$808E5AE7-6864-4CD2-A0AD-F61C3BA36BCE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d84b377a7eae8c808e349b225719978bca04c78","datavalue":{"value":{"entity-type":"item","numeric-id":4268715,"id":"Q4268715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"679b5e5233f855f33615fa3c01fe8e25875a0886","datavalue":{"value":{"amount":"+0.8885329365730286","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1100894$B9AC83D3-47AD-4107-8C53-7A78E04C6D5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91912791803eab5a9ad6aead8f071a5f689bfd3a","datavalue":{"value":{"entity-type":"item","numeric-id":4277535,"id":"Q4277535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1515ed8bfd872dd92db69ecbd028ae0bd84639ed","datavalue":{"value":{"amount":"+0.8829621076583862","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1100894$D939787F-681D-4975-A210-E2FA4696323F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be4c2900d0698c743a0e2d621fa1cc306538bc73","datavalue":{"value":{"entity-type":"item","numeric-id":5748796,"id":"Q5748796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96c86942831dd5657fcb6fa07feb9735bc723b18","datavalue":{"value":{"amount":"+0.8780230283737183","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1100894$0EFEABD1-EF37-47BA-BC4C-E739E6346156","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3967cfbeacc4a046d825bbb0205b55f46b4d2f26","datavalue":{"value":{"entity-type":"item","numeric-id":2914351,"id":"Q2914351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7b4f07a3f8e55051563ebb61600e137a6925cb6","datavalue":{"value":{"amount":"+0.8745381832122803","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1100894$72C42718-DFCE-495B-8406-F22138EAFD2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95d5527f85ee05521034828c4dc5df9a94832c09","datavalue":{"value":{"entity-type":"item","numeric-id":1822961,"id":"Q1822961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a366b32b997d3f2b339201a0c3786875fe489da8","datavalue":{"value":{"amount":"+0.8512321710586548","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1100894$E9842FE4-2586-41E3-8731-B8F5B635F425","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"One way functions and pseudorandom generators","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/One_way_functions_and_pseudorandom_generators"}}}}}