2,262 reputation
29
bio website
location
age
visits member for 1 year, 6 months
seen Apr 17 at 12:08

Apr
10
comment Is there a simple zero knowledge proof of $x$ for $b=x^x\pmod p$?
If you fix the group to be $Z_p$ it might make sense. I don't have the time right now to write a full answer, but I think there is no such ZKP: In general, there is no relation between $x^x$ and $y^y$, which could be expressed as a polynomial of $x,y$ or a similar construction. Something like this is part of DSA/ ElGamal signatures, where you have something like $p(x)^{q(x)}$ ($p,q$ being polynomials, depending on $x$), which is why unforgeability can be proven. However, the topic of extracting $x$ from $x^x$ is quite difficult (and I can't think of an actual link to DLOG, for example).
Apr
10
comment Is there a simple zero knowledge proof of $x$ for $b=x^x\pmod p$?
The changing of the question makes DrLecter's answer seem not applicable. The original statement of $a^{(x^2)}=b$ was solved by that paper, $x^x=b$ isn't.
Apr
10
revised What are some disadvantages of homomorphic encryption schemes?
Changed first sentence, due to comment.
Apr
10
comment What are some disadvantages of homomorphic encryption schemes?
Well, the definition of the properties are (almost) equivalent. Just one term is used when you actually want this property and the other when you don't. The actual difference is, that malleability only requires some sort of relation, while leaving the actual relation unspecified
Mar
31
comment Cryptographic system with double keys with reversible order
In the IND-CPA game the adversary usually only gets one challenge ciphertext. This still breaks all deterministic encryption, but if $E$ is probabilistic it isn't necessarily the case. However, probabilistic schemes can probably not provide this commutativity.
Mar
28
comment Times of nested algorithms in proofs of security
It seems I don't understand what you mean. $A$ NEVER waits for $A'$. $A$ does not even know $A'$ exists. $A$ is a full fledged algorithm: You start it with some input, it runs for a certain time (which is $t$) and then it stops. There is no interaction with $A'$.
Mar
28
comment Times of nested algorithms in proofs of security
$A$ is used to construct $A'$. That means, $A$ exists on its own already. The time $t$ does not state the time required in this context, but for the algorithm $A$ alone. $A'$ is based on $A$, so it has to consider the time spent for $A$ as well.
Mar
27
comment Times of nested algorithms in proofs of security
That is a wrong conclusion. The computations are bound by $n\cdot t_c \geq t' - t$. But if $A'$ has to do any computations after it $A$ terminated and gave the results, they do not end at the same time. Even in your simple example, the attack $A$ alone does 2 steps of time ($A$ is a standalone algorithm), while $A$ requires to wait for $A$ for 2 units and do 2 computations of its own, so overall $4$ (if you assume the time slots to be equal, and no parallel execution).
Mar
27
revised Times of nested algorithms in proofs of security
added 1176 characters in body
Mar
27
answered Times of nested algorithms in proofs of security
Mar
27
comment Near preimages, applicable to Bitcoin?
As far as I know, bitcoin mining is pretty much a brute-force effort: Try out different combinations, e.g. starting at a random value and then increment by $1$, so that you don't cover numbers that someone else already checked. There is no cryptanalysis done, or any kind of advanced attack technique.
Mar
25
comment Construct an encryption algorithm using hash function
Skein works... because it is built upon threefish, which is a blockcipher. The proof that Skein is a PRNG is built upon Threefish being a PRP. So basically the proof of security is along the lines "We design a secure encryption scheme, which is based on a secure hash function, which is based on a secure encryption scheme. And we assume this encryption scheme to be secure. So our final design must also be secure."
Mar
25
answered Construct an encryption algorithm using hash function
Mar
25
comment Construct an encryption algorithm using hash function
Without checking the exact text, I am pretty sure he also wrote in Applied Cryptography, that this is not save without a proper cryptanalysis. Hash functions work differently than encryption functions. For example differential cryptanalysis doesn't do anything in hash functions, but it can break encryption.
Mar
25
comment Construct an encryption algorithm using hash function
It's quite similar to Can I use HMAC-SHA1 in counter mode to make a stream cipher?, Hash Based Encryption (fast & simple), how well would this compare to AES?... there are even more out there.
Mar
25
comment Challenge–response authentication which can be done in head?
One-way functions are quite hard to calculate in your head alone. If the listener has access to a computer, there is no algorithm he couldn't brute force. But even then, probably there is no such algorithm due to the limits of calculations in the human brain
Mar
25
comment why it is not possible to find inverse of its own in diffie-hellman protocol?
Asking twice doesn't give you a better answer than DrLecter's in the other post, because that answer is already correct.
Mar
25
comment What is difference between PRG, PRF, and PRP
Ah, you're right, sorry. I forgot about the basic homomorphism feature of being structure preserving...
Mar
24
comment What is difference between PRG, PRF, and PRP
Ah, I just read the last paragraph. The non-determinism is wrong. A different output would only be possible for a different key, and this will also happen for a PRP.
Mar
24
comment What is difference between PRG, PRF, and PRP
The reasoning and notation is quite off from common standards. $f:X \rightarrow X$ means, it is an endomorphism. But what you meant is an isomorphism. Just saying that the domain and range are the same structure does not imply a bijection (e.g. $\mathbb{Z} \rightarrow \mathbb{Z}: x \rightarrow 0$ is formally okay, but not a bijection). In short: A PRP is a bijective PRF. That's it. Bijective functions are invertible, but it does not mean this algorithm is efficient (or can be found easily); and this is not required from PRPs. Dont mix them with block ciphers