Publication Information

{'id': 'https://openalex.org/W2122086332', 'doi': 'https://doi.org/10.1007/s00037-007-0234-9', 'title': 'Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions', 'display_name': 'Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions', 'publication_year': 2007, 'publication_date': '2007-12-01', 'ids': {'openalex': 'https://openalex.org/W2122086332', 'doi': 'https://doi.org/10.1007/s00037-007-0234-9', 'mag': '2122086332'}, 'language': 'en', 'primary_location': {'is_oa': True, 'landing_page_url': 'https://doi.org/10.1007/s00037-007-0234-9', 'pdf_url': 'https://link.springer.com/content/pdf/10.1007/s00037-007-0234-9.pdf', 'source': {'id': 'https://openalex.org/S193995496', 'display_name': 'Computational Complexity', 'issn_l': '1016-3328', 'issn': ['1016-3328', '1420-8954'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310320186', 'host_organization_name': 'Birkhäuser', 'host_organization_lineage': ['https://openalex.org/P4310320186', 'https://openalex.org/P4310319900', 'https://openalex.org/P4310319965'], 'host_organization_lineage_names': ['Birkhäuser', 'Springer Science+Business Media', 'Springer Nature'], 'type': 'journal'}, 'license': 'cc-by-nc', 'license_id': 'https://openalex.org/licenses/cc-by-nc', 'version': 'publishedVersion', 'is_accepted': True, 'is_published': True}, 'type': 'article', 'type_crossref': 'journal-article', 'indexed_in': ['crossref'], 'open_access': {'is_oa': True, 'oa_status': 'hybrid', 'oa_url': 'https://link.springer.com/content/pdf/10.1007/s00037-007-0234-9.pdf', 'any_repository_has_fulltext': False}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5023640008', 'display_name': 'Daniele Micciancio', 'orcid': 'https://orcid.org/0000-0003-3323-9985'}, 'institutions': [{'id': 'https://openalex.org/I36258959', 'display_name': 'University of California, San Diego', 'ror': 'https://ror.org/0168r3w48', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I36258959']}], 'countries': ['US'], 'is_corresponding': True, 'raw_author_name': 'Daniele Micciancio', 'raw_affiliation_strings': ['Computer Science and Engineering Department, University of California, San Diego, La Jolla, USA 92093-0404'], 'affiliations': [{'raw_affiliation_string': 'Computer Science and Engineering Department, University of California, San Diego, La Jolla, USA 92093-0404', 'institution_ids': ['https://openalex.org/I36258959']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 1, 'corresponding_author_ids': ['https://openalex.org/A5023640008'], 'corresponding_institution_ids': ['https://openalex.org/I36258959'], 'apc_list': {'value': 2290, 'currency': 'EUR', 'value_usd': 2890, 'provenance': 'doaj'}, 'apc_paid': {'value': 2290, 'currency': 'EUR', 'value_usd': 2890, 'provenance': 'doaj'}, 'fwci': 13.542, 'has_fulltext': True, 'fulltext_origin': 'pdf', 'cited_by_count': 237, 'citation_normalized_percentile': {'value': 0.984675, 'is_in_top_1_percent': False, 'is_in_top_10_percent': True}, 'cited_by_percentile_year': {'min': 98, 'max': 99}, 'biblio': {'volume': '16', 'issue': '4', 'first_page': '365', 'last_page': '411'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10237', 'display_name': 'Cryptography and Data Security', 'score': 0.9991, 'subfield': {'id': 'https://openalex.org/subfields/1702', 'display_name': 'Artificial Intelligence'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, 'topics': [{'id': 'https://openalex.org/T10237', 'display_name': 'Cryptography and Data Security', 'score': 0.9991, 'subfield': {'id': 'https://openalex.org/subfields/1702', 'display_name': 'Artificial Intelligence'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T10720', 'display_name': 'Complexity and Algorithms in Graphs', 'score': 0.9962, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T12288', 'display_name': 'Optimization and Search Problems', 'score': 0.9795, 'subfield': {'id': 'https://openalex.org/subfields/1705', 'display_name': 'Computer Networks and Communications'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/lattice-problem', 'display_name': 'Lattice problem', 'score': 0.5578434}, {'id': 'https://openalex.org/keywords/lattice', 'display_name': 'Lattice (music)', 'score': 0.54108465}], 'concepts': [{'id': 'https://openalex.org/C113138325', 'wikidata': 'https://www.wikidata.org/wiki/Q864457', 'display_name': 'Knapsack problem', 'level': 2, 'score': 0.87514293}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.7124168}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.60438615}, {'id': 'https://openalex.org/C168482242', 'wikidata': 'https://www.wikidata.org/wiki/Q6497128', 'display_name': 'Lattice problem', 'level': 3, 'score': 0.5578434}, {'id': 'https://openalex.org/C2781204021', 'wikidata': 'https://www.wikidata.org/wiki/Q6497091', 'display_name': 'Lattice (music)', 'level': 2, 'score': 0.54108465}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.5047933}, {'id': 'https://openalex.org/C33676613', 'wikidata': 'https://www.wikidata.org/wiki/Q13415176', 'display_name': 'Dimension (graph theory)', 'level': 2, 'score': 0.44166762}, {'id': 'https://openalex.org/C311688', 'wikidata': 'https://www.wikidata.org/wiki/Q2393193', 'display_name': 'Time complexity', 'level': 2, 'score': 0.4388864}, {'id': 'https://openalex.org/C2780378348', 'wikidata': 'https://www.wikidata.org/wiki/Q25351438', 'display_name': 'Ring (chemistry)', 'level': 2, 'score': 0.41810793}, {'id': 'https://openalex.org/C14036430', 'wikidata': 'https://www.wikidata.org/wiki/Q3736076', 'display_name': 'Function (biology)', 'level': 2, 'score': 0.41158727}, {'id': 'https://openalex.org/C126255220', 'wikidata': 'https://www.wikidata.org/wiki/Q141495', 'display_name': 'Mathematical optimization', 'level': 1, 'score': 0.17456481}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.12759653}, {'id': 'https://openalex.org/C178489894', 'wikidata': 'https://www.wikidata.org/wiki/Q8789', 'display_name': 'Cryptography', 'level': 2, 'score': 0.09318796}, {'id': 'https://openalex.org/C185592680', 'wikidata': 'https://www.wikidata.org/wiki/Q2329', 'display_name': 'Chemistry', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C121332964', 'wikidata': 'https://www.wikidata.org/wiki/Q413', 'display_name': 'Physics', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C178790620', 'wikidata': 'https://www.wikidata.org/wiki/Q11351', 'display_name': 'Organic chemistry', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C78458016', 'wikidata': 'https://www.wikidata.org/wiki/Q840400', 'display_name': 'Evolutionary biology', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C24890656', 'wikidata': 'https://www.wikidata.org/wiki/Q82811', 'display_name': 'Acoustics', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C86803240', 'wikidata': 'https://www.wikidata.org/wiki/Q420', 'display_name': 'Biology', 'level': 0, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': True, 'landing_page_url': 'https://doi.org/10.1007/s00037-007-0234-9', 'pdf_url': 'https://link.springer.com/content/pdf/10.1007/s00037-007-0234-9.pdf', 'source': {'id': 'https://openalex.org/S193995496', 'display_name': 'Computational Complexity', 'issn_l': '1016-3328', 'issn': ['1016-3328', '1420-8954'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310320186', 'host_organization_name': 'Birkhäuser', 'host_organization_lineage': ['https://openalex.org/P4310320186', 'https://openalex.org/P4310319900', 'https://openalex.org/P4310319965'], 'host_organization_lineage_names': ['Birkhäuser', 'Springer Science+Business Media', 'Springer Nature'], 'type': 'journal'}, 'license': 'cc-by-nc', 'license_id': 'https://openalex.org/licenses/cc-by-nc', 'version': 'publishedVersion', 'is_accepted': True, 'is_published': True}], 'best_oa_location': {'is_oa': True, 'landing_page_url': 'https://doi.org/10.1007/s00037-007-0234-9', 'pdf_url': 'https://link.springer.com/content/pdf/10.1007/s00037-007-0234-9.pdf', 'source': {'id': 'https://openalex.org/S193995496', 'display_name': 'Computational Complexity', 'issn_l': '1016-3328', 'issn': ['1016-3328', '1420-8954'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310320186', 'host_organization_name': 'Birkhäuser', 'host_organization_lineage': ['https://openalex.org/P4310320186', 'https://openalex.org/P4310319900', 'https://openalex.org/P4310319965'], 'host_organization_lineage_names': ['Birkhäuser', 'Springer Science+Business Media', 'Springer Nature'], 'type': 'journal'}, 'license': 'cc-by-nc', 'license_id': 'https://openalex.org/licenses/cc-by-nc', 'version': 'publishedVersion', 'is_accepted': True, 'is_published': True}, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 84, 'referenced_works': ['https://openalex.org/W105728036', 'https://openalex.org/W1485280854', 'https://openalex.org/W149470655', 'https://openalex.org/W1499237070', 'https://openalex.org/W1506941173', 'https://openalex.org/W1519128479', 'https://openalex.org/W1524372733', 'https://openalex.org/W1546634390', 'https://openalex.org/W1553144034', 'https://openalex.org/W1560680010', 'https://openalex.org/W1562285034', 'https://openalex.org/W1582043969', 'https://openalex.org/W1587056734', 'https://openalex.org/W1589844548', 'https://openalex.org/W1592441913', 'https://openalex.org/W1601111578', 'https://openalex.org/W1608795135', 'https://openalex.org/W1675339804', 'https://openalex.org/W1788833175', 'https://openalex.org/W1834548846', 'https://openalex.org/W1868947940', 'https://openalex.org/W1920504236', 'https://openalex.org/W1921478076', 'https://openalex.org/W1968182591', 'https://openalex.org/W1972050218', 'https://openalex.org/W1972792640', 'https://openalex.org/W1975442866', 'https://openalex.org/W1981326822', 'https://openalex.org/W1982051149', 'https://openalex.org/W1989510734', 'https://openalex.org/W1994790157', 'https://openalex.org/W2012045293', 'https://openalex.org/W2012589104', 'https://openalex.org/W2012632515', 'https://openalex.org/W2015281423', 'https://openalex.org/W2015880590', 'https://openalex.org/W2019982338', 'https://openalex.org/W2027528470', 'https://openalex.org/W2029948184', 'https://openalex.org/W2037634865', 'https://openalex.org/W2044378531', 'https://openalex.org/W2050689197', 'https://openalex.org/W2051176401', 'https://openalex.org/W2056492141', 'https://openalex.org/W2060064230', 'https://openalex.org/W2060296335', 'https://openalex.org/W2074196013', 'https://openalex.org/W2074594718', 'https://openalex.org/W2077244027', 'https://openalex.org/W2080137555', 'https://openalex.org/W2083175934', 'https://openalex.org/W2090955183', 'https://openalex.org/W2096221836', 'https://openalex.org/W2101362102', 'https://openalex.org/W2103236224', 'https://openalex.org/W2106287110', 'https://openalex.org/W2110824700', 'https://openalex.org/W2111416661', 'https://openalex.org/W2117362057', 'https://openalex.org/W2122215811', 'https://openalex.org/W2122412778', 'https://openalex.org/W2126483728', 'https://openalex.org/W2132302072', 'https://openalex.org/W2135124252', 'https://openalex.org/W2141040012', 'https://openalex.org/W2142247058', 'https://openalex.org/W2144593761', 'https://openalex.org/W2146633075', 'https://openalex.org/W2150780437', 'https://openalex.org/W2163375015', 'https://openalex.org/W2169649500', 'https://openalex.org/W2180929963', 'https://openalex.org/W2186793764', 'https://openalex.org/W2401610261', 'https://openalex.org/W3014312596', 'https://openalex.org/W3144422206', 'https://openalex.org/W3217775779', 'https://openalex.org/W41804080', 'https://openalex.org/W4205426033', 'https://openalex.org/W4232705780', 'https://openalex.org/W4238141527', 'https://openalex.org/W4251436657', 'https://openalex.org/W4255703439', 'https://openalex.org/W4285719527'], 'related_works': ['https://openalex.org/W4389115646', 'https://openalex.org/W2771248855', 'https://openalex.org/W2757878194', 'https://openalex.org/W2567490660', 'https://openalex.org/W2392212259', 'https://openalex.org/W2071893554', 'https://openalex.org/W1999768565', 'https://openalex.org/W1979729322', 'https://openalex.org/W1572789216', 'https://openalex.org/W1505360842'], 'abstract_inverted_index': {'We': [0, 63, 115], 'investigate': [1], 'the': [2, 9, 68, 72, 78, 92, 98, 101, 112, 121, 140, 172, 180, 199, 206, 215, 228, 231, 257, 284], 'average-case': [3, 287], 'complexity': [4, 246, 253, 288], 'of': [5, 8, 51, 67, 80, 87, 100, 120, 147, 183, 214, 230, 289], 'a': [6, 21, 23, 28, 56, 117, 281], 'generalization': [7], 'compact': [10, 65, 130, 168], 'knapsack': [11, 70, 169], 'problem': [12, 89, 203, 210], 'to': [13, 137], 'arbitrary': [14], 'rings:': [15], 'given': [16], 'm': [17, 24, 41, 82, 157], '(random)': [18, 29], 'ring': [19, 99, 122], 'elements': [20], '1,...,': [22], '∈': [25, 33, 42], 'R': [26, 123], 'and': [27, 77, 124, 205, 238, 251, 271, 286, 295], 'target': [30], 'value': [31], 'b': [32], 'R,': [34], 'find': [35], 'coefficients': [36], 'x': [37, 40, 59], '1,': [38], '...,': [39], 'S': [43, 45, 74, 126], '(where': [44], 'is': [46, 75, 83, 97, 174], 'an': [47], 'appropriately': [48], 'chosen': [49], 'subset': [50, 125], 'R)': [52], 'such': [53], 'that': [54, 127, 132, 152], '∑': [55], 'i': [57, 60], '·': [58], '=': [61, 158], 'b.': [62], 'consider': [64], 'versions': [66], 'generalized': [69, 129, 167], 'where': [71], 'set': [73], 'large': [76], 'number': [79], 'weights': [81], 'small.': [84], 'Most': [85], 'variants': [86], 'this': [88, 196], 'considered': [90, 194], 'in': [91, 107, 111, 195, 227, 256], 'past': [93], '(e.g.,': [94], 'when': [95], '$$R={\\mathbb{Z}}$$': [96], 'integers)': [102], 'can': [103, 276], 'be': [104, 278], 'easily': [105], 'solved': [106], 'polynomial': [108], 'time': [109, 252], 'even': [110, 142], 'worst': [113], 'case.': [114], 'propose': [116], 'new': [118], 'choice': [119], 'yields': [128], 'knapsacks': [131], 'are': [133, 198], 'seemingly': [134], 'very': [135, 144, 236], 'hard': [136, 178], 'solve': [138], 'on': [139, 171, 244], 'average,': [141], 'for': [143, 153, 220], 'small': [145], 'values': [146], 'm.': [148], 'Namely,': [149], 'we': [150], 'prove': [151], 'any': [154], 'unbounded': [155], 'function': [156], 'ω(1)': [159], 'with': [160, 248, 263], 'arbitrarily': [161], 'slow': [162], 'growth': [163], 'rate,': [164], 'solving': [165], 'our': [166], 'problems': [170, 186, 193, 292], 'average': [173], 'at': [175], 'least': [176], 'as': [177, 179, 280], 'worst-case': [181, 191, 245, 285], 'instance': [182], 'various': [184, 290], 'approximation': [185, 221], 'over': [187, 293], 'cyclic': [188, 294], 'lattices.': [189, 297], 'Specific': [190], 'lattice': [192, 291], 'paper': [197], 'shortest': [200], 'independent': [201], 'vector': [202, 217], 'SIVP': [204], 'guaranteed': [207], 'distance': [208], 'decoding': [209], 'GDD': [211], '(a': [212], 'variant': [213], 'closest': [216], 'problem,': [218], 'CVP)': [219], 'factors': [222], 'n': [223], '1+∈': [224], 'almost': [225, 254], 'linear': [226, 255], 'dimension': [229], 'lattice.': [232], 'Our': [233, 274], 'results': [234, 275], 'yield': [235], 'efficient': [237], 'provably': [239], 'secure': [240], 'one-way': [241], 'functions': [242], '(based': [243], 'assumptions)': [247], 'key': [249, 269], 'size': [250, 270], 'security': [258, 265], 'parameter': [259], 'n.': [260], 'Previous': [261], 'constructions': [262], 'similar': [264], 'guarantees': [266], 'required': [267], 'quadratic': [268], 'computation': [272], 'time.': [273], 'also': [277], 'formulated': [279], 'connection': [282], 'between': [283], 'quasi-cyclic': [296]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2122086332', 'counts_by_year': [{'year': 2024, 'cited_by_count': 10}, {'year': 2023, 'cited_by_count': 15}, {'year': 2022, 'cited_by_count': 25}, {'year': 2021, 'cited_by_count': 9}, {'year': 2020, 'cited_by_count': 11}, {'year': 2019, 'cited_by_count': 8}, {'year': 2018, 'cited_by_count': 20}, {'year': 2017, 'cited_by_count': 13}, {'year': 2016, 'cited_by_count': 12}, {'year': 2015, 'cited_by_count': 16}, {'year': 2014, 'cited_by_count': 17}, {'year': 2013, 'cited_by_count': 10}, {'year': 2012, 'cited_by_count': 18}], 'updated_date': '2024-12-26T17:51:54.268669', 'created_date': '2016-06-24'}