Zero-Knowledge Argument for Simultaneous Discrete Logarithms

In Crypto 1992, Chaum and Pedersen introduced a protocol (CP protocol for short) for proving the equality of two discrete logarithms (EQDL) with unconditional soundness, which is widely used nowadays and plays a central role in DL-based cryptography. Somewhat surprisingly, the CP protocol has never been improved for nearly two decades since its advent. We note that the CP protocol is usually used as a non-interactive proof by using the Fiat-Shamir heuristic, which inevitably relies on the random oracle model (ROM) and assumes that the adversary is computationally bounded. In this paper, we present an EQDL protocol in the ROM which saves approximately 40% of the computational cost and approximately 33% of the prover??s outgoing message size when instantiated with the same security parameter. The catch is that our security guarantee only holds for computationally bounded adversaries. Our idea can be naturally extended for simultaneously showing the equality of n discrete logarithms with O(1)-size commitment, in contrast to the n-element adaption of the CP protocol which requires O(n)-size. This improvement benefits a variety of interesting cryptosystems, ranging from signatures and anonymous credential systems, to verifiable secret sharing and threshold cryptosystems. As an example, we present a signature scheme that only takes one (offline) exponentiation to sign, without utilizing pairing, relying on the standard decisional Diffie-Hellman assumption.     

基于离散对数和单向函数的代理签名方案

该文基于离散对数问题和单向函数的安全性,提出了一个新的安全代理签名方案。方案引入授权文书和时间证书等概念,克服了代理人滥用权力的缺陷,使代理人只能在特定时间内进行次数一定的代理签名;新设计的算法,有效分离了实际签名权和代理签名权,克服了签名验证者不易理解所收到的签名究竟是某人自己的真实签名还是受人之托的代理签名的缺陷。分析表明,新方案是一个安全可行的代理签名方案,具有较好的理论价值和应用价值。     

Idempotent Computation over Finite Fields

In this paper, we provide an account of several new techniques for computing the primitive idempotents of a commutative artinian algebra over a finite field. Examples of such algebras include the center of a finite group algebra or any finite dimensional quotient of a polynomial ring. The computational methods described are applicable in fairly general situations and the algorithms presented are easily programmed. Both pseudocode and operation counts are provided. As an application, the problem of factoring polynomials over finite fields is discussed.     

有限域上稀疏多元多项式插值算法

稀疏插值是一种降低计算机代数算法时间复杂度的有效方法,在信号处理、压缩感知、结式计算、图像处理等领域都有广泛应用。为了提高稀疏多元多项式插值算法的效率,对Javadi/Monagan稀疏插值算法进行了改进。首先,消除了必须预先给定项数界T的限制,通过计算特定的矩阵行列式,得到插值多项式f的准确项数。然后,消除了必须预先给定次数界D的限制,通过构造辅助函数,利用概率法结合提前终止技术的Cauchy插值法,得到插值多项式f的准确次数,解决了Javadi和Monagan论文中提出的次数界D过高而导致的高计算复杂度的问题。理论分析和实验结果表明了改进算法的优势,特别是在给定的次数界D过高的情况下,相较于Javadi/Monagan算法,改进算法的性能有较大提高。更进一步,由于改进算法无须给定项数界T和次数界D,对于实际问题在利用插值恢复或近似时更具实用性。     

Factoring in Skew-polynomial Rings over Finite Fields

Efficient algorithms are presented for factoring polynomials in the skew-polynomial ringF[x;σ], a non-commutative generalization of the usual ring of polynomialsF[x], whereFis a finite field and σ:F → Fis an automorphism (iterated Frobenius map). Applications include fast functional decomposition algorithms for a class of polynomials inF[x] whose decompositions are “wild” and previously thought to be difficult to compute.     

A Method for Fast Computation of the Fourier Transform over a Finite Field

We consider the problem of fast computation of the Fourier transform over a finite field by decomposing an arbitrary polynomial into a sum of linearized polynomials. Examples of algorithms for the Fourier transform with complexity less than that of the best known analogs are given.     

Efficient Decomposition of Associative Algebras over Finite Fields

We present new, efficient algorithms for some fundamental computations with finite-dimensional (but not necessarily commutative) associative algebras over finite fields. For a semisimple algebra A we show how to compute a complete Wedderburn decomposition of A as a direct sum of simple algebras, an isomorphism between each simple component and a full matrix algebra, and a basis for the centre of A. If A is given by a generating set of matrices inF^m × m, then our algorithm requires aboutO (m³) operations inF, in addition to the cost of factoring a polynomial inF[ x ] of degree O(m), and the cost of generating a small number of random elements from A. We also show how to compute a complete set of orthogonal primitive idempotents in any associative algebra over a finite field in this same time.     

有限域上二次型的密码学特性

该文给出有限域上二次型的紧致表示形式,讨论了它们的密码学特性;给出了特征等于2的有限域上．二次型是平衡函数的充要条件,并指出特征不等于2的有限域上．二次型都不是平衡函数;给出了二次函数是平衡函数的充要条件．从该文结果可以看出Pieprzyk等用二次函数构造的方案是错误的．     

Multi-twisted Additive Codes with Complementary Duals over Finite Fields

Problems of Information Transmission - Multi-twisted (MT) additive codes over finite fields form an important class of additive codes and are generalizations of constacyclic additive codes. In this...     

Factorization of Polynomials over Finite Fields and Characteristic Sequences

A new factorization algorithm for polynomials over finite fields was recently developed by the first author. For finite fields of characteristic 2, it is known from previous work that this algorithm has several advantages over the classical Berlekamp algorithm. In this paper we show that the linearization step in the new algorithm is feasible—in the sense that it can be carried out in polynomial time—for arbitrary finite fields, by using an approach based on decimation operators and characteristic linear recurring sequences. We also introduce a general principle for the linearization of the factorization problem for polynomials over finite fields.     

离散场的一种快速体绘制方法

针对大规模离散数据场的特点,首先给出了三维直线的两种体素化表示方法,然后建立了三维离散直线的基路径,并提出了基于基路径的直接体绘制方法。该方法由于充分利用了射线之间的相关性,所以可明显加速体绘制过程,且对高分辨率离散数据场有普遍的应用价值。     

一种基于有限域的快速乘法器的设计与实现

基于有限域上椭圆曲线公开密匙协议的离散对数计算算法正日益成为热点,而有限域上的计算尤其是乘法计算极大地影响其加／解密速度。为了提高椭圆曲线密码系统的计算速度,需要从很多方面考虑,但其中关键的一点在于如何提高乘法器的速度,且保持其规模在能够接受的范围。在对椭圆曲线的分析基础上提出了一种有限复合域GF((2^m1)^m2)上的快速乘法器。该乘法器采用并行计算和串行计算相结合的原则,在增加少量硬件规模将一次有限域乘法的计算速度由原来的m=m2m1个时钟周期降低到m2个时钟周期,从而极大地提高了乘法器的计算速度。通过FPGA的验证测试证明该方法在速度上完全适合椭圆曲线密码系统。     

Calculating Invariant Rings of Finite Groups over Arbitrary Fields

An algorithm is presented which calculates rings of polynomial invariants of finite linear groups over an arbitrary fieldK. Up to now, such algorithms have been available only for the case that the characteristic ofKdoes not divide the group order. Some applications to the question whether a modular invariant ring is Cohen—Macaulay or isomorphic to a polynomial ring are discussed.     

特征3有限域上的椭圆曲线算法改进

减少求逆运算次数是快速计算椭圆曲线密码的主要方法之一。若采用逐次累加的方法计算特征3有限域上椭圆曲线标量乘法2kP,需要k次求逆运算。本文根据递推归纳、转换求逆为乘法的思想,推导了直接计算2kP的公式,使求逆运算降至1次。从理论上比较了两种计算方法的运算效率:所提出的新算法在k=4时比逐次累加计算量减少1%,并且减少量随着k的增大而增多,在极限情况下可减少约26%。     

Distributed Matrix-Free Solution of Large Sparse Linear Systems over Finite Fields

We describe a coarse-grain parallel approach for the homogeneous solution of linear systems. Our solutions are symbolic, i.e., exact rather than numerical approximations. We have performed an outer loop parallelization that works well in conjunction with a black box abstraction for the coefficient matrix. Our implementation can be run on a network cluster of UNIX workstations as well as on an SP-2 multiprocessor. Task distribution and management are effected through MPI and other packages. Fault tolerance, checkpointing, and recovery are incorporated. Detailed timings are presented for experiments with systems that arise in RSA challenge integer factoring efforts. For example, we can solve a 252,222 × 252,222 system with about 11.04 million nonzero entries over the Galois field with two elements using four processors of an SP-2 multiprocessor, in about 26.5 hours CPU time. Received June 1, 1997; revised March 10, 1998.     

Algorithms for Exponentiation in Finite Fields

Gauss periods yield (self-dual) normal bases in finite fields, and these normal bases can be used to implement arithmetic efficiently. It is shown that for a small prime power q and infinitely many integersn , multiplication in a normal basis of Fqn over Fq can be computed with O(n logn loglog n), division with O(n log²n loglog n) operations in Fq, and exponentiation of an arbitrary element in Fqn withO (n²loglog n) operations in Fq. We also prove that using a polynomial basis exponentiation in F 2 n can be done with the same number of operations in F 2 for all n. The previous best estimates were O(n²) for multiplication in a normal basis, andO (n²log n loglog n) for exponentiation in a polynomial basis.     

有限域上快速分块Jacket变换

提出了一种在有限域上的简单上闭链分块逆Jacket变换(CBIJT)。为将高阶的上闭链逆Jacket矩阵(CBIJM)因式分解成单位矩阵和低阶稀疏矩阵,考虑运用带来快速变换的连续结构来减少计算负荷。采用类似的递归方式分析两个CBIJT,即单维和双维CBIJT。这两个CBIJT为单位矩阵和低阶CBIJT的多重Kronecker积。     

基于有限域上圆锥曲线的公钥密码系统

随着Internet的迅猛发展,公钥密码系统以其算法简单、安全性高已经成为密码学领域的一个非常重要的研究课题.为了更加方便地构建公钥密码系统,文中在介绍了有限域上的圆锥曲线C(Fp)及其离散对数问题、明文嵌入与译码算法的基础上,给出了公钥密码系统在圆锥曲线C(Fp)上的模拟,这里户是奇素数,Fp为p元有限域.这些圆锥曲线密码系统的安全性是基于C(Fp)上离散对数的计算,较椭圆曲线密码系统更易于设计与实现.     

基于有限域上圆锥曲线的公钥密码系统

随着Internet的迅猛发展，公钥密码系统以其算法简单、安全性高已经成为密码学领域的一个非常重要的研究课题。为了更加方便地构建公钥密码系统，文中在介绍了有限域上的圆锥曲线C(Fp)及其离散对数问题、明文嵌入与译码算法的基础上，给出了公钥密码系统在圆锥曲线C(Fp)上的模拟，这里p是奇素数，Fp为p元有限域。这些圆锥曲线密码系统的安全性是基于C(Fp)上离散对数的计算，较椭圆曲线密码系统更易于设计与实现。