搜索结果: 61-75 共查到“Polynomial”相关记录358条 . 查询时间(0.086 秒)
Some Trade-off Results for Polynomial Calculus
Proof complexity polynomial calculus PCR resolution trade-offs size space degree pebble games
2016/1/23
We present size-space trade-offs for the polynomial calculus(PC) and polynomial calculus resolution (PCR) proof sys-tems. These are the first true size-space trade-offs in any algebraic proof system, ...
A Fully Polynomial Approximation Scheme for Approximating a Sum of Random Variables
Threshold probability Tail probability Approximate counting Counting knapsack FPTAS
2016/1/22
Given n independent integer-valued random variables X 1 , X 2 ,..., X n and an integer C, we study the fundamental problem of computing the probability that the sum X = X 1 + X 2 +···+ X n is at most ...
Rounding and Chaining LLL: Finding Faster Small Roots of Univariate Polynomial Congruences
Coppersmith's Algorithm Small Roots of Polynomial Equations LLL
2016/1/9
In a seminal work at EUROCRYPT '96, Coppersmith showed how to find all small roots of a univariate polynomial congruence in polynomial time: this has found many applications in public-key cryptanalysi...
Secure Outsourced Computation of the Characteristic Polynomial and Eigenvalues of Matrix
Cloud Computing Outsourced computation Matrix
2016/1/9
Linear algebra plays an important role in computer science,
especially in cryptography.Numerous cryptog-raphic protocols, scientific
computations, and numerical computations are based on linear alge...
Polynomial Spaces: A New Framework for Composite-to-Prime-Order Transformations
bilinear maps composite-order groups Groth-Sahai proofs
2016/1/9
At Eurocrypt 2010, Freeman presented a framework to convert cryptosystems based on compositeorder
groups into ones that use prime-order groups. Such a transformation is interesting not only from
a c...
Homomorphic Signatures with Efficient Verification for Polynomial Functions
homomorphic signatures verifiable computation
2016/1/9
A homomorphic signature scheme for a class of functions C
allows a client to sign and upload elements of some data set D on a
server. At any later point, the server can derive a (publicly verifiable...
High-speed Polynomial Multiplication Architecture for Ring-LWE and SHE Cryptosystems
Cryptography Polynomial multiplication Number theoretic transform (NTT)
2016/1/7
Polynomial multiplication is the basic and most computationally intensive operation in ring-Learning With Errors (ring-LWE) encryption and ``Somewhat" Homomorphic Encryption (SHE) cryptosystems. In th...
SBIM(Q) - a Multivariate Polynomial Trapdoor Function over the Field of Rational Numbers
trap-door function bi-permutations quasigroup transformations
2016/1/7
In this paper we define a trapdoor function called SBIM(Q) by using multivariate polynomials over the field of rational numbers Q. The public key consists of 2n multivariate polynomials with 3n variab...
Summation polynomial algorithms for elliptic curves in characteristic two
ECDLP summation polynomials index calculus
2016/1/6
The paper is about the discrete logarithm problem for elliptic curves over characteristic 2 finite fields
F2n of prime degree n. We consider practical issues about index calculus attacks using summat...
A Polynomial-Time Key-Recovery Attack on MQQ Cryptosystems
MQ cryptography MQQ cryptosystems Equivalent keys
2016/1/6
We investigate the security of the family of MQQ public key cryptosystems using multivariate
quadratic quasigroups (MQQ). These cryptosystems show especially good performance properties.
In particul...
Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms - Simplified Setting for Small Characteristic Finite Fields
discrete logarithm problem finite fields
2016/1/6
In this paper, we revisit the recent small characteristic discrete logarithm algorithms. We show that a simplified description of the algorithm, together with some additional ideas, permits to obtain ...
Solving Polynomial Systems with Noise over F_2: Revisited
Cold Boot attack Characteristic Set method Serpent
2016/1/5
Solving polynomial systems with noise over F2 is a fundamental
problem in computer science, especially in cryptanalysis. ISBS
is a new method for solving this problem based on the idea of incrementa...
A Chinese Remainder Theorem Approach to Bit-Parallel GF(2^n) Polynomial Basis Multipliers for Irreducible Trinomials
implementation Irreducible Trinomials
2016/1/5
We show that the step “modulo the degree-n field generating irreducible polynomial” in the classical definition of the GF(2^n) multiplication operation can be avoided. This leads to an alternative rep...
Oblivious Polynomial Evaluation and Secure Set-Intersection from Algebraic PRFs
Efficient Secure Computation Oblivious Polynomial Evaluation Secure Set-Intersection
2016/1/5
In this paper we study the two fundamental functionalities oblivious polynomial evaluation in the
exponent and set-intersection, and introduce a new technique for designing efficient secure protocols...
Some New Results on Binary Polynomial Multiplication
Polynomial multiplication binary fields
2016/1/4
This paper presents several methods for reducing the number of bit operations for multiplication of
polynomials over the binary field. First, a modified Bernstein’s 3-way algorithm is introduced, fol...