19,732 reputation
32171
bio website
location
age
visits member for 2 years, 11 months
seen 2 hours ago

Jan
29
comment Efficiently computing the neutral element in a ring isomorphic to Z/NZ?
Angela, what does it mean to say you are "given the elements of $S$"? There are exponentially many elements of $S$, so we cannot be literally given a list of all elements of $S$ (represented somehow) -- that wouldn't make sense. So what do you mean? P.S. Make sure you edit your question to make it self-contained and comprehensible without reading the comment thread. This is not a discussion forum. We expect you to spend serious effort to craft a well-posed, well-explained problem statement.
Jan
29
answered Predicting Java's PRNG using partial output
Jan
29
comment Predicting Java's PRNG using partial output
You say algorithms that involve 30,000 steps are not feasible. Frankly: I'm super-skeptical about that claim. Have you tried implementing such a thing? Such a computation will probably finish in microseconds. I find it hard to imagine that this is too slow.
Jan
22
revised Encrypting a TCP connection between two unknown nodes
Please use the answer space for answers. This is not the place for requests for donations, sales, or money -- they aren't an answer to the author's question. Stick to answering the question. Thank you for your understanding!
Jan
21
comment Efficiently computing the neutral element in a ring isomorphic to Z/NZ?
Finally, are you familiar with the concept of black-box fields, and Dan Boneh's seminal result on this topic? crypto.stanford.edu/~dabo/pubs/abstracts/bbf.html If I understood your question, I could probably give you a better explanation of exactly how that is relevant; but as it stands, I'll just say that I suspect it to be closely related to what you're asking about. It shows how to invert any field homomorphism in subexponential time. You're asking about a ring homomorphism, which is closely related.
Jan
21
comment Efficiently computing the neutral element in a ring isomorphic to Z/NZ?
If you can select a random element of $S$, and you can multiply in $S$, then a simple algorithm is: factor $N$, then let $x$ be a random element in $S$, and compute $x^{\varphi(N)}$. This is a subexponential time algorithm to compute the element $1$ in $S$. If this isn't allowed in your model, you need to clarify your model. (If $N=\infty$, your problem is not well-defined. For instance, how were you planning to represent ring elements? It's also unlikely to be relevant to crypto. So I suggest you throw that one out.)
Jan
21
comment Efficiently computing the neutral element in a ring isomorphic to Z/NZ?
I'm having a hard time understanding the question. What's given? What are you trying to compute? Am I given an integer $N$, and told that there is some ring $S$ that is isomorphic to the ring $\mathbb{Z}/N\mathbb{Z}$, but I'm given no other information about $S$, and my job is to find the image of $1$ in $S$? That is obviously not solvable. Did you mean to supply some additional side information? For instance, do you have some way of representing elements in $S$, and some black box that can perform addition, multiplication, inversion in $S$, and that can apply the isomorphism function?
Jan
19
awarded  Revival
Jan
15
comment Oracle DBMS_RANDOM algorithm?
What research have you done? There's lots written in textbooks and on the Internet (and on this site) about the criteria for a PRNG to be fit for cryptography. Also, please, one question per question; you've crammed two different questions into one post.
Jan
15
reviewed Approve suggested edit on plausible-deniability tag wiki
Jan
15
reviewed Approve suggested edit on plausible-deniability tag wiki excerpt
Jan
13
comment Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?
@fgrieu, yup, it doesn't allow you to verify that a LFSR given to you by someone else is maximal-length. However, as I suspect you already know, if you want to generate a LFSR that others can verify is probably maximal-length, you could seed a deterministic PRNG (DRBG) with a "nothing-up-my-sleeve number", and then use the output of that PRNG as the random numbers for my algorithm. That'll allow anyone else to verify that you've generated the LFSR polynomial in a way that you can't easily bias. The security level will depend on the value of $n$.
Jan
13
revised Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?
Add justification of the fact. Add optimization. Fix typo. Improve proof.
Jan
13
comment Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?
@fgrieu, OK, those are good points. I've added those to the algorithm. Setting the constant term and requiring an odd number of taps is just an optimization. (If you choose a polynomial that doesn't have the low bit set, then it'll fail the check that its period divides $2^n-1$ and will be rejected in step 3 of my algorithm.)
Jan
13
revised Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?
Add justification of the fact. Add optimization. Fix typo.
Jan
13
revised Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?
added 909 characters in body
Jan
12
revised 2PC Private Set Intersection Optimized for asymmetrically sized sets
Edit question per comment thread.
Jan
10
comment Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?
For instance, the Unix factor commands factors $2^{320}-1$ in 1.5 seconds, yielding the factorization $2^{320}-1 = 3 \times 5 \times 5 \times 11 \times 17 \times 31 \times 41 \times 257 \times 641 \times 61681 \times 65537 \times 414721 \times 3602561 \times 6700417 \times 4278255361 \times 44479210368001 \times 94455684953484563055991838558081$.
Jan
10
comment Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?
Well, that's a different problem statement. You might do better by asking about the actual problem you want to solve. I think the simplest solution to that problem will involve factoring $2^n-1$. I think you are over-estimating the complexity of that approach. You should be able to factor $2^{320}-1$ using standard tools, without breaking a sweat. (cont.)
Jan
10
revised Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?
fix Latex typo.