2,695 reputation
213
bio website
location
age
visits member for 1 year, 11 months
seen yesterday

Jul
21
comment How to calculate complexity of ElGamal cryptosystem?
Your time complexity assumptions are correct for this algorithm, and space complexity is $O(1)$ in the number of variables or $O(n)$ if you consider the length of the numbers. However, the algorithm can be achieved faster, because of what poncho wrote in his answer. Basically, it is like calculating $a \cdot b$ as $a+a+a...+a$ with $b$ summands.
Jul
15
comment Leak-proof protocol: is such a thing possible?
There is no proof that no other communication channels exist. The only statement you can make about a system is "we don't know any other channel". And with an abstract model in mind, you might already have removed channels which can be used in reality. Timing, power, EM radiation, etc. are only some side channels. There are others like ordering of packets, length of messages, sound (for the air gaped example), choice of identifiers, etc. Even if you have e.g. something like a set of elements, in reality it will come as an ordered list of elements, and this can be used to transfer information.
Jul
15
answered Leak-proof protocol: is such a thing possible?
Jul
15
comment Protocol: Coin Flipping over phone
Since this looks like a homework question, I didn't want to spoil the answer right away. Even preimage resistance isn't needed, it just has to be a binding commitment scheme. Of course, preimage resistance provides some computational binding scheme.
Jul
15
comment Protocol: Coin Flipping over phone
What is "uncertainty" in this context? And to 2: No it is wrong. The function is not binding at all, even without knowledge of $n$.
Jul
15
comment A question about elliptic curves and finite fields in bilinear pairings
Formulas can be inserted here with common Latex notation, by using '$ $'.
Jul
1
comment Exactly two of the four roots must be greater than N/2
right... $p\neq q$. I wrote a comment, and not an answer, but I shouldn't have left it out. Anyway, you're making it more confusing anyone trying to learn something here, by throwing in other things. For example, $p \equiv q \equiv 3$ mod $4$ is not required for the theorem.
Jul
1
comment Exactly two of the four roots must be greater than N/2
This can easily be proven by the fact that with a square root $a$, there is also a square root $-a$. And if you look at this pair, one will be between 0 and $N/2$ and the other one between $N/2$ and $N$.
Jul
1
comment Exactly two of the four roots must be greater than N/2
It is correct for all primes greater than 2. There are (at least) 4 square roots if $\phi(N)$ is a multiple of 4. And for every uneven $p,q$, that's the case.
Jun
30
comment How to prove NIZK proof of knowledge?
The problem is, there is no $s$. Of course you can base $st_i$ on some value $s$ and reuse this. But you can not prove that to anyone. The protocol would have the very same statistical distribution as if you chose $st_i$ at random in every round. Assume e.g. the cyclic group $\mathbb{Z}_3^*=\{1,2\}$. Assume $s$ is from that group, too, but fixed, and $s'$ the other element (also fixed). Now it doesn't matter if I give you $t_i$, $s\cdot t_i$ or (s' \cdot t_i). In either case, if $t_i$ is chosen uniform, those 3 choices are uniform, too. But you can not prove that you used a fixed $s$ either.
Jun
30
comment Functions that are only second-preimage resistant?
I don't think that there is such a function. Noncryptographic hash functions are neither designed for nor examined w.r.t. preimage resistance. Either you care for cryptographic aspects and then you need to do it properly, or you don't. I don't think there is a middle ground.
Jun
26
comment RSA example-calculation: Public Key = Private Key (e = d)
Have a look here, that's the same problem with different numbers ($e=d=5, N=15,\phi(N)=12$)
Jun
24
revised Choose a random number that is different from a bunch of other secret numbers
revised my statement
Jun
24
comment Choose a random number that is different from a bunch of other secret numbers
Hm, you're right about that, there is a ZK proof. But even thinking about it makes my head hurt... I'll change my answer accordingly, and add how to go about it.
Jun
23
comment What algorithm would give the shortest ciphertext for very short plaintexts?
Ah, you're right about counter mode offering no integrity any more. But it does avoid the weakness of ECB that the same plaintext is always transformed into the same ciphertext. But I guess, counter mode is after all a bad idea.
Jun
23
comment What algorithm would give the shortest ciphertext for very short plaintexts?
Alternatively, AES in counter mode also hides the ECB weakness. If you have some part of the message as verification means (something like 3 bytes zero at the end), it doesn't even matter if packages arrive slightly out of order, because multiple counter increments can be tested.
Jun
23
comment What algorithm would give the shortest ciphertext for very short plaintexts?
Do not do this. Especially if you have a very small plaintext space, ECB performs poorly. Imagine using AES in ECB mode on messages with length 1 bit. Every message would be an encryption of $0$ or $1$. Finding out what is $E(0)$ and $E(1)$ is not that much guesswork any more. Especially with short messages, it is very important to have some form of randomization to hide the fact that the same message has been encrypted.
Jun
23
answered Choose a random number that is different from a bunch of other secret numbers
Jun
23
comment Functions that are only second-preimage resistant?
The definition of collision resistance means "find two values, which result in the same hash". If such a value is already baked in the definition of the function, collision resistance is broken. Additionally, the (small) difference between first and second preimage resistance becomes clear when you look for the $a\neq b$ statement, although in real functions are considered pretty much the same. But for example the identity function is collision resistant and second preimage resistant but not first preimage resistant.
Jun
23
comment Functions that are only second-preimage resistant?
Dingo, you might want to state what your actual goal is. Avoiding to use a "normal" cryptographic hash function? Or do you actually want to have something that is not collision resistant? As practical example of such a function, you can use MD5, which is broken for collision resistance but preimage resistance is still considered okay-ish.