[{"date_created":"2018-12-11T11:52:16Z","volume":25,"title":"A counterexample to the chain rule for conditional HILL entropy","oa_version":"Submitted Version","author":[{"orcid":"0000-0003-2835-9093","first_name":"Stephan","last_name":"Krenn","id":"329FCCF0-F248-11E8-B48F-1D18A9856A87","full_name":"Krenn, Stephan"},{"first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z"},{"first_name":"Akshay","full_name":"Wadia, Akshay","last_name":"Wadia"},{"first_name":"Daniel","last_name":"Wichs","full_name":"Wichs, Daniel"}],"scopus_import":1,"day":"01","publication_status":"published","file_date_updated":"2020-07-14T12:44:56Z","intvolume":"        25","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"abstract":[{"lang":"eng","text":"Most entropy notions H(.) like Shannon or min-entropy satisfy a chain rule stating that for random variables X,Z, and A we have H(X|Z,A)≥H(X|Z)−|A|. That is, by conditioning on A the entropy of X can decrease by at most the bitlength |A| of A. Such chain rules are known to hold for some computational entropy notions like Yao’s and unpredictability-entropy. For HILL entropy, the computational analogue of min-entropy, the chain rule is of special interest and has found many applications, including leakage-resilient cryptography, deterministic encryption, and memory delegation. These applications rely on restricted special cases of the chain rule. Whether the chain rule for conditional HILL entropy holds in general was an open problem for which we give a strong negative answer: we construct joint distributions (X,Z,A), where A is a distribution over a single bit, such that the HILL entropy H HILL (X|Z) is large but H HILL (X|Z,A) is basically zero.\r\n\r\nOur counterexample just makes the minimal assumption that NP⊈P/poly. Under the stronger assumption that injective one-way function exist, we can make all the distributions efficiently samplable.\r\n\r\nFinally, we show that some more sophisticated cryptographic objects like lossy functions can be used to sample a distribution constituting a counterexample to the chain rule making only a single invocation to the underlying object."}],"has_accepted_license":"1","file":[{"file_name":"IST-2017-766-v1+1_678.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"7659296174fa75f5f0364f31f46f4bcf","file_size":483258,"date_created":"2018-12-12T10:13:29Z","creator":"system","date_updated":"2020-07-14T12:44:56Z","file_id":"5012"}],"department":[{"_id":"KrPi"}],"month":"09","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","issue":"3","citation":{"mla":"Krenn, Stephan, et al. “A Counterexample to the Chain Rule for Conditional HILL Entropy.” <i>Computational Complexity</i>, vol. 25, no. 3, Springer, 2016, pp. 567–605, doi:<a href=\"https://doi.org/10.1007/s00037-015-0120-9\">10.1007/s00037-015-0120-9</a>.","apa":"Krenn, S., Pietrzak, K. Z., Wadia, A., &#38; Wichs, D. (2016). A counterexample to the chain rule for conditional HILL entropy. <i>Computational Complexity</i>. Springer. <a href=\"https://doi.org/10.1007/s00037-015-0120-9\">https://doi.org/10.1007/s00037-015-0120-9</a>","chicago":"Krenn, Stephan, Krzysztof Z Pietrzak, Akshay Wadia, and Daniel Wichs. “A Counterexample to the Chain Rule for Conditional HILL Entropy.” <i>Computational Complexity</i>. Springer, 2016. <a href=\"https://doi.org/10.1007/s00037-015-0120-9\">https://doi.org/10.1007/s00037-015-0120-9</a>.","ista":"Krenn S, Pietrzak KZ, Wadia A, Wichs D. 2016. A counterexample to the chain rule for conditional HILL entropy. Computational Complexity. 25(3), 567–605.","short":"S. Krenn, K.Z. Pietrzak, A. Wadia, D. Wichs, Computational Complexity 25 (2016) 567–605.","ieee":"S. Krenn, K. Z. Pietrzak, A. Wadia, and D. Wichs, “A counterexample to the chain rule for conditional HILL entropy,” <i>Computational Complexity</i>, vol. 25, no. 3. Springer, pp. 567–605, 2016.","ama":"Krenn S, Pietrzak KZ, Wadia A, Wichs D. A counterexample to the chain rule for conditional HILL entropy. <i>Computational Complexity</i>. 2016;25(3):567-605. doi:<a href=\"https://doi.org/10.1007/s00037-015-0120-9\">10.1007/s00037-015-0120-9</a>"},"pubrep_id":"766","language":[{"iso":"eng"}],"oa":1,"type":"journal_article","date_updated":"2023-02-23T11:05:09Z","_id":"1479","publisher":"Springer","doi":"10.1007/s00037-015-0120-9","quality_controlled":"1","ddc":["004"],"page":"567 - 605","publist_id":"5715","related_material":{"record":[{"id":"2940","status":"public","relation":"earlier_version"}]},"year":"2016","date_published":"2016-09-01T00:00:00Z","acknowledgement":"This work was partly funded by the European Research Council under ERC Starting Grant 259668-PSPC and ERC Advanced Grant 321310-PERCY.\r\n","ec_funded":1,"project":[{"call_identifier":"FP7","grant_number":"259668","name":"Provable Security for Physical Cryptography","_id":"258C570E-B435-11E9-9278-68D0E5697425"}],"publication":"Computational Complexity","status":"public"},{"citation":{"ama":"Krenn S, Pietrzak KZ, Wadia A. A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it. In: Sahai A, ed. Vol 7785. Springer; 2013:23-39. doi:<a href=\"https://doi.org/10.1007/978-3-642-36594-2_2\">10.1007/978-3-642-36594-2_2</a>","ieee":"S. Krenn, K. Z. Pietrzak, and A. Wadia, “A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it,” presented at the TCC: Theory of Cryptography Conference, Tokyo, Japan, 2013, vol. 7785, pp. 23–39.","short":"S. Krenn, K.Z. Pietrzak, A. Wadia, in:, A. Sahai (Ed.), Springer, 2013, pp. 23–39.","ista":"Krenn S, Pietrzak KZ, Wadia A. 2013. A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it. TCC: Theory of Cryptography Conference, LNCS, vol. 7785, 23–39.","chicago":"Krenn, Stephan, Krzysztof Z Pietrzak, and Akshay Wadia. “A Counterexample to the Chain Rule for Conditional HILL Entropy, and What Deniable Encryption Has to Do with It.” edited by Amit Sahai, 7785:23–39. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-642-36594-2_2\">https://doi.org/10.1007/978-3-642-36594-2_2</a>.","apa":"Krenn, S., Pietrzak, K. Z., &#38; Wadia, A. (2013). A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it. In A. Sahai (Ed.) (Vol. 7785, pp. 23–39). Presented at the TCC: Theory of Cryptography Conference, Tokyo, Japan: Springer. <a href=\"https://doi.org/10.1007/978-3-642-36594-2_2\">https://doi.org/10.1007/978-3-642-36594-2_2</a>","mla":"Krenn, Stephan, et al. <i>A Counterexample to the Chain Rule for Conditional HILL Entropy, and What Deniable Encryption Has to Do with It</i>. Edited by Amit Sahai, vol. 7785, Springer, 2013, pp. 23–39, doi:<a href=\"https://doi.org/10.1007/978-3-642-36594-2_2\">10.1007/978-3-642-36594-2_2</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"file":[{"date_created":"2019-01-22T14:11:11Z","file_size":414823,"date_updated":"2020-07-14T12:45:54Z","creator":"dernst","file_id":"5875","file_name":"2013_LNCS_Krenn.pdf","access_level":"open_access","content_type":"application/pdf","relation":"main_file","checksum":"beb0cc1c0579da2d2e84394230a5da78"}],"month":"01","publication_status":"published","file_date_updated":"2020-07-14T12:45:54Z","has_accepted_license":"1","intvolume":"      7785","abstract":[{"lang":"eng","text":"A chain rule for an entropy notion H(.) states that the entropy H(X) of a variable X decreases by at most l if conditioned on an l-bit string A, i.e., H(X|A)&gt;= H(X)-l. More generally, it satisfies a chain rule for conditional entropy if H(X|Y,A)&gt;= H(X|Y)-l.\r\n\r\nAll natural information theoretic entropy notions we are aware of (like Shannon or min-entropy) satisfy some kind of chain rule for conditional entropy. Moreover, many computational entropy notions (like Yao entropy, unpredictability entropy and several variants of HILL entropy) satisfy the chain rule for conditional entropy, though here not only the quantity decreases by l, but also the quality of the entropy decreases exponentially in l. However, for \r\nthe standard notion of conditional HILL entropy (the computational equivalent of min-entropy) the existence of such a rule was unknown so far.\r\n\r\nIn this paper, we prove that for conditional HILL entropy no meaningful chain rule exists, assuming the existence of one-way permutations: there exist distributions X,Y,A, where A is a distribution over a single bit, but  $H(X|Y)&gt;&gt;H(X|Y,A)$, even if we simultaneously allow for a massive degradation in the quality of the entropy.\r\n\r\nThe idea underlying our construction is based on a surprising connection between the chain rule for HILL entropy and deniable encryption. "}],"volume":7785,"date_created":"2018-12-11T12:00:27Z","author":[{"last_name":"Krenn","id":"329FCCF0-F248-11E8-B48F-1D18A9856A87","full_name":"Krenn, Stephan","first_name":"Stephan","orcid":"0000-0003-2835-9093"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654"},{"first_name":"Akshay","full_name":"Wadia, Akshay","last_name":"Wadia"}],"scopus_import":1,"day":"29","title":"A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it","oa_version":"Submitted Version","ec_funded":1,"date_published":"2013-01-29T00:00:00Z","conference":{"location":"Tokyo, Japan","start_date":"2013-03-03","end_date":"2013-03-06","name":"TCC: Theory of Cryptography Conference"},"project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","name":"Provable Security for Physical Cryptography","grant_number":"259668","call_identifier":"FP7"}],"status":"public","publist_id":"3795","year":"2013","related_material":{"record":[{"id":"1479","relation":"later_version","status":"public"}]},"quality_controlled":"1","page":"23 - 39","ddc":["000"],"date_updated":"2023-02-23T10:00:43Z","_id":"2940","type":"conference","doi":"10.1007/978-3-642-36594-2_2","alternative_title":["LNCS"],"editor":[{"first_name":"Amit","full_name":"Sahai, Amit","last_name":"Sahai"}],"publisher":"Springer"},{"year":"2013","month":"01","publist_id":"3732","oa":1,"status":"public","extern":1,"citation":{"apa":"Bangerter, E., Barzan, S., Krenn, S., Sadeghi, A., Schneider, T., &#38; Tsay, J. (2013). Bringing Zero-Knowledge Proofs of Knowledge to Practice. In B. Christianson, J. Malcolm, V. Matyas, &#38; M. Roe (Eds.) (Vol. 7028, pp. 51–62). Presented at the SPW: Security Protocols Workshop, Springer. <a href=\"https://doi.org/10.1007/978-3-642-36213-2_9\">https://doi.org/10.1007/978-3-642-36213-2_9</a>","mla":"Bangerter, Endre, et al. <i>Bringing Zero-Knowledge Proofs of Knowledge to Practice</i>. Edited by Bruce Christianson et al., vol. 7028, Springer, 2013, pp. 51–62, doi:<a href=\"https://doi.org/10.1007/978-3-642-36213-2_9\">10.1007/978-3-642-36213-2_9</a>.","ista":"Bangerter E, Barzan S, Krenn S, Sadeghi A, Schneider T, Tsay J. 2013. Bringing Zero-Knowledge Proofs of Knowledge to Practice. SPW: Security Protocols Workshop, LNCS, vol. 7028, 51–62.","chicago":"Bangerter, Endre, Stefania Barzan, Stephan Krenn, Ahmad Sadeghi, Thomas Schneider, and Joe Tsay. “Bringing Zero-Knowledge Proofs of Knowledge to Practice.” edited by Bruce Christianson, James Malcolm, Vashek Matyas, and Michael Roe, 7028:51–62. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-642-36213-2_9\">https://doi.org/10.1007/978-3-642-36213-2_9</a>.","ieee":"E. Bangerter, S. Barzan, S. Krenn, A. Sadeghi, T. Schneider, and J. Tsay, “Bringing Zero-Knowledge Proofs of Knowledge to Practice,” presented at the SPW: Security Protocols Workshop, 2013, vol. 7028, pp. 51–62.","short":"E. Bangerter, S. Barzan, S. Krenn, A. Sadeghi, T. Schneider, J. Tsay, in:, B. Christianson, J. Malcolm, V. Matyas, M. Roe (Eds.), Springer, 2013, pp. 51–62.","ama":"Bangerter E, Barzan S, Krenn S, Sadeghi A, Schneider T, Tsay J. Bringing Zero-Knowledge Proofs of Knowledge to Practice. In: Christianson B, Malcolm J, Matyas V, Roe M, eds. Vol 7028. Springer; 2013:51-62. doi:<a href=\"https://doi.org/10.1007/978-3-642-36213-2_9\">10.1007/978-3-642-36213-2_9</a>"},"date_published":"2013-01-08T00:00:00Z","conference":{"name":"SPW: Security Protocols Workshop"},"acknowledgement":"This work is being performed within the FP7 EU project CACE (Computer Aided Cryptography Engineering).","doi":"10.1007/978-3-642-36213-2_9","author":[{"full_name":"Bangerter, Endre","last_name":"Bangerter","first_name":"Endre"},{"first_name":"Stefania","full_name":"Barzan, Stefania","last_name":"Barzan"},{"last_name":"Krenn","full_name":"Stephan Krenn","id":"329FCCF0-F248-11E8-B48F-1D18A9856A87","first_name":"Stephan","orcid":"0000-0003-2835-9093"},{"first_name":"Ahmad","full_name":"Sadeghi, Ahmad-Reza","last_name":"Sadeghi"},{"full_name":"Schneider, Thomas","last_name":"Schneider","first_name":"Thomas"},{"first_name":"Joe","full_name":"Tsay, Joe-Kai","last_name":"Tsay"}],"day":"08","alternative_title":["LNCS"],"editor":[{"last_name":"Christianson","full_name":"Christianson, Bruce","first_name":"Bruce"},{"last_name":"Malcolm","full_name":"Malcolm, James A.","first_name":"James"},{"first_name":"Vashek","full_name":"Matyas, Vashek","last_name":"Matyas"},{"full_name":"Roe, Michael","last_name":"Roe","first_name":"Michael"}],"title":"Bringing Zero-Knowledge Proofs of Knowledge to Practice","publisher":"Springer","date_updated":"2021-01-12T07:40:10Z","_id":"2973","volume":7028,"type":"conference","date_created":"2018-12-11T12:00:38Z","page":"51 - 62","intvolume":"      7028","abstract":[{"text":"Efficient zero-knowledge proofs of knowledge (ZK-PoK) are basic building blocks of many practical cryptographic applications such as identification schemes, group signatures, and secure multiparty computation. Currently, first applications that critically rely on ZK-PoKs are being deployed in the real world. The most prominent example is Direct Anonymous Attestation (DAA), which was adopted by the Trusted Computing Group (TCG) and implemented as one of the functionalities of the cryptographic Trusted Platform Module (TPM) chip.\n\nImplementing systems using ZK-PoK turns out to be challenging, since ZK-PoK are, loosely speaking, significantly more complex than standard crypto primitives, such as encryption and signature schemes. As a result, implementation cycles of ZK-PoK are time-consuming and error-prone, in particular for developers with minor or no cryptographic skills. \n\nIn this paper we report on our ongoing and future research vision with the goal to bring ZK-PoK to practice by making them accessible to crypto and security engineers. To this end we are developing compilers and related tools that support and partially automate the design, implementation, verification and secure implementation of ZK-PoK protocols.","lang":"eng"}],"main_file_link":[{"open_access":"1","url":"http://eprint.iacr.org/2009/211.pdf"}],"quality_controlled":0,"publication_status":"published"},{"issue":"1","citation":{"apa":"Alwen, J. F., Krenn, S., Pietrzak, K. Z., &#38; Wichs, D. (2013). Learning with rounding, revisited: New reduction properties and applications. Presented at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United States: Springer. <a href=\"https://doi.org/10.1007/978-3-642-40041-4_4\">https://doi.org/10.1007/978-3-642-40041-4_4</a>","mla":"Alwen, Joel F., et al. <i>Learning with Rounding, Revisited: New Reduction Properties and Applications</i>. Vol. 8042, no. 1, Springer, 2013, pp. 57–74, doi:<a href=\"https://doi.org/10.1007/978-3-642-40041-4_4\">10.1007/978-3-642-40041-4_4</a>.","chicago":"Alwen, Joel F, Stephan Krenn, Krzysztof Z Pietrzak, and Daniel Wichs. “Learning with Rounding, Revisited: New Reduction Properties and Applications.” Lecture Notes in Computer Science. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-642-40041-4_4\">https://doi.org/10.1007/978-3-642-40041-4_4</a>.","ista":"Alwen JF, Krenn S, Pietrzak KZ, Wichs D. 2013. Learning with rounding, revisited: New reduction properties and applications. 8042(1), 57–74.","ieee":"J. F. Alwen, S. Krenn, K. Z. Pietrzak, and D. Wichs, “Learning with rounding, revisited: New reduction properties and applications,” vol. 8042, no. 1. Springer, pp. 57–74, 2013.","short":"J.F. Alwen, S. Krenn, K.Z. Pietrzak, D. Wichs, 8042 (2013) 57–74.","ama":"Alwen JF, Krenn S, Pietrzak KZ, Wichs D. Learning with rounding, revisited: New reduction properties and applications. 2013;8042(1):57-74. doi:<a href=\"https://doi.org/10.1007/978-3-642-40041-4_4\">10.1007/978-3-642-40041-4_4</a>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"pubrep_id":"684","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"file":[{"checksum":"16d428408a806b8e49eecc607deab115","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"IST-2016-684-v1+1_098.pdf","file_id":"4912","date_updated":"2020-07-14T12:45:35Z","creator":"system","file_size":587898,"date_created":"2018-12-12T10:11:55Z"}],"month":"01","publication_status":"published","file_date_updated":"2020-07-14T12:45:35Z","has_accepted_license":"1","abstract":[{"text":"The learning with rounding (LWR) problem, introduced by Banerjee, Peikert and Rosen at EUROCRYPT ’12, is a variant of learning with errors (LWE), where one replaces random errors with deterministic rounding. The LWR problem was shown to be as hard as LWE for a setting of parameters where the modulus and modulus-to-error ratio are super-polynomial. In this work we resolve the main open problem and give a new reduction that works for a larger range of parameters, allowing for a polynomial modulus and modulus-to-error ratio. In particular, a smaller modulus gives us greater efficiency, and a smaller modulus-to-error ratio gives us greater security, which now follows from the worst-case hardness of GapSVP with polynomial (rather than super-polynomial) approximation factors.\r\n\r\nAs a tool in the reduction, we show that there is a “lossy mode” for the LWR problem, in which LWR samples only reveal partial information about the secret. This property gives us several interesting new applications, including a proof that LWR remains secure with weakly random secrets of sufficient min-entropy, and very simple constructions of deterministic encryption, lossy trapdoor functions and reusable extractors.\r\n\r\nOur approach is inspired by a technique of Goldwasser et al. from ICS ’10, which implicitly showed the existence of a “lossy mode” for LWE. By refining this technique, we also improve on the parameters of that work to only requiring a polynomial (instead of super-polynomial) modulus and modulus-to-error ratio.\r\n","lang":"eng"}],"intvolume":"      8042","volume":8042,"date_created":"2018-12-11T11:56:37Z","author":[{"first_name":"Joel F","last_name":"Alwen","full_name":"Alwen, Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Stephan","orcid":"0000-0003-2835-9093","last_name":"Krenn","full_name":"Krenn, Stephan","id":"329FCCF0-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654"},{"full_name":"Wichs, Daniel","last_name":"Wichs","first_name":"Daniel"}],"day":"01","scopus_import":1,"oa_version":"Published Version","title":"Learning with rounding, revisited: New reduction properties and applications","ec_funded":1,"date_published":"2013-01-01T00:00:00Z","conference":{"location":"Santa Barbara, CA, United States","start_date":"2013-08-18","end_date":"2013-08-22","name":"CRYPTO: International Cryptology Conference"},"project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","name":"Provable Security for Physical Cryptography","grant_number":"259668","call_identifier":"FP7"}],"status":"public","publist_id":"4687","year":"2013","quality_controlled":"1","page":"57 - 74","ddc":["000","004"],"date_updated":"2021-01-12T06:56:21Z","_id":"2259","type":"conference","series_title":"Lecture Notes in Computer Science","doi":"10.1007/978-3-642-40041-4_4","alternative_title":["LNCS"],"publisher":"Springer"},{"language":[{"iso":"eng"}],"status":"public","publication":"Proceedings of the 2012 ACM conference on Computer and communications security","oa":1,"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","acknowledgement":"This work was partially funded by National Funds through the FCT - Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology) within project ENI-AC/2224/2009, by ENIAC Joint Undertaking under grant agreement number 120224, European Projects FP7-256980 NESSoS and FP7-229599 AMAROUT, Spanish National project TIN2009-14599 DESAFIOS 10, and Madrid Regional project S2009TIC-1465 PROMETIDOS.","date_published":"2012-10-01T00:00:00Z","conference":{"name":"CCS: Computer and Communications Security","end_date":"2012-10-18","start_date":"2012-10-16","location":"Raleigh, NC, USA"},"citation":{"ama":"Almeida J, Barbosa M, Bangerter E, Barthe G, Krenn S, Béguelin S. Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols. In: <i>Proceedings of the 2012 ACM Conference on Computer and Communications Security</i>. ACM; 2012:488-500. doi:<a href=\"https://doi.org/10.1145/2382196.2382249\">10.1145/2382196.2382249</a>","ieee":"J. Almeida, M. Barbosa, E. Bangerter, G. Barthe, S. Krenn, and S. Béguelin, “Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols,” in <i>Proceedings of the 2012 ACM conference on Computer and communications security</i>, Raleigh, NC, USA, 2012, pp. 488–500.","short":"J. Almeida, M. Barbosa, E. Bangerter, G. Barthe, S. Krenn, S. Béguelin, in:, Proceedings of the 2012 ACM Conference on Computer and Communications Security, ACM, 2012, pp. 488–500.","ista":"Almeida J, Barbosa M, Bangerter E, Barthe G, Krenn S, Béguelin S. 2012. Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols. Proceedings of the 2012 ACM conference on Computer and communications security. CCS: Computer and Communications Security, 488–500.","chicago":"Almeida, José, Manuel Barbosa, Endre Bangerter, Gilles Barthe, Stephan Krenn, and Santiago Béguelin. “Full Proof Cryptography: Verifiable Compilation of Efficient Zero-Knowledge Protocols.” In <i>Proceedings of the 2012 ACM Conference on Computer and Communications Security</i>, 488–500. ACM, 2012. <a href=\"https://doi.org/10.1145/2382196.2382249\">https://doi.org/10.1145/2382196.2382249</a>.","apa":"Almeida, J., Barbosa, M., Bangerter, E., Barthe, G., Krenn, S., &#38; Béguelin, S. (2012). Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols. In <i>Proceedings of the 2012 ACM conference on Computer and communications security</i> (pp. 488–500). Raleigh, NC, USA: ACM. <a href=\"https://doi.org/10.1145/2382196.2382249\">https://doi.org/10.1145/2382196.2382249</a>","mla":"Almeida, José, et al. “Full Proof Cryptography: Verifiable Compilation of Efficient Zero-Knowledge Protocols.” <i>Proceedings of the 2012 ACM Conference on Computer and Communications Security</i>, ACM, 2012, pp. 488–500, doi:<a href=\"https://doi.org/10.1145/2382196.2382249\">10.1145/2382196.2382249</a>."},"month":"10","year":"2012","publist_id":"3798","department":[{"_id":"KrPi"}],"abstract":[{"lang":"eng","text":"Developers building cryptography into security-sensitive applications face a daunting task. Not only must they understand the security guarantees delivered by the constructions they choose, they must also implement and combine them correctly and efficiently. Cryptographic compilers free developers from this task by turning high-level specifications of security goals into efficient implementations. Yet, trusting such tools is hard as they rely on complex mathematical machinery and claim security properties that are subtle and difficult to verify. In this paper we present ZKCrypt, an optimizing cryptographic compiler achieving an unprecedented level of assurance without sacrificing practicality for a comprehensive class of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline of ZKCrypt integrates purpose-built verified compilers and verifying compilers producing formal proofs in the CertiCrypt framework. By combining the guarantees delivered by each stage, ZKCrypt provides assurance that the output implementation securely realizes the abstract proof goal given as input. We report on the main characteristics of ZKCrypt, highlight new definitions and concepts at its foundations, and illustrate its applicability through a representative example of an anonymous credential system."}],"page":"488 - 500","publication_status":"published","quality_controlled":"1","main_file_link":[{"url":"https://eprint.iacr.org/2012/258","open_access":"1"}],"oa_version":"Submitted Version","publisher":"ACM","title":"Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols","day":"01","scopus_import":1,"author":[{"first_name":"José","full_name":"Almeida, José","last_name":"Almeida"},{"full_name":"Barbosa, Manuel","last_name":"Barbosa","first_name":"Manuel"},{"first_name":"Endre","last_name":"Bangerter","full_name":"Bangerter, Endre"},{"last_name":"Barthe","full_name":"Barthe, Gilles","first_name":"Gilles"},{"id":"329FCCF0-F248-11E8-B48F-1D18A9856A87","full_name":"Krenn, Stephan","last_name":"Krenn","orcid":"0000-0003-2835-9093","first_name":"Stephan"},{"first_name":"Santiago","last_name":"Béguelin","full_name":"Béguelin, Santiago"}],"doi":"10.1145/2382196.2382249","date_created":"2018-12-11T12:00:26Z","type":"conference","_id":"2937","date_updated":"2021-01-12T07:39:53Z"},{"title":"Commitments and efficient zero knowledge proofs from learning parity with noise","oa_version":"Submitted Version","author":[{"first_name":"Abhishek","last_name":"Jain","full_name":"Jain, Abhishek"},{"full_name":"Krenn, Stephan","id":"329FCCF0-F248-11E8-B48F-1D18A9856A87","last_name":"Krenn","orcid":"0000-0003-2835-9093","first_name":"Stephan"},{"full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654"},{"last_name":"Tentes","full_name":"Tentes, Aris","first_name":"Aris"}],"day":"01","scopus_import":1,"date_created":"2018-12-11T12:00:38Z","volume":7658,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"abstract":[{"lang":"eng","text":"We construct a perfectly binding string commitment scheme whose security is based on the learning parity with noise (LPN) assumption, or equivalently, the hardness of decoding random linear codes. Our scheme not only allows for a simple and efficient zero-knowledge proof of knowledge for committed values (essentially a Σ-protocol), but also for such proofs showing any kind of relation amongst committed values, i.e. proving that messages m_0,...,m_u, are such that m_0=C(m_1,...,m_u) for any circuit C.\r\n\r\nTo get soundness which is exponentially small in a security parameter t, and when the zero-knowledge property relies on the LPN problem with secrets of length l, our 3 round protocol has communication complexity O(t|C|l log(l)) and computational complexity of O(t|C|l) bit operations. The hidden constants are small, and the computation consists mostly of computing inner products of bit-vectors."}],"intvolume":"      7658","has_accepted_license":"1","publication_status":"published","file_date_updated":"2020-07-14T12:45:58Z","month":"12","file":[{"file_size":482570,"date_created":"2018-12-12T10:14:00Z","creator":"system","date_updated":"2020-07-14T12:45:58Z","file_id":"5048","file_name":"IST-2016-721-v1+1_513.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"ab879537385efc4cb4203e7ef0fea17b"}],"department":[{"_id":"KrPi"}],"pubrep_id":"721","language":[{"iso":"eng"}],"oa":1,"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ieee":"A. Jain, S. Krenn, K. Z. Pietrzak, and A. Tentes, “Commitments and efficient zero knowledge proofs from learning parity with noise,” presented at the ASIACRYPT: Theory and Application of Cryptology and Information Security, Beijing, China, 2012, vol. 7658, pp. 663–680.","short":"A. Jain, S. Krenn, K.Z. Pietrzak, A. Tentes, in:, X. Wang, K. Sako (Eds.), Springer, 2012, pp. 663–680.","ama":"Jain A, Krenn S, Pietrzak KZ, Tentes A. Commitments and efficient zero knowledge proofs from learning parity with noise. In: Wang X, Sako K, eds. Vol 7658. Springer; 2012:663-680. doi:<a href=\"https://doi.org/10.1007/978-3-642-34961-4_40\">10.1007/978-3-642-34961-4_40</a>","apa":"Jain, A., Krenn, S., Pietrzak, K. Z., &#38; Tentes, A. (2012). Commitments and efficient zero knowledge proofs from learning parity with noise. In X. Wang &#38; K. Sako (Eds.) (Vol. 7658, pp. 663–680). Presented at the ASIACRYPT: Theory and Application of Cryptology and Information Security, Beijing, China: Springer. <a href=\"https://doi.org/10.1007/978-3-642-34961-4_40\">https://doi.org/10.1007/978-3-642-34961-4_40</a>","mla":"Jain, Abhishek, et al. <i>Commitments and Efficient Zero Knowledge Proofs from Learning Parity with Noise</i>. Edited by Xiaoyun Wang and Kazue Sako, vol. 7658, Springer, 2012, pp. 663–80, doi:<a href=\"https://doi.org/10.1007/978-3-642-34961-4_40\">10.1007/978-3-642-34961-4_40</a>.","ista":"Jain A, Krenn S, Pietrzak KZ, Tentes A. 2012. Commitments and efficient zero knowledge proofs from learning parity with noise. ASIACRYPT: Theory and Application of Cryptology and Information Security, LNCS, vol. 7658, 663–680.","chicago":"Jain, Abhishek, Stephan Krenn, Krzysztof Z Pietrzak, and Aris Tentes. “Commitments and Efficient Zero Knowledge Proofs from Learning Parity with Noise.” edited by Xiaoyun Wang and Kazue Sako, 7658:663–80. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-34961-4_40\">https://doi.org/10.1007/978-3-642-34961-4_40</a>."},"editor":[{"first_name":"Xiaoyun","last_name":"Wang","full_name":"Wang, Xiaoyun"},{"first_name":"Kazue","last_name":"Sako","full_name":"Sako, Kazue"}],"publisher":"Springer","doi":"10.1007/978-3-642-34961-4_40","alternative_title":["LNCS"],"type":"conference","date_updated":"2021-01-12T07:40:11Z","_id":"2974","ddc":["004","005"],"page":"663 - 680","year":"2012","publist_id":"3730","project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","name":"Provable Security for Physical Cryptography","grant_number":"259668","call_identifier":"FP7"}],"status":"public","conference":{"location":"Beijing, China","end_date":"2012-12-06","start_date":"2012-12-02","name":"ASIACRYPT: Theory and Application of Cryptology and Information Security"},"acknowledgement":"We are grateful to Petros Mol for helpful discussions on the reduction for the hardness of the xLPN problem.\r\n","date_published":"2012-12-01T00:00:00Z","ec_funded":1},{"conference":{"name":"ASIACRYPT: Theory and Application of Cryptology and Information Security"},"date_published":"2011-11-21T00:00:00Z","acknowledgement":"This work was in part funded by the Swiss Hasler Foundation, and the EU FP7 grants 216483 and 216499, as well as by the NSF grant CNS-0716690.","citation":{"ama":"Camenisch J, Krenn S, Shoup V. A Framework for Practical Universally Composable Zero-Knowledge Protocols. In: Lee D, Wang X, eds. Vol 7073. Springer; 2011:449-467. doi:<a href=\"https://doi.org/10.1007/978-3-642-25385-0\">10.1007/978-3-642-25385-0</a>","ieee":"J. Camenisch, S. Krenn, and V. Shoup, “A Framework for Practical Universally Composable Zero-Knowledge Protocols,” presented at the ASIACRYPT: Theory and Application of Cryptology and Information Security, 2011, vol. 7073, pp. 449–467.","short":"J. Camenisch, S. Krenn, V. Shoup, in:, D. Lee, X. Wang (Eds.), Springer, 2011, pp. 449–467.","ista":"Camenisch J, Krenn S, Shoup V. 2011. A Framework for Practical Universally Composable Zero-Knowledge Protocols. ASIACRYPT: Theory and Application of Cryptology and Information Security, LNCS, vol. 7073, 449–467.","chicago":"Camenisch, Jan, Stephan Krenn, and Victor Shoup. “A Framework for Practical Universally Composable Zero-Knowledge Protocols.” edited by Dong Lee and Xiaoyun Wang, 7073:449–67. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-25385-0\">https://doi.org/10.1007/978-3-642-25385-0</a>.","apa":"Camenisch, J., Krenn, S., &#38; Shoup, V. (2011). A Framework for Practical Universally Composable Zero-Knowledge Protocols. In D. Lee &#38; X. Wang (Eds.) (Vol. 7073, pp. 449–467). Presented at the ASIACRYPT: Theory and Application of Cryptology and Information Security, Springer. <a href=\"https://doi.org/10.1007/978-3-642-25385-0\">https://doi.org/10.1007/978-3-642-25385-0</a>","mla":"Camenisch, Jan, et al. <i>A Framework for Practical Universally Composable Zero-Knowledge Protocols</i>. Edited by Dong Lee and Xiaoyun Wang, vol. 7073, Springer, 2011, pp. 449–67, doi:<a href=\"https://doi.org/10.1007/978-3-642-25385-0\">10.1007/978-3-642-25385-0</a>."},"status":"public","extern":1,"publist_id":"3728","month":"11","year":"2011","publication_status":"published","quality_controlled":0,"main_file_link":[{"open_access":"0","url":"http://eprint.iacr.org/2011/228.pdf"}],"intvolume":"      7073","abstract":[{"lang":"eng","text":"Zero-knowledge proofs of knowledge (ZK-PoK) for discrete logarithms and related problems are indispensable for practical cryptographic protocols. Recently, Camenisch, Kiayias, and Yung provided a specification language (the CKY-language) for such protocols which allows for a modular design and protocol analysis: for every zero-knowledge proof specified in this language, protocol designers are ensured that there exists an efficient protocol which indeed proves the specified statement.\n\nHowever, the protocols resulting from their compilation techniques only satisfy the classical notion of ZK-PoK, which is not retained are when they used as building blocks for higher-level applications or composed with other protocols.\nThis problem can be tackled by moving to the Universal Composability (UC) framework, which guarantees retention of security when composing protocols in arbitrary ways.  \nWhile there exist generic transformations from $\\Sigma$-protocols to UC-secure protocols, these transformation are often too inefficient for practice.\n \nIn this paper we introduce a specification language akin to the CKY-language and a compiler such that the resulting protocols are UC-secure and efficient. \nTo this end, we propose an extension of the UC-framework addressing the \nissue that UC-secure zero-knowledge proofs are by definition proofs of knowledge, and state a special composition theorem which allows one to use the weaker -- but more efficient and often sufficient -- notion of proofs of membership in the UC-framework.  \nWe believe that our contributions enable the design of practically efficient protocols that are UC-secure and thus themselves can be used as building blocks."}],"page":"449 - 467","type":"conference","date_created":"2018-12-11T12:00:39Z","date_updated":"2021-01-12T07:40:11Z","_id":"2975","volume":7073,"editor":[{"full_name":"Lee, Dong Hoon","last_name":"Lee","first_name":"Dong"},{"first_name":"Xiaoyun","full_name":"Wang, Xiaoyun","last_name":"Wang"}],"publisher":"Springer","title":"A Framework for Practical Universally Composable Zero-Knowledge Protocols","doi":"10.1007/978-3-642-25385-0","author":[{"first_name":"Jan","full_name":"Camenisch, Jan","last_name":"Camenisch"},{"orcid":"0000-0003-2835-9093","first_name":"Stephan","id":"329FCCF0-F248-11E8-B48F-1D18A9856A87","full_name":"Stephan Krenn","last_name":"Krenn"},{"first_name":"Victor","last_name":"Shoup","full_name":"Shoup, Victor"}],"day":"21","alternative_title":["LNCS"]},{"doi":"10.1109/SP.2011.22","author":[{"first_name":"David","last_name":"Gullasch","full_name":"Gullasch, David"},{"last_name":"Bangerter","full_name":"Bangerter, Endre","first_name":"Endre"},{"id":"329FCCF0-F248-11E8-B48F-1D18A9856A87","full_name":"Stephan Krenn","last_name":"Krenn","orcid":"0000-0003-2835-9093","first_name":"Stephan"}],"day":"01","title":"Cache Games - Bringing Access-Based Cache Attacks on AES to Practice","publisher":"IEEE","date_updated":"2021-01-12T07:40:11Z","_id":"2976","type":"conference","date_created":"2018-12-11T12:00:39Z","page":"490 - 505","abstract":[{"text":"Side channel attacks on cryptographic systems exploit information\ngained from physical implementations rather than theoretical\nweaknesses of a scheme. In recent years, major achievements were made\nfor the class of so called access-driven cache attacks. Such attacks\nexploit the leakage of the memory locations accessed by a victim\nprocess.\n\nIn this paper we consider the AES block cipher and present an attack\nwhich is capable of recovering the full secret key in almost realtime\nfor AES-128, requiring only a very limited number of observed\nencryptions. Unlike previous attacks, we do not require any\ninformation about the plaintext (such as its distribution, etc.).\nMoreover, for the first time, we also show how the plaintext can be\nrecovered without having access to the ciphertext at all.  It is the\nfirst working attack on AES implementations using compressed\ntables. There, no efficient techniques to identify the beginning\nof AES rounds is known, which is the fundamental assumption underlying previous\nattacks.\n\nWe have a fully working implementation of our attack which is able to\nrecover AES keys after observing as little as 100 encryptions. It\nworks against the OpenSSL 0.9.8n implementation of AES on Linux\nsystems.  Our spy process does not require any special privileges\nbeyond those of a standard Linux user. A contribution of probably\nindependent interest is a denial of service attack on the task scheduler of\ncurrent Linux systems (CFS), which allows one to observe (on average)\nevery single memory access of a victim process.","lang":"eng"}],"main_file_link":[{"open_access":"0","url":"http://eprint.iacr.org/2010/594.pdf"}],"publication_status":"published","quality_controlled":0,"year":"2011","month":"01","publist_id":"3727","extern":1,"status":"public","citation":{"apa":"Gullasch, D., Bangerter, E., &#38; Krenn, S. (2011). Cache Games - Bringing Access-Based Cache Attacks on AES to Practice (pp. 490–505). Presented at the S&#38;P: IEEE Symposium on Security and Privacy, IEEE. <a href=\"https://doi.org/10.1109/SP.2011.22\">https://doi.org/10.1109/SP.2011.22</a>","mla":"Gullasch, David, et al. <i>Cache Games - Bringing Access-Based Cache Attacks on AES to Practice</i>. IEEE, 2011, pp. 490–505, doi:<a href=\"https://doi.org/10.1109/SP.2011.22\">10.1109/SP.2011.22</a>.","chicago":"Gullasch, David, Endre Bangerter, and Stephan Krenn. “Cache Games - Bringing Access-Based Cache Attacks on AES to Practice,” 490–505. IEEE, 2011. <a href=\"https://doi.org/10.1109/SP.2011.22\">https://doi.org/10.1109/SP.2011.22</a>.","ista":"Gullasch D, Bangerter E, Krenn S. 2011. Cache Games - Bringing Access-Based Cache Attacks on AES to Practice. S&#38;P: IEEE Symposium on Security and Privacy, 490–505.","ieee":"D. Gullasch, E. Bangerter, and S. Krenn, “Cache Games - Bringing Access-Based Cache Attacks on AES to Practice,” presented at the S&#38;P: IEEE Symposium on Security and Privacy, 2011, pp. 490–505.","short":"D. Gullasch, E. Bangerter, S. Krenn, in:, IEEE, 2011, pp. 490–505.","ama":"Gullasch D, Bangerter E, Krenn S. Cache Games - Bringing Access-Based Cache Attacks on AES to Practice. In: IEEE; 2011:490-505. doi:<a href=\"https://doi.org/10.1109/SP.2011.22\">10.1109/SP.2011.22</a>"},"date_published":"2011-01-01T00:00:00Z","conference":{"name":"S&P: IEEE Symposium on Security and Privacy"},"acknowledgement":"This work was in part funded by the European Community’s Seventh Framework Programme (FP7) under grant agreement no. 216499 and the Swiss Hasler Foundation.\nAn extended abstract was also accepted for COSADE 2011."},{"citation":{"ista":"Bangerter E, Krenn S, Seifriz M, Ultes Nitsche U. 2011. cPLC - A Cryptographic Programming Language and Compiler. ISSA: Information Security South Africa.","chicago":"Bangerter, Endre, Stephan Krenn, Martial Seifriz, and Ulrich Ultes Nitsche. “CPLC - A Cryptographic Programming Language and Compiler.” edited by Hein Venter, Marijke Coetzee, and Marianne Loock. IEEE, 2011. <a href=\"https://doi.org/10.1109/ISSA.2011.6027533\">https://doi.org/10.1109/ISSA.2011.6027533</a>.","apa":"Bangerter, E., Krenn, S., Seifriz, M., &#38; Ultes Nitsche, U. (2011). cPLC - A Cryptographic Programming Language and Compiler. In H. Venter, M. Coetzee, &#38; M. Loock (Eds.). Presented at the ISSA: Information Security South Africa, IEEE. <a href=\"https://doi.org/10.1109/ISSA.2011.6027533\">https://doi.org/10.1109/ISSA.2011.6027533</a>","mla":"Bangerter, Endre, et al. <i>CPLC - A Cryptographic Programming Language and Compiler</i>. Edited by Hein Venter et al., IEEE, 2011, doi:<a href=\"https://doi.org/10.1109/ISSA.2011.6027533\">10.1109/ISSA.2011.6027533</a>.","ama":"Bangerter E, Krenn S, Seifriz M, Ultes Nitsche U. cPLC - A Cryptographic Programming Language and Compiler. In: Venter H, Coetzee M, Loock M, eds. IEEE; 2011. doi:<a href=\"https://doi.org/10.1109/ISSA.2011.6027533\">10.1109/ISSA.2011.6027533</a>","ieee":"E. Bangerter, S. Krenn, M. Seifriz, and U. Ultes Nitsche, “cPLC - A Cryptographic Programming Language and Compiler,” presented at the ISSA: Information Security South Africa, 2011.","short":"E. Bangerter, S. Krenn, M. Seifriz, U. Ultes Nitsche, in:, H. Venter, M. Coetzee, M. Loock (Eds.), IEEE, 2011."},"date_published":"2011-08-01T00:00:00Z","acknowledgement":"This work was in part funded by the European Community’s Seventh Framework Programme (FP7) under grant agreement no. 216499 and the Swiss Hasler Foundation under projects no. 09037 and 10069.","conference":{"name":"ISSA: Information Security South Africa"},"extern":1,"status":"public","publist_id":"3726","year":"2011","month":"08","publication_status":"published","quality_controlled":0,"abstract":[{"lang":"eng","text":"Cryptographic two-party protocols are used ubiquitously in\n    everyday life. While some of these protocols are easy to\n    understand and implement (e.g., key exchange or transmission of\n    encrypted data), many of them are much more complex (e.g.,\n    e-banking and e-voting applications, or anonymous authentication\n    and credential systems).\n\n    For a software engineer without appropriate cryptographic skills\n    the implementation of such protocols is often difficult, time\n    consuming and error-prone. For this reason, a number of compilers\n    supporting programmers have been published in recent\n    years. However, they are either designed for very specific\n    cryptographic primitives (e.g., zero-knowledge proofs of\n    knowledge), or they only offer a very low level of abstraction and\n    thus again demand substantial mathematical and cryptographic\n    skills from the programmer. Finally, some of the existing\n    compilers do not produce executable code, but only metacode which\n    has to be instantiated with mathematical libraries, encryption\n    routines, etc. before it can actually be used.\n  \n    In this paper we present a cryptographically aware compiler which\n    is equally useful to cryptographers who want to benchmark\n    protocols designed on paper, and to programmers who want to\n    implement complex security sensitive protocols without having to\n    understand all subtleties. Our tool offers a high level of\n    abstraction and outputs well-structured and documented Java\n    code. We believe that our compiler can contribute to shortening\n    the development cycles of cryptographic applications and to\n    reducing their error-proneness."}],"date_updated":"2021-01-12T07:40:12Z","_id":"2977","type":"conference","date_created":"2018-12-11T12:00:39Z","author":[{"full_name":"Bangerter, Endre","last_name":"Bangerter","first_name":"Endre"},{"orcid":"0000-0003-2835-9093","first_name":"Stephan","full_name":"Stephan Krenn","id":"329FCCF0-F248-11E8-B48F-1D18A9856A87","last_name":"Krenn"},{"full_name":"Seifriz, Martial","last_name":"Seifriz","first_name":"Martial"},{"full_name":"Ultes-Nitsche, Ulrich","last_name":"Ultes Nitsche","first_name":"Ulrich"}],"doi":"10.1109/ISSA.2011.6027533","day":"01","editor":[{"first_name":"Hein","last_name":"Venter","full_name":"Venter, Hein S."},{"full_name":"Coetzee, Marijke","last_name":"Coetzee","first_name":"Marijke"},{"last_name":"Loock","full_name":"Loock, Marianne","first_name":"Marianne"}],"title":"cPLC - A Cryptographic Programming Language and Compiler","publisher":"IEEE"},{"year":"2010","month":"02","publist_id":"3725","oa":1,"status":"public","extern":1,"citation":{"apa":"Bangerter, E., Camenisch, J., &#38; Krenn, S. (2010). Efficiency Limitations for Σ-Protocols for Group Homomorphisms. In D. Micciancio (Ed.) (Vol. 5978, pp. 553–571). Presented at the TCC: Theory of Cryptography Conference, Springer. <a href=\"https://doi.org/10.1007/978-3-642-11799-2\">https://doi.org/10.1007/978-3-642-11799-2</a>","mla":"Bangerter, Endre, et al. <i>Efficiency Limitations for Σ-Protocols for Group Homomorphisms</i>. Edited by Daniele Micciancio, vol. 5978, Springer, 2010, pp. 553–71, doi:<a href=\"https://doi.org/10.1007/978-3-642-11799-2\">10.1007/978-3-642-11799-2</a>.","ista":"Bangerter E, Camenisch J, Krenn S. 2010. Efficiency Limitations for Σ-Protocols for Group Homomorphisms. TCC: Theory of Cryptography Conference, LNCS, vol. 5978, 553–571.","chicago":"Bangerter, Endre, Jan Camenisch, and Stephan Krenn. “Efficiency Limitations for Σ-Protocols for Group Homomorphisms.” edited by Daniele Micciancio, 5978:553–71. Springer, 2010. <a href=\"https://doi.org/10.1007/978-3-642-11799-2\">https://doi.org/10.1007/978-3-642-11799-2</a>.","ieee":"E. Bangerter, J. Camenisch, and S. Krenn, “Efficiency Limitations for Σ-Protocols for Group Homomorphisms,” presented at the TCC: Theory of Cryptography Conference, 2010, vol. 5978, pp. 553–571.","short":"E. Bangerter, J. Camenisch, S. Krenn, in:, D. Micciancio (Ed.), Springer, 2010, pp. 553–571.","ama":"Bangerter E, Camenisch J, Krenn S. Efficiency Limitations for Σ-Protocols for Group Homomorphisms. In: Micciancio D, ed. Vol 5978. Springer; 2010:553-571. doi:<a href=\"https://doi.org/10.1007/978-3-642-11799-2\">10.1007/978-3-642-11799-2</a>"},"date_published":"2010-02-08T00:00:00Z","conference":{"name":"TCC: Theory of Cryptography Conference"},"alternative_title":["LNCS"],"day":"08","doi":"10.1007/978-3-642-11799-2","author":[{"first_name":"Endre","full_name":"Bangerter, Endre","last_name":"Bangerter"},{"last_name":"Camenisch","full_name":"Camenisch, Jan","first_name":"Jan"},{"orcid":"0000-0003-2835-9093","first_name":"Stephan","full_name":"Stephan Krenn","id":"329FCCF0-F248-11E8-B48F-1D18A9856A87","last_name":"Krenn"}],"title":"Efficiency Limitations for Σ-Protocols for Group Homomorphisms","publisher":"Springer","editor":[{"first_name":"Daniele","last_name":"Micciancio","full_name":"Micciancio, Daniele"}],"_id":"2978","volume":5978,"date_updated":"2021-01-12T07:40:12Z","date_created":"2018-12-11T12:00:39Z","type":"conference","page":"553 - 571","intvolume":"      5978","abstract":[{"lang":"eng","text":"Efficient zero-knowledge proofs of knowledge for group homomorphisms are essential for numerous systems in applied cryptography. Especially, Σ-protocols for proving knowledge of discrete logarithms in known and hidden order groups are of prime importance. Yet, while these proofs can be performed very efficiently within groups of known order, for hidden order groups the respective proofs are far less efficient.\n\nThis paper shows strong evidence that this efficiency gap cannot be bridged. Namely, while there are efficient protocols allowing a prover to cheat only with negligibly small probability in the case of known order groups, we provide strong evidence that for hidden order groups this probability is bounded below by 1/2 for all efficient  Σ-protocols not using common reference strings or the like.\n\nWe prove our results for a comprehensive class of Σ-protocols in the generic group model, and further strengthen them by investigating certain instantiations in the plain model."}],"main_file_link":[{"open_access":"1","url":"http://eprint.iacr.org/2009/595.pdf"}],"quality_controlled":0,"publication_status":"published"},{"status":"public","extern":1,"oa":1,"acknowledgement":"This work was in part funded by the European Community's Seventh Framework Programme (FP7) under grant agreement no. 216499.\nA preliminary version of the compiler can be found at http://zkc.cace-project.eu.","conference":{"name":"ESORICS: European Symposium on Research in Computer Security"},"date_published":"2010-08-30T00:00:00Z","citation":{"chicago":"Almeida, José, Endre Bangerter, Manuel Barbosa, Stephan Krenn, Ahmad Sadeghi, and Thomas Schneider. “A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols.” edited by Dimitris Gritzalis, Bart Preneel, and Marianthi Theoharidou, 6345:151–67. Springer, 2010. <a href=\"https://doi.org/10.1007/978-3-642-15497-3\">https://doi.org/10.1007/978-3-642-15497-3</a>.","ista":"Almeida J, Bangerter E, Barbosa M, Krenn S, Sadeghi A, Schneider T. 2010. A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols. ESORICS: European Symposium on Research in Computer Security, LNCS, vol. 6345, 151–167.","apa":"Almeida, J., Bangerter, E., Barbosa, M., Krenn, S., Sadeghi, A., &#38; Schneider, T. (2010). A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols. In D. Gritzalis, B. Preneel, &#38; M. Theoharidou (Eds.) (Vol. 6345, pp. 151–167). Presented at the ESORICS: European Symposium on Research in Computer Security, Springer. <a href=\"https://doi.org/10.1007/978-3-642-15497-3\">https://doi.org/10.1007/978-3-642-15497-3</a>","mla":"Almeida, José, et al. <i>A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols</i>. Edited by Dimitris Gritzalis et al., vol. 6345, Springer, 2010, pp. 151–67, doi:<a href=\"https://doi.org/10.1007/978-3-642-15497-3\">10.1007/978-3-642-15497-3</a>.","ama":"Almeida J, Bangerter E, Barbosa M, Krenn S, Sadeghi A, Schneider T. A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols. In: Gritzalis D, Preneel B, Theoharidou M, eds. Vol 6345. Springer; 2010:151-167. doi:<a href=\"https://doi.org/10.1007/978-3-642-15497-3\">10.1007/978-3-642-15497-3</a>","ieee":"J. Almeida, E. Bangerter, M. Barbosa, S. Krenn, A. Sadeghi, and T. Schneider, “A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols,” presented at the ESORICS: European Symposium on Research in Computer Security, 2010, vol. 6345, pp. 151–167.","short":"J. Almeida, E. Bangerter, M. Barbosa, S. Krenn, A. Sadeghi, T. Schneider, in:, D. Gritzalis, B. Preneel, M. Theoharidou (Eds.), Springer, 2010, pp. 151–167."},"month":"08","year":"2010","publist_id":"3724","intvolume":"      6345","abstract":[{"lang":"eng","text":"Zero-knowledge proofs of knowledge (ZK-PoK) are important building blocks for numerous cryptographic applications. Although ZK-PoK have a high potential impact, their real world deployment is  typically hindered by their significant complexity compared to other (non-interactive) crypto primitives. Moreover, their design and implementation are time-consuming and error-prone.\n\nWe contribute to overcoming these challenges as follows: We present a comprehensive specification language and a compiler for ZK-PoK protocols based on Σ-protocols. The compiler allows the fully automatic translation of an abstract description of a proof goal into an executable implementation. Moreover, the compiler overcomes various restrictions of previous approaches, e.g., it supports the important class of exponentiation homomorphisms with hidden-order co-domain,  needed for privacy-preserving applications such as DAA. Finally, our compiler is certifying, in the sense that it automatically produces a formal proof of the soundness of the compiled protocol for a large class of protocols using the Isabelle/HOL theorem prover. \n"}],"page":"151 - 167","publication_status":"published","quality_controlled":0,"main_file_link":[{"url":"http://eprint.iacr.org/2010/339.pdf","open_access":"1"}],"editor":[{"first_name":"Dimitris","full_name":"Gritzalis, Dimitris","last_name":"Gritzalis"},{"last_name":"Preneel","full_name":"Preneel, Bart","first_name":"Bart"},{"last_name":"Theoharidou","full_name":"Theoharidou, Marianthi","first_name":"Marianthi"}],"title":"A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols","publisher":"Springer","author":[{"first_name":"José","full_name":"Almeida, José Bacelar","last_name":"Almeida"},{"first_name":"Endre","full_name":"Bangerter, Endre","last_name":"Bangerter"},{"last_name":"Barbosa","full_name":"Barbosa, Manuel","first_name":"Manuel"},{"first_name":"Stephan","orcid":"0000-0003-2835-9093","last_name":"Krenn","id":"329FCCF0-F248-11E8-B48F-1D18A9856A87","full_name":"Stephan Krenn"},{"full_name":"Sadeghi, Ahmad-Reza","last_name":"Sadeghi","first_name":"Ahmad"},{"full_name":"Schneider, Thomas","last_name":"Schneider","first_name":"Thomas"}],"doi":"10.1007/978-3-642-15497-3","day":"30","alternative_title":["LNCS"],"type":"conference","date_created":"2018-12-11T12:00:40Z","date_updated":"2021-01-12T07:40:13Z","_id":"2979","volume":6345},{"oa":1,"status":"public","extern":1,"citation":{"chicago":"Bangerter, Endre, Thomas Briner, Wilko Henecka, Stephan Krenn, Ahmad Sadeghi, and Thomas Schneider. “Automatic Generation of Sigma-Protocols.” edited by Fabio Martinelli and Bart Preneel, 6391:67–82. Springer, 2010. <a href=\"https://doi.org/10.1007/978-3-642-16441-5\">https://doi.org/10.1007/978-3-642-16441-5</a>.","ista":"Bangerter E, Briner T, Henecka W, Krenn S, Sadeghi A, Schneider T. 2010. Automatic Generation of Sigma-Protocols. EuroPKI: Public Key Infrastructures, Services and Applications, LNCS, vol. 6391, 67–82.","mla":"Bangerter, Endre, et al. <i>Automatic Generation of Sigma-Protocols</i>. Edited by Fabio Martinelli and Bart Preneel, vol. 6391, Springer, 2010, pp. 67–82, doi:<a href=\"https://doi.org/10.1007/978-3-642-16441-5\">10.1007/978-3-642-16441-5</a>.","apa":"Bangerter, E., Briner, T., Henecka, W., Krenn, S., Sadeghi, A., &#38; Schneider, T. (2010). Automatic Generation of Sigma-Protocols. In F. Martinelli &#38; B. Preneel (Eds.) (Vol. 6391, pp. 67–82). Presented at the EuroPKI: Public Key Infrastructures, Services and Applications, Springer. <a href=\"https://doi.org/10.1007/978-3-642-16441-5\">https://doi.org/10.1007/978-3-642-16441-5</a>","ama":"Bangerter E, Briner T, Henecka W, Krenn S, Sadeghi A, Schneider T. Automatic Generation of Sigma-Protocols. In: Martinelli F, Preneel B, eds. Vol 6391. Springer; 2010:67-82. doi:<a href=\"https://doi.org/10.1007/978-3-642-16441-5\">10.1007/978-3-642-16441-5</a>","short":"E. Bangerter, T. Briner, W. Henecka, S. Krenn, A. Sadeghi, T. Schneider, in:, F. Martinelli, B. Preneel (Eds.), Springer, 2010, pp. 67–82.","ieee":"E. Bangerter, T. Briner, W. Henecka, S. Krenn, A. Sadeghi, and T. Schneider, “Automatic Generation of Sigma-Protocols,” presented at the EuroPKI: Public Key Infrastructures, Services and Applications, 2010, vol. 6391, pp. 67–82."},"acknowledgement":"This work was performed within the FP7 EU project CACE (Computer Aided Cryptography Engineering).","conference":{"name":"EuroPKI: Public Key Infrastructures, Services and Applications"},"date_published":"2010-10-25T00:00:00Z","year":"2010","month":"10","publist_id":"3723","page":"67 - 82","intvolume":"      6391","abstract":[{"text":"Efficient zero-knowledge proofs of knowledge (ZK-PoK) are basic\n  building blocks of many practical cryptographic applications such as\n  identification schemes, group signatures, and secure multi-party\n  computation (SMPC). Currently, first applications that essentially\n  rely on ZK-PoKs are being deployed in the real world. The most\n  prominent example is the Direct Anonymous Attestation (DAA)\n  protocol, which was adopted by the Trusted Computing Group (TCG) \n  and implemented as one of the functionalities of the cryptographic \n  chip Trusted Platform Module (TPM).\n\nImplementing systems using ZK-PoK turns out to be challenging,\n  since ZK-PoK are significantly more complex than standard crypto\n  primitives (e.g., encryption and signature schemes). As a result, \n  the design-implementation cycles of ZK-PoK are time-consuming\n  and error-prone.\n\nTo overcome this, we present a compiler with corresponding languages \n  for the automatic generation of sound and efficient ZK-PoK based on \n  Σ-protocols. The protocol designer using our compiler formulates \n  the goal of a ZK-PoK proof in a high-level protocol specification language,\n  which abstracts away unnecessary technicalities from the designer. The\n  compiler then automatically generates the protocol implementation in \n  Java code; alternatively, the compiler can output a description of the \n  protocol in LaTeX which can be used for documentation or verification.","lang":"eng"}],"main_file_link":[{"open_access":"1","url":"http://eprint.iacr.org/2008/471.pdf"}],"publication_status":"published","quality_controlled":0,"author":[{"first_name":"Endre","last_name":"Bangerter","full_name":"Bangerter, Endre"},{"first_name":"Thomas","last_name":"Briner","full_name":"Briner, Thomas"},{"last_name":"Henecka","full_name":"Henecka, Wilko","first_name":"Wilko"},{"first_name":"Stephan","orcid":"0000-0003-2835-9093","id":"329FCCF0-F248-11E8-B48F-1D18A9856A87","full_name":"Stephan Krenn","last_name":"Krenn"},{"first_name":"Ahmad","full_name":"Sadeghi, Ahmad-Reza","last_name":"Sadeghi"},{"last_name":"Schneider","full_name":"Schneider, Thomas","first_name":"Thomas"}],"doi":"10.1007/978-3-642-16441-5","day":"25","alternative_title":["LNCS"],"editor":[{"full_name":"Martinelli, Fabio","last_name":"Martinelli","first_name":"Fabio"},{"full_name":"Preneel, Bart","last_name":"Preneel","first_name":"Bart"}],"title":"Automatic Generation of Sigma-Protocols","publisher":"Springer","date_updated":"2021-01-12T07:40:13Z","_id":"2980","volume":6391,"type":"conference","date_created":"2018-12-11T12:00:40Z"}]