Timeline for What does the expression $1^n$ mean as a function argument?
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 2, 2013 at 6:22 | history | edited | Henrick Hellström | CC BY-SA 3.0 |
added 77 characters in body
|
| May 1, 2013 at 23:09 | history | edited | Henrick Hellström | CC BY-SA 3.0 |
added 223 characters in body
|
| May 1, 2013 at 22:47 | comment | added | Henrick Hellström | let us continue this discussion in chat | |
| May 1, 2013 at 22:36 | history | edited | Henrick Hellström | CC BY-SA 3.0 |
added 20 characters in body
|
| May 1, 2013 at 22:27 | history | edited | Henrick Hellström | CC BY-SA 3.0 |
added 764 characters in body
|
| May 1, 2013 at 22:21 | history | edited | Henrick Hellström | CC BY-SA 3.0 |
added 764 characters in body
|
| May 1, 2013 at 21:36 | comment | added | Henrick Hellström | @D.W.: I think we should make a distinction between "valid attributes" and "numerically possible attribute values". I meant the former, istm you mean the latter. My point is that if you accept more than $2^n$ different attributes as valid in the sense that you accept more than $n$ predicates, you still can't use the numerical methods outlined in the paper for selecting attributes that combine more than $n$ predicates at a time - you will end up with an overdetermined equation system if you try to select an attribute for $n+1$ predicates. | |
| May 1, 2013 at 21:06 | comment | added | D.W. | @HenrickHellström, maybe I'd better narrow my comments. As a simple starter, the answer claims "there are $2^n$ possible attribute values", but this does not appear to be correct. It appears there are $N^n$ possible attribute values (as the set of attributes is $Z_N^n$); certainly it's a lot more than $2^n$. (OK, the attribute $(a_1,\dots,a_n)$ might be equivalent to $(2a_1,\dots,2a_n)$, but even then there would still be at least $N^{n-1}$ non-equivalent attribute values.) | |
| May 1, 2013 at 21:02 | comment | added | Henrick Hellström | @D.W.: Unless my math is completely off, there can't be $N^n$ possible disjoint attribute values, due to the way the predicates and attributes are combined, using a dot vector product in $\mathbb Z_N$. If the dot vector product evaluates to $0$, the predicate is "included" in the attribute. Assuming both attribute hiding and information theoretic security, the number of independent predicates and attributes are bounded by the number of linear equations that would be required to solve unknown predicates, which is $n$. | |
| May 1, 2013 at 20:38 | comment | added | D.W. | @HenrickHellström, thanks, I see what you mean about more going on here. I still don't think this answer is quite right, though. The set of attributes is $Z_N^n$, where $N$ is a large integer; thus, there are $N^n$ possible attribute values, not $2^n$. There is no reason why $1^n=(1,1,\dots,1)$ would be a particularly special or interesting attribute value. Therefore, I believe that $1^n$ is passed to the Setup routine for the reasons in my answer (force it to be polytime in $n$), not anything to do with representing the set of all predicates/attributes. | |
| May 1, 2013 at 20:36 | history | edited | D.W. | CC BY-SA 3.0 |
deleted 1 characters in body
|
| May 1, 2013 at 20:33 | comment | added | Henrick Hellström | @D.W.: There is more to it. The parameter $n$ is not just an empty place holder that only exists in the security parameter $1^n$, but represents the number of dimensions in the formal attribute set $\mathbb Z_N^n$. Confer page 3. | |
| May 1, 2013 at 20:12 | history | edited | D.W. | CC BY-SA 3.0 |
added 156 characters in body
|
| May 1, 2013 at 20:11 | comment | added | D.W. | Henrick, your answer sounds plausible on the surface, but when I read the paper, it's pretty clear that it is not correct. The real story is that $1^n$ is a security parameter (as the paper states in Definition 1), not some representation of hidden predicates, and the real explanation is the one given at crypto.stackexchange.com/q/8174/351 | |
| Apr 2, 2013 at 15:12 | comment | added | Paŭlo Ebermann | Actually, I didn't read the paper at all (being a bit on limited time), I just remember that usage convention from other papers. All "normal" (not brute-force) algorithms used in Cryptography are somehow supposed to be polynomial-time (or probabilistic polynomial). | |
| Mar 29, 2013 at 9:35 | history | edited | Henrick Hellström | CC BY-SA 3.0 |
added 470 characters in body
|
| Mar 29, 2013 at 0:38 | comment | added | Henrick Hellström | @PaŭloEbermann: Thanks, the link wasn't available when I wrote my first reply. FWIW the definitions only mention that the same security parameter is also an implicit parameter of the set of attributes and set of predicates. On what page did you find the reference to polynomial time setup? | |
| Mar 28, 2013 at 23:53 | history | edited | Henrick Hellström | CC BY-SA 3.0 |
added 553 characters in body
|
| Mar 28, 2013 at 22:17 | comment | added | Paŭlo Ebermann | I added some clarification on why this is used. Feel free to revert if you think it doesn't fit your answer, then I'll post it as a separate answer. | |
| Mar 28, 2013 at 22:16 | history | edited | Paŭlo Ebermann | CC BY-SA 3.0 |
add some reasoning about why this is done.
|
| Mar 28, 2013 at 9:40 | history | answered | Henrick Hellström | CC BY-SA 3.0 |