--- _id: '650' abstract: - lang: eng text: 'In this work we present a short and unified proof for the Strong and Weak Regularity Lemma, based on the cryptographic tech-nique called low-complexity approximations. In short, both problems reduce to a task of finding constructively an approximation for a certain target function under a class of distinguishers (test functions), where dis-tinguishers are combinations of simple rectangle-indicators. In our case these approximations can be learned by a simple iterative procedure, which yields a unified and simple proof, achieving for any graph with density d and any approximation parameter the partition size. The novelty in our proof is: (a) a simple approach which yields both strong and weaker variant, and (b) improvements when d = o(1). At an abstract level, our proof can be seen a refinement and simplification of the “analytic” proof given by Lovasz and Szegedy.' alternative_title: - LNCS author: - first_name: Maciej full_name: Skórski, Maciej id: EC09FA6A-02D0-11E9-8223-86B7C91467DD last_name: Skórski citation: ama: 'Skórski M. A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds. In: Jäger G, Steila S, eds. Vol 10185. Springer; 2017:586-599. doi:10.1007/978-3-319-55911-7_42' apa: 'Skórski, M. (2017). A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds. In G. Jäger & S. Steila (Eds.) (Vol. 10185, pp. 586–599). Presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland: Springer. https://doi.org/10.1007/978-3-319-55911-7_42' chicago: 'Skórski, Maciej. “A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds.” edited by Gerhard Jäger and Silvia Steila, 10185:586–99. Springer, 2017. https://doi.org/10.1007/978-3-319-55911-7_42.' ieee: 'M. Skórski, “A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds,” presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland, 2017, vol. 10185, pp. 586–599.' ista: 'Skórski M. 2017. A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds. TAMC: Theory and Applications of Models of Computation, LNCS, vol. 10185, 586–599.' mla: 'Skórski, Maciej. A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds. Edited by Gerhard Jäger and Silvia Steila, vol. 10185, Springer, 2017, pp. 586–99, doi:10.1007/978-3-319-55911-7_42.' short: M. Skórski, in:, G. Jäger, S. Steila (Eds.), Springer, 2017, pp. 586–599. conference: end_date: 2017-04-22 location: Bern, Switzerland name: 'TAMC: Theory and Applications of Models of Computation' start_date: 2017-04-20 date_created: 2018-12-11T11:47:42Z date_published: 2017-01-01T00:00:00Z date_updated: 2021-01-12T08:07:46Z day: '01' department: - _id: KrPi doi: 10.1007/978-3-319-55911-7_42 editor: - first_name: Gerhard full_name: Jäger, Gerhard last_name: Jäger - first_name: Silvia full_name: Steila, Silvia last_name: Steila intvolume: ' 10185' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2016/965.pdf month: '01' oa: 1 oa_version: Submitted Version page: 586 - 599 publication_identifier: issn: - '03029743' publication_status: published publisher: Springer publist_id: '7119' quality_controlled: '1' scopus_import: 1 status: public title: 'A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds' type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 10185 year: '2017' ... --- _id: '6527' abstract: - lang: eng text: "A memory-hard function (MHF) ƒn with parameter n can be computed in sequential time and space n. Simultaneously, a high amortized parallel area-time complexity (aAT) is incurred per evaluation. In practice, MHFs are used to limit the rate at which an adversary (using a custom computational device) can evaluate a security sensitive function that still occasionally needs to be evaluated by honest users (using an off-the-shelf general purpose device). The most prevalent examples of such sensitive functions are Key Derivation Functions (KDFs) and password hashing algorithms where rate limits help mitigate off-line dictionary attacks. As the honest users' inputs to these functions are often (low-entropy) passwords special attention is given to a class of side-channel resistant MHFs called iMHFs.\r\n\r\nEssentially all iMHFs can be viewed as some mode of operation (making n calls to some round function) given by a directed acyclic graph (DAG) with very low indegree. Recently, a combinatorial property of a DAG has been identified (called \"depth-robustness\") which results in good provable security for an iMHF based on that DAG. Depth-robust DAGs have also proven useful in other cryptographic applications. Unfortunately, up till now, all known very depth-robust DAGs are impractically complicated and little is known about their exact (i.e. non-asymptotic) depth-robustness both in theory and in practice.\r\n\r\nIn this work we build and analyze (both formally and empirically) several exceedingly simple and efficient to navigate practical DAGs for use in iMHFs and other applications. For each DAG we:\r\n*Prove that their depth-robustness is asymptotically maximal.\r\n*Prove bounds of at least 3 orders of magnitude better on their exact depth-robustness compared to known bounds for other practical iMHF.\r\n*Implement and empirically evaluate their depth-robustness and aAT against a variety of state-of-the art (and several new) depth-reduction and low aAT attacks. \r\nWe find that, against all attacks, the new DAGs perform significantly better in practice than Argon2i, the most widely deployed iMHF in practice.\r\n\r\nAlong the way we also improve the best known empirical attacks on the aAT of Argon2i by implementing and testing several heuristic versions of a (hitherto purely theoretical) depth-reduction attack. Finally, we demonstrate practicality of our constructions by modifying the Argon2i code base to use one of the new high aAT DAGs. Experimental benchmarks on a standard off-the-shelf CPU show that the new modifications do not adversely affect the impressive throughput of Argon2i (despite seemingly enjoying significantly higher aAT).\r\n" author: - first_name: Joel F full_name: Alwen, Joel F id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87 last_name: Alwen - first_name: Jeremiah full_name: Blocki, Jeremiah last_name: Blocki - first_name: Ben full_name: Harsha, Ben last_name: Harsha citation: ama: 'Alwen JF, Blocki J, Harsha B. Practical graphs for optimal side-channel resistant memory-hard functions. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM Press; 2017:1001-1017. doi:10.1145/3133956.3134031' apa: 'Alwen, J. F., Blocki, J., & Harsha, B. (2017). Practical graphs for optimal side-channel resistant memory-hard functions. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (pp. 1001–1017). Dallas, TX, USA: ACM Press. https://doi.org/10.1145/3133956.3134031' chicago: Alwen, Joel F, Jeremiah Blocki, and Ben Harsha. “Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions.” In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 1001–17. ACM Press, 2017. https://doi.org/10.1145/3133956.3134031. ieee: J. F. Alwen, J. Blocki, and B. Harsha, “Practical graphs for optimal side-channel resistant memory-hard functions,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, TX, USA, 2017, pp. 1001–1017. ista: 'Alwen JF, Blocki J, Harsha B. 2017. Practical graphs for optimal side-channel resistant memory-hard functions. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. CCS: Conference on Computer and Communications Security, 1001–1017.' mla: Alwen, Joel F., et al. “Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions.” Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, ACM Press, 2017, pp. 1001–17, doi:10.1145/3133956.3134031. short: J.F. Alwen, J. Blocki, B. Harsha, in:, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, ACM Press, 2017, pp. 1001–1017. conference: end_date: 2017-11-03 location: Dallas, TX, USA name: 'CCS: Conference on Computer and Communications Security' start_date: 2017-10-30 date_created: 2019-06-06T13:21:29Z date_published: 2017-10-30T00:00:00Z date_updated: 2021-01-12T08:07:53Z day: '30' department: - _id: KrPi doi: 10.1145/3133956.3134031 ec_funded: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2017/443 month: '10' oa: 1 oa_version: Submitted Version page: 1001-1017 project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security publication_identifier: isbn: - '9781450349468' publication_status: published publisher: ACM Press quality_controlled: '1' scopus_import: 1 status: public title: Practical graphs for optimal side-channel resistant memory-hard functions type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2017' ... --- _id: '6526' abstract: - lang: eng text: 'This paper studies the complexity of estimating Rényi divergences of discrete distributions: p observed from samples and the baseline distribution q known a priori. Extending the results of Acharya et al. (SODA''15) on estimating Rényi entropy, we present improved estimation techniques together with upper and lower bounds on the sample complexity. We show that, contrarily to estimating Rényi entropy where a sublinear (in the alphabet size) number of samples suffices, the sample complexity is heavily dependent on events occurring unlikely in q, and is unbounded in general (no matter what an estimation technique is used). For any divergence of integer order bigger than 1, we provide upper and lower bounds on the number of samples dependent on probabilities of p and q (the lower bounds hold for non-integer orders as well). We conclude that the worst-case sample complexity is polynomial in the alphabet size if and only if the probabilities of q are non-negligible. This gives theoretical insights into heuristics used in the applied literature to handle numerical instability, which occurs for small probabilities of q. Our result shows that they should be handled with care not only because of numerical issues, but also because of a blow up in the sample complexity.' article_number: '8006529' author: - first_name: Maciej full_name: Skórski, Maciej id: EC09FA6A-02D0-11E9-8223-86B7C91467DD last_name: Skórski citation: ama: 'Skórski M. On the complexity of estimating Rènyi divergences. In: 2017 IEEE International Symposium on Information Theory (ISIT). IEEE; 2017. doi:10.1109/isit.2017.8006529' apa: 'Skórski, M. (2017). On the complexity of estimating Rènyi divergences. In 2017 IEEE International Symposium on Information Theory (ISIT). Aachen, Germany: IEEE. https://doi.org/10.1109/isit.2017.8006529' chicago: Skórski, Maciej. “On the Complexity of Estimating Rènyi Divergences.” In 2017 IEEE International Symposium on Information Theory (ISIT). IEEE, 2017. https://doi.org/10.1109/isit.2017.8006529. ieee: M. Skórski, “On the complexity of estimating Rènyi divergences,” in 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, 2017. ista: 'Skórski M. 2017. On the complexity of estimating Rènyi divergences. 2017 IEEE International Symposium on Information Theory (ISIT). ISIT: International Symposium on Information Theory, 8006529.' mla: Skórski, Maciej. “On the Complexity of Estimating Rènyi Divergences.” 2017 IEEE International Symposium on Information Theory (ISIT), 8006529, IEEE, 2017, doi:10.1109/isit.2017.8006529. short: M. Skórski, in:, 2017 IEEE International Symposium on Information Theory (ISIT), IEEE, 2017. conference: end_date: 2017-06-30 location: Aachen, Germany name: 'ISIT: International Symposium on Information Theory' start_date: 2017-06-25 date_created: 2019-06-06T12:53:09Z date_published: 2017-08-09T00:00:00Z date_updated: 2021-01-12T08:07:53Z day: '09' department: - _id: KrPi doi: 10.1109/isit.2017.8006529 ec_funded: 1 external_id: arxiv: - '1702.01666' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1702.01666 month: '08' oa: 1 oa_version: Preprint project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication: 2017 IEEE International Symposium on Information Theory (ISIT) publication_identifier: isbn: - '9781509040964' publication_status: published publisher: IEEE quality_controlled: '1' scopus_import: 1 status: public title: On the complexity of estimating Rènyi divergences type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 year: '2017' ... --- _id: '697' abstract: - lang: eng text: 'De, Trevisan and Tulsiani [CRYPTO 2010] show that every distribution over n-bit strings which has constant statistical distance to uniform (e.g., the output of a pseudorandom generator mapping n-1 to n bit strings), can be distinguished from the uniform distribution with advantage epsilon by a circuit of size O( 2^n epsilon^2). We generalize this result, showing that a distribution which has less than k bits of min-entropy, can be distinguished from any distribution with k bits of delta-smooth min-entropy with advantage epsilon by a circuit of size O(2^k epsilon^2/delta^2). As a special case, this implies that any distribution with support at most 2^k (e.g., the output of a pseudoentropy generator mapping k to n bit strings) can be distinguished from any given distribution with min-entropy k+1 with advantage epsilon by a circuit of size O(2^k epsilon^2). Our result thus shows that pseudoentropy distributions face basically the same non-uniform attacks as pseudorandom distributions. ' alternative_title: - LIPIcs article_number: '39' author: - 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: Maciej full_name: Skórski, Maciej id: EC09FA6A-02D0-11E9-8223-86B7C91467DD last_name: Skórski citation: ama: 'Pietrzak KZ, Skórski M. Non uniform attacks against pseudoentropy. In: Vol 80. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.ICALP.2017.39' apa: 'Pietrzak, K. Z., & Skórski, M. (2017). Non uniform attacks against pseudoentropy (Vol. 80). Presented at the ICALP: International Colloquium on Automata, Languages, and Programming, Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2017.39' chicago: Pietrzak, Krzysztof Z, and Maciej Skórski. “Non Uniform Attacks against Pseudoentropy,” Vol. 80. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.ICALP.2017.39. ieee: 'K. Z. Pietrzak and M. Skórski, “Non uniform attacks against pseudoentropy,” presented at the ICALP: International Colloquium on Automata, Languages, and Programming, Warsaw, Poland, 2017, vol. 80.' ista: 'Pietrzak KZ, Skórski M. 2017. Non uniform attacks against pseudoentropy. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 80, 39.' mla: Pietrzak, Krzysztof Z., and Maciej Skórski. Non Uniform Attacks against Pseudoentropy. Vol. 80, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.ICALP.2017.39. short: K.Z. Pietrzak, M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. conference: end_date: 2017-07-14 location: Warsaw, Poland name: 'ICALP: International Colloquium on Automata, Languages, and Programming' start_date: 2017-07-10 date_created: 2018-12-11T11:47:59Z date_published: 2017-07-01T00:00:00Z date_updated: 2021-01-12T08:11:15Z day: '01' ddc: - '005' department: - _id: KrPi doi: 10.4230/LIPIcs.ICALP.2017.39 ec_funded: 1 file: - access_level: open_access checksum: e95618a001692f1af2d68f5fde43bc1f content_type: application/pdf creator: system date_created: 2018-12-12T10:08:40Z date_updated: 2020-07-14T12:47:46Z file_id: '4701' file_name: IST-2017-893-v1+1_LIPIcs-ICALP-2017-39.pdf file_size: 601004 relation: main_file file_date_updated: 2020-07-14T12:47:46Z has_accepted_license: '1' intvolume: ' 80' language: - iso: eng month: '07' oa: 1 oa_version: Published Version project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication_identifier: issn: - '18688969' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik publist_id: '7003' pubrep_id: '893' quality_controlled: '1' scopus_import: 1 status: public title: Non uniform attacks against pseudoentropy 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: 80 year: '2017' ... --- _id: '710' abstract: - lang: eng text: 'We revisit the problem of estimating entropy of discrete distributions from independent samples, studied recently by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015), improving their upper and lower bounds on the necessary sample size n. For estimating Renyi entropy of order alpha, up to constant accuracy and error probability, we show the following * Upper bounds n = O(1) 2^{(1-1/alpha)H_alpha} for integer alpha>1, as the worst case over distributions with Renyi entropy equal to H_alpha. * Lower bounds n = Omega(1) K^{1-1/alpha} for any real alpha>1, with the constant being an inverse polynomial of the accuracy, as the worst case over all distributions on K elements. Our upper bounds essentially replace the alphabet size by a factor exponential in the entropy, which offers improvements especially in low or medium entropy regimes (interesting for example in anomaly detection). As for the lower bounds, our proof explicitly shows how the complexity depends on both alphabet and accuracy, partially solving the open problem posted in previous works. The argument for upper bounds derives a clean identity for the variance of falling-power sum of a multinomial distribution. Our approach for lower bounds utilizes convex optimization to find a distribution with possibly worse estimation performance, and may be of independent interest as a tool to work with Le Cam’s two point method. ' alternative_title: - LIPIcs article_number: '20' author: - first_name: Maciej full_name: Obremski, Maciej last_name: Obremski - first_name: Maciej full_name: Skórski, Maciej id: EC09FA6A-02D0-11E9-8223-86B7C91467DD last_name: Skórski citation: ama: 'Obremski M, Skórski M. Renyi entropy estimation revisited. In: Vol 81. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.APPROX-RANDOM.2017.20' apa: 'Obremski, M., & Skórski, M. (2017). Renyi entropy estimation revisited (Vol. 81). Presented at the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, Berkeley, USA: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20' chicago: Obremski, Maciej, and Maciej Skórski. “Renyi Entropy Estimation Revisited,” Vol. 81. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20. ieee: M. Obremski and M. Skórski, “Renyi entropy estimation revisited,” presented at the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, Berkeley, USA, 2017, vol. 81. ista: Obremski M, Skórski M. 2017. Renyi entropy estimation revisited. 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, LIPIcs, vol. 81, 20. mla: Obremski, Maciej, and Maciej Skórski. Renyi Entropy Estimation Revisited. Vol. 81, 20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.APPROX-RANDOM.2017.20. short: M. Obremski, M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. conference: end_date: 2017-08-18 location: Berkeley, USA name: 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX start_date: 2017-08-18 date_created: 2018-12-11T11:48:04Z date_published: 2017-08-01T00:00:00Z date_updated: 2021-01-12T08:11:50Z day: '01' ddc: - '005' - '600' department: - _id: KrPi doi: 10.4230/LIPIcs.APPROX-RANDOM.2017.20 ec_funded: 1 file: - access_level: open_access checksum: 89225c7dcec2c93838458c9102858985 content_type: application/pdf creator: system date_created: 2018-12-12T10:13:10Z date_updated: 2020-07-14T12:47:49Z file_id: '4991' file_name: IST-2017-888-v1+1_LIPIcs-APPROX-RANDOM-2017-20.pdf file_size: 604813 relation: main_file file_date_updated: 2020-07-14T12:47:49Z has_accepted_license: '1' intvolume: ' 81' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication_identifier: issn: - '18688969' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik publist_id: '6979' pubrep_id: '888' quality_controlled: '1' scopus_import: 1 status: public title: Renyi entropy estimation revisited 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: 81 year: '2017' ... --- _id: '838' abstract: - lang: eng text: 'In this thesis we discuss the exact security of message authentications codes HMAC , NMAC , and PMAC . NMAC is a mode of operation which turns a fixed input-length keyed hash function f into a variable input-length function. A practical single-key variant of NMAC called HMAC is a very popular and widely deployed message authentication code (MAC). PMAC is a block-cipher based mode of operation, which also happens to be the most famous fully parallel MAC. NMAC was introduced by Bellare, Canetti and Krawczyk Crypto’96, who proved it to be a secure pseudorandom function (PRF), and thus also a MAC, under two assumptions. Unfortunately, for many instantiations of HMAC one of them has been found to be wrong. To restore the provable guarantees for NMAC , Bellare [Crypto’06] showed its security without this assumption. PMAC was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a pseudorandom permutation over n -bit strings, PMAC constitutes a provably secure variable input-length PRF. For adversaries making q queries, each of length at most ` (in n -bit blocks), and of total length σ ≤ q` , the original paper proves an upper bound on the distinguishing advantage of O ( σ 2 / 2 n ), while the currently best bound is O ( qσ/ 2 n ). In this work we show that this bound is tight by giving an attack with advantage Ω( q 2 `/ 2 n ). In the PMAC construction one initially XORs a mask to every message block, where the mask for the i th block is computed as τ i := γ i · L , where L is a (secret) random value, and γ i is the i -th codeword of the Gray code. Our attack applies more generally to any sequence of γ i ’s which contains a large coset of a subgroup of GF (2 n ). As for NMAC , our first contribution is a simpler and uniform proof: If f is an ε -secure PRF (against q queries) and a δ - non-adaptively secure PRF (against q queries), then NMAC f is an ( ε + `qδ )-secure PRF against q queries of length at most ` blocks each. We also show that this ε + `qδ bound is basically tight by constructing an f for which an attack with advantage `qδ exists. Moreover, we analyze the PRF-security of a modification of NMAC called NI by An and Bellare that avoids the constant rekeying on multi-block messages in NMAC and allows for an information-theoretic analysis. We carry out such an analysis, obtaining a tight `q 2 / 2 c bound for this step, improving over the trivial bound of ` 2 q 2 / 2 c . Finally, we investigate, if the security of PMAC can be further improved by using τ i ’s that are k -wise independent, for k > 1 (the original has k = 1). We observe that the security of PMAC will not increase in general if k = 2, and then prove that the security increases to O ( q 2 / 2 n ), if the k = 4. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether k = 3 is already sufficient to get this level of security is left as an open problem. Keywords: Message authentication codes, Pseudorandom functions, HMAC, PMAC. ' alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Michal full_name: Rybar, Michal id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87 last_name: Rybar citation: ama: Rybar M. (The exact security of) Message authentication codes. 2017. doi:10.15479/AT:ISTA:th_828 apa: Rybar, M. (2017). (The exact security of) Message authentication codes. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_828 chicago: Rybar, Michal. “(The Exact Security of) Message Authentication Codes.” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_828. ieee: M. Rybar, “(The exact security of) Message authentication codes,” Institute of Science and Technology Austria, 2017. ista: Rybar M. 2017. (The exact security of) Message authentication codes. Institute of Science and Technology Austria. mla: Rybar, Michal. (The Exact Security of) Message Authentication Codes. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_828. short: M. Rybar, (The Exact Security of) Message Authentication Codes, Institute of Science and Technology Austria, 2017. date_created: 2018-12-11T11:48:46Z date_published: 2017-06-26T00:00:00Z date_updated: 2023-09-07T12:02:28Z day: '26' ddc: - '000' degree_awarded: PhD department: - _id: KrPi doi: 10.15479/AT:ISTA:th_828 file: - access_level: open_access checksum: ff8639ec4bded6186f44c7bd3ee26804 content_type: application/pdf creator: system date_created: 2018-12-12T10:10:13Z date_updated: 2020-07-14T12:48:12Z file_id: '4799' file_name: IST-2017-828-v1+3_2017_Rybar_thesis.pdf file_size: 847400 relation: main_file - access_level: closed checksum: 3462101745ce8ad199c2d0f75dae4a7e content_type: application/zip creator: dernst date_created: 2019-04-05T08:24:11Z date_updated: 2020-07-14T12:48:12Z file_id: '6202' file_name: 2017_Thesis_Rybar_source.zip file_size: 26054879 relation: source_file file_date_updated: 2020-07-14T12:48:12Z has_accepted_license: '1' language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: '86' publication_identifier: issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria publist_id: '6810' pubrep_id: '828' related_material: record: - id: '2082' relation: part_of_dissertation status: public - id: '6196' relation: part_of_dissertation status: public status: public title: (The exact security of) Message authentication codes type: dissertation user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2017' ... --- _id: '6196' abstract: - lang: eng text: PMAC is a simple and parallel block-cipher mode of operation, which was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a (pseudo)random permutation over n-bit strings, PMAC constitutes a provably secure variable input-length (pseudo)random function. For adversaries making q queries, each of length at most l (in n-bit blocks), and of total length σ ≤ ql, the original paper proves an upper bound on the distinguishing advantage of Ο(σ2/2n), while the currently best bound is Ο (qσ/2n).In this work we show that this bound is tight by giving an attack with advantage Ω (q2l/2n). In the PMAC construction one initially XORs a mask to every message block, where the mask for the ith block is computed as τi := γi·L, where L is a (secret) random value, and γi is the i-th codeword of the Gray code. Our attack applies more generally to any sequence of γi’s which contains a large coset of a subgroup of GF(2n). We then investigate if the security of PMAC can be further improved by using τi’s that are k-wise independent, for k > 1 (the original distribution is only 1-wise independent). We observe that the security of PMAC will not increase in general, even if the masks are chosen from a 2-wise independent distribution, and then prove that the security increases to O(q<2/2n), if the τi are 4-wise independent. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether 3-wise independence is already sufficient to get this level of security is left as an open problem. author: - first_name: Peter full_name: Gazi, Peter id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87 last_name: Gazi - 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: Michal full_name: Rybar, Michal id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87 last_name: Rybar citation: ama: Gazi P, Pietrzak KZ, Rybar M. The exact security of PMAC. IACR Transactions on Symmetric Cryptology. 2017;2016(2):145-161. doi:10.13154/TOSC.V2016.I2.145-161 apa: Gazi, P., Pietrzak, K. Z., & Rybar, M. (2017). The exact security of PMAC. IACR Transactions on Symmetric Cryptology. Ruhr University Bochum. https://doi.org/10.13154/TOSC.V2016.I2.145-161 chicago: Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact Security of PMAC.” IACR Transactions on Symmetric Cryptology. Ruhr University Bochum, 2017. https://doi.org/10.13154/TOSC.V2016.I2.145-161. ieee: P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact security of PMAC,” IACR Transactions on Symmetric Cryptology, vol. 2016, no. 2. Ruhr University Bochum, pp. 145–161, 2017. ista: Gazi P, Pietrzak KZ, Rybar M. 2017. The exact security of PMAC. IACR Transactions on Symmetric Cryptology. 2016(2), 145–161. mla: Gazi, Peter, et al. “The Exact Security of PMAC.” IACR Transactions on Symmetric Cryptology, vol. 2016, no. 2, Ruhr University Bochum, 2017, pp. 145–61, doi:10.13154/TOSC.V2016.I2.145-161. short: P. Gazi, K.Z. Pietrzak, M. Rybar, IACR Transactions on Symmetric Cryptology 2016 (2017) 145–161. date_created: 2019-04-04T13:48:23Z date_published: 2017-02-03T00:00:00Z date_updated: 2023-09-07T12:02:27Z day: '03' ddc: - '000' department: - _id: KrPi doi: 10.13154/TOSC.V2016.I2.145-161 ec_funded: 1 file: - access_level: open_access checksum: f23161d685dd957ae8d7274132999684 content_type: application/pdf creator: dernst date_created: 2019-04-04T13:53:58Z date_updated: 2020-07-14T12:47:24Z file_id: '6197' file_name: 2017_IACR_Gazi.pdf file_size: 597335 relation: main_file file_date_updated: 2020-07-14T12:47:24Z has_accepted_license: '1' intvolume: ' 2016' issue: '2' language: - iso: eng month: '02' oa: 1 oa_version: Published Version page: 145-161 project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication: IACR Transactions on Symmetric Cryptology publication_identifier: eissn: - 2519-173X publication_status: published publisher: Ruhr University Bochum quality_controlled: '1' related_material: record: - id: '838' relation: dissertation_contains status: public status: public title: The exact security of PMAC 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: 2016 year: '2017' ... --- _id: '559' abstract: - lang: eng text: 'Proofs of space (PoS) were suggested as more ecological and economical alternative to proofs of work, which are currently used in blockchain designs like Bitcoin. The existing PoS are based on rather sophisticated graph pebbling lower bounds. Much simpler and in several aspects more efficient schemes based on inverting random functions have been suggested, but they don’t give meaningful security guarantees due to existing time-memory trade-offs. In particular, Hellman showed that any permutation over a domain of size N can be inverted in time T by an algorithm that is given S bits of auxiliary information whenever (Formula presented). For functions Hellman gives a weaker attack with S2· T≈ N2 (e.g., S= T≈ N2/3). To prove lower bounds, one considers an adversary who has access to an oracle f: [ N] → [N] and can make T oracle queries. The best known lower bound is S· T∈ Ω(N) and holds for random functions and permutations. We construct functions that provably require more time and/or space to invert. Specifically, for any constant k we construct a function [N] → [N] that cannot be inverted unless Sk· T∈ Ω(Nk) (in particular, S= T≈ (Formula presented). Our construction does not contradict Hellman’s time-memory trade-off, because it cannot be efficiently evaluated in forward direction. However, its entire function table can be computed in time quasilinear in N, which is sufficient for the PoS application. Our simplest construction is built from a random function oracle g: [N] × [N] → [ N] and a random permutation oracle f: [N] → N] and is defined as h(x) = g(x, x′) where f(x) = π(f(x′)) with π being any involution without a fixed point, e.g. flipping all the bits. For this function we prove that any adversary who gets S bits of auxiliary information, makes at most T oracle queries, and inverts h on an ϵ fraction of outputs must satisfy S2· T∈ Ω(ϵ2N2).' alternative_title: - LNCS author: - first_name: Hamza M full_name: Abusalah, Hamza M id: 40297222-F248-11E8-B48F-1D18A9856A87 last_name: Abusalah - first_name: Joel F full_name: Alwen, Joel F id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87 last_name: Alwen - first_name: Bram full_name: Cohen, Bram last_name: Cohen - first_name: Danylo full_name: Khilko, Danylo last_name: Khilko - 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: Leonid full_name: Reyzin, Leonid last_name: Reyzin citation: ama: 'Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. In: Vol 10625. Springer; 2017:357-379. doi:10.1007/978-3-319-70697-9_13' apa: 'Abusalah, H. M., Alwen, J. F., Cohen, B., Khilko, D., Pietrzak, K. Z., & Reyzin, L. (2017). Beyond Hellman’s time-memory trade-offs with applications to proofs of space (Vol. 10625, pp. 357–379). Presented at the ASIACRYPT: Theory and Applications of Cryptology and Information Security, Hong Kong, China: Springer. https://doi.org/10.1007/978-3-319-70697-9_13' chicago: Abusalah, Hamza M, Joel F Alwen, Bram Cohen, Danylo Khilko, Krzysztof Z Pietrzak, and Leonid Reyzin. “Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space,” 10625:357–79. Springer, 2017. https://doi.org/10.1007/978-3-319-70697-9_13. ieee: 'H. M. Abusalah, J. F. Alwen, B. Cohen, D. Khilko, K. Z. Pietrzak, and L. Reyzin, “Beyond Hellman’s time-memory trade-offs with applications to proofs of space,” presented at the ASIACRYPT: Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017, vol. 10625, pp. 357–379.' ista: 'Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. 2017. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. ASIACRYPT: Theory and Applications of Cryptology and Information Security, LNCS, vol. 10625, 357–379.' mla: Abusalah, Hamza M., et al. Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space. Vol. 10625, Springer, 2017, pp. 357–79, doi:10.1007/978-3-319-70697-9_13. short: H.M. Abusalah, J.F. Alwen, B. Cohen, D. Khilko, K.Z. Pietrzak, L. Reyzin, in:, Springer, 2017, pp. 357–379. conference: end_date: 2017-12-07 location: Hong Kong, China name: 'ASIACRYPT: Theory and Applications of Cryptology and Information Security' start_date: 2017-12-03 date_created: 2018-12-11T11:47:10Z date_published: 2017-11-18T00:00:00Z date_updated: 2023-09-07T12:30:22Z day: '18' department: - _id: KrPi doi: 10.1007/978-3-319-70697-9_13 ec_funded: 1 intvolume: ' 10625' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2017/893.pdf month: '11' oa: 1 oa_version: Submitted Version page: 357 - 379 project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication_identifier: isbn: - 978-331970696-2 publication_status: published publisher: Springer publist_id: '7257' quality_controlled: '1' related_material: record: - id: '83' relation: dissertation_contains status: public scopus_import: 1 status: public title: Beyond Hellman’s time-memory trade-offs with applications to proofs of space type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 10625 year: '2017' ... --- _id: '637' abstract: - lang: eng text: For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future. Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to 2n. However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of m ≪ n bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only 2m ≪ 2n. In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs. alternative_title: - LNCS author: - first_name: Zahra full_name: Jafargholi, Zahra last_name: Jafargholi - first_name: Chethan full_name: Kamath Hosdurg, Chethan id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87 last_name: Kamath Hosdurg - first_name: Karen full_name: Klein, Karen id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87 last_name: Klein - first_name: Ilan full_name: Komargodski, Ilan last_name: Komargodski - 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: 'Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs D. Be adaptive avoid overcommitting. In: Katz J, Shacham H, eds. Vol 10401. Springer; 2017:133-163. doi:10.1007/978-3-319-63688-7_5' apa: 'Jafargholi, Z., Kamath Hosdurg, C., Klein, K., Komargodski, I., Pietrzak, K. Z., & Wichs, D. (2017). Be adaptive avoid overcommitting. In J. Katz & H. Shacham (Eds.) (Vol. 10401, pp. 133–163). Presented at the CRYPTO: Cryptology, Santa Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-319-63688-7_5' chicago: Jafargholi, Zahra, Chethan Kamath Hosdurg, Karen Klein, Ilan Komargodski, Krzysztof Z Pietrzak, and Daniel Wichs. “Be Adaptive Avoid Overcommitting.” edited by Jonathan Katz and Hovav Shacham, 10401:133–63. Springer, 2017. https://doi.org/10.1007/978-3-319-63688-7_5. ieee: 'Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K. Z. Pietrzak, and D. Wichs, “Be adaptive avoid overcommitting,” presented at the CRYPTO: Cryptology, Santa Barbara, CA, United States, 2017, vol. 10401, pp. 133–163.' ista: 'Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs D. 2017. Be adaptive avoid overcommitting. CRYPTO: Cryptology, LNCS, vol. 10401, 133–163.' mla: Jafargholi, Zahra, et al. Be Adaptive Avoid Overcommitting. Edited by Jonathan Katz and Hovav Shacham, vol. 10401, Springer, 2017, pp. 133–63, doi:10.1007/978-3-319-63688-7_5. short: Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K.Z. Pietrzak, D. Wichs, in:, J. Katz, H. Shacham (Eds.), Springer, 2017, pp. 133–163. conference: end_date: 2017-07-24 location: Santa Barbara, CA, United States name: 'CRYPTO: Cryptology' start_date: 2017-07-20 date_created: 2018-12-11T11:47:38Z date_published: 2017-01-01T00:00:00Z date_updated: 2023-09-07T13:32:11Z day: '01' department: - _id: KrPi doi: 10.1007/978-3-319-63688-7_5 ec_funded: 1 editor: - first_name: Jonathan full_name: Katz, Jonathan last_name: Katz - first_name: Hovav full_name: Shacham, Hovav last_name: Shacham intvolume: ' 10401' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2017/515 month: '01' oa: 1 oa_version: Submitted Version page: 133 - 163 project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication_identifier: isbn: - 978-331963687-0 publication_status: published publisher: Springer publist_id: '7151' quality_controlled: '1' related_material: record: - id: '10035' relation: dissertation_contains status: public scopus_import: 1 status: public title: Be adaptive avoid overcommitting type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 10401 year: '2017' ... --- _id: '1174' abstract: - lang: eng text: Security of cryptographic applications is typically defined by security games. The adversary, within certain resources, cannot win with probability much better than 0 (for unpredictability applications, like one-way functions) or much better than 1/2 (indistinguishability applications for instance encryption schemes). In so called squared-friendly applications the winning probability of the adversary, for different values of the application secret randomness, is not only close to 0 or 1/2 on average, but also concentrated in the sense that its second central moment is small. The class of squared-friendly applications, which contains all unpredictability applications and many indistinguishability applications, is particularly important for key derivation. Barak et al. observed that for square-friendly applications one can beat the "RT-bound", extracting secure keys with significantly smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications one can directly use a "weak" key, which has only high entropy, as a secure key. In this paper we give sharp lower bounds on square security assuming security for "weak" keys. We show that any application which is either (a) secure with weak keys or (b) allows for entropy savings for keys derived by universal hashing, must be square-friendly. Quantitatively, our lower bounds match the positive results of Dodis and Yu and Barak et al. (TCC\'13, CRYPTO\'11) Hence, they can be understood as a general characterization of squared-friendly applications. While the positive results on squared-friendly applications where derived by one clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we need more machinery. In our approach we use convex optimization techniques and some theory of circular matrices. alternative_title: - LIPIcs article_number: '57' article_processing_charge: No author: - first_name: Maciej full_name: Skórski, Maciej id: EC09FA6A-02D0-11E9-8223-86B7C91467DD last_name: Skórski citation: ama: 'Skórski M. Lower bounds on key derivation for square-friendly applications. In: Vol 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.STACS.2017.57' apa: 'Skórski, M. (2017). Lower bounds on key derivation for square-friendly applications (Vol. 66). Presented at the STACS: Symposium on Theoretical Aspects of Computer Science, Hannover, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2017.57' chicago: Skórski, Maciej. “Lower Bounds on Key Derivation for Square-Friendly Applications,” Vol. 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.STACS.2017.57. ieee: 'M. Skórski, “Lower bounds on key derivation for square-friendly applications,” presented at the STACS: Symposium on Theoretical Aspects of Computer Science, Hannover, Germany, 2017, vol. 66.' ista: 'Skórski M. 2017. Lower bounds on key derivation for square-friendly applications. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 66, 57.' mla: Skórski, Maciej. Lower Bounds on Key Derivation for Square-Friendly Applications. Vol. 66, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.STACS.2017.57. short: M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. conference: end_date: 2017-03-11 location: Hannover, Germany name: 'STACS: Symposium on Theoretical Aspects of Computer Science' start_date: 2017-03-08 date_created: 2018-12-11T11:50:32Z date_published: 2017-03-01T00:00:00Z date_updated: 2023-09-20T11:23:15Z day: '01' department: - _id: KrPi doi: 10.4230/LIPIcs.STACS.2017.57 ec_funded: 1 external_id: isi: - '000521077300057' intvolume: ' 66' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: http://drops.dagstuhl.de/opus/volltexte/2017/6976 month: '03' oa: 1 oa_version: Submitted Version project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication_identifier: issn: - '18688969' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik publist_id: '6180' quality_controlled: '1' scopus_import: '1' status: public title: Lower bounds on key derivation for square-friendly applications type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 66 year: '2017' ... --- _id: '1176' abstract: - lang: eng text: The algorithm Argon2i-B of Biryukov, Dinu and Khovratovich is currently being considered by the IRTF (Internet Research Task Force) as a new de-facto standard for password hashing. An older version (Argon2i-A) of the same algorithm was chosen as the winner of the recent Password Hashing Competition. An important competitor to Argon2i-B is the recently introduced Balloon Hashing (BH) algorithm of Corrigan-Gibs, Boneh and Schechter. A key security desiderata for any such algorithm is that evaluating it (even using a custom device) requires a large amount of memory amortized across multiple instances. Alwen and Blocki (CRYPTO 2016) introduced a class of theoretical attacks against Argon2i-A and BH. While these attacks yield large asymptotic reductions in the amount of memory, it was not, a priori, clear if (1) they can be extended to the newer Argon2i-B, (2) the attacks are effective on any algorithm for practical parameter ranges (e.g., 1GB of memory) and (3) if they can be effectively instantiated against any algorithm under realistic hardware constrains. In this work we answer all three of these questions in the affirmative for all three algorithms. This is also the first work to analyze the security of Argon2i-B. In more detail, we extend the theoretical attacks of Alwen and Blocki (CRYPTO 2016) to the recent Argon2i-B proposal demonstrating severe asymptotic deficiencies in its security. Next we introduce several novel heuristics for improving the attack's concrete memory efficiency even when on-chip memory bandwidth is bounded. We then simulate our attacks on randomly sampled Argon2i-A, Argon2i-B and BH instances and measure the resulting memory consumption for various practical parameter ranges and for a variety of upperbounds on the amount of parallelism available to the attacker. Finally we describe, implement, and test a new heuristic for applying the Alwen-Blocki attack to functions employing a technique developed by Corrigan-Gibs et al. for improving concrete security of memory-hard functions. We analyze the collected data and show the effects various parameters have on the memory consumption of the attack. In particular, we can draw several interesting conclusions about the level of security provided by these functions. · For the Alwen-Blocki attack to fail against practical memory parameters, Argon2i-B must be instantiated with more than 10 passes on memory - beyond the "paranoid" parameter setting in the current IRTF proposal. · The technique of Corrigan-Gibs for improving security can also be overcome by the Alwen-Blocki attack under realistic hardware constraints. · On a positive note, both the asymptotic and concrete security of Argon2i-B seem to improve on that of Argon2i-A. article_number: '7961977' article_processing_charge: No author: - first_name: Joel F full_name: Alwen, Joel F id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87 last_name: Alwen - first_name: Jeremiah full_name: Blocki, Jeremiah last_name: Blocki citation: ama: 'Alwen JF, Blocki J. Towards practical attacks on Argon2i and balloon hashing. In: IEEE; 2017. doi:10.1109/EuroSP.2017.47' apa: 'Alwen, J. F., & Blocki, J. (2017). Towards practical attacks on Argon2i and balloon hashing. Presented at the EuroS&P: European Symposium on Security and Privacy, Paris, France: IEEE. https://doi.org/10.1109/EuroSP.2017.47' chicago: Alwen, Joel F, and Jeremiah Blocki. “Towards Practical Attacks on Argon2i and Balloon Hashing.” IEEE, 2017. https://doi.org/10.1109/EuroSP.2017.47. ieee: 'J. F. Alwen and J. Blocki, “Towards practical attacks on Argon2i and balloon hashing,” presented at the EuroS&P: European Symposium on Security and Privacy, Paris, France, 2017.' ista: 'Alwen JF, Blocki J. 2017. Towards practical attacks on Argon2i and balloon hashing. EuroS&P: European Symposium on Security and Privacy, 7961977.' mla: Alwen, Joel F., and Jeremiah Blocki. Towards Practical Attacks on Argon2i and Balloon Hashing. 7961977, IEEE, 2017, doi:10.1109/EuroSP.2017.47. short: J.F. Alwen, J. Blocki, in:, IEEE, 2017. conference: end_date: 2017-04-28 location: Paris, France name: 'EuroS&P: European Symposium on Security and Privacy' start_date: 2017-04-26 date_created: 2018-12-11T11:50:33Z date_published: 2017-07-03T00:00:00Z date_updated: 2023-09-20T11:22:25Z day: '03' department: - _id: KrPi doi: 10.1109/EuroSP.2017.47 external_id: isi: - '000424197300011' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2016/759 month: '07' oa: 1 oa_version: Submitted Version publication_identifier: isbn: - 978-150905761-0 publication_status: published publisher: IEEE publist_id: '6178' quality_controlled: '1' scopus_import: '1' status: public title: Towards practical attacks on Argon2i and balloon hashing type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2017' ... --- _id: '1187' abstract: - lang: eng text: We construct efficient authentication protocols and message authentication codes (MACs) whose security can be reduced to the learning parity with noise (LPN) problem. Despite a large body of work—starting with the (Formula presented.) protocol of Hopper and Blum in 2001—until now it was not even known how to construct an efficient authentication protocol from LPN which is secure against man-in-the-middle attacks. A MAC implies such a (two-round) protocol. article_processing_charge: No article_type: original author: - first_name: Eike full_name: Kiltz, Eike last_name: Kiltz - 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: Daniele full_name: Venturi, Daniele last_name: Venturi - first_name: David full_name: Cash, David last_name: Cash - first_name: Abhishek full_name: Jain, Abhishek last_name: Jain citation: ama: Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. Efficient authentication from hard learning problems. Journal of Cryptology. 2017;30(4):1238-1275. doi:10.1007/s00145-016-9247-3 apa: Kiltz, E., Pietrzak, K. Z., Venturi, D., Cash, D., & Jain, A. (2017). Efficient authentication from hard learning problems. Journal of Cryptology. Springer. https://doi.org/10.1007/s00145-016-9247-3 chicago: Kiltz, Eike, Krzysztof Z Pietrzak, Daniele Venturi, David Cash, and Abhishek Jain. “Efficient Authentication from Hard Learning Problems.” Journal of Cryptology. Springer, 2017. https://doi.org/10.1007/s00145-016-9247-3. ieee: E. Kiltz, K. Z. Pietrzak, D. Venturi, D. Cash, and A. Jain, “Efficient authentication from hard learning problems,” Journal of Cryptology, vol. 30, no. 4. Springer, pp. 1238–1275, 2017. ista: Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. 2017. Efficient authentication from hard learning problems. Journal of Cryptology. 30(4), 1238–1275. mla: Kiltz, Eike, et al. “Efficient Authentication from Hard Learning Problems.” Journal of Cryptology, vol. 30, no. 4, Springer, 2017, pp. 1238–75, doi:10.1007/s00145-016-9247-3. short: E. Kiltz, K.Z. Pietrzak, D. Venturi, D. Cash, A. Jain, Journal of Cryptology 30 (2017) 1238–1275. date_created: 2018-12-11T11:50:37Z date_published: 2017-10-01T00:00:00Z date_updated: 2023-09-20T11:20:58Z day: '01' ddc: - '000' department: - _id: KrPi doi: 10.1007/s00145-016-9247-3 ec_funded: 1 external_id: isi: - '000410788600007' file: - access_level: open_access checksum: c647520d115b772a1682fc06fa273eb1 content_type: application/pdf creator: dernst date_created: 2020-05-14T16:30:17Z date_updated: 2020-07-14T12:44:37Z file_id: '7843' file_name: 2017_JournalCrypto_Kiltz.pdf file_size: 516959 relation: main_file file_date_updated: 2020-07-14T12:44:37Z has_accepted_license: '1' intvolume: ' 30' isi: 1 issue: '4' language: - iso: eng month: '10' oa: 1 oa_version: Submitted Version page: 1238 - 1275 project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks - _id: 258C570E-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '259668' name: Provable Security for Physical Cryptography publication: Journal of Cryptology publication_status: published publisher: Springer publist_id: '6166' quality_controlled: '1' related_material: record: - id: '3238' relation: earlier_version status: public scopus_import: '1' status: public title: Efficient authentication from hard learning problems type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 30 year: '2017' ... --- _id: '1177' abstract: - lang: eng text: Boldyreva, Palacio and Warinschi introduced a multiple forking game as an extension of general forking. The notion of (multiple) forking is a useful abstraction from the actual simulation of cryptographic scheme to the adversary in a security reduction, and is achieved through the intermediary of a so-called wrapper algorithm. Multiple forking has turned out to be a useful tool in the security argument of several cryptographic protocols. However, a reduction employing multiple forking incurs a significant degradation of (Formula presented.) , where (Formula presented.) denotes the upper bound on the underlying random oracle calls and (Formula presented.) , the number of forkings. In this work we take a closer look at the reasons for the degradation with a tighter security bound in mind. We nail down the exact set of conditions for success in the multiple forking game. A careful analysis of the cryptographic schemes and corresponding security reduction employing multiple forking leads to the formulation of ‘dependence’ and ‘independence’ conditions pertaining to the output of the wrapper in different rounds. Based on the (in)dependence conditions we propose a general framework of multiple forking and a General Multiple Forking Lemma. Leveraging (in)dependence to the full allows us to improve the degradation factor in the multiple forking game by a factor of (Formula presented.). By implication, the cost of a single forking involving two random oracles (augmented forking) matches that involving a single random oracle (elementary forking). Finally, we study the effect of these observations on the concrete security of existing schemes employing multiple forking. We conclude that by careful design of the protocol (and the wrapper in the security reduction) it is possible to harness our observations to the full extent. acknowledgement: "We are grateful to the anonymous reviewers for their insightful comments. The\r\ndetailed reports helped us a lot to address the technical mistakes as well as to improve the overall presentation of the paper." author: - first_name: Chethan full_name: Kamath Hosdurg, Chethan id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87 last_name: Kamath Hosdurg - first_name: Sanjit full_name: Chatterjee, Sanjit last_name: Chatterjee citation: ama: 'Kamath Hosdurg C, Chatterjee S. A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound. Algorithmica. 2016;74(4):1321-1362. doi:10.1007/s00453-015-9997-6' apa: 'Kamath Hosdurg, C., & Chatterjee, S. (2016). A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound. Algorithmica. Springer. https://doi.org/10.1007/s00453-015-9997-6' chicago: 'Kamath Hosdurg, Chethan, and Sanjit Chatterjee. “A Closer Look at Multiple-Forking: Leveraging (in)Dependence for a Tighter Bound.” Algorithmica. Springer, 2016. https://doi.org/10.1007/s00453-015-9997-6.' ieee: 'C. Kamath Hosdurg and S. Chatterjee, “A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound,” Algorithmica, vol. 74, no. 4. Springer, pp. 1321–1362, 2016.' ista: 'Kamath Hosdurg C, Chatterjee S. 2016. A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound. Algorithmica. 74(4), 1321–1362.' mla: 'Kamath Hosdurg, Chethan, and Sanjit Chatterjee. “A Closer Look at Multiple-Forking: Leveraging (in)Dependence for a Tighter Bound.” Algorithmica, vol. 74, no. 4, Springer, 2016, pp. 1321–62, doi:10.1007/s00453-015-9997-6.' short: C. Kamath Hosdurg, S. Chatterjee, Algorithmica 74 (2016) 1321–1362. date_created: 2018-12-11T11:50:33Z date_published: 2016-04-01T00:00:00Z date_updated: 2021-01-12T06:48:52Z day: '01' department: - _id: KrPi doi: 10.1007/s00453-015-9997-6 intvolume: ' 74' issue: '4' language: - iso: eng main_file_link: - open_access: '1' url: http://eprint.iacr.org/2013/651 month: '04' oa: 1 oa_version: Submitted Version page: 1321 - 1362 publication: Algorithmica publication_status: published publisher: Springer publist_id: '6177' quality_controlled: '1' status: public title: 'A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound' type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 74 year: '2016' ... --- _id: '1179' abstract: - lang: eng text: "Computational notions of entropy have recently found many applications, including leakage-resilient cryptography, deterministic encryption or memory delegation. The two main types of results which make computational notions so useful are (1) Chain rules, which quantify by how much the computational entropy of a variable decreases if conditioned on some other variable (2) Transformations, which quantify to which extend one type of entropy implies another.\r\n\r\nSuch chain rules and transformations typically lose a significant amount in quality of the entropy, and are the reason why applying these results one gets rather weak quantitative security bounds. In this paper we for the first time prove lower bounds in this context, showing that existing results for transformations are, unfortunately, basically optimal for non-adaptive black-box reductions (and it’s hard to imagine how non black-box reductions or adaptivity could be useful here.)\r\n\r\nA variable X has k bits of HILL entropy of quality (ϵ,s)\r\nif there exists a variable Y with k bits min-entropy which cannot be distinguished from X with advantage ϵ\r\n\r\nby distinguishing circuits of size s. A weaker notion is Metric entropy, where we switch quantifiers, and only require that for every distinguisher of size s, such a Y exists.\r\n\r\nWe first describe our result concerning transformations. By definition, HILL implies Metric without any loss in quality. Metric entropy often comes up in applications, but must be transformed to HILL for meaningful security guarantees. The best known result states that if a variable X has k bits of Metric entropy of quality (ϵ,s)\r\n, then it has k bits of HILL with quality (2ϵ,s⋅ϵ2). We show that this loss of a factor Ω(ϵ−2)\r\n\r\nin circuit size is necessary. In fact, we show the stronger result that this loss is already necessary when transforming so called deterministic real valued Metric entropy to randomised boolean Metric (both these variants of Metric entropy are implied by HILL without loss in quality).\r\n\r\nThe chain rule for HILL entropy states that if X has k bits of HILL entropy of quality (ϵ,s)\r\n, then for any variable Z of length m, X conditioned on Z has k−m bits of HILL entropy with quality (ϵ,s⋅ϵ2/2m). We show that a loss of Ω(2m/ϵ) in circuit size necessary here. Note that this still leaves a gap of ϵ between the known bound and our lower bound." acknowledgement: "K. Pietrzak—Supported by the European Research Council consolidator grant (682815-TOCNeT).\r\nM. Skórski—Supported by the National Science Center, Poland (2015/17/N/ST6/03564)." alternative_title: - LNCS author: - 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: Skorski full_name: Maciej, Skorski last_name: Maciej citation: ama: 'Pietrzak KZ, Maciej S. Pseudoentropy: Lower-bounds for chain rules and transformations. In: Vol 9985. Springer; 2016:183-203. doi:10.1007/978-3-662-53641-4_8' apa: 'Pietrzak, K. Z., & Maciej, S. (2016). Pseudoentropy: Lower-bounds for chain rules and transformations (Vol. 9985, pp. 183–203). Presented at the TCC: Theory of Cryptography Conference, Beijing, China: Springer. https://doi.org/10.1007/978-3-662-53641-4_8' chicago: 'Pietrzak, Krzysztof Z, and Skorski Maciej. “Pseudoentropy: Lower-Bounds for Chain Rules and Transformations,” 9985:183–203. Springer, 2016. https://doi.org/10.1007/978-3-662-53641-4_8.' ieee: 'K. Z. Pietrzak and S. Maciej, “Pseudoentropy: Lower-bounds for chain rules and transformations,” presented at the TCC: Theory of Cryptography Conference, Beijing, China, 2016, vol. 9985, pp. 183–203.' ista: 'Pietrzak KZ, Maciej S. 2016. Pseudoentropy: Lower-bounds for chain rules and transformations. TCC: Theory of Cryptography Conference, LNCS, vol. 9985, 183–203.' mla: 'Pietrzak, Krzysztof Z., and Skorski Maciej. Pseudoentropy: Lower-Bounds for Chain Rules and Transformations. Vol. 9985, Springer, 2016, pp. 183–203, doi:10.1007/978-3-662-53641-4_8.' short: K.Z. Pietrzak, S. Maciej, in:, Springer, 2016, pp. 183–203. conference: end_date: 2016-11-03 location: Beijing, China name: 'TCC: Theory of Cryptography Conference' start_date: 2016-10-31 date_created: 2018-12-11T11:50:34Z date_published: 2016-10-22T00:00:00Z date_updated: 2021-01-12T06:48:53Z day: '22' department: - _id: KrPi doi: 10.1007/978-3-662-53641-4_8 ec_funded: 1 intvolume: ' 9985' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2016/159 month: '10' oa: 1 oa_version: Preprint page: 183 - 203 project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication_status: published publisher: Springer publist_id: '6175' quality_controlled: '1' scopus_import: 1 status: public title: 'Pseudoentropy: Lower-bounds for chain rules and transformations' type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 9985 year: '2016' ... --- _id: '1231' abstract: - lang: eng text: 'We study the time-and memory-complexities of the problem of computing labels of (multiple) randomly selected challenge-nodes in a directed acyclic graph. The w-bit label of a node is the hash of the labels of its parents, and the hash function is modeled as a random oracle. Specific instances of this problem underlie both proofs of space [Dziembowski et al. CRYPTO’15] as well as popular memory-hard functions like scrypt. As our main tool, we introduce the new notion of a probabilistic parallel entangled pebbling game, a new type of combinatorial pebbling game on a graph, which is closely related to the labeling game on the same graph. As a first application of our framework, we prove that for scrypt, when the underlying hash function is invoked n times, the cumulative memory complexity (CMC) (a notion recently introduced by Alwen and Serbinenko (STOC’15) to capture amortized memory-hardness for parallel adversaries) is at least Ω(w · (n/ log(n))2). This bound holds for adversaries that can store many natural functions of the labels (e.g., linear combinations), but still not arbitrary functions thereof. We then introduce and study a combinatorial quantity, and show how a sufficiently small upper bound on it (which we conjecture) extends our CMC bound for scrypt to hold against arbitrary adversaries. We also show that such an upper bound solves the main open problem for proofs-of-space protocols: namely, establishing that the time complexity of computing the label of a random node in a graph on n nodes (given an initial kw-bit state) reduces tightly to the time complexity for black pebbling on the same graph (given an initial k-node pebbling).' acknowledgement: "Joël Alwen, Chethan Kamath, and Krzysztof Pietrzak’s research is partially supported by an ERC starting grant (259668-PSPC). Vladimir Kolmogorov is partially supported by an ERC consolidator grant (616160-DOICV). Binyi Chen was partially supported by NSF grants CNS-1423566 and CNS-1514526, and a gift from the Gareatis Foundation. Stefano Tessaro was partially supported by NSF grants CNS-1423566, CNS-1528178, a Hellman Fellowship, and the Glen and Susanne Culler Chair.\r\n\r\nThis work was done in part while the authors were visiting the Simons Institute for the Theory of Computing, supported by the Simons Foundation and by the DIMACS/Simons Collaboration in Cryptography through NSF grant CNS-1523467." alternative_title: - LNCS author: - first_name: Joel F full_name: Alwen, Joel F id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87 last_name: Alwen - first_name: Binyi full_name: Chen, Binyi last_name: Chen - first_name: Chethan full_name: Kamath Hosdurg, Chethan id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87 last_name: Kamath Hosdurg - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - 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: Stefano full_name: Tessaro, Stefano last_name: Tessaro citation: ama: 'Alwen JF, Chen B, Kamath Hosdurg C, Kolmogorov V, Pietrzak KZ, Tessaro S. On the complexity of scrypt and proofs of space in the parallel random oracle model. In: Vol 9666. Springer; 2016:358-387. doi:10.1007/978-3-662-49896-5_13' apa: 'Alwen, J. F., Chen, B., Kamath Hosdurg, C., Kolmogorov, V., Pietrzak, K. Z., & Tessaro, S. (2016). On the complexity of scrypt and proofs of space in the parallel random oracle model (Vol. 9666, pp. 358–387). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria: Springer. https://doi.org/10.1007/978-3-662-49896-5_13' chicago: Alwen, Joel F, Binyi Chen, Chethan Kamath Hosdurg, Vladimir Kolmogorov, Krzysztof Z Pietrzak, and Stefano Tessaro. “On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model,” 9666:358–87. Springer, 2016. https://doi.org/10.1007/978-3-662-49896-5_13. ieee: 'J. F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K. Z. Pietrzak, and S. Tessaro, “On the complexity of scrypt and proofs of space in the parallel random oracle model,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria, 2016, vol. 9666, pp. 358–387.' ista: 'Alwen JF, Chen B, Kamath Hosdurg C, Kolmogorov V, Pietrzak KZ, Tessaro S. 2016. On the complexity of scrypt and proofs of space in the parallel random oracle model. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 9666, 358–387.' mla: Alwen, Joel F., et al. On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model. Vol. 9666, Springer, 2016, pp. 358–87, doi:10.1007/978-3-662-49896-5_13. short: J.F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2016, pp. 358–387. conference: end_date: 2016-05-12 location: Vienna, Austria name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques' start_date: 2016-05-08 date_created: 2018-12-11T11:50:51Z date_published: 2016-04-28T00:00:00Z date_updated: 2021-01-12T06:49:15Z day: '28' department: - _id: KrPi - _id: VlKo doi: 10.1007/978-3-662-49896-5_13 ec_funded: 1 intvolume: ' 9666' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2016/100 month: '04' oa: 1 oa_version: Submitted Version page: 358 - 387 project: - _id: 258C570E-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '259668' name: Provable Security for Physical Cryptography - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' publication_status: published publisher: Springer publist_id: '6103' quality_controlled: '1' scopus_import: 1 status: public title: On the complexity of scrypt and proofs of space in the parallel random oracle model type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 9666 year: '2016' ... --- _id: '1233' abstract: - lang: eng text: About three decades ago it was realized that implementing private channels between parties which can be adaptively corrupted requires an encryption scheme that is secure against selective opening attacks. Whether standard (IND-CPA) security implies security against selective opening attacks has been a major open question since. The only known reduction from selective opening to IND-CPA security loses an exponential factor. A polynomial reduction is only known for the very special case where the distribution considered in the selective opening security experiment is a product distribution, i.e., the messages are sampled independently from each other. In this paper we give a reduction whose loss is quantified via the dependence graph (where message dependencies correspond to edges) of the underlying message distribution. In particular, for some concrete distributions including Markov distributions, our reduction is polynomial. acknowledgement: G. Fuchsbauer and K. Pietrzak are supported by the European Research Council, ERC Starting Grant (259668-PSPC). F. Heuer is funded by a Sofja Kovalevskaja Award of the Alexander von Humboldt Foundation and DFG SPP 1736, Algorithms for BIG DATA. E. Kiltz is supported by a Sofja Kovalevskaja Award of the Alexander von Humboldt Foundation, the German Israel Foundation, and ERC Project ERCC (FP7/615074). alternative_title: - LNCS author: - first_name: Georg full_name: Fuchsbauer, Georg id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87 last_name: Fuchsbauer - first_name: Felix full_name: Heuer, Felix last_name: Heuer - first_name: Eike full_name: Kiltz, Eike last_name: Kiltz - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 citation: ama: 'Fuchsbauer G, Heuer F, Kiltz E, Pietrzak KZ. Standard security does imply security against selective opening for markov distributions. In: Vol 9562. Springer; 2016:282-305. doi:10.1007/978-3-662-49096-9_12' apa: 'Fuchsbauer, G., Heuer, F., Kiltz, E., & Pietrzak, K. Z. (2016). Standard security does imply security against selective opening for markov distributions (Vol. 9562, pp. 282–305). Presented at the TCC: Theory of Cryptography Conference, Tel Aviv, Israel: Springer. https://doi.org/10.1007/978-3-662-49096-9_12' chicago: Fuchsbauer, Georg, Felix Heuer, Eike Kiltz, and Krzysztof Z Pietrzak. “Standard Security Does Imply Security against Selective Opening for Markov Distributions,” 9562:282–305. Springer, 2016. https://doi.org/10.1007/978-3-662-49096-9_12. ieee: 'G. Fuchsbauer, F. Heuer, E. Kiltz, and K. Z. Pietrzak, “Standard security does imply security against selective opening for markov distributions,” presented at the TCC: Theory of Cryptography Conference, Tel Aviv, Israel, 2016, vol. 9562, pp. 282–305.' ista: 'Fuchsbauer G, Heuer F, Kiltz E, Pietrzak KZ. 2016. Standard security does imply security against selective opening for markov distributions. TCC: Theory of Cryptography Conference, LNCS, vol. 9562, 282–305.' mla: Fuchsbauer, Georg, et al. Standard Security Does Imply Security against Selective Opening for Markov Distributions. Vol. 9562, Springer, 2016, pp. 282–305, doi:10.1007/978-3-662-49096-9_12. short: G. Fuchsbauer, F. Heuer, E. Kiltz, K.Z. Pietrzak, in:, Springer, 2016, pp. 282–305. conference: end_date: 2016-01-13 location: Tel Aviv, Israel name: 'TCC: Theory of Cryptography Conference' start_date: 2016-01-10 date_created: 2018-12-11T11:50:51Z date_published: 2016-01-01T00:00:00Z date_updated: 2021-01-12T06:49:16Z day: '01' department: - _id: KrPi doi: 10.1007/978-3-662-49096-9_12 ec_funded: 1 intvolume: ' 9562' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2015/853 month: '01' oa: 1 oa_version: Submitted Version page: 282 - 305 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: '6100' quality_controlled: '1' scopus_import: 1 status: public title: Standard security does imply security against selective opening for markov distributions type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 9562 year: '2016' ... --- _id: '1365' abstract: - lang: eng text: A memory-hard function (MHF) f is equipped with a space cost σ and time cost τ parameter such that repeatedly computing fσ,τ on an application specific integrated circuit (ASIC) is not economically advantageous relative to a general purpose computer. Technically we would like that any (generalized) circuit for evaluating an iMHF fσ,τ has area × time (AT) complexity at Θ(σ2 ∗ τ). A data-independent MHF (iMHF) has the added property that it can be computed with almost optimal memory and time complexity by an algorithm which accesses memory in a pattern independent of the input value. Such functions can be specified by fixing a directed acyclic graph (DAG) G on n = Θ(σ ∗ τ) nodes representing its computation graph. In this work we develop new tools for analyzing iMHFs. First we define and motivate a new complexity measure capturing the amount of energy (i.e. electricity) required to compute a function. We argue that, in practice, this measure is at least as important as the more traditional AT-complexity. Next we describe an algorithm A for repeatedly evaluating an iMHF based on an arbitrary DAG G. We upperbound both its energy and AT complexities per instance evaluated in terms of a certain combinatorial property of G. Next we instantiate our attack for several general classes of DAGs which include those underlying many of the most important iMHF candidates in the literature. In particular, we obtain the following results which hold for all choices of parameters σ and τ (and thread-count) such that n = σ ∗ τ. -The Catena-Dragonfly function of [FLW13] has AT and energy complexities O(n1.67). -The Catena-Butterfly function of [FLW13] has complexities is O(n1.67). -The Double-Buffer and the Linear functions of [CGBS16] both have complexities in O(n1.67). -The Argon2i function of [BDK15] (winner of the Password Hashing Competition [PHC]) has complexities O(n7/4 log(n)). -The Single-Buffer function of [CGBS16] has complexities O(n7/4 log(n)). -Any iMHF can be computed by an algorithm with complexities O(n2/ log1 −ε(n)) for all ε > 0. In particular when τ = 1 this shows that the goal of constructing an iMHF with AT-complexity Θ(σ2 ∗ τ ) is unachievable. Along the way we prove a lemma upper-bounding the depth-robustness of any DAG which may prove to be of independent interest. alternative_title: - LNCS author: - first_name: Joel F full_name: Alwen, Joel F id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87 last_name: Alwen - first_name: Jeremiah full_name: Blocki, Jeremiah last_name: Blocki citation: ama: 'Alwen JF, Blocki J. Efficiently computing data-independent memory-hard functions. In: Vol 9815. Springer; 2016:241-271. doi:10.1007/978-3-662-53008-5_9' apa: 'Alwen, J. F., & Blocki, J. (2016). Efficiently computing data-independent memory-hard functions (Vol. 9815, pp. 241–271). Presented at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, USA: Springer. https://doi.org/10.1007/978-3-662-53008-5_9' chicago: Alwen, Joel F, and Jeremiah Blocki. “Efficiently Computing Data-Independent Memory-Hard Functions,” 9815:241–71. Springer, 2016. https://doi.org/10.1007/978-3-662-53008-5_9. ieee: 'J. F. Alwen and J. Blocki, “Efficiently computing data-independent memory-hard functions,” presented at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, USA, 2016, vol. 9815, pp. 241–271.' ista: 'Alwen JF, Blocki J. 2016. Efficiently computing data-independent memory-hard functions. CRYPTO: International Cryptology Conference, LNCS, vol. 9815, 241–271.' mla: Alwen, Joel F., and Jeremiah Blocki. Efficiently Computing Data-Independent Memory-Hard Functions. Vol. 9815, Springer, 2016, pp. 241–71, doi:10.1007/978-3-662-53008-5_9. short: J.F. Alwen, J. Blocki, in:, Springer, 2016, pp. 241–271. conference: end_date: 2016-08-18 location: Santa Barbara, CA, USA name: 'CRYPTO: International Cryptology Conference' start_date: 2016-08-14 date_created: 2018-12-11T11:51:36Z date_published: 2016-08-01T00:00:00Z date_updated: 2021-01-12T06:50:11Z day: '01' department: - _id: KrPi doi: 10.1007/978-3-662-53008-5_9 intvolume: ' 9815' language: - iso: eng main_file_link: - open_access: '1' url: http://eprint.iacr.org/2016/115 month: '08' oa: 1 oa_version: Preprint page: 241 - 271 publication_status: published publisher: Springer publist_id: '5876' quality_controlled: '1' scopus_import: 1 status: public title: Efficiently computing data-independent memory-hard functions type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 9815 year: '2016' ... --- _id: '1366' abstract: - lang: eng text: 'We study the problem of devising provably secure PRNGs with input based on the sponge paradigm. Such constructions are very appealing, as efficient software/hardware implementations of SHA-3 can easily be translated into a PRNG in a nearly black-box way. The only existing sponge-based construction, proposed by Bertoni et al. (CHES 2010), fails to achieve the security notion of robustness recently considered by Dodis et al. (CCS 2013), for two reasons: (1) The construction is deterministic, and thus there are high-entropy input distributions on which the construction fails to extract random bits, and (2) The construction is not forward secure, and presented solutions aiming at restoring forward security have not been rigorously analyzed. We propose a seeded variant of Bertoni et al.’s PRNG with input which we prove secure in the sense of robustness, delivering in particular concrete security bounds. On the way, we make what we believe to be an important conceptual contribution, developing a variant of the security framework of Dodis et al. tailored at the ideal permutation model that captures PRNG security in settings where the weakly random inputs are provided from a large class of possible adversarial samplers which are also allowed to query the random permutation. As a further application of our techniques, we also present an efficient sponge-based key-derivation function (which can be instantiated from SHA-3 in a black-box fashion), which we also prove secure when fed with samples from permutation-dependent distributions.' alternative_title: - LNCS author: - first_name: Peter full_name: Gazi, Peter id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87 last_name: Gazi - first_name: Stefano full_name: Tessaro, Stefano last_name: Tessaro citation: ama: 'Gazi P, Tessaro S. Provably robust sponge-based PRNGs and KDFs. In: Vol 9665. Springer; 2016:87-116. doi:10.1007/978-3-662-49890-3_4' apa: 'Gazi, P., & Tessaro, S. (2016). Provably robust sponge-based PRNGs and KDFs (Vol. 9665, pp. 87–116). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria: Springer. https://doi.org/10.1007/978-3-662-49890-3_4' chicago: Gazi, Peter, and Stefano Tessaro. “Provably Robust Sponge-Based PRNGs and KDFs,” 9665:87–116. Springer, 2016. https://doi.org/10.1007/978-3-662-49890-3_4. ieee: 'P. Gazi and S. Tessaro, “Provably robust sponge-based PRNGs and KDFs,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria, 2016, vol. 9665, pp. 87–116.' ista: 'Gazi P, Tessaro S. 2016. Provably robust sponge-based PRNGs and KDFs. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 9665, 87–116.' mla: Gazi, Peter, and Stefano Tessaro. Provably Robust Sponge-Based PRNGs and KDFs. Vol. 9665, Springer, 2016, pp. 87–116, doi:10.1007/978-3-662-49890-3_4. short: P. Gazi, S. Tessaro, in:, Springer, 2016, pp. 87–116. conference: end_date: 2016-05-12 location: Vienna, Austria name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques' start_date: 2016-05-08 date_created: 2018-12-11T11:51:36Z date_published: 2016-05-01T00:00:00Z date_updated: 2021-01-12T06:50:11Z day: '01' department: - _id: KrPi doi: 10.1007/978-3-662-49890-3_4 ec_funded: 1 intvolume: ' 9665' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2016/169/20160219:201940 month: '05' oa: 1 oa_version: Preprint page: 87 - 116 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: '5872' quality_controlled: '1' scopus_import: 1 status: public title: Provably robust sponge-based PRNGs and KDFs type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 9665 year: '2016' ... --- _id: '1592' abstract: - lang: eng text: A modular approach to constructing cryptographic protocols leads to simple designs but often inefficient instantiations. On the other hand, ad hoc constructions may yield efficient protocols at the cost of losing conceptual simplicity. We suggest a new design paradigm, structure-preserving cryptography, that provides a way to construct modular protocols with reasonable efficiency while retaining conceptual simplicity. A cryptographic scheme over a bilinear group is called structure-preserving if its public inputs and outputs consist of elements from the bilinear groups and their consistency can be verified by evaluating pairing-product equations. As structure-preserving schemes smoothly interoperate with each other, they are useful as building blocks in modular design of cryptographic applications. This paper introduces structure-preserving commitment and signature schemes over bilinear groups with several desirable properties. The commitment schemes include homomorphic, trapdoor and length-reducing commitments to group elements, and the structure-preserving signature schemes are the first ones that yield constant-size signatures on multiple group elements. A structure-preserving signature scheme is called automorphic if the public keys lie in the message space, which cannot be achieved by compressing inputs via a cryptographic hash function, as this would destroy the mathematical structure we are trying to preserve. Automorphic signatures can be used for building certification chains underlying privacy-preserving protocols. Among a vast number of applications of structure-preserving protocols, we present an efficient round-optimal blind-signature scheme and a group signature scheme with an efficient and concurrently secure protocol for enrolling new members. acknowledgement: The authors would like to thank the anonymous reviewers of this paper. We also would like to express our appreciation to the program committee and the anonymous reviewers for CRYPTO 2010. The first author thanks Sherman S. M. Chow for his comment on group signatures in Sect. 7.1. author: - first_name: Masayuki full_name: Abe, Masayuki last_name: Abe - first_name: Georg full_name: Fuchsbauer, Georg id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87 last_name: Fuchsbauer - first_name: Jens full_name: Groth, Jens last_name: Groth - first_name: Kristiyan full_name: Haralambiev, Kristiyan last_name: Haralambiev - first_name: Miyako full_name: Ohkubo, Miyako last_name: Ohkubo citation: ama: Abe M, Fuchsbauer G, Groth J, Haralambiev K, Ohkubo M. Structure preserving signatures and commitments to group elements. Journal of Cryptology. 2016;29(2):363-421. doi:10.1007/s00145-014-9196-7 apa: Abe, M., Fuchsbauer, G., Groth, J., Haralambiev, K., & Ohkubo, M. (2016). Structure preserving signatures and commitments to group elements. Journal of Cryptology. Springer. https://doi.org/10.1007/s00145-014-9196-7 chicago: Abe, Masayuki, Georg Fuchsbauer, Jens Groth, Kristiyan Haralambiev, and Miyako Ohkubo. “Structure Preserving Signatures and Commitments to Group Elements.” Journal of Cryptology. Springer, 2016. https://doi.org/10.1007/s00145-014-9196-7. ieee: M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, and M. Ohkubo, “Structure preserving signatures and commitments to group elements,” Journal of Cryptology, vol. 29, no. 2. Springer, pp. 363–421, 2016. ista: Abe M, Fuchsbauer G, Groth J, Haralambiev K, Ohkubo M. 2016. Structure preserving signatures and commitments to group elements. Journal of Cryptology. 29(2), 363–421. mla: Abe, Masayuki, et al. “Structure Preserving Signatures and Commitments to Group Elements.” Journal of Cryptology, vol. 29, no. 2, Springer, 2016, pp. 363–421, doi:10.1007/s00145-014-9196-7. short: M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, M. Ohkubo, Journal of Cryptology 29 (2016) 363–421. date_created: 2018-12-11T11:52:54Z date_published: 2016-04-01T00:00:00Z date_updated: 2021-01-12T06:51:49Z day: '01' department: - _id: KrPi doi: 10.1007/s00145-014-9196-7 intvolume: ' 29' issue: '2' language: - iso: eng month: '04' oa_version: None page: 363 - 421 publication: Journal of Cryptology publication_status: published publisher: Springer publist_id: '5579' quality_controlled: '1' scopus_import: 1 status: public title: Structure preserving signatures and commitments to group elements type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 29 year: '2016' ... --- _id: '1225' abstract: - lang: eng text: At Crypto 2015 Fuchsbauer, Hanser and Slamanig (FHS) presented the first standard-model construction of efficient roundoptimal blind signatures that does not require complexity leveraging. It is conceptually simple and builds on the primitive of structure-preserving signatures on equivalence classes (SPS-EQ). FHS prove the unforgeability of their scheme assuming EUF-CMA security of the SPS-EQ scheme and hardness of a version of the DH inversion problem. Blindness under adversarially chosen keys is proven under an interactive variant of the DDH assumption. We propose a variant of their scheme whose blindness can be proven under a non-interactive assumption, namely a variant of the bilinear DDH assumption. We moreover prove its unforgeability assuming only unforgeability of the underlying SPS-EQ but no additional assumptions as needed for the FHS scheme. alternative_title: - LNCS author: - first_name: Georg full_name: Fuchsbauer, Georg id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87 last_name: Fuchsbauer - first_name: Christian full_name: Hanser, Christian last_name: Hanser - first_name: Chethan full_name: Kamath Hosdurg, Chethan id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87 last_name: Kamath Hosdurg - first_name: Daniel full_name: Slamanig, Daniel last_name: Slamanig citation: ama: 'Fuchsbauer G, Hanser C, Kamath Hosdurg C, Slamanig D. Practical round-optimal blind signatures in the standard model from weaker assumptions. In: Vol 9841. Springer; 2016:391-408. doi:10.1007/978-3-319-44618-9_21' apa: 'Fuchsbauer, G., Hanser, C., Kamath Hosdurg, C., & Slamanig, D. (2016). Practical round-optimal blind signatures in the standard model from weaker assumptions (Vol. 9841, pp. 391–408). Presented at the SCN: Security and Cryptography for Networks, Amalfi, Italy: Springer. https://doi.org/10.1007/978-3-319-44618-9_21' chicago: Fuchsbauer, Georg, Christian Hanser, Chethan Kamath Hosdurg, and Daniel Slamanig. “Practical Round-Optimal Blind Signatures in the Standard Model from Weaker Assumptions,” 9841:391–408. Springer, 2016. https://doi.org/10.1007/978-3-319-44618-9_21. ieee: 'G. Fuchsbauer, C. Hanser, C. Kamath Hosdurg, and D. Slamanig, “Practical round-optimal blind signatures in the standard model from weaker assumptions,” presented at the SCN: Security and Cryptography for Networks, Amalfi, Italy, 2016, vol. 9841, pp. 391–408.' ista: 'Fuchsbauer G, Hanser C, Kamath Hosdurg C, Slamanig D. 2016. Practical round-optimal blind signatures in the standard model from weaker assumptions. SCN: Security and Cryptography for Networks, LNCS, vol. 9841, 391–408.' mla: Fuchsbauer, Georg, et al. Practical Round-Optimal Blind Signatures in the Standard Model from Weaker Assumptions. Vol. 9841, Springer, 2016, pp. 391–408, doi:10.1007/978-3-319-44618-9_21. short: G. Fuchsbauer, C. Hanser, C. Kamath Hosdurg, D. Slamanig, in:, Springer, 2016, pp. 391–408. conference: end_date: 2016-09-02 location: Amalfi, Italy name: 'SCN: Security and Cryptography for Networks' start_date: 2016-08-31 date_created: 2018-12-11T11:50:49Z date_published: 2016-08-11T00:00:00Z date_updated: 2023-02-23T10:08:16Z day: '11' department: - _id: KrPi doi: 10.1007/978-3-319-44618-9_21 ec_funded: 1 intvolume: ' 9841' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2016/662 month: '08' oa: 1 oa_version: Submitted Version page: 391 - 408 project: - _id: 258C570E-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '259668' name: Provable Security for Physical Cryptography - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication_status: published publisher: Springer publist_id: '6109' quality_controlled: '1' related_material: record: - id: '1647' relation: earlier_version status: public scopus_import: 1 status: public title: Practical round-optimal blind signatures in the standard model from weaker assumptions type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 9841 year: '2016' ...