Scholarlink

<p>The Vector Oblivious Linear Evaluation in the Head (VOLEitH) paradigm has proven to be a versatile tool to design zero-knowledge proofs and signatures in post-quantum cryptography. In this paper, we propose three VOLE-friendly modellings for Proofs of Knowledge (PoK) of a solution of an instance of the Linear Code Equivalence Problem (LEP). For the first two schemes, we propose two new reductions from LEP to the Multivariate Quadratic (MQ) problem, that may be of independent interest for the cryptanalysis of LEP. Instead, the last model is obtained by generalizing a recent work by Bettaieb et al. to the context of monomial matrices instead of permutation matrices. While our proposed schemes exhibit larger signature sizes compared to LESS, they improve the computational efficiency, reducing the overall complexity from <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(n^3)\)</EquationSource> </InlineEquation> to <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(O(n^2\log n )\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(O(n^2\log ^2 n )\)</EquationSource> </InlineEquation>, where <i>n</i> is the length of the code.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

VOLE-in-the-head signatures based on the linear code equivalence problem

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年2月17日

查看全文
  • Michele Battagliola,
  • Laura Mattiuz,
  • Alessio Meneghetti

摘要

The Vector Oblivious Linear Evaluation in the Head (VOLEitH) paradigm has proven to be a versatile tool to design zero-knowledge proofs and signatures in post-quantum cryptography. In this paper, we propose three VOLE-friendly modellings for Proofs of Knowledge (PoK) of a solution of an instance of the Linear Code Equivalence Problem (LEP). For the first two schemes, we propose two new reductions from LEP to the Multivariate Quadratic (MQ) problem, that may be of independent interest for the cryptanalysis of LEP. Instead, the last model is obtained by generalizing a recent work by Bettaieb et al. to the context of monomial matrices instead of permutation matrices. While our proposed schemes exhibit larger signature sizes compared to LESS, they improve the computational efficiency, reducing the overall complexity from \(O(n^3)\) to \(O(n^2\log n )\) and \(O(n^2\log ^2 n )\) , where n is the length of the code.