Point Decomposition Problem in Binary Elliptic Curves

DOI10.1007/978-3-319-30840-1_10zbMATH Open1352.94042arXiv1504.02347OpenAlexW2208552461MaRDI QIDQ2806768FDOQ2806768

Authors: Koray Karabina 

Publication date: 19 May 2016

Published in: Mathematics of Computation, Information Security and Cryptology - ICISC 2015 (Search for Journal in Brave)

Abstract: We analyze the point decomposition problem (PDP) in binary elliptic curves. It is known that PDP in an elliptic curve group can be reduced to solving a particular system of multivariate non-linear system of equations derived from the so called Semaev summation polynomials. We modify the underlying system of equations by introducing some auxiliary variables. We argue that the trade-off between lowering the degree of Semaev polynomials and increasing the number of variables is worth.

Full work available at URL: https://arxiv.org/abs/1504.02347

Recommendations

• The point decomposition problem over hyperelliptic curves, Toward efficient computation of discrete logarithms in even characteristic
• The vector decomposition problem for elliptic and hyperelliptic curves
• Points on elliptic curves over finite fields
• Integer points on elliptic curves
• Integer points on elliptic curves
• scientific article; zbMATH DE number 1273657
• scientific article; zbMATH DE number 2085440
• Fast Point Decompression for Standard Elliptic Curves
• Computing integral points on elliptic curves
• scientific article

zbMATH Keywords

elliptic curvesdiscrete logarithm problempairing-based cryptographyexponentiationpoint decomposition problemsquaringSemaev polynomialscyclotomic subgroups

Mathematics Subject Classification ID

Cryptography (94A60) Finite fields (field-theoretic aspects) (12E20) Applications to coding theory and cryptography of arithmetic geometry (14G50)

Cites Work

• High-Speed Software Implementation of the Optimal Ate Pairing over Barreto–Naehrig Curves
• A taxonomy of pairing-friendly elliptic curves
• Faster explicit formulas for computing pairings over ordinary curves
• Compression in Finite Fields and Torus-Based Cryptography
• Factor-4 and 6 compression of cyclotomic subgroups of \(\mathbb F^*_{2^{4m}}\) and \(\mathbb F^*_{3^{6m}}\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Public-key cryptosystems based on cubic finite field extensions
• Title not available (Why is that?)
• Practical Cryptography in High Dimensional Tori
• Pairing-Friendly Elliptic Curves of Prime Order
• Advances in Cryptology - CRYPTO 2003
• Algorithmic Number Theory
• Speeding the Pollard and Elliptic Curve Methods of Factorization
• Faster squaring in the cyclotomic subgroup of sixth degree extensions
• Integer Variable χ–Based Ate Pairing
• Algorithmic Number Theory
• Cryptography and Coding
• Implementing cryptographic pairings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Advances in Cryptology – CRYPTO 2004
• Constructing tower extensions of finite fields for implementation of pairing-based cryptography
• Double-exponentiation in factor-4 groups and its applications

Cited In (21)

• Koblitz curves over quadratic fields
• Recent progress on the elliptic curve discrete logarithm problem
• Secure and Efficient Pairing at 256-Bit Security Level
• Double-exponentiation in factor-4 groups and its applications
• Choosing and generating parameters for pairing implementation on BN curves
• Updating key size estimations for pairings
• Improving the computation of the optimal ate pairing for a high security level
• Optimized and Secure Pairing-Friendly Elliptic Curves Suitable for One Layer Proof Composition
• An Analysis of the Vector Decomposition Problem
• Title not available (Why is that?)
• Low-cost addition-subtraction sequences for the final exponentiation in pairings
• A survey of elliptic curves for proof systems
• Fast subgroup membership testings for \(\mathbb{G}_1, \mathbb{G}_2\) and \(\mathbb{G}_T\) on pairing-friendly curves
• Faster squaring in the cyclotomic subgroup of sixth degree extensions
• Faster hashing to \({\mathbb G}_2\)
• Families of SNARK-friendly 2-chains of elliptic curves
• The point decomposition problem over hyperelliptic curves, Toward efficient computation of discrete logarithms in even characteristic
• Cocks-Pinch curves of embedding degrees five to eight and optimal ate pairing computation
• The vector decomposition problem for elliptic and hyperelliptic curves
• Title not available (Why is that?)
• Pairings in rank-1 constraint systems

Uses Software

• Barreto-Naehrig

This page was built for publication: Point Decomposition Problem in Binary Elliptic Curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2806768)