--- _id: '1479' 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." 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" author: - first_name: Stephan full_name: Krenn, Stephan id: 329FCCF0-F248-11E8-B48F-1D18A9856A87 last_name: Krenn orcid: 0000-0003-2835-9093 - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 - first_name: Akshay full_name: Wadia, Akshay last_name: Wadia - first_name: Daniel full_name: Wichs, Daniel last_name: Wichs citation: ama: Krenn S, Pietrzak KZ, Wadia A, Wichs D. A counterexample to the chain rule for conditional HILL entropy. Computational Complexity. 2016;25(3):567-605. doi:10.1007/s00037-015-0120-9 apa: Krenn, S., Pietrzak, K. Z., Wadia, A., & Wichs, D. (2016). A counterexample to the chain rule for conditional HILL entropy. Computational Complexity. Springer. https://doi.org/10.1007/s00037-015-0120-9 chicago: Krenn, Stephan, Krzysztof Z Pietrzak, Akshay Wadia, and Daniel Wichs. “A Counterexample to the Chain Rule for Conditional HILL Entropy.” Computational Complexity. Springer, 2016. https://doi.org/10.1007/s00037-015-0120-9. ieee: S. Krenn, K. Z. Pietrzak, A. Wadia, and D. Wichs, “A counterexample to the chain rule for conditional HILL entropy,” Computational Complexity, vol. 25, no. 3. Springer, pp. 567–605, 2016. 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. mla: Krenn, Stephan, et al. “A Counterexample to the Chain Rule for Conditional HILL Entropy.” Computational Complexity, vol. 25, no. 3, Springer, 2016, pp. 567–605, doi:10.1007/s00037-015-0120-9. short: S. Krenn, K.Z. Pietrzak, A. Wadia, D. Wichs, Computational Complexity 25 (2016) 567–605. date_created: 2018-12-11T11:52:16Z date_published: 2016-09-01T00:00:00Z date_updated: 2023-02-23T11:05:09Z day: '01' ddc: - '004' department: - _id: KrPi doi: 10.1007/s00037-015-0120-9 ec_funded: 1 file: - access_level: open_access checksum: 7659296174fa75f5f0364f31f46f4bcf content_type: application/pdf creator: system date_created: 2018-12-12T10:13:29Z date_updated: 2020-07-14T12:44:56Z file_id: '5012' file_name: IST-2017-766-v1+1_678.pdf file_size: 483258 relation: main_file file_date_updated: 2020-07-14T12:44:56Z has_accepted_license: '1' intvolume: ' 25' issue: '3' language: - iso: eng month: '09' oa: 1 oa_version: Submitted Version page: 567 - 605 project: - _id: 258C570E-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '259668' name: Provable Security for Physical Cryptography publication: Computational Complexity publication_status: published publisher: Springer publist_id: '5715' pubrep_id: '766' quality_controlled: '1' related_material: record: - id: '2940' relation: earlier_version status: public scopus_import: 1 status: public title: A counterexample to the chain rule for conditional HILL entropy tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 25 year: '2016' ... --- _id: '2259' abstract: - lang: eng 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" alternative_title: - LNCS author: - first_name: Joel F full_name: Alwen, Joel F id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87 last_name: Alwen - first_name: Stephan full_name: Krenn, Stephan id: 329FCCF0-F248-11E8-B48F-1D18A9856A87 last_name: Krenn orcid: 0000-0003-2835-9093 - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 - first_name: Daniel full_name: Wichs, Daniel last_name: Wichs citation: ama: 'Alwen JF, Krenn S, Pietrzak KZ, Wichs D. Learning with rounding, revisited: New reduction properties and applications. 2013;8042(1):57-74. doi:10.1007/978-3-642-40041-4_4' apa: 'Alwen, J. F., Krenn, S., Pietrzak, K. Z., & 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. https://doi.org/10.1007/978-3-642-40041-4_4' 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. https://doi.org/10.1007/978-3-642-40041-4_4.' 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.' ista: 'Alwen JF, Krenn S, Pietrzak KZ, Wichs D. 2013. Learning with rounding, revisited: New reduction properties and applications. 8042(1), 57–74.' mla: 'Alwen, Joel F., et al. Learning with Rounding, Revisited: New Reduction Properties and Applications. Vol. 8042, no. 1, Springer, 2013, pp. 57–74, doi:10.1007/978-3-642-40041-4_4.' short: J.F. Alwen, S. Krenn, K.Z. Pietrzak, D. Wichs, 8042 (2013) 57–74. conference: end_date: 2013-08-22 location: Santa Barbara, CA, United States name: 'CRYPTO: International Cryptology Conference' start_date: 2013-08-18 date_created: 2018-12-11T11:56:37Z date_published: 2013-01-01T00:00:00Z date_updated: 2021-01-12T06:56:21Z day: '01' ddc: - '000' - '004' department: - _id: KrPi doi: 10.1007/978-3-642-40041-4_4 ec_funded: 1 file: - access_level: open_access checksum: 16d428408a806b8e49eecc607deab115 content_type: application/pdf creator: system date_created: 2018-12-12T10:11:55Z date_updated: 2020-07-14T12:45:35Z file_id: '4912' file_name: IST-2016-684-v1+1_098.pdf file_size: 587898 relation: main_file file_date_updated: 2020-07-14T12:45:35Z has_accepted_license: '1' intvolume: ' 8042' issue: '1' language: - iso: eng month: '01' oa: 1 oa_version: Published Version page: 57 - 74 project: - _id: 258C570E-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '259668' name: Provable Security for Physical Cryptography publication_status: published publisher: Springer publist_id: '4687' pubrep_id: '684' quality_controlled: '1' scopus_import: 1 series_title: Lecture Notes in Computer Science status: public title: 'Learning with rounding, revisited: New reduction properties and applications' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8042 year: '2013' ... --- _id: '2940' 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)>= H(X)-l. More generally, it satisfies a chain rule for conditional entropy if H(X|Y,A)>= 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)>>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. " alternative_title: - LNCS author: - first_name: Stephan full_name: Krenn, Stephan id: 329FCCF0-F248-11E8-B48F-1D18A9856A87 last_name: Krenn orcid: 0000-0003-2835-9093 - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 - first_name: Akshay full_name: Wadia, Akshay last_name: Wadia 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:10.1007/978-3-642-36594-2_2' apa: 'Krenn, S., Pietrzak, K. Z., & 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. https://doi.org/10.1007/978-3-642-36594-2_2' 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. https://doi.org/10.1007/978-3-642-36594-2_2. 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.' 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.' mla: Krenn, Stephan, et al. A Counterexample to the Chain Rule for Conditional HILL Entropy, and What Deniable Encryption Has to Do with It. Edited by Amit Sahai, vol. 7785, Springer, 2013, pp. 23–39, doi:10.1007/978-3-642-36594-2_2. short: S. Krenn, K.Z. Pietrzak, A. Wadia, in:, A. Sahai (Ed.), Springer, 2013, pp. 23–39. conference: end_date: 2013-03-06 location: Tokyo, Japan name: 'TCC: Theory of Cryptography Conference' start_date: 2013-03-03 date_created: 2018-12-11T12:00:27Z date_published: 2013-01-29T00:00:00Z date_updated: 2023-02-23T10:00:43Z day: '29' ddc: - '000' department: - _id: KrPi doi: 10.1007/978-3-642-36594-2_2 ec_funded: 1 editor: - first_name: Amit full_name: Sahai, Amit last_name: Sahai file: - access_level: open_access checksum: beb0cc1c0579da2d2e84394230a5da78 content_type: application/pdf creator: dernst date_created: 2019-01-22T14:11:11Z date_updated: 2020-07-14T12:45:54Z file_id: '5875' file_name: 2013_LNCS_Krenn.pdf file_size: 414823 relation: main_file file_date_updated: 2020-07-14T12:45:54Z has_accepted_license: '1' intvolume: ' 7785' language: - iso: eng month: '01' oa: 1 oa_version: Submitted Version page: 23 - 39 project: - _id: 258C570E-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '259668' name: Provable Security for Physical Cryptography publication_status: published publisher: Springer publist_id: '3795' quality_controlled: '1' related_material: record: - id: '1479' relation: later_version status: public scopus_import: 1 status: public title: A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 7785 year: '2013' ... --- _id: '2973' abstract: - lang: eng 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." acknowledgement: This work is being performed within the FP7 EU project CACE (Computer Aided Cryptography Engineering). alternative_title: - LNCS author: - first_name: Endre full_name: Bangerter, Endre last_name: Bangerter - first_name: Stefania full_name: Barzan, Stefania last_name: Barzan - first_name: Stephan full_name: Stephan Krenn id: 329FCCF0-F248-11E8-B48F-1D18A9856A87 last_name: Krenn orcid: 0000-0003-2835-9093 - first_name: Ahmad full_name: Sadeghi, Ahmad-Reza last_name: Sadeghi - first_name: Thomas full_name: Schneider, Thomas last_name: Schneider - first_name: Joe full_name: Tsay, Joe-Kai last_name: Tsay citation: 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:10.1007/978-3-642-36213-2_9' apa: 'Bangerter, E., Barzan, S., Krenn, S., Sadeghi, A., Schneider, T., & Tsay, J. (2013). Bringing Zero-Knowledge Proofs of Knowledge to Practice. In B. Christianson, J. Malcolm, V. Matyas, & M. Roe (Eds.) (Vol. 7028, pp. 51–62). Presented at the SPW: Security Protocols Workshop, Springer. https://doi.org/10.1007/978-3-642-36213-2_9' 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. https://doi.org/10.1007/978-3-642-36213-2_9. 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.' 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.' mla: Bangerter, Endre, et al. Bringing Zero-Knowledge Proofs of Knowledge to Practice. Edited by Bruce Christianson et al., vol. 7028, Springer, 2013, pp. 51–62, doi:10.1007/978-3-642-36213-2_9. 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. conference: name: 'SPW: Security Protocols Workshop' date_created: 2018-12-11T12:00:38Z date_published: 2013-01-08T00:00:00Z date_updated: 2021-01-12T07:40:10Z day: '08' doi: 10.1007/978-3-642-36213-2_9 editor: - first_name: Bruce full_name: Christianson, Bruce last_name: Christianson - first_name: James full_name: Malcolm, James A. last_name: Malcolm - first_name: Vashek full_name: Matyas, Vashek last_name: Matyas - first_name: Michael full_name: Roe, Michael last_name: Roe extern: 1 intvolume: ' 7028' main_file_link: - open_access: '1' url: http://eprint.iacr.org/2009/211.pdf month: '01' oa: 1 page: 51 - 62 publication_status: published publisher: Springer publist_id: '3732' quality_controlled: 0 status: public title: Bringing Zero-Knowledge Proofs of Knowledge to Practice type: conference volume: 7028 year: '2013' ... --- _id: '2937' 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. 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. author: - first_name: José full_name: Almeida, José last_name: Almeida - first_name: Manuel full_name: Barbosa, Manuel last_name: Barbosa - first_name: Endre full_name: Bangerter, Endre last_name: Bangerter - first_name: Gilles full_name: Barthe, Gilles last_name: Barthe - first_name: Stephan full_name: Krenn, Stephan id: 329FCCF0-F248-11E8-B48F-1D18A9856A87 last_name: Krenn orcid: 0000-0003-2835-9093 - first_name: Santiago full_name: Béguelin, Santiago last_name: Béguelin 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: Proceedings of the 2012 ACM Conference on Computer and Communications Security. ACM; 2012:488-500. doi:10.1145/2382196.2382249' apa: 'Almeida, J., Barbosa, M., Bangerter, E., Barthe, G., Krenn, S., & Béguelin, S. (2012). Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols. In Proceedings of the 2012 ACM conference on Computer and communications security (pp. 488–500). Raleigh, NC, USA: ACM. https://doi.org/10.1145/2382196.2382249' 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 Proceedings of the 2012 ACM Conference on Computer and Communications Security, 488–500. ACM, 2012. https://doi.org/10.1145/2382196.2382249.' 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 Proceedings of the 2012 ACM conference on Computer and communications security, Raleigh, NC, USA, 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.' mla: 'Almeida, José, et al. “Full Proof Cryptography: Verifiable Compilation of Efficient Zero-Knowledge Protocols.” Proceedings of the 2012 ACM Conference on Computer and Communications Security, ACM, 2012, pp. 488–500, doi:10.1145/2382196.2382249.' 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. conference: end_date: 2012-10-18 location: Raleigh, NC, USA name: 'CCS: Computer and Communications Security' start_date: 2012-10-16 date_created: 2018-12-11T12:00:26Z date_published: 2012-10-01T00:00:00Z date_updated: 2021-01-12T07:39:53Z day: '01' department: - _id: KrPi doi: 10.1145/2382196.2382249 language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2012/258 month: '10' oa: 1 oa_version: Submitted Version page: 488 - 500 publication: Proceedings of the 2012 ACM conference on Computer and communications security publication_status: published publisher: ACM publist_id: '3798' quality_controlled: '1' scopus_import: 1 status: public title: 'Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols' type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 year: '2012' ... --- _id: '2974' 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." acknowledgement: "We are grateful to Petros Mol for helpful discussions on the reduction for the hardness of the xLPN problem.\r\n" alternative_title: - LNCS author: - first_name: Abhishek full_name: Jain, Abhishek last_name: Jain - first_name: Stephan full_name: Krenn, Stephan id: 329FCCF0-F248-11E8-B48F-1D18A9856A87 last_name: Krenn orcid: 0000-0003-2835-9093 - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 - first_name: Aris full_name: Tentes, Aris last_name: Tentes citation: 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:10.1007/978-3-642-34961-4_40' apa: 'Jain, A., Krenn, S., Pietrzak, K. Z., & Tentes, A. (2012). Commitments and efficient zero knowledge proofs from learning parity with noise. In X. Wang & K. Sako (Eds.) (Vol. 7658, pp. 663–680). Presented at the ASIACRYPT: Theory and Application of Cryptology and Information Security, Beijing, China: Springer. https://doi.org/10.1007/978-3-642-34961-4_40' 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. https://doi.org/10.1007/978-3-642-34961-4_40. 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.' 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.' mla: Jain, Abhishek, et al. Commitments and Efficient Zero Knowledge Proofs from Learning Parity with Noise. Edited by Xiaoyun Wang and Kazue Sako, vol. 7658, Springer, 2012, pp. 663–80, doi:10.1007/978-3-642-34961-4_40. short: A. Jain, S. Krenn, K.Z. Pietrzak, A. Tentes, in:, X. Wang, K. Sako (Eds.), Springer, 2012, pp. 663–680. conference: end_date: 2012-12-06 location: Beijing, China name: 'ASIACRYPT: Theory and Application of Cryptology and Information Security' start_date: 2012-12-02 date_created: 2018-12-11T12:00:38Z date_published: 2012-12-01T00:00:00Z date_updated: 2021-01-12T07:40:11Z day: '01' ddc: - '004' - '005' department: - _id: KrPi doi: 10.1007/978-3-642-34961-4_40 ec_funded: 1 editor: - first_name: Xiaoyun full_name: Wang, Xiaoyun last_name: Wang - first_name: Kazue full_name: Sako, Kazue last_name: Sako file: - access_level: open_access checksum: ab879537385efc4cb4203e7ef0fea17b content_type: application/pdf creator: system date_created: 2018-12-12T10:14:00Z date_updated: 2020-07-14T12:45:58Z file_id: '5048' file_name: IST-2016-721-v1+1_513.pdf file_size: 482570 relation: main_file file_date_updated: 2020-07-14T12:45:58Z has_accepted_license: '1' intvolume: ' 7658' language: - iso: eng month: '12' oa: 1 oa_version: Submitted Version page: 663 - 680 project: - _id: 258C570E-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '259668' name: Provable Security for Physical Cryptography publication_status: published publisher: Springer publist_id: '3730' pubrep_id: '721' scopus_import: 1 status: public title: Commitments and efficient zero knowledge proofs from learning parity with noise tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 7658 year: '2012' ... --- _id: '2975' 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." 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. alternative_title: - LNCS author: - first_name: Jan full_name: Camenisch, Jan last_name: Camenisch - first_name: Stephan full_name: Stephan Krenn id: 329FCCF0-F248-11E8-B48F-1D18A9856A87 last_name: Krenn orcid: 0000-0003-2835-9093 - first_name: Victor full_name: Shoup, Victor last_name: Shoup 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:10.1007/978-3-642-25385-0' apa: 'Camenisch, J., Krenn, S., & Shoup, V. (2011). A Framework for Practical Universally Composable Zero-Knowledge Protocols. In D. Lee & X. Wang (Eds.) (Vol. 7073, pp. 449–467). Presented at the ASIACRYPT: Theory and Application of Cryptology and Information Security, Springer. https://doi.org/10.1007/978-3-642-25385-0' 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. https://doi.org/10.1007/978-3-642-25385-0. 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.' 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.' mla: Camenisch, Jan, et al. A Framework for Practical Universally Composable Zero-Knowledge Protocols. Edited by Dong Lee and Xiaoyun Wang, vol. 7073, Springer, 2011, pp. 449–67, doi:10.1007/978-3-642-25385-0. short: J. Camenisch, S. Krenn, V. Shoup, in:, D. Lee, X. Wang (Eds.), Springer, 2011, pp. 449–467. conference: name: 'ASIACRYPT: Theory and Application of Cryptology and Information Security' date_created: 2018-12-11T12:00:39Z date_published: 2011-11-21T00:00:00Z date_updated: 2021-01-12T07:40:11Z day: '21' doi: 10.1007/978-3-642-25385-0 editor: - first_name: Dong full_name: Lee, Dong Hoon last_name: Lee - first_name: Xiaoyun full_name: Wang, Xiaoyun last_name: Wang extern: 1 intvolume: ' 7073' main_file_link: - open_access: '0' url: http://eprint.iacr.org/2011/228.pdf month: '11' page: 449 - 467 publication_status: published publisher: Springer publist_id: '3728' quality_controlled: 0 status: public title: A Framework for Practical Universally Composable Zero-Knowledge Protocols type: conference volume: 7073 year: '2011' ... --- _id: '2977' 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." 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. author: - first_name: Endre full_name: Bangerter, Endre last_name: Bangerter - first_name: Stephan full_name: Stephan Krenn id: 329FCCF0-F248-11E8-B48F-1D18A9856A87 last_name: Krenn orcid: 0000-0003-2835-9093 - first_name: Martial full_name: Seifriz, Martial last_name: Seifriz - first_name: Ulrich full_name: Ultes-Nitsche, Ulrich last_name: Ultes Nitsche citation: 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:10.1109/ISSA.2011.6027533' apa: 'Bangerter, E., Krenn, S., Seifriz, M., & Ultes Nitsche, U. (2011). cPLC - A Cryptographic Programming Language and Compiler. In H. Venter, M. Coetzee, & M. Loock (Eds.). Presented at the ISSA: Information Security South Africa, IEEE. https://doi.org/10.1109/ISSA.2011.6027533' 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. https://doi.org/10.1109/ISSA.2011.6027533. 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.' ista: 'Bangerter E, Krenn S, Seifriz M, Ultes Nitsche U. 2011. cPLC - A Cryptographic Programming Language and Compiler. ISSA: Information Security South Africa.' mla: Bangerter, Endre, et al. CPLC - A Cryptographic Programming Language and Compiler. Edited by Hein Venter et al., IEEE, 2011, doi:10.1109/ISSA.2011.6027533. short: E. Bangerter, S. Krenn, M. Seifriz, U. Ultes Nitsche, in:, H. Venter, M. Coetzee, M. Loock (Eds.), IEEE, 2011. conference: name: 'ISSA: Information Security South Africa' date_created: 2018-12-11T12:00:39Z date_published: 2011-08-01T00:00:00Z date_updated: 2021-01-12T07:40:12Z day: '01' doi: 10.1109/ISSA.2011.6027533 editor: - first_name: Hein full_name: Venter, Hein S. last_name: Venter - first_name: Marijke full_name: Coetzee, Marijke last_name: Coetzee - first_name: Marianne full_name: Loock, Marianne last_name: Loock extern: 1 month: '08' publication_status: published publisher: IEEE publist_id: '3726' quality_controlled: 0 status: public title: cPLC - A Cryptographic Programming Language and Compiler type: conference year: '2011' ... --- _id: '2976' abstract: - lang: eng text: |- Side channel attacks on cryptographic systems exploit information gained from physical implementations rather than theoretical weaknesses of a scheme. In recent years, major achievements were made for the class of so called access-driven cache attacks. Such attacks exploit the leakage of the memory locations accessed by a victim process. In this paper we consider the AES block cipher and present an attack which is capable of recovering the full secret key in almost realtime for AES-128, requiring only a very limited number of observed encryptions. Unlike previous attacks, we do not require any information about the plaintext (such as its distribution, etc.). Moreover, for the first time, we also show how the plaintext can be recovered without having access to the ciphertext at all. It is the first working attack on AES implementations using compressed tables. There, no efficient techniques to identify the beginning of AES rounds is known, which is the fundamental assumption underlying previous attacks. We have a fully working implementation of our attack which is able to recover AES keys after observing as little as 100 encryptions. It works against the OpenSSL 0.9.8n implementation of AES on Linux systems. Our spy process does not require any special privileges beyond those of a standard Linux user. A contribution of probably independent interest is a denial of service attack on the task scheduler of current Linux systems (CFS), which allows one to observe (on average) every single memory access of a victim process. 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. An extended abstract was also accepted for COSADE 2011. author: - first_name: David full_name: Gullasch, David last_name: Gullasch - first_name: Endre full_name: Bangerter, Endre last_name: Bangerter - first_name: Stephan full_name: Stephan Krenn id: 329FCCF0-F248-11E8-B48F-1D18A9856A87 last_name: Krenn orcid: 0000-0003-2835-9093 citation: ama: 'Gullasch D, Bangerter E, Krenn S. Cache Games - Bringing Access-Based Cache Attacks on AES to Practice. In: IEEE; 2011:490-505. doi:10.1109/SP.2011.22' apa: 'Gullasch, D., Bangerter, E., & Krenn, S. (2011). Cache Games - Bringing Access-Based Cache Attacks on AES to Practice (pp. 490–505). Presented at the S&P: IEEE Symposium on Security and Privacy, IEEE. https://doi.org/10.1109/SP.2011.22' chicago: Gullasch, David, Endre Bangerter, and Stephan Krenn. “Cache Games - Bringing Access-Based Cache Attacks on AES to Practice,” 490–505. IEEE, 2011. https://doi.org/10.1109/SP.2011.22. ieee: 'D. Gullasch, E. Bangerter, and S. Krenn, “Cache Games - Bringing Access-Based Cache Attacks on AES to Practice,” presented at the S&P: IEEE Symposium on Security and Privacy, 2011, pp. 490–505.' ista: 'Gullasch D, Bangerter E, Krenn S. 2011. Cache Games - Bringing Access-Based Cache Attacks on AES to Practice. S&P: IEEE Symposium on Security and Privacy, 490–505.' mla: Gullasch, David, et al. Cache Games - Bringing Access-Based Cache Attacks on AES to Practice. IEEE, 2011, pp. 490–505, doi:10.1109/SP.2011.22. short: D. Gullasch, E. Bangerter, S. Krenn, in:, IEEE, 2011, pp. 490–505. conference: name: 'S&P: IEEE Symposium on Security and Privacy' date_created: 2018-12-11T12:00:39Z date_published: 2011-01-01T00:00:00Z date_updated: 2021-01-12T07:40:11Z day: '01' doi: 10.1109/SP.2011.22 extern: 1 main_file_link: - open_access: '0' url: http://eprint.iacr.org/2010/594.pdf month: '01' page: 490 - 505 publication_status: published publisher: IEEE publist_id: '3727' quality_controlled: 0 status: public title: Cache Games - Bringing Access-Based Cache Attacks on AES to Practice type: conference year: '2011' ... --- _id: '2979' 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" acknowledgement: |- This work was in part funded by the European Community's Seventh Framework Programme (FP7) under grant agreement no. 216499. A preliminary version of the compiler can be found at http://zkc.cace-project.eu. alternative_title: - LNCS author: - first_name: José full_name: Almeida, José Bacelar last_name: Almeida - first_name: Endre full_name: Bangerter, Endre last_name: Bangerter - first_name: Manuel full_name: Barbosa, Manuel last_name: Barbosa - first_name: Stephan full_name: Stephan Krenn id: 329FCCF0-F248-11E8-B48F-1D18A9856A87 last_name: Krenn orcid: 0000-0003-2835-9093 - first_name: Ahmad full_name: Sadeghi, Ahmad-Reza last_name: Sadeghi - first_name: Thomas full_name: Schneider, Thomas last_name: Schneider citation: 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:10.1007/978-3-642-15497-3' apa: '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. In D. Gritzalis, B. Preneel, & M. Theoharidou (Eds.) (Vol. 6345, pp. 151–167). Presented at the ESORICS: European Symposium on Research in Computer Security, Springer. https://doi.org/10.1007/978-3-642-15497-3' 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. https://doi.org/10.1007/978-3-642-15497-3. 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.' 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.' mla: Almeida, José, et al. A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols. Edited by Dimitris Gritzalis et al., vol. 6345, Springer, 2010, pp. 151–67, doi:10.1007/978-3-642-15497-3. 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. conference: name: 'ESORICS: European Symposium on Research in Computer Security' date_created: 2018-12-11T12:00:40Z date_published: 2010-08-30T00:00:00Z date_updated: 2021-01-12T07:40:13Z day: '30' doi: 10.1007/978-3-642-15497-3 editor: - first_name: Dimitris full_name: Gritzalis, Dimitris last_name: Gritzalis - first_name: Bart full_name: Preneel, Bart last_name: Preneel - first_name: Marianthi full_name: Theoharidou, Marianthi last_name: Theoharidou extern: 1 intvolume: ' 6345' main_file_link: - open_access: '1' url: http://eprint.iacr.org/2010/339.pdf month: '08' oa: 1 page: 151 - 167 publication_status: published publisher: Springer publist_id: '3724' quality_controlled: 0 status: public title: A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols type: conference volume: 6345 year: '2010' ... --- _id: '2980' abstract: - lang: eng 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." acknowledgement: This work was performed within the FP7 EU project CACE (Computer Aided Cryptography Engineering). alternative_title: - LNCS author: - first_name: Endre full_name: Bangerter, Endre last_name: Bangerter - first_name: Thomas full_name: Briner, Thomas last_name: Briner - first_name: Wilko full_name: Henecka, Wilko last_name: Henecka - first_name: Stephan full_name: Stephan Krenn id: 329FCCF0-F248-11E8-B48F-1D18A9856A87 last_name: Krenn orcid: 0000-0003-2835-9093 - first_name: Ahmad full_name: Sadeghi, Ahmad-Reza last_name: Sadeghi - first_name: Thomas full_name: Schneider, Thomas last_name: Schneider citation: 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:10.1007/978-3-642-16441-5' apa: 'Bangerter, E., Briner, T., Henecka, W., Krenn, S., Sadeghi, A., & Schneider, T. (2010). Automatic Generation of Sigma-Protocols. In F. Martinelli & B. Preneel (Eds.) (Vol. 6391, pp. 67–82). Presented at the EuroPKI: Public Key Infrastructures, Services and Applications, Springer. https://doi.org/10.1007/978-3-642-16441-5' 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. https://doi.org/10.1007/978-3-642-16441-5. 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.' 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. Automatic Generation of Sigma-Protocols. Edited by Fabio Martinelli and Bart Preneel, vol. 6391, Springer, 2010, pp. 67–82, doi:10.1007/978-3-642-16441-5. short: E. Bangerter, T. Briner, W. Henecka, S. Krenn, A. Sadeghi, T. Schneider, in:, F. Martinelli, B. Preneel (Eds.), Springer, 2010, pp. 67–82. conference: name: 'EuroPKI: Public Key Infrastructures, Services and Applications' date_created: 2018-12-11T12:00:40Z date_published: 2010-10-25T00:00:00Z date_updated: 2021-01-12T07:40:13Z day: '25' doi: 10.1007/978-3-642-16441-5 editor: - first_name: Fabio full_name: Martinelli, Fabio last_name: Martinelli - first_name: Bart full_name: Preneel, Bart last_name: Preneel extern: 1 intvolume: ' 6391' main_file_link: - open_access: '1' url: http://eprint.iacr.org/2008/471.pdf month: '10' oa: 1 page: 67 - 82 publication_status: published publisher: Springer publist_id: '3723' quality_controlled: 0 status: public title: Automatic Generation of Sigma-Protocols type: conference volume: 6391 year: '2010' ... --- _id: '2978' 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. This 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. We 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. alternative_title: - LNCS author: - first_name: Endre full_name: Bangerter, Endre last_name: Bangerter - first_name: Jan full_name: Camenisch, Jan last_name: Camenisch - first_name: Stephan full_name: Stephan Krenn id: 329FCCF0-F248-11E8-B48F-1D18A9856A87 last_name: Krenn orcid: 0000-0003-2835-9093 citation: 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:10.1007/978-3-642-11799-2' apa: 'Bangerter, E., Camenisch, J., & 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. https://doi.org/10.1007/978-3-642-11799-2' chicago: Bangerter, Endre, Jan Camenisch, and Stephan Krenn. “Efficiency Limitations for Σ-Protocols for Group Homomorphisms.” edited by Daniele Micciancio, 5978:553–71. Springer, 2010. https://doi.org/10.1007/978-3-642-11799-2. 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.' 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.' mla: Bangerter, Endre, et al. Efficiency Limitations for Σ-Protocols for Group Homomorphisms. Edited by Daniele Micciancio, vol. 5978, Springer, 2010, pp. 553–71, doi:10.1007/978-3-642-11799-2. short: E. Bangerter, J. Camenisch, S. Krenn, in:, D. Micciancio (Ed.), Springer, 2010, pp. 553–571. conference: name: 'TCC: Theory of Cryptography Conference' date_created: 2018-12-11T12:00:39Z date_published: 2010-02-08T00:00:00Z date_updated: 2021-01-12T07:40:12Z day: '08' doi: 10.1007/978-3-642-11799-2 editor: - first_name: Daniele full_name: Micciancio, Daniele last_name: Micciancio extern: 1 intvolume: ' 5978' main_file_link: - open_access: '1' url: http://eprint.iacr.org/2009/595.pdf month: '02' oa: 1 page: 553 - 571 publication_status: published publisher: Springer publist_id: '3725' quality_controlled: 0 status: public title: Efficiency Limitations for Σ-Protocols for Group Homomorphisms type: conference volume: 5978 year: '2010' ...