{"entities":{"Q1198029":{"pageid":1208778,"ns":120,"title":"Item:Q1198029","lastrevid":66847029,"modified":"2026-04-12T13:15:22Z","type":"item","id":"Q1198029","labels":{"en":{"language":"en","value":"An almost-constant round interactive zero-knowledge proof"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 92097"}},"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":"Q1198029$B7D8363C-B504-4659-A5C9-A675F8717E79","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"022ca4181d0746f35e854421b8ad2a9a1c610023","datavalue":{"value":{"text":"An almost-constant round interactive zero-knowledge proof","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1198029$D1DCACFC-C86F-4365-8A4A-4EC5F2A8F168","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"41646177fe57aa71f02d514f24c7094fb3513071","datavalue":{"value":"0753.68038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198029$E6E4AFCF-DDDC-458F-AD44-BECFC989E774","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0343a384efec13e06e8521b875adf02c77d360f2","datavalue":{"value":"10.1016/0020-0190(92)90094-C","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198029$BF2851FF-AD45-423A-8E24-29A90DDCD166","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198029$31C2E2CB-9D53-4669-BE76-7AD2E2241FA5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1198029$67FFAE07-A4B6-466A-91B0-BA13C2E6B6B6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0a997591093eed405d84ebfcd51a58c310722674","datavalue":{"value":"We consider an Arthur-Merlin black-box IZKP for which \\(t(| x|)\\succ1\\), that is, \\(t\\) is any unbounded function of \\(| x|\\). We are concerned with functions which grow very slowly, significantly slower than any iterated logarithm. For example, we can take \\(t=\\log\\ast| x|\\) [\\textit{G. Brassard} and \\textit{P. GiLLES}, Algorithmics. Theory and practice, London etc.: Prentice-Hall (1988)]. We call such functions almost-constant. From our earlier remarks it follows that \\(t\\) cannot be constant unless the corresponding problem is feasible.   We shall see that in particular cases, both the running time and the communication complexity are less than those of comparable schemes by a factor of \\(\\log| x|\\) (for the same security level). This applies even if the probabilities \\(1-| x|^{-k}\\) and \\(| x|^{- k}\\) mentioned earlier are replaced by \\(1-2^{-| x|}\\) and \\(2^{- | x|}\\) respectively.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198029$6E8A36AB-A142-4DE3-BFA5-7F08525506D7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"58bd804a9b32ab16fea71636cf187b83a20de8f7","datavalue":{"value":"68P25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198029$869EB977-E053-4E0D-B08F-C1FA3EA5D604","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e1f144a9ab7064f6f8c78503075f6cd455ea06f6","datavalue":{"value":"94A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198029$C11EAF58-7614-46A9-AB4A-81D71AB4045D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198029$7DD84492-8A10-4EF1-8FAF-AE9249930442","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf2726c5c2109371cc10358eaa69bc4df711caf7","datavalue":{"value":"68P15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198029$602B48AF-269D-4FAF-ACB2-E56C6FED08E1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eca0bc6259d0b4ca35b7011dad51ebc7edcd85ed","datavalue":{"value":"92097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198029$AC2DB542-0A94-4DAD-B2ED-D9DF6288E861","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a72d1c726cabab8d82c5bcf212bd12e8b120a29","datavalue":{"value":"zero-knowledge proofs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198029$7CB6AA36-B49A-44A1-A5BE-1741B21C6DDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b01d27999f1c5b4276fcd13876c58aa3f286f197","datavalue":{"value":"Arthur-Merlin black-box IZKP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198029$4481B283-C837-4FAE-B911-23C7C2DB9D1A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a47f3a4188dbbb6096a8ac1ff23bcc3e5ae4cec","datavalue":{"value":{"entity-type":"item","numeric-id":2395274,"id":"Q2395274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198029$A8EBA053-2A65-4117-85B0-6CA3A679445D","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":"Q1198029$9C762AE1-D3AD-4354-89B8-5D842CA982FC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2ab7e41845f95d630a116a9b143665ad309e566","datavalue":{"value":{"entity-type":"item","numeric-id":4040055,"id":"Q4040055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198029$F4ED702B-F860-4892-802D-A1F5D17B575D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"574192bab7f8588ac988fb733f51a5394ead6555","datavalue":{"value":{"entity-type":"item","numeric-id":1110348,"id":"Q1110348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198029$A7708C16-154A-40F4-A2F5-5C00F1E7AE9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96134485c530fc6f7e7dce302adc011604bf376e","datavalue":{"value":{"entity-type":"item","numeric-id":3358225,"id":"Q3358225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198029$CB0E4E7A-0D22-4AC2-BCF0-F9BBB5C93A8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18d61579d9949e96d2a3d9ee11cbf91e51d5f0d6","datavalue":{"value":{"entity-type":"item","numeric-id":1112785,"id":"Q1112785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198029$E26527B4-F47D-4C37-83AB-CA1A5E966078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c2eb86bbd6348ea66e162419695a7061e84e58c","datavalue":{"value":{"entity-type":"item","numeric-id":3777940,"id":"Q3777940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198029$1F59FEDE-E0FB-43BA-BE85-E268802266BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb24dff4005148539085ff5c885035cfccaed69","datavalue":{"value":{"entity-type":"item","numeric-id":4140967,"id":"Q4140967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198029$1B9C5AD4-14DE-47B8-A792-66748F510643","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cae5dbf608a4fbb95c614045c711f136df4c3f1","datavalue":{"value":{"entity-type":"item","numeric-id":4038698,"id":"Q4038698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198029$414C081F-8400-470C-957D-A2977FE640A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb4c62e6619c90e64a6184568783067da56015e6","datavalue":{"value":{"entity-type":"item","numeric-id":4302852,"id":"Q4302852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198029$AF09B757-DFBD-4184-817B-A78E9A91C6EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae477ba2300400eec2908d55329cb4248dc074d4","datavalue":{"value":{"entity-type":"item","numeric-id":3833627,"id":"Q3833627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198029$DB1A13F4-0C0B-4A40-ADFB-6C010EF25294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04c71417eb8c9f2e918253566d502e63d2431fbf","datavalue":{"value":{"entity-type":"item","numeric-id":3197311,"id":"Q3197311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198029$76F86485-4153-4F4E-9C83-51A90813314D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b3f5a8a10869ec88219cb00a8e26322589b3b28a","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90094-c","type":"string"},"datatype":"url"},"type":"statement","id":"Q1198029$8D2F8400-77D7-41D4-BE13-B760D199286D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bbf1ea7f289f9fef68134b43cbe36fe86c8bc104","datavalue":{"value":"W1999954816","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198029$1C7069EB-8FB6-4222-9C8E-CE4D080827CD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4de940302a205471c27c182a2271f568ac69a519","datavalue":{"value":{"entity-type":"item","numeric-id":5445525,"id":"Q5445525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8eada142704f12ad84f515dde30bd77627144772","datavalue":{"value":{"amount":"+0.8134416937828064","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":"Q1198029$25F1329C-9E5D-434E-878F-8E75D1F876EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45fcaee4d7cd486f4d0482dc00b82ee820512708","datavalue":{"value":{"entity-type":"item","numeric-id":4875450,"id":"Q4875450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c64e568afd8624f18742d495536d4da596df7db1","datavalue":{"value":{"amount":"+0.8063861131668091","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":"Q1198029$876F4B54-91C8-4B97-A730-119FDCC064ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfe89bfdd0a6e9dc3c4ba1c872d265303ff77631","datavalue":{"value":{"entity-type":"item","numeric-id":1924196,"id":"Q1924196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c64e568afd8624f18742d495536d4da596df7db1","datavalue":{"value":{"amount":"+0.8063861131668091","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":"Q1198029$21DC8EC7-C0BD-423B-AF61-0D804030DF87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"336bbdac2f0eaa75d1b2a74e60dd2be06596636a","datavalue":{"value":{"entity-type":"item","numeric-id":4038698,"id":"Q4038698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2150c2e6a4b0c2386ad393613e86cabd85a56513","datavalue":{"value":{"amount":"+0.8026224374771118","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":"Q1198029$041EA823-DAA2-4EAE-9B33-431B57F61F1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b27131ceba0b7ad09f9c23bade53817da718f8c","datavalue":{"value":{"entity-type":"item","numeric-id":3210166,"id":"Q3210166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2150c2e6a4b0c2386ad393613e86cabd85a56513","datavalue":{"value":{"amount":"+0.8026224374771118","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":"Q1198029$7B7DC715-9849-47FF-A2BF-AD64CA550996","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An almost-constant round interactive zero-knowledge proof","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_almost-constant_round_interactive_zero-knowledge_proof"}}}}}