In this paper, we present a deterministic attack on (EC)DSA signature scheme, providing that several signatures are known such that the corresponding ephemeral keys share a certain amount of bits without knowing their...
详细信息
In this paper, we present a deterministic attack on (EC)DSA signature scheme, providing that several signatures are known such that the corresponding ephemeral keys share a certain amount of bits without knowing their value. By eliminating the shared blocks of bits between the ephemeral keys, we get a lattice of dimension equal to the number of signatures having a vector containing the private key. We compute an upper bound for the distance of this vector from a target vector, and next, using Kannan's enumeration algorithm, we determine it and hence the secret key. The attack can be made highly efficient by appropriately selecting the number of shared bits and the number of signatures.
In this paper, we introduce a series of attacks on DSA schemes that, under certain assumptions, can expose the secret key when one or more signed messages are accessible. By utilizing these signed messages, we constru...
详细信息
In this paper, we introduce a series of attacks on DSA schemes that, under certain assumptions, can expose the secret key when one or more signed messages are accessible. By utilizing these signed messages, we construct a system of linear congruences with at most one solution smaller than a specific bound, which can be efficiently determined using Babai's Nearest Plane algorithm. As a case study, we provide a successful attack on secp161k1, assuming that a particular multiple of an ephemeral key is 161 bits long. (c) 2024 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
At ACM-CCS 2014, Cheon, Lee and Seo introduced a particularly fast additively homomorphic encryption scheme (CLS scheme) based on a new number theoretic assumption, the co-Approximate Common Divisor (co-ACD) assumptio...
详细信息
ISBN:
(纸本)9783031157776;9783031157769
At ACM-CCS 2014, Cheon, Lee and Seo introduced a particularly fast additively homomorphic encryption scheme (CLS scheme) based on a new number theoretic assumption, the co-Approximate Common Divisor (co-ACD) assumption. However, at Crypto 2015, Fouque et al. presented several lattice-based attacks that effectively devastated this scheme. They proved that a few known plaintexts are sufficient to break both the symmetric-key and the public-key variants, and they gave a heuristic lattice method for solving the search co-ACD problem. In this paper, we mainly improve in terms of the number of samples, and propose a new key-retrieval attack. We first give an effective attack by Coppersmith's method to break the co-ACD problem with N = p(1) center dot center dot center dot p(n) is known. If n is within a certain range, our work is theoretically valid for a wider range of parameters. When n = 2, we can successfully solve it with only two samples, that is the smallest number of needed samples to the best of our knowledge. A known plaintext attack on the CLS scheme can be simply converted to solving the co-ACD problem with a known N, again requiring fewer samples than before to retrieve the private key. Finally, we show a ciphertext-only attack with a hybrid approach of direct lattice and Coppersmith's method that can recover the key with a smaller number of ciphertexts and without any restriction on the plaintext size, but N is needed. All of our attacks are heuristic, but we have experimentally verified that these attacks work efficiently for the parameters proposed in the CLS scheme, which can be broken in seconds by experiments.
We consider the problem of communicating over a relay-assisted multiple-input multiple-output (MIMO) channel with additive noise, in which physically separated relays forward quantized information to a central decoder...
详细信息
We consider the problem of communicating over a relay-assisted multiple-input multiple-output (MIMO) channel with additive noise, in which physically separated relays forward quantized information to a central decoder where the transmitted message is to be decoded. We assume that channel state information is available in the transmitter and show that the design of a rational-forcing precoder-a precoder which is matched to the quantizers used in the relays-is beneficial for reducing the symbol error probability. It turns out that for such rationalforcing precoder based systems, there is natural tradeoff between the peak to average power ratio in the transmitter and the rate of communication between the relays and the central decoder. The precoder design problem is formulated mathematically, and several algorithms are developed for realizing this tradeoff. Optimality of the decoder communication rate is shown based on a result in distributed function computation. Numerical and simulation results show that a useful tradeoff can be obtained between the excess decoder communication rate and the peakaverage power ratio in the transmitter.
For the Fibonacci sequence the identity F-n(2) + F-n+1(2) = F2n+1 holds for all n >= 0. Let X := (X-l)(l >= 1) be the sequence of X-coordinates of the positive integer solutions (X, Y) of the Pell equation X-2 -...
详细信息
For the Fibonacci sequence the identity F-n(2) + F-n+1(2) = F2n+1 holds for all n >= 0. Let X := (X-l)(l >= 1) be the sequence of X-coordinates of the positive integer solutions (X, Y) of the Pell equation X-2 - dY(2) = +/- 1 corresponding to a nonsquare integer d > 1. In this paper, we investigate all positive nonsquare integers d for which there are at least two positive integers X and X' of X having a representation as the sum of xth powers of two consecutive terms of a Lucas sequence. Then we solve this problem for Fibonacci numbers.
Given a parametric lattice with a basis given by polynomials in Z[t], we give an algorithm to construct an lll-reduced basis whose elements are eventually quasi-polynomial in t: that is, they are given by formulas tha...
详细信息
Given a parametric lattice with a basis given by polynomials in Z[t], we give an algorithm to construct an lll-reduced basis whose elements are eventually quasi-polynomial in t: that is, they are given by formulas that are piecewise polynomial in t (for sufficiently large t), such that each piece is given by a congruence class modulo a period. As a consequence, we show that there are parametric solutions of the shortest vector problem and closest vector problem that are also eventually quasi-polynomial in t.
The "Schur-Siegel-Smyth trace problem" is a famous open problem that has existed for nearly 100 years. To study this problem with the known methods, we need to find all totally positive algebraic integers wi...
详细信息
The "Schur-Siegel-Smyth trace problem" is a famous open problem that has existed for nearly 100 years. To study this problem with the known methods, we need to find all totally positive algebraic integers with small trace. In this work, on the basis of the classical algorithm, we construct a new type of explicit auxiliary functions related to Chebyshev polynomials to give better bounds for Sk, and reduce sharply the computing time. We are then able to push the computation to degree 15 and prove that there is no such totally positive algebraic integer with absolute trace 1.8. As an application, we improve the lower bound for the absolute trace of totally positive algebraic integers to 1.793145 . . . .
From the well-known Fibonacci sequence, the number F-10=55=5 center dot 11 is an example not only as a repdigit (a number with only one distinct digit) but also as a product of two repdigits with consecutive lengths, ...
详细信息
From the well-known Fibonacci sequence, the number F-10=55=5 center dot 11 is an example not only as a repdigit (a number with only one distinct digit) but also as a product of two repdigits with consecutive lengths, 5 and 11. Here we find all the Fibonacci numbers that can be written as the product of k repdigits with consecutive lengths.
As internet technology advances and our interactions increasingly take place online, cryptography emerges as a valuable tool to address security concerns. Cryptography serves as a means to guarantee the protection of ...
详细信息
As internet technology advances and our interactions increasingly take place online, cryptography emerges as a valuable tool to address security concerns. Cryptography serves as a means to guarantee the protection of privacy and confidential information, thereby instilling confidence when sharing and exchanging such data with other parties. One of the benefits of cryptography is providing confidentiality, which protects our information;either data in transit or data at ease. Three new attacks have been proposed on RSA type modulus N=p2q. The equation eX−NY=Z−(p2k+q2m)Y is the basis for the first attack involves random values of k and m such that k being a multiple of 2 and m being a multiple of 3, both being integers with |p2k+q2m|1/2 and gcd(X,Y)=1. If Z<[Formula presented]N1/3Y and XY<[Formula presented], then by using continued fractions, factoring N can be accomplished within polynomial *** paper also suggested the vulnerabilities t RSA cryptosystem moduli Ns=ps2qs for t≥2 and s=1,…,t for the second and third attack. The attacks are effective if there exists a relationship between t RSA public keys (Nt,et) expressed as esx−Nsys=zs−(ps2k+qs2m)ys or esxs−Nsy=zs−(ps2k+qs2m)y, where the variables x, xs, y, ys, and zs are sufficiently small. The importance lies in the presence of an algorithm that operates within probabilistic polynomial time, which is capable of accepting public parameters as input and yield the factors p and q as output. By employing this algorithm, one can verify whether a key falls within the vulnerable class or not. This characteristic can be valuable when designing a cryptosystem
In this paper, we present a GPU-based parallel algorithm for the Learning With Errors (LWE) problem using a lattice-based Bounded Distance Decoding (BDD) approach. To the best of our knowledge, this is the first GPU-b...
详细信息
In this paper, we present a GPU-based parallel algorithm for the Learning With Errors (LWE) problem using a lattice-based Bounded Distance Decoding (BDD) approach. To the best of our knowledge, this is the first GPU-based implementation for the LWE problem. Compared to the sequential BDD implementation of Lindner-Peikert and pruned-enumeration strategies by Kirshanova [1], our GPU-based implementation is almost faster by a factor 6 and 9 respectively. The used GPU is NVIDIA GeForce GTX 1060 6G. We also provided a parallel implementation using two GPUs. The results showed that our algorithm is scalable and faster than the sequential version (Lindner-Peikert and pruned-enumeration) by a factor of almost 13 and 16 respectively. Moreover, the results showed that our parallel implementation using two GPUs is more efficient than Kirshanova et al.'s parallel implementation using 20 CPU-cores.
暂无评论