tag:blogger.com,1999:blog-786333285568106173.post7117143604220909221..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: Encoding ProofsMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-786333285568106173.post-72224214734959154602009-10-27T20:35:50.775-04:002009-10-27T20:35:50.775-04:00I love how your now co-author list their [probable...I love how your now co-author list their [probable] initial submission on their papers page.David Coughlinhttps://www.blogger.com/profile/15859839245975431814noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-23722207795740854932009-10-27T19:48:20.215-04:002009-10-27T19:48:20.215-04:00I don't see a natural interpretation of non-sy...I don't see a natural interpretation of non-systematic representation.<br /><br />A one-way permutation should be efficiently computable, so a time-t adversary should be able to get about t evaluations of the permutation, which you can model by having the permutation itself be available for lookup. Then (if you are trying to prove a lower bound for non-uniform algorithms in an oracle setting) the algorithm can have some non-uniform advice, which is the redundant part of the data structure. At this point, from Hellman and Yao it follows that the optimal tradeoff for inverting is time t and redundancy m provided m*t > N where N is the size of the range of the permutation.<br /><br />Here is a question that has been open for 10+ years: suppose I want to determine the non-uniform complexity of inverting a random *function* rather than a permutation. Fiat and Naor show that a random function mapping [N] into [N] can be inverted in time t with redundancy m provided t* m^2 > N, up to polylogN terms. (Same if the function is not random, but it has the property that the preimage size is at most polylogN.)<br /><br />Amos Fiat, Moni Naor: <br />Rigorous Time/Space Trade-offs for Inverting Functions. <br />SIAM J. Comput. 29(3): 790-803 (1999)<br /><br />And this paper shows that this trade-off (which has the interesting case t=m=N^{2/3}) is best possible under rather restrictive assumptions on what the redundant part of the data structure is allowed to contain, and how it is allowed to be used<br /><br />Elad Barkan, Eli Biham, Adi Shamir:<br />Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs. <br />CRYPTO 2006: 1-21<br /><br />Is t=m=N^{2/3} best possible for functions with small pre-images in the fully-general cell-probe / non-uniform-oracle-algorithm model?<br /><br />(For general functions, Fiat-Naor only get the trade-off tm^3>N^3, which has the interesting case t=m=N^{3/4})<br /><br />Even showing that t=m=N^{1/2+eps} is not achievable would be interesting because it would separate the complexity of functions from the complexity of permutations, for which t=m=N^{1/2} is achievable.Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-5758516906217981902009-10-27T18:22:32.465-04:002009-10-27T18:22:32.465-04:00One crypto application, which can already be hinte...One crypto application, which can already be hinted from my paper with Erik is that if gives a lower bound on the time for decrypting a message on the bit/cell probe model. Although the lower bound is extremely weak, nothing higher than that has been proven as far as we were able to ascertain.<br /><br />Here's the scheme. You create a random permutation <i>π</i> of the integers 1 to n. Consider this permutation to be your encrypting key as follows. A message M composed of say nlog n bits is encoded by sending <i>π</i> applied to the first log n bits, then <i>π</i> to the next log n bits and so on.<br /><br />Now assume that Eve manages to get her hands on the private key, encoded in whatever form she prefers. Even so, by the lower bound it follows that this is not enough to decode the message in constant time per log n bits. Her choices are now (a) to spend time t decoding each word for a total decoding time of n*t, (b) to bite the bullet and build a data structure of size n/t to assist in fast lookups for a total time of n*t+n/t > 2n, or (c) to obtain more data from the channel which by the lower bound is at least an additional n log n bits.<br /><br />The generalization to the cell probe model gives n*t +n/(log n)^t > n+n/log n lower bound for breaking the key.<br /><br />The decrypting lower bound is extremely weak: breaking the message takes Eve an extra n/log n <i>additive</i> term.Alex Lopez-Ortiznoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-17732452724107165052009-10-27T09:09:30.080-04:002009-10-27T09:09:30.080-04:00The encoding technique is certainly well-known in ...The encoding technique is certainly well-known in data structures. It appeared for instance in [Fredman '82], [Demaine Lopez-Ortiz '01], [Demaine Patrascu '04], [Golynski '09]. I don't think you can attribute it to any one person.<br /><br />Luca, now we have lower bounds for storing permutations in a non-systematic fashion [Golynski'09]. Can this be connected to crypto? Does non-systematic have any natural meaning there?<br /><br /><i>What is that you don't like in the first proof? [...] Is it this conditioning that you consider not too intuitive? Just asking since I found the first proof really cute</i><br /><br />The high entropy given the conditioning is intuitive (for someone in the area), but rather technical to prove. For instance, I didn't even deal with independent variables, but with two dependent vectors, each having independent coordinates.<br /><br />If you can get the proof down to essentially high school math, you should always do it :)Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-13467264248619094922009-10-27T06:47:41.343-04:002009-10-27T06:47:41.343-04:00What is that you don't like in the first proof...What is that you don't like in the first proof?<br /><br />The first proof argues Q_0, Q_delta can be encoded efficiently even under some arbitrary conditioning (with sufficiently high probability)?<br /><br />Is it this conditioning that you consider not too intuitive?<br /><br />Just asking since I found the first proof really cute.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-33540278721583428322009-10-27T03:39:04.479-04:002009-10-27T03:39:04.479-04:00Isn't also the constructive proof of Lovasz...Isn't also the constructive proof of Lovasz's local lemma an encoding proof?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-90862793582218995742009-10-26T22:38:50.804-04:002009-10-26T22:38:50.804-04:00Hi Luca.
I like your connection to data structure...Hi Luca.<br /><br />I like your connection to data structures a lot, thanks!<br /><br />Regarding Kolmogorov complexity comparison, I think the difference is that the encoding arguments are expected to be used there, since this is more or less what definition states. But the encoding technique is somewhat surprising at the first glance (until one thinks about it, as Luca just did).<br /><br />Indeed, my first inclination to argue that no small circuit can invert a random permutation with forward oracle access is to perhaps to first fix the circuit, and argue that <br /><br />Pr (fixed circuit succeeds with probability > e) << 1/#circuits. <br /><br />And computing the latter probability is somewhat painful. Certainly doable for this relatively simple example, but IMHO much more complicated than the beautiful encoding technique. Namely, compress a random permutation as follows (simplified): give the small circuit as advice, describe the set<br /> S of inputs on which the circuit succeeds, describe pi^{-1}(S) as a set, and then explicitly describe pi^{-1}(y) for all remaining y's. The rest is just counting the size of this description in one line! Very natural, no probability calculations!<br /><br />YevgeniyAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-31924897040714832292009-10-26T22:08:17.272-04:002009-10-26T22:08:17.272-04:00Hi Yevgeniy,
it turns out that this 1990 paper of...Hi Yevgeniy,<br /><br />it turns out that this 1990 paper of Andy Yao<br /><br />Andrew Chi-Chih Yao: <br />Coherent Functions and Program Checkers<br />STOC 1990: 84-94<br /><br />already had the main idea of the proof you mention from my paper with Rosario. He deals with the simpler question of the complexity of inverting a random permutation on all inputs and he shows that, roughly speaking, if you have an oracle inversion algorithm for a permutation that uses m bits of advice and has query complexity q, then a 1/q fraction of the outputs of the permutation are implied by the other outputs and by the advice.<br /><br />If you think of the permutation itself, plus the m bits of advice, as a data structure with m bits of redundancy, and of the q-query oracle inversion algorithm as a q-query algorithm in the cell-probe model, then Yao's result (and the one with Rosario, and the later ones etc.) are really redundancy/query trade-off for certain systematic data structures, so it's not surprising that one would end up using similar techniques.Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-61244934295334293102009-10-26T20:28:32.328-04:002009-10-26T20:28:32.328-04:00Interestingly, as far as I know, the encoding tech...<i>Interestingly, as far as I know, the encoding technique for proving the lower bounds was first observed by Gennaro-Trevisan.</i><br /><br />Isn't the entire field of Kolmogorov complexity all about using encodings of random objects to prove lower bounds or are you talking about a more specialized application?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-16329003068714853992009-10-26T14:53:11.489-04:002009-10-26T14:53:11.489-04:00Hi Mihai.
Interestingly, as far as I know, the en...Hi Mihai.<br /><br />Interestingly, as far as I know, the encoding technique for proving the lower bounds was first observed by Gennaro-Trevisan. They observed that if there is a small circuit for inverting a random permutation with non-trivial probability, then you can compact the description of the random permutation.<br /><br />Although quite basic, I totally agree and love this technique. More recently, several paper co-authored by Iftach Heitner (and others, of course) applied this technique to much more powerful situations, where a direct proof seem hard. One nice thing about the encoding technique is that the encoder/decoder are allowed to be inefficient, if you one proves the lower bound on efficiency of some algorithm or cryptographic assumption.<br /><br />Recently, I worked with Iftach (and a student) on a paper where we successfully used this technique to argue the impossibility of black-box reduction from one problem to another (more or less), and I truly appreciated its power.<br /><br />Very interesting that it is used in algorithms much less (and much more recently) than in crypto, and that it is not as known in data structures as much as it is known in crypto.<br /><br />YevgeniyAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-63675663416934669422009-10-26T06:53:04.202-04:002009-10-26T06:53:04.202-04:00I'm not a computer scientist, and to me this s...<i>I'm not a computer scientist, and to me this sounds like a recipe for lots and lots of incorrect results. Add to that the common practice in CS of not submitting to journals...</i><br /><br />Spotting errors is very hard. The idea that journal reviewers do it is wishful thinking. But the good news is that 90% of what we publish is crap, so who cares if it's correct or not? If somebody actually cares about your result, it will get checked.<br /><br /><i>You mean you were getting scooped or something on this result and so you were forced to do it to ensure at least a merge?</i><br /><br />I was getting "scooped" by a weaker result which was not an independent discovery. My choice was between submitting to SODA and accepting a merger of the author lists, or starting a public fight. Since I chose the former, it doesn't make sense to go into details now.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-65972520408914895442009-10-26T05:39:08.795-04:002009-10-26T05:39:08.795-04:00You mean you were getting scooped or something on ...You mean you were getting scooped or something on this result and so you were forced to do it to ensure at least a merge? I mean tell me the story...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-75355459534436362472009-10-25T21:08:27.303-04:002009-10-25T21:08:27.303-04:00"Well, the common opinion is that PCs rarely ...<em>"Well, the common opinion is that PCs rarely read technical in the paper. So it's as peer-reviewed as any other paper in the conference :) "</em><br /><br />That sounds bad. I'm not a computer scientist, and to me this sounds like a recipe for lots and lots of incorrect results. Add to that the common practice in CS of not submitting to journals...<br /><br />Out of curiosity, what proportion of conference papers in CS do you think have fatal errors in them?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-35610172039606025022009-10-25T19:51:29.434-04:002009-10-25T19:51:29.434-04:00I am curious to learn how many commenters are goin...<i>I am curious to learn how many commenters are going to look at the techniques in the paper(s), and how many people are going to zoom in on the tiny politically incorrect statements in Mihai's blog post.</i><br /><br />To each his own :)<br /><br /><i>So the camera-ready version bears little resemblance to the accepted version? Can it even be called a "peer-reviewed" publication in that case?</i><br /><br />Well, the common opinion is that PCs rarely read technical in the paper. So it's as peer-reviewed as any other paper in the conference :) -- my introduction didn't change, of course.<br /><br /><i>You quit IBM?</i><br /><br />Sure (with ample notice). I was going to the Central European Olympiad in Romania, and then starting at ATT.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-76360743392983130502009-10-25T19:45:25.024-04:002009-10-25T19:45:25.024-04:00You quit IBM?You quit IBM?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-57574830224897584292009-10-25T11:51:59.552-04:002009-10-25T11:51:59.552-04:00I agree with what well said by Morin.
More to the...I agree with what well said by Morin.<br /><br />More to the point, it would be very nice to write a pedagogical paper in which the usefulness of the "encoding technique" is illustrated on a variety of examples.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-40780191390847381562009-10-25T09:05:14.671-04:002009-10-25T09:05:14.671-04:00It's nice to see someone putting effort into c...It's nice to see someone putting effort into cleaning up a result even after it has been accepted. <br /><br />Too many authors do what you did (to meet the deadline) and then take the program committee's acceptance as a certificate that the paper is "good enough."Anonymoushttps://www.blogger.com/profile/06328185728688465505noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-22190095845979805532009-10-25T03:11:18.304-04:002009-10-25T03:11:18.304-04:00So the camera-ready version bears little resemblan...So the camera-ready version bears little resemblance to the accepted version? Can it even be called a "peer-reviewed" publication in that case?Craiovanoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-35988235307260070992009-10-25T01:24:43.464-04:002009-10-25T01:24:43.464-04:00I am curious to learn how many commenters are goin...I am curious to learn how many commenters are going to look at the techniques in the paper(s), and how many people are going to zoom in on the tiny politically incorrect statements in Mihai's blog post. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-73795269076416691322009-10-24T19:44:06.182-04:002009-10-24T19:44:06.182-04:00What sort of behavior?What sort of behavior?Anonymousnoreply@blogger.com