meta user
network profile
| bio | website | |
|---|---|---|
| location | ||
| age | ||
| visits | member for | 1 year, 9 months |
| seen | 1 hour ago | |
| stats | profile views | 34 |
|
Nov 14 |
comment |
Are there practical upper limits of RSA key lengths? To be fair to RSA, 1 million bits is well over the FFT range. Encryption is closer to $O(n \log n \log \log n)$, and decryption $O(n^2 \log n \log \log n)$. |
|
Oct 6 |
comment |
How to calculate the time it'll take to crack RSA or DH? It's probably worth pointing out that the main difference between the NFS for factoring vs discrete log is the linear algebra step: in the former, we only have to solve a matrix modulo 2, while the latter requires it be solved modulo $p-1$, which greatly increases the cost of this step (even ignoring space and communication constraints). |
|
Sep 30 |
comment |
How robust is discrete logarithm in GF(2^n) ? Note that the Weil descent approach to elliptic curves of composite-degree transfers the discrete logarithm from $E(\mathbb{F}_{2^n})$ to $J(\mathbb{F}_{2^{(n/p)}})$, where $p$ is some divisor of $n$, and $J$ is the Jacobian of a high-degree hyperelliptic curve where the discrete log might be faster. The original question, however, was about discrete logarithms in the base field $\mathbb{F}_{2^n}$; the Weil/Tate pairing might be used to transfer $E(\mathbb{F}_{2^n})$ to $\mathbb{F}_{2^n}$ (MOV and FR attacks). |
|
Sep 29 |
answered | Can ECDSA signatures be safely made “deterministic”? |
|
Sep 23 |
comment |
Is there a simple hash function that one can compute without a computer? Squaring modulo something wouldn't be NP-hard; if modulo a prime, we know how to compute square roots efficiently, and if modulo a composite reduces to factorization, which is not known to be in NP-hard or NP-complete. |
|
Sep 23 |
answered | How long does it take to crack DES and AES? |
|
Sep 21 |
comment |
Accelerating SHA-1 In an SSL server, you are serving many independent (parallel) clients simultaneously...there's plenty of coarse-grained parallelism to explore there. Not sure whether that is your case. Note that you can also explore SIMD (XMM, soon YMM) registers to perform 4 (resp. 8)-way SHA-1, along with multiple cores/GPU. |
|
Sep 9 |
comment |
Mapping points between elliptic curves and the integers This is probably a silly question, but doesn't regular point compression almost do this? Granted, the output is not in $Z_p$, but it's guaranteed to be in $Z/(2p+1)Z$. |
|
Sep 2 |
comment |
What is the sign bit for in Feige-Fiat-Shamir? You're right, I missed the missing sign on the setup. The signed $I_j$ appear to only be required to make the scheme unrestricted input zero knowledge. This just means that the prover leaks nothing. Without the sign, we know a priori that $I_j$ is a quadratic residue modulo $n$, which would be a hard computational problem otherwise. The authors do mention some practical applications of this distinction later on in the JoC version of the paper, particularly when applying (public) transformations to $I_j$. |
|
Sep 2 |
answered | Why is public-key encryption so much less efficient than secret-key encryption? |
|
Sep 1 |
comment |
What is the sign bit for in Feige-Fiat-Shamir? In the paragraph following what I quoted, they mention their use of $1/S_i^2$ instead of simply $S_i^2$ as having "no theoretical significance, but optimizes the practical implementations of the scheme". Wikipedia seems to use $S_i^2$, possibly to remain coherent with the original Fiat-Shamir approach. |
|
Sep 1 |
answered | What is the sign bit for in Feige-Fiat-Shamir? |
|
Aug 30 |
awarded | Student |
|
Aug 30 |
asked | Pairing-friendly curves in small characteristic fields |
|
Aug 30 |
awarded | Supporter |
|
Aug 30 |
comment |
How to practically find solutions to a discrete logarithm? There are very few public index calculus implementations. One of them is Chris Studholme's, which works but just barely. If your problem is small enough to be solved in 60 seconds, MAGMA has a pretty good solver (it includes both the Linear and Gaussian Integer sieve). |
|
Aug 28 |
awarded | Teacher |
|
Aug 28 |
answered | How to practically find solutions to a discrete logarithm? |
