Reputation
22,097
Next tag badge:
98/100 score
23/20 answers
Badges
4 30 80
Newest
 Constituent
Impact
~482k people reached

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 plausible-deniability tag wiki
Jan
15
reviewed Approve 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.
Jan
10
answered Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?
Jan
10
comment Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?
Why would you need a LFSR of length $n=2991$? (1) Why would you need such a long LFSR? (2) Even if you needed a LFSR that has at least 2991 bits of state for some reason I haven't anticipated, why can't you just use a slightly larger LFSR, say $n=2992$?
Jan
10
comment How to prove that a ciphertext is encrypting multiplication of two values?
@curious, about your question on generic proof argument: see the sentence in my answer "It is known that every statement in NP..." Generic proof argument refers to a ZK proof that uses that general result.