2024-03-29T13:24:47Zhttp://uvadoc.uva.es/oai/requestoai:uvadoc.uva.es:10324/317382021-06-24T07:41:07Zcom_10324_32197com_10324_952com_10324_894com_10324_1129com_10324_931col_10324_32199col_10324_1193
Márquez Corbella, Irene
14454058-4fec-49ea-b8aa-026a72012965
500
Martínez Moro, Edgar
c5ef9023b86c1566
500
0000-0003-1243-2049
Pellikaan, Ruud
7d12f1d5-a60f-4e89-802b-a8042238f76b
500
Ruano Benito, Diego
721b449b68d900c9
500
0000-0001-7304-0087
2018-09-25T09:51:47Z
2018-09-25T09:51:47Z
2014
Journal of Symbolic Computation. Volume 64, pages 67-87 (2014)
http://uvadoc.uva.es/handle/10324/31738
http://dx.doi.org/10.1016/j.jsc.2013.12.007
Producción Científica
Code-based cryptography is an interesting alternative to classic number-theoretic public key cryptosystem since it is conjectured to be secure against quantum computer attacks. Many families of codes have been proposed for these cryptosystems such as algebraic geometry codes. In [Designs, Codes and Cryptography, pages 1-16, 2012] -for so called very strong algebraic geometry codes $\mathcal C=C_L(\mathcal X, \mathcal P, E)$, where $\mathcal X$ is an algebraic curve over $\mathbb F_q$, $\mathcal P$ is an $n$-tuple of mutually distinct $\mathbb F_q$-rational points of $\mathcal X$ and $E$ is a divisor of $\mathcal X$ with disjoint support from $\mathcal P$ --- it was shown that an equivalent representation $\mathcal C=C_L(\mathcal Y, \mathcal Q, F)$ can be found. The $n$-tuple of points is obtained directly from a generator matrix of $\mathcal C$, where the columns are viewed as homogeneous coordinates of these points. The curve $\mathcal Y$ is given by $I_2(\mathcal Y)$, the homogeneous elements of degree $2$ of the vanishing ideal $I(\mathcal Y)$. Furthermore, it was shown that $I_2(\mathcal Y)$ can be computed efficiently as the kernel of certain linear map. What was not shown was how to get the divisor $F$ and how to obtain efficiently an adequate decoding algorithm for the new representation. The main result of this paper is an efficient computational approach to the first problem, that is getting $F$. The security status of the McEliece public key cryptosystem using algebraic geometry codes is still not completely settled and is left as an open problem
This research was partly supported by the Danish National Research Foundation and the National Science Foundation of China (Grant No.\ 11061130539) for the Danish-Chinese Center for Applications of Algebraic Geometry in Coding Theory and Cryptography and by Spanish grants MTM2007-64704, MTM2010-21580-C02-02 and MTM2012-36917-C03-03. Part of the research of the second author is also funded by the Vernon Wilson Endowed Chair at Eastern Kentucky University during his sabbatical leave.
application/pdf
eng
info:eu-repo/semantics/openAccess
http://creativecommons.org/licenses/by-nc-nd/4.0/
Attribution-NonCommercial-NoDerivatives 4.0 International
Computational Aspects of Retrieving a Representation of an Algebraic Geometry Code
info:eu-repo/semantics/article
SI
ORIGINAL
JSC2014eprint.pdf
JSC2014eprint.pdf
application/pdf
463961
https://uvadoc.uva.es/bitstream/10324/31738/1/JSC2014eprint.pdf
de8ec12a262f42e1653035ffaf4ee170
MD5
1
CC-LICENSE
license_url
license_url
text/plain
49
https://uvadoc.uva.es/bitstream/10324/31738/2/license_url
4afdbb8c545fd630ea7db775da747b2f
MD5
2
license_text
license_text
text/html; charset=utf-8
0
https://uvadoc.uva.es/bitstream/10324/31738/3/license_text
d41d8cd98f00b204e9800998ecf8427e
MD5
3
license_rdf
license_rdf
application/rdf+xml; charset=utf-8
0
https://uvadoc.uva.es/bitstream/10324/31738/4/license_rdf
d41d8cd98f00b204e9800998ecf8427e
MD5
4
LICENSE
license.txt
license.txt
text/plain
4250
https://uvadoc.uva.es/bitstream/10324/31738/5/license.txt
909e634ba52becf192e4e9b4bcde7863
MD5
5
THUMBNAIL
JSC2014eprint.pdf.jpg
JSC2014eprint.pdf.jpg
IM Thumbnail
image/jpeg
3649
https://uvadoc.uva.es/bitstream/10324/31738/6/JSC2014eprint.pdf.jpg
36e395388b584b316aaf1a3064262a33
MD5
6
10324/31738
oai:uvadoc.uva.es:10324/31738
2021-06-24 09:41:07.948
UVaDOC
repositorio@uva.es
QUNVRVJETyBERSAgRURJQ0kmT2FjdXRlO04gRUxFQ1RSJk9hY3V0ZTtOSUNBIFkgRElGVVNJJk9hY3V0ZTtOIEVOIElOVEVSTkVUIAoKRWwgb2JqZXRpdm8gZnVuZGFtZW50YWwgZGVsIFJlcG9zaXRvcmlvIEluc3RpdHVjaW9uYWwgIGVzICBsYSBkaXZ1bGdhY2kmb2FjdXRlO24gZGUgbGEgUFJPRFVDQ0kmT2FjdXRlO04gQ0lFTlQmSWFjdXRlO0ZJQ0EgCmRlIGxhIFVuaXZlcnNpZGFkICBkZSBWYWxsYWRvbGlkLCBwYXJhIGxvIGN1YWwgbGEgVW5pdmVyc2lkYWQgcG9uZSBsb3MgbWVkaW9zIHQmZWFjdXRlO2NuaWNvcyBuZWNlc2FyaW9zIG9mcmVjaWVuZG8gIHVuYSAgCmJhc2UgIGRlICBkYXRvcyAgYSB0ZXh0byBjb21wbGV0byB5IGVuIGZvcm1hdG8gZWxlY3RyJm9hY3V0ZTtuaWNvLCBhIHRyYXYmZWFjdXRlO3MgZGUgSW50ZXJuZXQsIGZhY2lsaXRhbmRvIGFzJmlhY3V0ZTsgCmxhIHZpc2liaWxpZGFkIHkgYWNjZXNvIGEgbGEgaW5mb3JtYWNpJm9hY3V0ZTtuIGNpZW50JmlhY3V0ZTtmaWNhIHkgdCZlYWN1dGU7Y25pY2EuCgpQYXJhICBxdWUgIGVsIFJlcG9zaXRvcmlvIGRlIGxhIFVuaXZlcnNpZGFkIGRlIFZhbGxhZG9saWQgcHVlZGEgcmVwcm9kdWNpciAgeSAgY29tdW5pY2FyIHAmdWFjdXRlO2JsaWNhbWVudGUgc3UgCmRvY3VtZW50byBlcyBuZWNlc2FyaW8gbGEgYWNlcHRhY2kmb2FjdXRlO24gZGUgbG9zIHNpZ3VpZW50ZXMgdCZlYWN1dGU7cm1pbm9zLgoKQWNlcHRhbmRvIGVzdGUgQWN1ZXJkbywgdXN0ZWQgIE1BTklGSUVTVEE6CgpQUklNRVJPOiBTZXIgIEVsIGF1dG9yIGRlIGVzdGUgVHJhYmFqbyB5IHRpdHVsYXIgZGUgbG9zIGRlcmVjaG9zIGRlICBwcm9waWVkYWQgIGludGVsZWN0dWFsLiAgTWFuaWZlc3RhbmRvICBxdWUgc29icmUgCmxhIG1pc21hIG5vIHRpZW5lIGNvbnRyYSZpYWN1dGU7ZG9zIG5pIGNvbnRyYWVyJmFhY3V0ZTsgY29tcHJvbWlzb3MgbyBncmF2JmFhY3V0ZTttZW5lcyBkZSBuaW5ndW5hIGVzcGVjaWUgIHF1ZSBhdGVudGVuIApjb250cmEgbG9zIGRlcmVjaG9zIHF1ZSBhIGxhIFVuaXZlcnNpZGFkIGxlIGNvcnJlc3BvbmRhbi4KU0VHVU5ETzogUXVlIGVsIGRvY3VtZW50byBlcyB1biB0cmFiYWpvIG9yaWdpbmFsIHN1eW8geSBxdWUgdGllbmUgZGVyZWNobyAgcGFyYSAgb3RvcmdhciAgIGxvcyBkZXJlY2hvcyBjb250ZW5pZG9zIAplbiBlc3RlIGFjdWVyZG8uIApEZWNsYXJhICBxdWUgIHN1IGRvY3VtZW50byBubyBpbmZyaW5nZSwgZW4gdGFudG8gZW4gY3VhbnRvIGxlIHNlYSBwb3NpYmxlICBzYWJlciwgIGxvcyAgZGVyZWNob3MgZGUgYXV0b3IgZGUgbmluZ3VuYSAKb3RyYSBwZXJzb25hIG8gZW50aWRhZC4KVEVSQ0VSTzogU2kgZWwgZG9jdW1lbnRvIGNvbnRpZW5lIG1hdGVyaWFsZXMgZGUgbG9zIGN1YWxlcyBubyB0aWVuZSBsb3MgIGRlcmVjaG8gIGRlICBhdXRvciwgIGRlY2xhcmEgIHF1ZSAgaGEgIG9idGVuaWRvCmVsIHBlcm1pc28gc2luIHJlc3RyaWNjaSZvYWN1dGU7biBkZWwgcHJvcGlldGFyaW8gZGUgbG9zIGRlcmVjaG8gZGUgYXV0b3IgcGFyYSBvdG9yZ2FyIGEgbGEgIFVuaXZlcnNpZGFkICBkZSAgVmFsbGFkb2xpZCwgIApsb3MgIGRlcmVjaG8gIHJlcXVlcmlkb3MgcG9yIGVzdGUgQWN1ZXJkbyAgeSAgcXVlICBlc2UgbWF0ZXJpYWwgIGN1eW9zICBkZXJlY2hvcyBzb24gZGUgdGVyY2Vyb3MgZXN0JmFhY3V0ZTsgY2xhcmFtZW50ZSAgCmlkZW50aWZpY2FkbyB5ICByZWNvbm9jaWRvICBlbiBlbCB0ZXh0byBvIGNvbnRlbmlkbyBkZWwgZG9jdW1lbnRvIGVudHJlZ2Fkby4KQ1VBUlRPOiBTaSBlbCBkb2N1bWVudG8gc2UgYmFzYSBlbiB1bmEgb2JyYSBxdWUgaGEgc2lkbyBwYXRyb2NpbmFkYQpvIGFwb3lhZGEgcG9yIHVuYSBhZ2VuY2lhIHUgb3JnYW5pemFjaSZvYWN1dGU7biBkaWZlcmVudGUgZGUgbGEgVW5pdmVyc2lkYWQgZGUgVmFsbGFkb2xpZCBzZSBwcmVzdXBvbmUgcXVlIHNlIGhhIGN1bXBsaWRvIApjb24gY3VhbHF1aWVyIGRlcmVjaG8gZGUgcmV2aXNpJnVhY3V0ZTtuIHUgb3RyYXMgb2JsaWdhY2lvbmVzIHJlcXVlcmlkYXMgcG9yIGVzdGUgQWN1ZXJkby4KUVVJTlRPOiBSZWNvbm9jZXIgcXVlIGFjZXB0YW5kbyBlc3RlIEFjdWVyZG8sIGVmZWN0JnVhY3V0ZTthIHVuYSAgY2VzaSZvYWN1dGU7biAKbm8gZXhjbHVzaXZhIGRlIGVzdGUgVHJhYmFqbyBhIGxhIFVuaXZlcnNpZGFkIGRlIFZhbGxhZG9saWQsICBjb24gY2FyJmFhY3V0ZTtjdGVyICBncmF0dWl0byB5ICBjb24gZmluZXMgZXhjbHVzaXZhbWVudGUgZGUgCmludmVzdGlnYWNpJm9hY3V0ZTtuIHkgZG9jZW5jaWEsICBhcyZpYWN1dGU7ICBjb21vICBsYSAgY2VzaSZvYWN1dGU7biBubyBleGNsdXNpdmEgZGUgIGxvcyBkZXJlY2hvcyBkZSByZXByb2R1Y2NpJm9hY3V0ZTtuLCAKY29tdW5pY2FjaSZvYWN1dGU7biAgeSAgZGlzdHJpYnVjaSZvYWN1dGU7biAgZGUgIHN1ICB0cmFiYWpvIG11bmRpYWxtZW50ZSwgZW4gZm9ybWF0byBlbGVjdHImb2FjdXRlO25pY28gcGFyYSBzdSBkaWZ1c2kmb2FjdXRlO24gCnAmdWFjdXRlO2JsaWNhLiAKTGEgdGl0dWxhcmlkYWQgZGUgbG9zIGRlcmVjaG9zIGRlIGV4cGxvdGFjaSZvYWN1dGU7biBkZSBsYSBwcm9waWVkYWQgaW50ZWxlY3R1YWwgc29icmUgbGEgb2JyYSBwZXJ0ZW5lY2UgeSBzZWd1aXImYWFjdXRlOyAKcGVydGVuZWNpZW5kbyBhbCBBdXRvci4KCkxhIFVuaXZlcnNpZGFkIGRlIFZhbGxhZG9saWQsIGVuIHZpcnR1ZCBkZWwgcHJlc2VudGUgQWN1ZXJkbyAKREVDTEFSQSBRdWU6CgpQUklNRVJPOiBBbGJlcmdhciZhYWN1dGU7IGVuIGVsIHJlcG9zaXRvcmlvIGluc3RpdHVjaW9uYWwgZGUgbGEgVW5pdmVyc2lkYWQgZGUgIFZhbGxhZG9saWQgIGVzdGUgVHJhYmFqby4gU2luIHBlcmp1aWNpbyBkZSBxdWUgCmVuIHVuIGZ1dHVybywgY29uIGVsIG9iamV0aXZvIGRlIGNvbnNlZ3VpciB1bmEgbWF5b3IgZGlmdXNpJm9hY3V0ZTtuLCBzZWEgcmVjb2dpZG8gdGFtYmkmZWFjdXRlO24gZW4gb3Ryb3MgcmVwb3NpdG9yaW9zIHF1ZSAKcHVlZGFuIGNvbnN0aXR1aXJzZSBhIG5pdmVsIHJlZ2lvbmFsLG5hY2lvbmFsIG8gaW50ZXJuYWNpb25hbC4gClNFR1VORE86IExhIFVuaXZlcnNpZGFkIGRlIFZhbGxhZG9saWQgcG9uZHImYWFjdXRlOyBhIGRpc3Bvc2ljaSZvYWN1dGU7biBkZSBzdXMgdXN1YXJpb3MgbGEgIFBST0RVQ0NJJk9hY3V0ZTtOIENJRU5UJklhY3V0ZTtGSUNBIApwYXJhIGVsIHVzbyBwcml2YWRvIHkgZmluZXMgZGUgaW52ZXN0aWdhY2kmb2FjdXRlO24gIHkgIGRvY2VuY2lhICBhdW5xdWUgIG5vIGdhcmFudGl6YSBuaSBhc3VtZSBuaW5ndW5hIHJlc3BvbnNhYmlsaWRhZCAgcG9yICAKbGFzICBmb3JtYXMgIGVuICBxdWUgIGxvcyAgdXN1YXJpb3MgIGhhZ2FuIHBvc3Rlcmlvcm1lbnRlIHVzbyBkZSBzdSBUcmFiYWpvLgpURVJDRVJPOiBMYSBVbml2ZXJzaWRhZCBubyB0aWVuZSBsYSBpbnRlbmNpJm9hY3V0ZTtuIGRlIGNlbnN1cmFyIG5pIHJldmlzYXIgZWwgVHJhYmFqbyBkZWwgYXV0b3IgeSBlbiBjb25zZWN1ZW5jaWEgc2VyJmFhY3V0ZTsgCmVsIGF1dG9yICByZXNwb25zYWJsZSBkZWwgY29udGVuaWRvIGRlIHN1IG9icmEuCkNVQVJUTzogRW4gZWwgcmVwb3NpdG9yaW8gaW5zdGl0dWNpb25hbCBkZSBsYSBVbml2ZXJzaWRhZCBkZSBWYWxsYWRvbGlkICBzZSBoYXImYWFjdXRlOyBtZW5jaSZvYWN1dGU7biBleHByZXNhIGEgbG9zIHVzb3MgCmF1dG9yaXphZG9zIGRlIGxhIG9icmEsIGJham8gbGEgbGljZW5jaWEgQ3JlYXRpdmUgQ29tbW9ucyBzZWxlY2Npb25hZGFzIHBvciBlbCBhdXRvciBkZWwgVHJhYmFqby4KCkVsIHByZXNlbnRlIEFjdWVyZG8gZW50cmFyJmFhY3V0ZTsgZW4gdmlnb3IgZW4gZXN0ZSBtb21lbnRvIHkgdGVuZHImYWFjdXRlOyB1bmEgZHVyYWNpJm9hY3V0ZTtuIGluZGVmaW5pZGEuIFNpbiBwZXJqdWljaW8gZGUgCmVzdGEgZHVyYWNpJm9hY3V0ZTtuIGluZGVmaW5pZGEgaW5pY2lhbG1lbnRlIHBhY3RhZGEsIHNlIHBvZHImYWFjdXRlOyBwb25lciBmaW4gYWwgcHJlc2VudGUgQWN1ZXJkbzogcG9yIHZvbHVudGFkIGRlIGxhcyBwYXJ0ZXMsIApwb3IgaW5jdW1wbGltaWVudG8gZGUgY3VhbHF1aWVyYSBkZSBsYXMgb2JsaWdhY2lvbmVzIGRlcml2YWRhcyBkZWwgQWN1ZXJkbywgcG9yIHZvbHVudGFkIGV4cHJlc2EgZGVsIEF1dG9yCkVuICBwcnVlYmEgZGUgY29uZm9ybWlkYWQsIGxhcyBwYXJ0ZXMgYWNlcHRhbiBlbCBwcmVzZW50ZSBBY3VlcmRvCgoKCgo=