Search

This paper presents an efficient algorithm for computing 11th-power residue symbols in the cyclo-tomic field ℚ (ζ 11 ) , $ \mathbb{Q}\left({{\zeta }_{11}} \right), $ where 11 is a primitive 11th root of unity. It extends an earlier algorithm due to Caranay and Scheidler (Int. J. Number Theory, 2010) for the 7th-power residue symbol. The new algorithm finds applications in the implementation of certain cryptographic schemes. [ABSTRACT FROM AUTHOR]

In this paper we provide a framework for applying classical search and preprocessing to quantum oracles for use with Grover's quantum search algorithm in order to lower the quantum circuit-complexity of Grover's algorithm for single-target search problems. This has the effect (for certain problems) of reducing a portion of the polynomial overhead contributed by the implementation cost of quantum oracles and can be used to provide either strict improvements or advantageous trade-offs in circuit-complexity. Our results indicate that it is possible for quantum oracles for certain single-target preimage search problems to reduce the quantum circuit-size from O 2 n / 2 ⋅ m C $O\left(2^{n/2}\cdot mC\right)$ (where C originates from the cost of implementing the quantum oracle) to O (2 n / 2 ⋅ m C) $O(2^{n/2} \cdot m\sqrt{C})$ without the use of quantum ram, whilst also slightly reducing the number of required qubits. This framework captures a previous optimisation of Grover's algorithm using preprocessing [21] applied to cryptanalysis, providing new asymptotic analysis. We additionally provide insights and asymptotic improvements on recent cryptanalysis [16] of SIKE [14] via Grover's algorithm, demonstrating that the speedup applies to this attack and impacting upon quantum security estimates [16] incorporated into the SIKE specification [14]. [ABSTRACT FROM AUTHOR]

As one of the most efficient lattice-based signature schemes, and one of the only ones to have seen deployment beyond an academic setting (e.g., as part of the VPN software suite strongSwan), BLISS has attracted a significant amount of attention in terms of its implementation security, and side-channel vulnerabilities of several parts of its signing algorithm have been identified in previous works. In this paper, we present an even simpler timing attack against it. The bimodal Gaussian distribution that BLISS is named after is achieved using a random sign flip during signature generation, and neither the original implementation of BLISS nor strongSwan ensure that this sign flip is carried out in constant time. It is therefore possible to recover the corresponding sign through side-channel leakage (using, e.g., cache attacks or branch tracing). We show that obtaining this single bit of leakage (for a moderate number of signatures) is in fact sufficient for a full key recovery attack. The recovery is carried out using a maximum likelihood estimation on the space of parameters, which can be seen as a statistical manifold. The analysis of the attack thus reduces to the computation of the Fisher information metric. [ABSTRACT FROM AUTHOR]

In the papers [New features for public key exchange algorithms, in: 18-th International ICWG Meeting (Krakow 2011)], [Strongly asymmetric PKD cryptographic algorithms: An implementation using the matrix model, in: Proceedings ISEC Conference (Shizuoka 2011)] a new scheme to produce public key agreement (PKA) algorithms was proposed and some examples based on polynomials (toy models) were discussed. In the present paper we introduce a non-commutative realization of the above mentioned scheme and prove that non-commutativity can be an essential ingredient of security in the sense that, in the class of algorithms constructed, under some commutativity assumptions on the matrices involved, we can find a breaking strategy, but dropping these assumptions we can not, even if we assume, as we do in all the attacks discussed in the present paper, that discrete logarithms have zero cost. [ABSTRACT FROM AUTHOR]

In this paper, we present a variant of Diem's index calculus algorithm to attack the discrete logarithm problem (DLP) in Jacobians of genus 3 non-hyperelliptic curves over a finite field 픽 q. We implement this new variant in C++ and study the complexity in both theory and practice, making the logarithmic factors and constants hidden in the O˜-notation precise. Our variant improves the computational complexity at the cost of a moderate increase in memory consumption, but we also improve the computational complexity even when we limit the memory usage to that of Diem's original algorithm. Finally, we examine how parallelization can help to reduce both the memory cost per computer and the running time for our algorithms. [ABSTRACT FROM AUTHOR]

This paper proposes the computation of the Tate pairing, Ate pairing and its variations on the special Jacobi quartic elliptic curve . We improve the doubling and addition steps in Miller's algorithm to compute the Tate pairing. We use the birational equivalence between Jacobi quartic curves and Weierstrass curves, together with a specific point representation to obtain the best result to date among curves with quartic twists. For the doubling and addition steps in Miller's algorithm for the computation of the Tate pairing, we obtain a theoretical gain up to and , depending on the embedding degree and the extension field arithmetic, with respect to Weierstrass curves and previous results on Jacobi quartic curves. Furthermore and for the first time, we compute and implement Ate, twisted Ate and optimal pairings on the Jacobi quartic curves. Our results are up to more efficient compared to the case of Weierstrass curves with quartic twists. [ABSTRACT FROM AUTHOR]

The connection between exponential sums and algebraic varieties has been known for at least six decades. Recently, Lisoněk exploited it to reformulate the Charpin-Gong characterization of a large class of hyper-bent functions in terms of numbers of points on hyperelliptic curves. As a consequence, he obtained a polynomial time and space algorithm for certain subclasses of functions in the Charpin-Gong family. In this paper, we settle a more general framework, together with detailed proofs, for such an approach and show that it applies naturally to a distinct family of functions proposed by Mesnager. Doing so, a polynomial time and space test for the hyper-bentness of functions in this family is obtained as well. Nonetheless, a straightforward application of such results does not provide a satisfactory criterion for explicit generation of functions in the Mesnager family. To address this issue, we show how to obtain a more efficient test leading to a substantial practical gain. We finally elaborate on an open problem about hyperelliptic curves related to a family of Boolean functions studied by Charpin and Gong. [ABSTRACT FROM AUTHOR]

As one of the most fundamental problems in multivariate public key cryptosystems (MPKC), Isomorphism of Polynomial (IP) induces an equivalence relation on the polynomials systems. The enumeration problem associated to IP consists of counting the number of equivalence classes and the cardinality of each class. The two problems correspond exactly to the study of the total number of different cryptographic schemes and the size of 'equivalent keys'. In this paper we give an algorithm using a divide-and-conquer method to count the number of equivalence classes according to the linear equivalence relation induced by the IP1S problem when . Then by giving the complexity gain of this algorithm compared with the exhaustive search algorithm and the experimental results, we show the high efficiency of this new algorithm. [ABSTRACT FROM AUTHOR]

This paper studies degree 3 Boolean functions in n variables which are rotation symmetric, that is, invariant under any cyclic shift of the indices of the variables. These rotation symmetric functions have been extensively studied in the last dozen years or so because of their importance in cryptography. Let denote the (Hamming) weight of the Boolean function f. We extend and simplify results of Bileschi, Cusick and Padgett, who gave an algorithm for finding a recursion for the sequence , where is the cubic rotation symmetric function generated by the monomial We show that the weights for the function (note this is just the sum of the first terms in the definition of ) satisfy the same recursion as the weights for . We prove the recursion for the weights of by a method based on the work by Bileschi-Cusick-Padgett, but we are able to avoid a lot of the complications in their proofs. In particular, we do not need the technical notion of ' g terms' or the elaborate proof of similarity of certain matrices. [ABSTRACT FROM AUTHOR]

In this paper we propose a method to construct logarithmic signatures which are not amalgamated transversal and further do not even have a periodic block. The latter property was crucial for the successful attack on the system MST 3 by Blackburn, Cid and Mullan (2009). The idea for our construction is based on the theory in Szabó's book 'Topics in Factorization of Abelian Groups'. [ABSTRACT FROM AUTHOR]

We explore the security of blind signatures under aborts where the user or the signer may stop the interactive signature issue protocol prematurely. Several works on blind signatures discuss security only in regard of completed executions and usually do not impose strong security requirements in case of aborts. One of the exceptions is the paper of Camenisch, Neven and Shelat (Eurocrypt, Simulatable adaptive oblivious transfer, Springer, 2007) where the notion of selective-failure blindness has been introduced. Roughly speaking, selective-failure blindness says that blindness should also hold in case the signer is able to learn that some executions have aborted. Here we augment the work of Camenisch et al. by showing how to turn every secure blind signature scheme into a selective-failure blind signature scheme. Our transformation only requires an additional computation of a commitment and therefore adds only a negligible overhead. We also study the case of multiple executions and notions of selective-failure blindness in this setting. We then discuss the case of user aborts and unforgeability under such aborts. We show that every three-move blind signature scheme remains unforgeable under such user aborts. Together with our transformation for selective-failure blindness we thus obtain an easy solution to ensure security under aborts of either party and which is applicable for example to the schemes of Pointcheval and Stern (Journal of Cryptology 13: 361-396, 2000). We finally revisit the construction of Camenisch et al. for simulatable adaptive oblivious transfer protocols, starting from selective-failure blind signatures where each message only has one valid signature (uniqueness). While our transformation to achieve selective-failure blindness does not preserve uniqueness, it can still be combined with a modified version of their protocol. Hence, we can derive such oblivious transfer protocols based on unique blind signature schemes only (in the random oracle model), without necessarily requiring selective-failure blindness from scratch. [ABSTRACT FROM AUTHOR]

In elliptic curve cryptosystems, scalar multiplications performed on the curves have much effect on the efficiency of the schemes, and many efficient methods have been proposed. In particular, recoding methods of the scalars play an important role in the performance of the algorithm used. For integer radices, the non-adjacent form (NAF) and its generalizations (e.g., the generalized non-adjacent form (GNAF) and the radix- r non-adjacent form ( rNAF)) have been proposed for minimizing the non-zero densities in the representations of the scalars. On the other hand, for subfield elliptic curves, the Frobenius expansions of the scalars can be used for improving efficiency. Unfortunately, there are only a few methods apply the techniques of NAF or its analogue to the Frobenius expansion, namely τ-adic NAF techniques on Koblitz curves and hyperelliptic Koblitz curves. In this paper, we try to combine these techniques, namely recoding methods for reducing non-zero density and the Frobenius expansion, and propose two new efficient recoding methods of scalars on more general family of subfield elliptic curves in odd characteristic. We also prove that the non-zero densities for the new methods are same as those for the original GNAF and rNAF. We estimate scalar multiplication costs on the above subfield elliptic curves in terms of elliptic curve operations and finite field operations for several previous methods and the proposed methods. In addition, we implement scalar multiplication on an subfield elliptic curve belonging to the above family, for the previous methods and a proposed method. As a result, our estimation and implementation show that the speed of the proposed methods improve between 8% and 50% over that for the Frobenius expansion method. [ABSTRACT FROM AUTHOR]

Bilinear pairings derived from supersingular elliptic curves of embedding degrees 4 and 6 over finite fields 2 m and 3 m, respectively, have been used to implement pairing-based cryptographic protocols. The pairing values lie in certain prime-order subgroups of the cyclotomic subgroups of orders 22 m + 1 and 32 m - 3 m + 1, respectively, of the multiplicative groups and . It was previously known how to compress the pairing values over characteristic two fields by a factor of 2, and the pairing values over characteristic three fields by a factor of 6. In this paper, we show how the pairing values over characteristic two fields can be compressed by a factor of 4. Moreover, we present and compare several algorithms for performing exponentiation in the prime-order subgroups using the compressed representations. In particular, in the case where the base is fixed, we expect to gain at least a 54% speed up over the fastest previously known exponentiation algorithm that uses factor-6 compressed representations. [ABSTRACT FROM AUTHOR]