Gröbner bases with coefficients in rings

This article gives a short introduction to the theory of Gröbner bases in a class of rings, which includes rings of differential operators and polynomial rings over commutative noetherian rings. A definition of reduced Gröbner bases for these rings is proposed.     

Improved convertible authenticated encryption scheme with provable security

Convertible authenticated encryption (CAE) schemes allow a signer to produce an authenticated ciphertext such that only a designated recipient can decrypt it and verify the recovered signature. The conversion property further enables the designated recipient to reveal an ordinary signature for dealing with a later dispute over repudiation. Based on the ElGamal cryptosystem, in 2009, Lee et al. proposed a CAE scheme with only heuristic security analyses. In this paper, we will demonstrate that their scheme is vulnerable to the chosen-plaintext attack and then further propose an improved variant. Additionally, in the random oracle model, we prove that the improved scheme achieves confidentiality against indistinguishability under adaptive chosen-ciphertext attacks (IND-CCA2) and unforgeability against existential forgery under adaptive chosen-message attacks (EF-CMA).     

Primeness of multivariate polynomial matrices

Different characterizations of primeness of polynomial matrices that are mutually equivalent in the one-dimensional case of univiriate polynomials lead to various primeness concepts in the multivariate situation. Applied to systems theory, this fact gives rise to a more refined view to observability and controllability of multidimensional systems. Algorithms for testing primeness properties are given based on computer algebraic techniques.     

An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography

In this paper, we present an efficient and general algorithm for decomposing multivariate polynomials of the same arbitrary degree. This problem, also known as the Functional Decomposition Problem (FDP), is classical in computer algebra. It is the first general method addressing the decomposition of multivariate polynomials (any degree, any number of polynomials). As a byproduct, our approach can be also used to recover an ideal I from its kth power I^k. The complexity of the algorithm depends on the ratio between the number of variables (n) and the number of polynomials (u). For example, polynomials of degree four can be decomposed in , when this ratio is smaller than . This work was initially motivated by a cryptographic application, namely the cryptanalysis of 2R⁻ schemes. From a cryptographic point of view, the new algorithm is so efficient that the principle of two-round schemes, including 2R⁻ schemes, becomes useless. Besides, we believe that our algorithm is of independent interest.     

Gröbner bases and the number of Latin squares related to autotopisms of order ≤7

Latin squares can be seen as multiplication tables of quasigroups, which are, in general, non-commutative and non-associative algebraic structures. The number of Latin squares having a fixed isotopism in their autotopism group is at the moment an open problem. In this paper, we use Gröbner bases to describe an algorithm that allows one to obtain the previous number. Specifically, this algorithm is implemented in Singular to obtain the number of Latin squares related to any autotopism of Latin squares of order up to 7.     

A new Gröbner basis conversion method based on stabilization techniques

We propose a new method for converting a Gröbner basis w.r.t. one term order into a Gröbner basis w.r.t. another term order by using the algorithm stabilization techniques proposed by Shirayanagi and Sweedler. First, we guess the support of the desired Gröbner basis from a floating-point Gröbner basis by exploiting the supportwise convergence property of the stabilized Buchberger’s algorithm. Next, assuming this support to be correct, we use linear algebra, namely, the method of indeterminate coefficients to determine the exact values for the coefficients. Related work includes the FGLM algorithm and its modular version. Our method is new in the sense that it can be thought of as a floating-point approach to the linear algebra method. The results of Maple computing experiments indicate that our method can be very effective in the case of non-rational coefficients, especially the ones including transcendental constants.     

A note on output feedback stabilizability of multivariable 2D systems

The output feedback stabilizability conditions of 2D systems are expressed in term of structural properties of a pair of commuting linear transformations. An algorithm is given for obtaining a stable closed-loop 2D characteristic polynomial.     

High speed architectures for Leviathan: a binary tree based stream cipher

Connectionless routed networks, built atop high-speed communication medium, require cryptographic algorithms capable of out-of-order keystream generation and high throughput. Binary tree based stream ciphers, of which Leviathan is an example, are capable of meeting both of these requirements. We investigate high-speed architectures for the binary tree traversal and show that the traversal approaches discussed can be extended to m-ary tree of height h. Of the two architectures presented, the pipeline architecture computes keystream at uniform rate and the parallel architecture bounds the worst-case variance in the time period between computations of consecutive output key words, which form the keystream. The design and implementation of Leviathan keystream generator based on the pipeline architecture for binary tree traversal are presented. We show that it is possible to achieve keystream generation rates approaching 1 Gbps with the pipeline architecture. The design was implemented in two parts, the keysetup and the keystream pipeline, targeting commercially available Xilinx XC2V4000 and XC2V3000 FPGAs. The keystream pipeline implementation operated at frequency of 50 MHz and occupied 6864 slices. The results were verified performing the timing simulation.     

Complete involutive rewriting systems

Given a monoid string rewriting system M, one way of obtaining a complete rewriting system for M is to use the classical Knuth–Bendix critical pairs completion algorithm. It is well-known that this algorithm is equivalent to computing a noncommutative Gröbner basis for M. This article develops an alternative approach, using noncommutative involutive basis methods to obtain a complete involutive rewriting system for M.     

New (t, n) threshold directed signature scheme with provable security

Directed signature scheme allows only a designated verifier to check the validity of the signature issued to him; and at the time of trouble or if necessary, any third party can verify the signature with the help of the signer or the designated verifier as well. Due to its merits, directed signature scheme is widely used in situations where the receiver’s privacy should be protected. Threshold directed signature is an extension of the standard directed signature, in which several signers may be required to cooperatively sign messages for sharing the responsibility and authority. To the best of our knowledge, threshold directed signature has not been well studied till now. Therefore, in this paper, we would like to formalize the threshold directed signature and its security model, then present a new (t, n) threshold directed signature scheme from bilinear pairings and use the techniques from provable security to analyze its security.     

List decoding codes on Garcia–Stictenoth tower using Gröbner basis

An account of the interpolation and the root-finding steps of list decoding of one-point codes is given. The interpolation step is reduced to the problem of finding the minimal element of the Gröbner basis of a submodule of a free module over a polynomial ring of one variable. The procedure for root-finding of the interpolation polynomial going modulo a large degree place is described from the tower point of view.     

WG: A family of stream ciphers with designed randomness properties

In this paper we present a family of stream ciphers which generate a keystream with ideal two-level autocorrelation. The design also guarantees other randomness properties, i.e., balance, long period, ideal tuple distribution, and high and exact linear complexity. We discuss how these properties are achieved by the proposed design and show how to select various parameters to obtain an efficient stream cipher for the desired security level. We also show that the proposed generators are secure against time/memory/data tradeoff attacks, algebraic attacks and correlation attacks. Finally we present WG-128¹ as a concrete example of a WG stream cipher with a key size of 128 bits.     

Computing difference-differential dimension polynomials by relative Gröbner bases in difference-differential modules

In this paper we present a new algorithmic approach for computing the Hilbert function of a finitely generated difference-differential module equipped with the natural double filtration. The approach is based on a method of special Gröbner bases with respect to “generalized term orders” on N^m×Zⁿ${\mathbb{N}}^m\times {\mathbb{Z}}^n$ and on difference-differential modules. We define a special type of reduction for two generalized term orders in a free left module over a ring of difference-differential operators. Then the concept of relative Gröbner bases w.r.t. two generalized term orders is defined. An algorithm for constructing these relative Gröbner bases is presented and verified. Using relative Gröbner bases, we are able to compute difference-differential dimension polynomials in two variables.     

可证明安全的可变门限代理重签名方案

已有的大部分门限代理重签名方案的门限值是固定的,而可变门限代理重签名方案更符合实际应用的需求,即根据消息的重要性可灵活地选择不同的门限值进行门限重签名。在Ateniese G等人提出的代理重签名方案Sbi的基础上,利用中国剩余定理提出了一个具有短公开参数和签名长度的可变门限代理重签名方案,并给出了该方案的安全性证明。根据可变的门限值,每个代理者都能非交互地生成相应的重签名子密钥和验证公钥。与现有方案相比, 新方案占用通信带宽低、计算效率高。     

Existence of the Exact CNOT on a Quantum Computer with the Exchange Interaction

We prove the existence of the exact CNOT gate on aquantum computer with the nearest-neighbor exchange interaction in the serial operation mode. Its existence has been an open problem, though a concrete sequence of exchange operations, which is approximately locally equivalent to the exact CNOT, has already been found. We found the exact values of time parameters (exchange rates between qubits) by using computer algebraic techniques such as Gröbner bases and resultants. These techniques have been widely used for finding rigorous solutions of simultaneous algebraic equations, and here are applied to finding quantum gates on the decoherence-free subsystem for the first time.PACS: 02.70.Wz, 03.65.Yz, 03.67.Lx     

Bounded distance decoding of linear error-correcting codes with Gröbner bases

The problem of bounded distance decoding of arbitrary linear codes using Gröbner bases is addressed. A new method is proposed, which is based on reducing an initial decoding problem to solving a certain system of polynomial equations over a finite field. The peculiarity of this system is that, when we want to decode up to half the minimum distance, it has a unique solution even over the algebraic closure of the considered finite field, although field equations are not added. The equations in the system have degree at most 2. As our experiments suggest, our method is much faster than the one of Fitzgerald–Lax. It is also shown via experiments that the proposed approach in some range of parameters is superior to the generic syndrome decoding.     

PolyBoRi: A framework for Gröbner-basis computations with Boolean polynomials

This work presents a new framework for Gröbner-basis computations with Boolean polynomials. Boolean polynomials can be modelled in a rather simple way, with both coefficients and degree per variable lying in {0,1}$\{0,1\}$. The ring of Boolean polynomials is, however, not a polynomial ring, but rather the quotient ring of the polynomial ring over the field with two elements modulo the field equations x²=x$x^2=x$ for each variable x$x$. Therefore, the usual polynomial data structures seem not to be appropriate for fast Gröbner-basis computations. We introduce a specialised data structure for Boolean polynomials based on zero-suppressed binary decision diagrams (ZDDs), which are capable of handling these polynomials more efficiently with respect to memory consumption and also computational speed. Furthermore, we concentrate on high-level algorithmic aspects, taking into account the new data structures as well as structural properties of Boolean polynomials. For example, a new useless-pair criterion for Gröbner-basis computations in Boolean rings is introduced. One of the motivations for our work is the growing importance of formal hardware and software verification based on Boolean expressions, which suffer–besides from the complexity of the problems –from the lack of an adequate treatment of arithmetic components. We are convinced that algebraic methods are more suited and we believe that our preliminary implementation shows that Gröbner-bases on specific data structures can be capable of handling problems of industrial size.