1,721,010 research outputs found
A New Formulation of the Linear Equivalence Problem and Shorter LESS Signatures
No full textThe Linear Equivalence Problem (LEP) asks to find a linear isometry between a given pair of linear codes; in the Hamming weight this is known as a monomial map. LEP has been used in cryptography to design the family of LESS signatures, which includes also some advanced schemes, such as ring and identity-based signatures. All of these schemes are obtained applying the Fiat-Shamir transformation to a Sigma protocol, in which the prover's responses contain a description of how the monomial map acts on all code coordinates; such a description constitutes the vast majority of the signature size. In this paper, we propose a new formulation of LEP, which we refer to as Information-Set (IS)-LEP. Exploiting IS-LEP, it is enough for the prover to provide the description of the monomial action only on an information set, instead of all the coordinates. Thanks to this new formulation, we are able to drastically reduce signature sizes for all LESS signature schemes, without any relevant computational overhead. We prove that IS-LEP and LEP are completely equivalent (indeed, the same problem), which means that improvement comes with no additional security assumption, either
An attack on a non-interactive key exchange from code equivalence
Full text linkA recent paper by Zhang and Zhang claims to construct the first code-based non-interactive key exchange protocol, using a modified version of the Code Equivalence Problem. In this paper we explain why this approach is flawed. Namely, we describe an attack which involves only linear algebra and completely breaks the protocol with overwhelming probability. A simple Magma script confirms our results
Cutting the GRASS: Threshold GRoup Action Signature Schemes
Full text linkGroup actions are fundamental mathematical tools, with a long history of use in cryptography. Indeed, the action of finite groups at the basis of the discrete logarithm problem is behind a very large portion of modern cryptographic systems. With the advent of post-quantum cryptography, however, other group actions, such as isogeny-based ones, received interest from the cryptographic community, attracted by the possibility of translating old discrete logarithm-based functionalities.
Usually, research focuses on abelian group actions; however in this work we show that isomorphism problems which stem from non-abelian cryptographic group actions can be viable building blocks for threshold signature schemes. In particular, we construct a full N-out-of-N threshold signature scheme, and discuss the efficiency issues arising from extending it to the generic T-out-of-N case. To give a practical outlook on our constructions, we instantiate them with two different flavors of code-based cryptographic group actions, respectively at the basis of the LESS and MEDS signature schemes, two of NIST’s candidates in the recent call for post-quantum standardization
On the computational hardness of the code equivalence problem in cryptography
Full text linkCode equivalence is a well-known concept in coding theory. Recently, literature saw an increased interest in this notion, due to the introduction of protocols based on the hardness of finding the equivalence between two linear codes. In this paper, we analyze the security of code equivalence, with a special focus on the hardest instances, in the interest of cryptographic usage. Our work stems from a thorough review of existing literature, identifies the various types of solvers for the problem, and provides a precise complexity analysis, where previously absent.
Furthermore, we are able to improve on the state of the art, providing more efficient algorithm variations, for which we include numerical simulation data. Our results include also a dedicated method for solving code equivalence with a quantum algorithm, as well as a refinement of quantum Information-Set Decoding (ISD) algorithms. In the end, the goal of this paper is to provide a complete, single point of access, which can be used as a tool for designing schemes that rely on the code equivalence problem
A new path to code-based signatures via identification schemes with restricted errors
No full textIn this paper, we introduce a new variant of the syndrome decoding problem (SDP), called restricted SDP (R-SDP), in which the entries of the solution vector live in a fixed subset of the underlying finite field. We prove the NP-completeness of R-SDP via a reduction from SDP and show how this new problem can be employed in identification schemes. We revisit some concepts of classical coding theory in light of this new setting, provide several bounds such as the Gilbert-Varshamov, the Singleton, and the Plotkin bound, and study the behavior of random codes. Resulting from this initial work, several proposals have arisen; in particular, the code-based digital signature scheme named CROSS, which is currently competing within NIST's additional call for post-quantum digital signatures, is based on R-SDP
Enhancing Threshold Group Action Signature Schemes: Adaptive Security and Scalability Improvements
Full text linkDesigning post-quantum digital signatures is a very active research area at present, with several protocols being developed, based on a variety of mathematical assumptions. Many of these signatures schemes can be used as a basis to define more advanced schemes, such as ring or threshold signatures, where multiple parties are involved in the signing process. Unfortunately, the majority of these protocols only considers a static adversary, that must declare which parties to corrupt at the beginning of the execution. However, a stronger security notion can be achieved, namely security against adaptive adversaries, that can corrupt parties at any times. In this paper we tackle the challenges of designing a post-quantum adaptively secure threshold signature scheme: starting from the GRASS signature scheme, which is only static secure, we show that it is possible to turn it into an adaptive secure threshold signature that we call GRASS+. In particular, we introduce two variants of the classical GAIP problem and discuss their security. We prove that our protocol is adaptively secure in the Random Oracle Model, if the adversary corrupts only t2 parties. We are also able to prove that GRASS+ achieves full adaptive security, with a corruption threshold of t, in the Black Box Group Action Model with Random Oracle. Finally, we improve the performance of the scheme by exploiting a better secret sharing, inspired from the work of Desmedt, Di Crescenzo, and Burmester from ASIACRYPT’94
Reproducible families of codes and cryptographic applications
Full text linkStructured linear block codes such as cyclic, quasi-cyclic and quasi-dyadic codes have gained an increasing role in recent years both in the context of error control and in that of code-based cryptography. Some well known families of structured linear block codes have been separately and intensively studied, without searching for possible bridges between them. In this article, we start from well known examples of this type and generalize them into a wider class of codes that we call â.,±-reproducible codes. Some families of â.,±-reproducible codes have the property that they can be entirely generated from a small number of signature vectors, and consequently admit matrices that can be described in a very compact way. We denote these codes as compactly reproducible codes and show that they encompass known families of compactly describable codes such as quasi-cyclic and quasi-dyadic codes. We then consider some cryptographic applications of codes of this type and show that their use can be advantageous for hindering some current attacks against cryptosystems relying on structured codes. This suggests that the general framework we introduce may enable future developments of code-based cryptography
A Reaction Attack Against Cryptosystems Based on LRPC Codes
Full text linkContains fulltext :
207833.pdf (Publisher’s version ) (Open Access)Progress in Cryptology – LATINCRYPT 201
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
