Reputation
21,849
Next tag badge:
98/100 score
23/20 answers
Badges
4 29 79
Impact
~464k people reached

Feb
7
comment Misunderstanding Broadcast Encryption
Check out non-committing encryption. Is it what you are looking for?
Feb
1
comment How hard is it to find plaintexts whose hashes satisfy $h(a)\oplus h(b)=h(c)$?
@JohnMeacham, I'm not familiar with SWIFFT, but if it satisfies $f(a+b)=f(a)+f(b)$, I would not call it a cryptographic hash function. The question specifically asks about cryptographic hash functions (and mentions SHA256 as an example); the term "cryptographic hash function" is often understand to require that the hash is effectively pseudorandom. So I think your criticism is debateable. If you have questions about what the OP meant by "cryptographic hash function", I suggest posting a comment underneath the question to ask the original poster to clarify.
Jan
31
comment Merkle hash tree updates
@user3150164, You can have a Merkle tree that has data values in internal nodes, if you want -- it's straightforward to extend all the ideas to that case. Alternatively, it's also possible to build a balanced binary tree data structure with values only in the leaves (and not in any internal nodes); the details of that are out of scope for this site (they're more appropriate for CS.SE than Crypto.SE). This is not a discussion forum, and not a place for extended back-and-forth or an interactive tutorial. I encourage you to formulate the original question more precisely in the future.
Jan
30
comment Merkle hash tree updates
@user3150164, inserting a new leaf at the leftmost edge can be done with $O(\lg n)$ operations. For instance, if $\ell$ is the leftmost leaf, you turn it into an internal node, with two children: $\ell$, and the new value. Then, you update the hashes of the nodes on the path to the root from these two new leaves. This takes $O(\lg n)$ time and hash updates. The general answer is: look at how any standard balanced binary tree data structure (e.g., AVL trees, red-black trees, etc.) handles this case -- they all handle this case, and achieve $O(\lg n)$ time. See paragraphs 2-4 of my answer.
Jan
30
comment Merkle hash tree updates
@user3150164, I've updated my answer with further explanation of these points.
Jan
30
comment Merkle hash tree updates
So, my advice is (1) take a closer look at the literature on balanced binary trees, (2) recognize that for most practical applications, the exact structure of the tree is not essential; all that matters is the set of values at the leaves, or possibly the order they are in. (If you have an application where you need something more, such as some special requirements on the shape of the tree, then the problem becomes different -- but that's an unusual requirement whose motivation is unclear, so don't be surprised if there haven't been many, or any, published papers on it.)
Jan
30
comment Merkle hash tree updates
Instead, the way that balanced binary tree data structures achieve $O(\lg n)$ running time is by weakening the requirement slightly: they insist that the height be $\le 2 \lg n$ (or some other slight weakening). That condition is perfectly sufficient for all needs. In practical applications there's no reason why we need the Merkle tree to have height exactly $\lg n$; height $2 \lg n$ is just as good. This relaxation is what allows balanced binary tree data structures to be efficient (including to handle the insert-at-front operation you mentioned efficiently). (cont.)
Jan
30
comment Merkle hash tree updates
@user3150164, I think I understand why you are finding this tricky -- I think the problem is that you are imposing a requirement that is stronger than it needs to be. The source of your confusion is the difference between requiring the height of the tree to be $\lg n$ vs requiring it to be $O(\lg n)$. If you insist that the height of the tree be exactly $\lg n$ (plus or minus one), then you are absolutely right that some operations can take $\Theta(n)$ time. (cont.)
Jan
30
comment Merkle hash tree updates
@user3150164, sure you can. You can do an order-preserving update by simply inserting the new value in the correct location (and if necessary deleting the old value) -- still trivial, nothing that would rise to the level of novel, publishable research. If you have a specific kind of operation that you can't see how to handle, I suggest you ask a specific question about that, but the question you actually asked was a very broad question, and I think my answer explains the answer to that broad question.
Jan
30
comment Rock-paper-scissors over network, how to protect from cheating server?
@Dillinur, yes, probably. See the paper published at IEEE Security & Privacy 2014 and other concurrent/subsequent work along those lines. Feel free to research those papers and write a detailed answer if you feel so inspired!
Jan
30
comment Hardness assumptions on composite order bilinear groups
I suggest you stick to one question per question. This site format doesn't work so well when you have more than one question in your question.
Jan
30
comment Achieving 32-bit verification code with 16-bit CRC?
I'm voting to close this question as off-topic because it is not about cryptography. (Questions about non-cryptographic checksums are off-topic; this site is for situations where there is an adversary, not about generic error detection mechanisms for non-adversarial situations.) See our help page for details of what is on-topic.
Jan
23
comment Hiding and Binding key in Groth-Sahai NIZK proof system
Please don't use images as the main content of your post. It's not accessible to the visually impaired and it's not indexed via search.
Jan
15
comment Formal security of recycled random blinding in a Paillier scheme
@Dave, for a fixed subset of the $R$'s, the chances of a collision are the same. Now count the number of such subsets. You'll find that there are exponentially many subsets, so once you sign a reasonably large number of messages, the probability that there exists some such multiplicative relationship is close to 1.
Jan
15
comment Formal security of recycled random blinding in a Paillier scheme
@Dave, I think some of your details are a bit off there: there's no reason that $R_a R_b = R_c R_d$ would require $a+b=c+d$.
Jan
15
comment Possible to use an accumulator to “license” or restrict the qty of certificates being used?
This might not be obvious, but the way this site works is that we expect all requirements to be in the question. This is not a discussion forum. Comments exist only to help you improve the question/the answer, and can disappear at any time. If you've worked out that the question needs to be revised/refined, you should edit the question accordingly -- and the same goes for your answer. Again, it's not a discussion forum, and readers shouldn't have to dive into some discussion in the comments to understand what the question is.
Jan
15
comment Possible to use an accumulator to “license” or restrict the qty of certificates being used?
Understood. But as I wrote... "that isn't quite what the question asked for". The question asked us to prevent issuing more than $n$ certificates. The answer doesn't mention this caveat. If the answer proposes a scheme that achieves something less than what was asked for, and where it might not be obvious that this is the case, it would be helpful to explain the limitations, describe what properties it does achieve, and explore whether the resulting scheme might still be adequate in practice or not. I suspect some child CA's might potentially be OK with their private key leaking.
Jan
15
comment Integrity protection in wireless sensor networks
For the future: 1. One question per question please. This site format doesn't work so well when you have a bunch of different questions stuffed together. 2. Please do more research before asking. We expect you to do a significant amount of research and self-study. Many of your questions are already answered in standard resources (textbooks, online resources, other questions on this site).
Jan
15
comment Possible to use an accumulator to “license” or restrict the qty of certificates being used?
This proposed solution doesn't work. A signer can still re-use the nonce to sign multiple messages. Therefore, this scheme doesn't prevent a child CA from issuing more than the allowed number of certificates. (Of course, if the child CA does issue more than the allowed number of signatures, it might allow others to forge signatures that look like they came from the child CA, so it might have some negative consequences for the child CA, but that's a bit delicate and isn't quite what the question asked for.)
Jan
14
comment Possible to use an accumulator to “license” or restrict the qty of certificates being used?
This answer doesn't work. I think you are confused about what a $n$-time signature scheme is. A $n$-time signature scheme is a signature scheme that is secure as long as it is used only $n$ times. There is no guarantee that it's impossible to sign $n+1$ messages, and indeed every $n$-time signature scheme I've ever seen does allow signer to sign $n+1$ messages if he wishes (though this could enable others to forge additional signatures).