{"entities":{"Q625101":{"pageid":626948,"ns":120,"title":"Item:Q625101","lastrevid":63286824,"modified":"2026-04-11T11:51:23Z","type":"item","id":"Q625101","labels":{"en":{"language":"en","value":"Cryptography in constant parallel time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5851567"}},"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":"Q625101$AB50129D-AB44-4BAC-A07B-27EEAEF8210F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5d8afc9781d71dd71f6b83d967b2a9b84692b7a3","datavalue":{"value":{"text":"Cryptography in constant parallel time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q625101$93ED2A31-A612-4D71-91F4-895DF5944B26","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e96d3cbe41c6cd80322f49d436bf5e8db2888670","datavalue":{"value":"1298.94001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625101$C22D1D9F-C7D3-413F-ABD5-DAF6F306B85C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e7d13dfa6c96eae4f48a9cc2ba922079cfbb1a9b","datavalue":{"value":"10.1007/978-3-642-17367-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625101$10229775-DC66-4819-958F-35F0E2DD57A2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5cebe65ceea15cd93b2f459850477a2bdf6aabec","datavalue":{"value":{"entity-type":"item","numeric-id":301520,"id":"Q301520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q625101$1B090421-28D0-4E9D-AB0D-2B1F0F827567","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ccde1a0bba036cf63ad721807d82986b035168c9","datavalue":{"value":{"entity-type":"item","numeric-id":213232,"id":"Q213232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q625101$DC935489-91B4-4C83-8BB1-AFB8CDFE9A63","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"85de1403c7134b762319ee716a072e8b3e81fb9e","datavalue":{"value":{"time":"+2011-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q625101$11453879-F973-45D7-9A15-F16AB9662ABD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"168625e5cac21df3ef9d7b400b136963d0274811","datavalue":{"value":"Function is locally computable or ``computationally simple'' (can be implemented by a class \\(N{C^0}\\) circuit), if every bit of the output can be computed by reading a constant number of bits of the input. The author proved in his PhD dissertation in 2007 [Cryptography in constant parallel time, \\url{http://www.eng.tau.ac.il/~bennyap/pubs/thesis.pdf}], that under standard intractability assumptions used in cryptography (e.g. that factoring large integers is computationally hard) most cryptographic primitives (one-way functions, pseudorandom generators, symmetric and public key encryption schemes, digital signatures, message authentication schemes, commitment schemes, collision resistant hash functions, zero-knowledge proofs) can be implemented as locally computable functions, actually as functions where every output bit depends only on four input bits; he also provided a compiler that transforms an implementation of a cryptographic primitive in a relatively high complexity class into an \\(N{C^0}\\) implementation.   This book is based on the author's dissertation with some additions [\\textit{B. Applebaum} et al., Comput. Complexity 15, No. 2, 115--162 (2006; Zbl 1143.94009)] and references to recent results in parallel cryptography. The book requires only minimal knowledge in computational complexity and cryptography and can be used as a textbook for advanced or graduate students, but it is useful also for researchers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q625101$691F154B-8346-4E62-B90B-A71C6AB39A5E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4e1df29911c330da2d8d89435a35b182dae9e523","datavalue":{"value":{"entity-type":"item","numeric-id":589408,"id":"Q589408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q625101$594546E1-105F-4135-A5BF-2739EC44EA86","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec639dabb19ee7efd8ad25e9cbf38528c68dd096","datavalue":{"value":"94-01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625101$25150785-6B0D-4347-972C-A5E21F5F21CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"98c5206e338942c77451c20a9a5ffe8ae1a4cf18","datavalue":{"value":"68-01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625101$E90D5D30-A29A-422D-853B-E7B01835F90B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625101$3492C7B0-8BF8-49EE-8A20-9D01E12791A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b71b42e4e887bf125b7436fe1334aef39047fb5c","datavalue":{"value":"94A62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625101$6D051877-068C-4FA4-8FAB-1D857C45FCC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"58bd804a9b32ab16fea71636cf187b83a20de8f7","datavalue":{"value":"68P25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625101$6638D6A6-763A-499D-AFAB-3973EE830E08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625101$214CFFF7-4716-44B4-9CBF-2FFDA108443C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f43b45b48369e4c976b2f647b122ae1f1e954b37","datavalue":{"value":"5851567","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625101$705E4AE8-8BE5-498E-BCB5-AE4BA69B267B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d54d97c9d74a7974164bd27bc3725f50a6bd71c8","datavalue":{"value":"cryptography","type":"string"},"datatype":"string"},"type":"statement","id":"Q625101$D2DB333E-31AE-4A12-9DC3-CAADD4CA2B68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae6f3e2460f5fd1e570ff1ecb3848030969ef42d","datavalue":{"value":"parallel time-complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q625101$18571294-F369-435E-A536-B013F262FD68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1bc35ff6443461d6244be562c7c2fb68b2d4a67","datavalue":{"value":"class \\(N{C^0}\\) circuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q625101$911BCC67-DC6E-4FDF-BD08-DE6F79434AAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9751e40fc64b559f097ced67cd2c8f328b9f12c","datavalue":{"value":"one-way function","type":"string"},"datatype":"string"},"type":"statement","id":"Q625101$A82BD361-7A73-4912-B24C-ED328467F42E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b777100f1127212b0abed5cca160ff94fac5adf","datavalue":{"value":"pseudorandom generator","type":"string"},"datatype":"string"},"type":"statement","id":"Q625101$61E221A4-303B-46CF-A110-1751FC852E74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b20193e17ab3d83c6d11ac47e585305bdc072b28","datavalue":{"value":"symmetric encryption","type":"string"},"datatype":"string"},"type":"statement","id":"Q625101$FAD749EE-29F4-4C9F-89A4-431B19C8D548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d326521a390cfdf084ee347b8d110b2f6a022bc","datavalue":{"value":"public key encryption","type":"string"},"datatype":"string"},"type":"statement","id":"Q625101$F08D8F6B-9C46-4A7B-93CE-EFFF881202FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b05c5a74cc052582e2cca37ae8e91129483570df","datavalue":{"value":"digital signature","type":"string"},"datatype":"string"},"type":"statement","id":"Q625101$67A4D5AE-0A76-4BC0-AD04-6449A2434A6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac66b3f16115d58779216144f67e4563e9869a53","datavalue":{"value":"message authentication scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q625101$B9362D4B-F757-4735-B599-9570A8C756D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e7fddf7d0c959c55ddc262596e80bfc37701f67d","datavalue":{"value":"commitment scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q625101$9AE599E0-CAC1-4757-BE03-E8946C126103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bea8dd784d91da69387caf4e88fd994e6ac34ce9","datavalue":{"value":"collision resistant hash function","type":"string"},"datatype":"string"},"type":"statement","id":"Q625101$724E6817-5346-4A90-BB9C-DDFCE9A357C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be8d3edd09944f75249407bd940adbd5a84e4713","datavalue":{"value":"zero-knowledge proof","type":"string"},"datatype":"string"},"type":"statement","id":"Q625101$7B4AD533-55B1-4ED9-BCAD-A5DDFF84C1C0","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":"Q625101$BB3562B2-EF31-410B-A7E3-D2F24E5F03B7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c802a4621b3d33b4f569aa9e5dbaec4d7498ea4a","datavalue":{"value":"https://doi.org/10.1007/978-3-642-17367-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q625101$8050F46E-9633-4A11-B4B3-9D0A6D7B1CBB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b7e493416a0ab52aee7ab28a3739d4e5f88c3e4b","datavalue":{"value":"W1603472107","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625101$0C2E6947-92AD-4864-8C84-D8A40D2564F6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"393fcb1a9e7a8be9df5b5be72cef8fbe0ac1a63f","datavalue":{"value":{"entity-type":"item","numeric-id":1037233,"id":"Q1037233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb01c86de706eb2a8b3a6964b0ef87ad99edab1e","datavalue":{"value":{"amount":"+0.8438332","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q625101$00EB037C-879B-4774-842C-9615F2F89776","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c14f6aacda3e529000a2f973c44fd6faa566eb1","datavalue":{"value":{"entity-type":"item","numeric-id":3612545,"id":"Q3612545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae61db62b02312ac7db5b6f9148a32eb707bc0cf","datavalue":{"value":{"amount":"+0.83636653","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q625101$EB7768D5-ADA4-450B-9AB0-8D92E9F7784A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e593070dafcdd2a99291a707fae736fe6e1207b","datavalue":{"value":{"entity-type":"item","numeric-id":5708362,"id":"Q5708362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45328f6bf8878d6a3f9030713fd1dc3bfa7c0c25","datavalue":{"value":{"amount":"+0.8223184","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q625101$05678059-3330-4A29-BD31-7AF7E705CBC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89f2c0481f343d98609825e53e69bd0578dbdd54","datavalue":{"value":{"entity-type":"item","numeric-id":2484164,"id":"Q2484164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d437816dd8ed8a4342b154413f97227ca8983fcb","datavalue":{"value":{"amount":"+0.8193573","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q625101$050122BD-C2E9-49FB-8D98-B67BCA40F833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17ef4ba1037a8645bd8a2ceea345b6f939f70edb","datavalue":{"value":{"entity-type":"item","numeric-id":1755445,"id":"Q1755445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13eb8d9335dec91a93ddfd6921ae3b2caa128e0c","datavalue":{"value":{"amount":"+0.81144184","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q625101$293B1181-1B23-474B-B050-56035B0DA781","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e25b2d256bbeec89cd5185d9205e0f8e9b0db80d","datavalue":{"value":{"entity-type":"item","numeric-id":4941849,"id":"Q4941849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc481fd7c9697117384cc57dfbe38ea3f07ab1e6","datavalue":{"value":{"amount":"+0.8088483","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q625101$4EF1DFCB-4051-4779-A3BF-B8D734E81E93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"737b37aa114b355b51b3ccb9f25a157ec95bf058","datavalue":{"value":{"entity-type":"item","numeric-id":3413440,"id":"Q3413440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e15e2859f427f77518f586a464992805674ac106","datavalue":{"value":{"amount":"+0.80665714","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q625101$C6A8893B-C887-4930-940F-49F22875DA45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff890c978580c13d90292e1d72de7ccbbd80aa5d","datavalue":{"value":{"entity-type":"item","numeric-id":5918810,"id":"Q5918810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41dfaae1d08604863863cf1ac0d06a0de8f5b0c1","datavalue":{"value":{"amount":"+0.80265385","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q625101$59FB51E9-E67D-4C21-B63E-A57F706E15A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a68e3db639d57ba087fa7468ae5bbe3b5ac0fa93","datavalue":{"value":{"entity-type":"item","numeric-id":332271,"id":"Q332271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34a9cb550f27cf36c602c0275a3d3d84fd0ba40c","datavalue":{"value":{"amount":"+0.80187315","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q625101$741653D5-419A-4B0F-9A24-B5BCF42B2F12","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Cryptography in constant parallel time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Cryptography_in_constant_parallel_time"}}}}}