[{"pubrep_id":"686","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","start_date":"2012-04-15","end_date":"2012-04-19","location":"Cambridge, UK"},"type":"conference","_id":"3282","department":[{"_id":"KrPi"}],"file_date_updated":"2020-07-14T12:46:06Z","ddc":["000","004"],"date_updated":"2021-01-12T07:42:22Z","intvolume":" 7237","month":"03","alternative_title":["LNCS"],"oa_version":"Submitted Version","abstract":[{"text":"Traditionally, symmetric-key message authentication codes (MACs) are easily built from pseudorandom functions (PRFs). In this work we propose a wide variety of other approaches to building efficient MACs, without going through a PRF first. In particular, unlike deterministic PRF-based MACs, where each message has a unique valid tag, we give a number of probabilistic MAC constructions from various other primitives/assumptions. Our main results are summarized as follows: We show several new probabilistic MAC constructions from a variety of general assumptions, including CCA-secure encryption, Hash Proof Systems and key-homomorphic weak PRFs. By instantiating these frameworks under concrete number theoretic assumptions, we get several schemes which are more efficient than just using a state-of-the-art PRF instantiation under the corresponding assumption. For probabilistic MACs, unlike deterministic ones, unforgeability against a chosen message attack (uf-cma ) alone does not imply security if the adversary can additionally make verification queries (uf-cmva ). We give an efficient generic transformation from any uf-cma secure MAC which is "message-hiding" into a uf-cmva secure MAC. This resolves the main open problem of Kiltz et al. from Eurocrypt'11; By using our transformation on their constructions, we get the first efficient MACs from the LPN assumption. While all our new MAC constructions immediately give efficient actively secure, two-round symmetric-key identification schemes, we also show a very simple, three-round actively secure identification protocol from any weak PRF. In particular, the resulting protocol is much more efficient than the trivial approach of building a regular PRF from a weak PRF. © 2012 International Association for Cryptologic Research.","lang":"eng"}],"license":"https://creativecommons.org/licenses/by/4.0/","ec_funded":1,"volume":7237,"language":[{"iso":"eng"}],"file":[{"date_created":"2018-12-12T10:14:23Z","file_name":"IST-2016-686-v1+1_059.pdf","creator":"system","date_updated":"2020-07-14T12:46:06Z","file_size":372292,"file_id":"5074","checksum":"8557c17a8c2586d06ebfe62d934f5c5f","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"publication_status":"published","project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Provable Security for Physical Cryptography","grant_number":"259668"}],"title":"Message authentication, revisited","author":[{"full_name":"Dodis, Yevgeniy","last_name":"Dodis","first_name":"Yevgeniy"},{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Eike","full_name":"Kiltz, Eike","last_name":"Kiltz"},{"full_name":"Wichs, Daniel","last_name":"Wichs","first_name":"Daniel"}],"publist_id":"3364","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Dodis, Yevgeniy, et al. Message Authentication, Revisited. Vol. 7237, Springer, 2012, pp. 355–74, doi:10.1007/978-3-642-29011-4_22.","ieee":"Y. Dodis, K. Z. Pietrzak, E. Kiltz, and D. Wichs, “Message authentication, revisited,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Cambridge, UK, 2012, vol. 7237, pp. 355–374.","short":"Y. Dodis, K.Z. Pietrzak, E. Kiltz, D. Wichs, in:, Springer, 2012, pp. 355–374.","apa":"Dodis, Y., Pietrzak, K. Z., Kiltz, E., & Wichs, D. (2012). Message authentication, revisited (Vol. 7237, pp. 355–374). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Cambridge, UK: Springer. https://doi.org/10.1007/978-3-642-29011-4_22","ama":"Dodis Y, Pietrzak KZ, Kiltz E, Wichs D. Message authentication, revisited. In: Vol 7237. Springer; 2012:355-374. doi:10.1007/978-3-642-29011-4_22","chicago":"Dodis, Yevgeniy, Krzysztof Z Pietrzak, Eike Kiltz, and Daniel Wichs. “Message Authentication, Revisited,” 7237:355–74. Springer, 2012. https://doi.org/10.1007/978-3-642-29011-4_22.","ista":"Dodis Y, Pietrzak KZ, Kiltz E, Wichs D. 2012. Message authentication, revisited. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 7237, 355–374."},"oa":1,"quality_controlled":"1","publisher":"Springer","acknowledgement":"Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC)","date_created":"2018-12-11T12:02:27Z","doi":"10.1007/978-3-642-29011-4_22","date_published":"2012-03-10T00:00:00Z","page":"355 - 374","day":"10","year":"2012","has_accepted_license":"1"},{"volume":7194,"ec_funded":1,"publication_status":"published","language":[{"iso":"eng"}],"alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"http://www.iacr.org/archive/tcc2012/71940166/71940166.pdf"}],"month":"05","intvolume":" 7194","abstract":[{"text":"The (decisional) learning with errors problem (LWE) asks to distinguish "noisy" inner products of a secret vector with random vectors from uniform. The learning parities with noise problem (LPN) is the special case where the elements of the vectors are bits. In recent years, the LWE and LPN problems have found many applications in cryptography. In this paper we introduce a (seemingly) much stronger adaptive assumption, called "subspace LWE" (SLWE), where the adversary can learn the inner product of the secret and random vectors after they were projected into an adaptively and adversarially chosen subspace. We prove that, surprisingly, the SLWE problem mapping into subspaces of dimension d is almost as hard as LWE using secrets of length d (the other direction is trivial.) This result immediately implies that several existing cryptosystems whose security is based on the hardness of the LWE/LPN problems are provably secure in a much stronger sense than anticipated. As an illustrative example we show that the standard way of using LPN for symmetric CPA secure encryption is even secure against a very powerful class of related key attacks. ","lang":"eng"}],"oa_version":"Submitted Version","department":[{"_id":"KrPi"}],"date_updated":"2021-01-12T07:42:21Z","type":"conference","conference":{"end_date":"2012-03-21","location":"Taormina, Sicily, Italy","start_date":"2012-03-19","name":"TCC: Theory of Cryptography Conference"},"status":"public","_id":"3280","page":"548 - 563","date_published":"2012-05-04T00:00:00Z","doi":"10.1007/978-3-642-28914-9_31","date_created":"2018-12-11T12:02:26Z","year":"2012","day":"04","quality_controlled":"1","publisher":"Springer","oa":1,"acknowledgement":"Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC Starting Grant (259668-PSPC).","author":[{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"publist_id":"3366","title":"Subspace LWE","citation":{"mla":"Pietrzak, Krzysztof Z. Subspace LWE. Vol. 7194, Springer, 2012, pp. 548–63, doi:10.1007/978-3-642-28914-9_31.","short":"K.Z. Pietrzak, in:, Springer, 2012, pp. 548–563.","ieee":"K. Z. Pietrzak, “Subspace LWE,” presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy, 2012, vol. 7194, pp. 548–563.","apa":"Pietrzak, K. Z. (2012). Subspace LWE (Vol. 7194, pp. 548–563). Presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy: Springer. https://doi.org/10.1007/978-3-642-28914-9_31","ama":"Pietrzak KZ. Subspace LWE. In: Vol 7194. Springer; 2012:548-563. doi:10.1007/978-3-642-28914-9_31","chicago":"Pietrzak, Krzysztof Z. “Subspace LWE,” 7194:548–63. Springer, 2012. https://doi.org/10.1007/978-3-642-28914-9_31.","ista":"Pietrzak KZ. 2012. Subspace LWE. TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 548–563."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","project":[{"call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425","grant_number":"259668","name":"Provable Security for Physical Cryptography"}]},{"citation":{"ista":"Pietrzak KZ, Rosen A, Segev G. 2012. Lossy functions do not amplify well. TCC: Theory of Cryptography Conference, LNCS, vol. 7194, 458–475.","chicago":"Pietrzak, Krzysztof Z, Alon Rosen, and Gil Segev. “Lossy Functions Do Not Amplify Well,” 7194:458–75. Springer, 2012. https://doi.org/10.1007/978-3-642-28914-9_26.","short":"K.Z. Pietrzak, A. Rosen, G. Segev, in:, Springer, 2012, pp. 458–475.","ieee":"K. Z. Pietrzak, A. Rosen, and G. Segev, “Lossy functions do not amplify well,” presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy, 2012, vol. 7194, pp. 458–475.","ama":"Pietrzak KZ, Rosen A, Segev G. Lossy functions do not amplify well. In: Vol 7194. Springer; 2012:458-475. doi:10.1007/978-3-642-28914-9_26","apa":"Pietrzak, K. Z., Rosen, A., & Segev, G. (2012). Lossy functions do not amplify well (Vol. 7194, pp. 458–475). Presented at the TCC: Theory of Cryptography Conference, Taormina, Sicily, Italy: Springer. https://doi.org/10.1007/978-3-642-28914-9_26","mla":"Pietrzak, Krzysztof Z., et al. Lossy Functions Do Not Amplify Well. Vol. 7194, Springer, 2012, pp. 458–75, doi:10.1007/978-3-642-28914-9_26."},"date_updated":"2021-01-12T07:42:22Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"},{"last_name":"Rosen","full_name":"Rosen, Alon","first_name":"Alon"},{"first_name":"Gil","last_name":"Segev","full_name":"Segev, Gil"}],"publist_id":"3365","title":"Lossy functions do not amplify well","department":[{"_id":"KrPi"}],"_id":"3281","conference":{"name":"TCC: Theory of Cryptography Conference","location":"Taormina, Sicily, Italy","end_date":"2012-03-21","start_date":"2012-03-19"},"type":"conference","status":"public","publication_status":"published","year":"2012","language":[{"iso":"eng"}],"day":"04","page":"458 - 475","date_created":"2018-12-11T12:02:26Z","date_published":"2012-05-04T00:00:00Z","doi":"10.1007/978-3-642-28914-9_26","volume":7194,"abstract":[{"lang":"eng","text":"We consider the problem of amplifying the "lossiness" of functions. We say that an oracle circuit C*: {0,1} m → {0,1}* amplifies relative lossiness from ℓ/n to L/m if for every function f:{0,1} n → {0,1} n it holds that 1 If f is injective then so is C f. 2 If f has image size of at most 2 n-ℓ, then C f has image size at most 2 m-L. The question is whether such C* exists for L/m ≫ ℓ/n. This problem arises naturally in the context of cryptographic "lossy functions," where the relative lossiness is the key parameter. We show that for every circuit C* that makes at most t queries to f, the relative lossiness of C f is at most L/m ≤ ℓ/n + O(log t)/n. In particular, no black-box method making a polynomial t = poly(n) number of queries can amplify relative lossiness by more than an O(logn)/n additive term. We show that this is tight by giving a simple construction (cascading with some randomization) that achieves such amplification."}],"acknowledgement":"We would like to thank Oded Goldreich and Omer Rein- gold for discussions at an early stage of this project, and Scott Aaronson for clarifications regarding the collision problem.\r\n","oa_version":"None","main_file_link":[{"url":"http://www.iacr.org/archive/tcc2012/tcc2012-index.html"}],"alternative_title":["LNCS"],"publisher":"Springer","quality_controlled":"1","intvolume":" 7194","month":"05"},{"date_created":"2018-12-11T12:02:27Z","date_published":"2012-01-01T00:00:00Z","page":"750 - 759","day":"01","publication_status":"published","year":"2012","month":"01","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1008.1555"}],"oa":1,"quality_controlled":0,"publisher":"SIAM","acknowledgement":"Vladimir Kolmogorov is supported by the Royal Academy of Eng ineering/EPSRC.","abstract":[{"text":"We study the complexity of valued constraint satisfaction problems (VCSP). A problem from VCSP is characterised by a constraint language, a fixed set of cost functions over a finite domain. An instance of the problem is specified by a sum of cost functions from the language and the goal is to minimise the sum. Under the unique games conjecture, the approximability of finite-valued VCSPs is well-understood, see Raghavendra [FOCS’08]. However, there is no characterisation of finite-valued VCSPs, let alone general-valued VCSPs, that can be solved exactly in polynomial time, thus giving insights from a combinatorial optimisation perspective.\nWe consider the case of languages containing all possible unary cost functions. In the case of languages consisting of only {0, ∞}-valued cost functions (i.e. relations), such languages have been called conservative and studied by Bulatov [LICS’03] and recently by Barto [LICS’11]. Since we study valued languages, we call a language conservative if it contains all finite-valued unary cost functions. The computational complexity of conservative valued languages has been studied by Cohen et al. [AIJ’06] for languages over Boolean domains, by Deineko et al. [JACM’08] for {0,1}-valued languages (a.k.a Max-CSP), and by Takhanov [STACS’10] for {0,∞}-valued languages containing all finite- valued unary cost functions (a.k.a. Min-Cost-Hom).\nWe prove a Schaefer-like dichotomy theorem for conservative valued languages: if all cost functions in the language satisfy a certain condition (specified by a complementary combination of STP and MJN multimorphisms), then any instance can be solved in polynomial time (via a new algorithm developed in this paper), otherwise the language is NP-hard. This is the first complete complexity classification of general-valued constraint languages over non-Boolean domains. It is a common phenomenon that complexity classifications of problems over non-Boolean domains is significantly harder than the Boolean case. The polynomial-time algorithm we present for the tractable cases is a generalisation of the submodular minimisation problem and a result of Cohen et al. [TCS’08].\nOur results generalise previous results by Takhanov [STACS’10] and (a subset of results) by Cohen et al. [AIJ’06] and Deineko et al. [JACM’08]. Moreover, our results do not rely on any computer-assisted search as in Deineko et al. [JACM’08], and provide a powerful tool for proving hardness of finite-valued and general-valued languages.","lang":"eng"}],"title":"The complexity of conservative valued CSPs","author":[{"first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Vladimir Kolmogorov","last_name":"Kolmogorov"},{"first_name":"Stanislav","full_name":"Živný, Stanislav","last_name":"Živný"}],"publist_id":"3362","extern":1,"citation":{"chicago":"Kolmogorov, Vladimir, and Stanislav Živný. “The Complexity of Conservative Valued CSPs,” 750–59. SIAM, 2012.","ista":"Kolmogorov V, Živný S. 2012. The complexity of conservative valued CSPs. SODA: Symposium on Discrete Algorithms, 750–759.","mla":"Kolmogorov, Vladimir, and Stanislav Živný. The Complexity of Conservative Valued CSPs. SIAM, 2012, pp. 750–59.","ieee":"V. Kolmogorov and S. Živný, “The complexity of conservative valued CSPs,” presented at the SODA: Symposium on Discrete Algorithms, 2012, pp. 750–759.","short":"V. Kolmogorov, S. Živný, in:, SIAM, 2012, pp. 750–759.","apa":"Kolmogorov, V., & Živný, S. (2012). The complexity of conservative valued CSPs (pp. 750–759). Presented at the SODA: Symposium on Discrete Algorithms, SIAM.","ama":"Kolmogorov V, Živný S. The complexity of conservative valued CSPs. In: SIAM; 2012:750-759."},"date_updated":"2021-01-12T07:42:23Z","status":"public","conference":{"name":"SODA: Symposium on Discrete Algorithms"},"type":"conference","_id":"3284"},{"title":"Continuous production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor","article_processing_charge":"No","publist_id":"7531","author":[{"first_name":"Alexey","full_name":"Shavel, Alexey","last_name":"Shavel"},{"full_name":"Cadavid, Doris","last_name":"Cadavid","first_name":"Doris"},{"first_name":"Maria","id":"43C61214-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5013-2843","full_name":"Ibáñez, Maria","last_name":"Ibáñez"},{"full_name":"Carrete, Alex","last_name":"Carrete","first_name":"Alex"},{"first_name":"Andreu","full_name":"Cabot, Andreu","last_name":"Cabot"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","citation":{"ista":"Shavel A, Cadavid D, Ibáñez M, Carrete A, Cabot A. 2012. Continuous production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor. Journal of the American Chemical Society. 134(3), 1438–1441.","chicago":"Shavel, Alexey, Doris Cadavid, Maria Ibáñez, Alex Carrete, and Andreu Cabot. “Continuous Production of Cu Inf 2 Inf ZnSnS Inf 4 Inf Nanocrystals in a Flow Reactor.” Journal of the American Chemical Society. ACS, 2012. https://doi.org/10.1021/ja209688a.","ieee":"A. Shavel, D. Cadavid, M. Ibáñez, A. Carrete, and A. Cabot, “Continuous production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor,” Journal of the American Chemical Society, vol. 134, no. 3. ACS, pp. 1438–1441, 2012.","short":"A. Shavel, D. Cadavid, M. Ibáñez, A. Carrete, A. Cabot, Journal of the American Chemical Society 134 (2012) 1438–1441.","apa":"Shavel, A., Cadavid, D., Ibáñez, M., Carrete, A., & Cabot, A. (2012). Continuous production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor. Journal of the American Chemical Society. ACS. https://doi.org/10.1021/ja209688a","ama":"Shavel A, Cadavid D, Ibáñez M, Carrete A, Cabot A. Continuous production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor. Journal of the American Chemical Society. 2012;134(3):1438-1441. doi:10.1021/ja209688a","mla":"Shavel, Alexey, et al. “Continuous Production of Cu Inf 2 Inf ZnSnS Inf 4 Inf Nanocrystals in a Flow Reactor.” Journal of the American Chemical Society, vol. 134, no. 3, ACS, 2012, pp. 1438–41, doi:10.1021/ja209688a."},"date_updated":"2021-01-12T07:42:29Z","status":"public","article_type":"original","type":"journal_article","_id":"330","date_created":"2018-12-11T11:45:51Z","date_published":"2012-01-02T00:00:00Z","doi":"10.1021/ja209688a","volume":134,"issue":"3","page":"1438 - 1441","language":[{"iso":"eng"}],"publication":"Journal of the American Chemical Society","day":"02","year":"2012","publication_status":"published","intvolume":" 134","month":"01","publisher":"ACS","quality_controlled":"1","oa_version":"None","abstract":[{"lang":"eng","text":"A procedure for the continuous production of Cu 2ZnSnS 4 (CZTS) nanoparticles with controlled composition is presented. CZTS nanoparticles were prepared through the reaction of the metals' amino complexes with elemental sulfur in a continuous-flow reactor at moderate temperatures (300-330 °C). High-resolution transmission electron microscopy and X-ray diffraction analysis showed the nanocrystals to have a crystallographic structure compatible with that of the kesterite. Chemical characterization of the materials showed the presence of the four elements in each individual nanocrystal. Composition control was achieved by adjusting the solution flow rate through the reactor and the proper choice of the nominal precursor concentration within the flowing solution. Single-particle analysis revealed a composition distribution within each sample, which was optimized at the highest synthesis temperatures used. "}]}]