@article{3010, abstract = {The formation of the leaf vascular pattern has fascinated biologists for centuries. In the early leaf primordium, complex networks of procambial cells emerge from homogeneous subepidermal tissue. The molecular nature of the underlying positional information is unknown, but various lines of evidence implicate gradually restricted transport routes of the plant hormone auxin in defining sites of procambium formation. Here we show that a crucial member of the AtPIN family of auxin-efflux-associated proteins, AtPIN1, is expressed prior to pre-procambial and procambial cell fate markers in domains that become restricted toward sites of procambium formation. Subcellular AtPIN1 polarity indicates that auxin is directed to distinct "convergence points" in the epidermis, from where it defines the positions of major veins. Integrated polarities in all emerging veins indicate auxin drainage toward pre-existing veins, but veins display divergent polarities as they become connected at both ends. Auxin application and transport inhibition reveal that convergence point positioning and AtPIN1 expression domain dynamics are self-organizing, auxin-transport-dependent processes. We derive a model for self-regulated, reiterative patterning of all vein orders and postulate at its onset a common epidermal auxin-focusing mechanism for major-vein positioning and phyllotactic patterning.}, author = {Scarpella, Enrico and Marcos, Danielle and Jirí Friml and Berleth, Thomas}, journal = {Genes and Development}, number = {8}, pages = {1015 -- 1027}, publisher = {Cold Spring Harbor Laboratory Press}, title = {{Control of leaf vascular patterning by polar auxin transport}}, doi = {10.1101/gad.1402406}, volume = {20}, year = {2006}, } @article{3011, abstract = {Polar flow of the phytohormone auxin requires plasma membrane‐associated PIN proteins and underlies multiple developmental processes in plants. Here we address the importance of the polarity of subcellular PIN localization for the directionality of auxin transport in Arabidopsis thaliana. Expression of different PINs in the root epidermis revealed the importance of PIN polar positions for directional auxin flow and root gravitropic growth. Interfering with sequence-embedded polarity signals directly demonstrates that PIN polarity is a primary factor in determining the direction of auxin flow in meristematic tissues. This finding provides a crucial piece in the puzzle of how auxin flow can be redirected via rapid changes in PIN polarity.}, author = {Wiśniewska, Justyna and Xu, Jian and Seifertová, Daniela and Brewer, Philip B and Růžička, Kamil and Blilou, Ikram and Rouquié, David and Eva Benková and Scheres, Ben and Jirí Friml}, journal = {Science}, number = {5775}, publisher = {American Association for the Advancement of Science}, title = {{Polar PIN localization directs auxin flow in plants}}, doi = {10.1126/science.1121356}, volume = {312}, year = {2006}, } @article{3012, abstract = {Intercellular flow of the phytohormone auxin underpins multiple developmental processes in plants. Plant-specific pin-formed (PIN) proteins and several phosphoglycoprotein (PGP) transporters are crucial factors in auxin transport-related development, yet the molecular function of PINs remains unknown. Here, we show that PINs mediate auxin efflux from mammalian and yeast cells without needing additional plant-specific factors. Conditional gain-of-function alleles and quantitative measurements of auxin accumulation in Arabidopsis and tobacco cultured cells revealed that the action of PINs in auxin efflux is distinct from PGP, rate-limiting, specific to auxins, and sensitive to auxin transport inhibitors. This suggests a direct involvement of PINs in catalyzing cellular auxin efflux.}, author = {Petrášek, Jan and Mravec, Jozef and Bouchard, Rodolphe and Blakeslee, Joshua and Melinda Abas and Seifertová, Daniela and Wiśniewska, Justyna and Tadele, Zerihun and Kubeš, Martin and Čovanová, Milada and Dhonukshe, Pankaj and Skůpa, Petr and Eva Benková and Perry, Lucie and Křeček, Pavel and Lee, Ok Ran and Fink, Gerald R and Geisler, Markus and Murphy, Angus S and Luschnig, Christian and Zažímalová, Eva and Jirí Friml}, journal = {Science}, number = {5775}, pages = {914 -- 918}, publisher = {American Association for the Advancement of Science}, title = {{PIN proteins perform a rate-limiting function in cellular auxin efflux}}, doi = {10.1126/science.1123542}, volume = {312}, year = {2006}, } @article{3013, abstract = {There is a growing demand for methods that allow rapid and reliable in situ localization of proteins in plant cells. The immunocytochemistry protocol presented here can be used routinely to observe protein localization patterns in tissue sections of various plant species. This protocol is especially suitable for plant species with more-complex tissue architecture (such as maize, Zea mays), which makes it difficult to use an easier whole-mount procedure for protein localization. To facilitate the antibody-antigen reaction, it is necessary to include a wax-embedding and tissue-sectioning step. The protocol consists of the following procedures: chemical fixation of tissue, dehydration, wax embedding, sectioning, dewaxing, rehydration, blocking and antibody incubation. The detailed protocol, recommended controls and troubleshooting are presented here, along with examples of applications.}, author = {Paciorek, Tomasz and Sauer, Michael and Balla, Jozef and Wiśniewska, Justyna and Jirí Friml}, journal = {Nature Protocols}, number = {1}, pages = {104 -- 107}, publisher = {Nature Publishing Group}, title = {{Immunocytochemical technique for protein localization in sections of plant tissues}}, doi = {10.1038/nprot.2006.16}, volume = {1}, year = {2006}, } @article{3014, abstract = {Plant biology is currently confronted with an overflow of expression profile data provided by high-throughput microarray transcription analyses. However, the tissue and cellular resolution of these techniques is limited. Thus, it is still necessary to examine the expression pattern of selected candidate genes at a cellular level. Here we present an in situ mRNA hybridization method that is routinely used in the analysis of gene expression patterns. The protocol is optimized for mRNA localizations in sectioned tissue of Arabidopsis seedlings including embryos, roots, hypocotyls, young primary leaves and flowers. The detailed protocol, recommended controls and troubleshooting are presented along with examples of application. The total time for the process is 10 days.}, author = {Brewer, Philip B and Heisler, Marcus G and Hejátko, Jan and Jirí Friml and Eva Benková}, journal = {Nature Protocols}, number = {3}, pages = {1462 -- 1467}, publisher = {Nature Publishing Group}, title = {{In situ hybridization for mRNA detection in Arabidopsis tissue sections}}, doi = {10.1038/nprot.2006.226}, volume = {1}, year = {2006}, } @article{3015, abstract = {As the field of plant molecular biology is swiftly advancing, a need has been created for methods that allow rapid and reliable in situ localization of proteins in plant cells. Here we describe a whole-mount 'immunolocalization' technique for various plant tissues, including roots, hypocotyls, cotyledons, young primary leaves and embryos of Arabidopsis thaliana and other species. The detailed protocol, recommended controls and troubleshooting are presented, along with examples of applications. The protocol consists of five main procedures: tissue fixation, tissue permeation, blocking, primary and secondary antibody incubation. Notably, the first procedure (tissue fixation) includes several steps (4-12) that are absolutely necessary for protein localization in hypocotyls, cotyledons and young primary leaves but should be omitted for other tissues. The protocol is usually done in 3 days, but could also be completed in 2 days.}, author = {Sauer, Michael and Paciorek, Tomasz and Eva Benková and Jirí Friml}, journal = {Nature Protocols}, number = {1}, pages = {98 -- 103}, publisher = {Nature Publishing Group}, title = {{Immunocytochemical techniques for whole mount in situ protein localization in plants}}, doi = {10.1038/nprot.2006.15}, volume = {1}, year = {2006}, } @article{3016, abstract = {Plant development is characterized by a profound ability to regenerate and form tissues with new axes of polarity. An unsolved question concerns how the position within a tissue and cues from neighboring cells are integrated to specify the polarity of individual cells. The canalization hypothesis proposes a feedback effect of the phytohormone auxin on the directionality of intercellular auxin flow as a means to polarize tissues. Here we identify a cellular and molecular mechanism for canalization. Local auxin application, wounding, or auxin accumulation during de novo organ formation lead to rearrangements in the subcellular polar localization of PIN auxin transport components. This auxin effect on PIN polarity is cell-specific, does not depend on PIN transcription, and involves the Aux/IAA-ARF (indole-3-acetic acid-auxin response factor) signaling pathway. Our data suggest that auxin acts as polarizing cue, which links individual cell polarity with tissue and organ polarity through control of PIN polar targeting. This feedback regulation provides a conceptual framework for polarization during multiple regenerative and patterning processes in plants.}, author = {Sauer, Michael and Balla, Jozef and Luschnig, Christian and Wiśniewska, Justyna and Reinöhl, Vilém and Friml, Jirí and Benková, Eva}, journal = {Genes and Development}, number = {20}, pages = {2902 -- 2911}, publisher = {Cold Spring Harbor Laboratory Press}, title = {{Canalization of auxin flow by Aux/IAA-ARF-dependent feedback regulation of PIN polarity}}, doi = {10.1101/gad.390806}, volume = {20}, year = {2006}, } @article{3017, abstract = {The plant hormone auxin plays crucial roles in regulating plant growth development, including embryo and root patterning, organ formation, vascular tissue differentiation and growth responses to environmental stimuli. Asymmetric auxin distribution patterns have been observed within tissues, and these so-called auxin gradients change dynamically during different developmental processes. Most auxin is synthesized in the shoot and distributed directionally throughout the plant. This polar auxin transport is mediated by auxin influx and efflux facilitators, whose subcellular polar localizations guide the direction of auxin flow. The polar localization of PIN auxin efflux carriers changes in response to developmental and external cues in order to channel auxin flow in a regulated manner for organized growth. Auxin itself modulates the expression and subcellular localization of PIN proteins, contributing to a complex pattern of feedback regulation. Here we review the available information mainly from studies of a model plant, Arabidopsis thaliana, on the generation of auxin gradients, the regulation of polar auxin transport and further downstream cellular events.}, author = {Tanaka, Hirokazu and Dhonukshe, Pankaj and Brewer, Philip and Friml, Jirí}, journal = {Cellular and Molecular Life Sciences}, number = {23}, pages = {2738 -- 2754}, publisher = {Birkhäuser}, title = {{Spatiotemporal asymmetric auxin distribution: A means to coordinate plant development}}, doi = {10.1007/s00018-006-6116-5}, volume = {63}, year = {2006}, } @article{3018, abstract = {The directional flow of the plant hormone auxin mediates multiple developmental processes, including patterning and tropisms. Apical and basal plasma membrane localization of AUXIN-RESISTANT1 (AUX1) and PIN-FORMED1 (PIN1) auxin transport components underpins the directionality of intercellular auxin flow in Arabidopsis thaliana roots. Here, we examined the mechanism of polar trafficking of AUX1. Real-time live cell analysis along with subcellular markers revealed that AUX1 resides at the apical plasma membrane of protophloem cells and at highly dynamic subpopulations of Golgi apparatus and endosomes in all cell types. Plasma membrane and intracellular pools of AUX1 are interconnected by actin-dependent constitutive trafficking, which is not sensitive to the vesicle trafficking inhibitor brefeldin A. AUX1 subcellular dynamics are not influenced by the auxin influx inhibitor NOA but are blocked by the auxin efflux inhibitors TIBA and PBA. Furthermore, auxin transport inhibitors and interference with the sterol composition of membranes disrupt polar AUX1 distribution at the plasma membrane. Compared with PIN1 trafficking, AUX1 dynamics display different sensitivities to trafficking inhibitors and are independent of the endosomal trafficking regulator ARF GEF GNOM. Hence, AUX1 uses a novel trafficking pathway in plants that is distinct from PIN trafficking, providing an additional mechanism for the fine regulation of auxin transport.}, author = {Kleine-Vehn, Jürgen and Dhonukshe, Pankaj and Swarup, Ranjan and Bennett, Malcolm and Jirí Friml}, journal = {Plant Cell}, number = {11}, pages = {3171 -- 3181}, publisher = {American Society of Plant Biologists}, title = {{Subcellular trafficking of the Arabidopsis auxin influx carrier AUX1 uses a novel pathway distinct from PIN1}}, doi = {10.1105/tpc.106.042770}, volume = {18}, year = {2006}, } @article{3020, abstract = {High throughput microarray transcription analyses provide us with the expression profiles for large amounts of plant genes. However, their tissue and cellular resolution is limited. Thus, for detailed functional analysis, it is still necessary to examine the expression pattern of selected candidate genes at a cellular level. Here, we present an in situ mRNA hybridization method that is routinely used for the analysis of plant gene expression patterns. The protocol is optimized for whole mount mRNA localizations in Arabidopsis seedling tissues including embryos, roots, hypocotyls and young primary leaves. It can also be used for comparable tissues in other species. Part of the protocol can also be automated and performed by a liquid handling robot. Here we present a detailed protocol, recommended controls and troubleshooting, along with examples of several applications. The total time to carry out the entire procedure is ∼7 d, depending on the tissue used.}, author = {Hejátko, Jan and Blilou, Ikram and Brewer, Philip B and Jirí Friml and Scheres, Ben and Eva Benková}, journal = {Nature Protocols}, number = {4}, pages = {1939 -- 1946}, publisher = {Nature Publishing Group}, title = {{In situ hybridization technique for mRNA detection in whole mount Arabidopsis samples}}, doi = {10.1038/nprot.2006.333}, volume = {1}, year = {2006}, } @article{3152, abstract = {The basic concepts of the molecular machinery that mediates cell migration have been gleaned from cell culture systems. However, the three-dimensional environment within an organism presents migrating cells with a much greater challenge. They must move between and among other cells while interpreting multiple attractive and repulsive cues to choose their proper path. They must coordinate their cell adhesion with their surroundings and know when to start and stop moving. New insights into the control of these remaining mysteries have emerged from genetic dissection and live imaging of germ cell migration in Drosophila, zebrafish, and mouse embryos. In this review, we first describe germ cell migration in cellular and mechanistic detail in these different model systems. We then compare these systems to highlight the emerging principles. Finally, we contrast the migration of germ cells with that of immune and cancer cells to outline the conserved and different mechanisms.}, author = {Kunwar, Prabhat S and Daria Siekhaus and Lehmann, Ruth}, journal = {Annual Review of Cell and Developmental Biology}, pages = {237 -- 265}, publisher = {Annual Reviews}, title = {{In vivo migration A germ cell perspective}}, doi = {10.1146/annurev.cellbio.22.010305.103337}, volume = {22}, year = {2006}, } @inproceedings{3180, abstract = {One of the most exciting advances in early vision has been the development of efficient energy minimization algorithms. Many early vision tasks require labeling each pixel with some quantity such as depth or texture. While many such problems can be elegantly expressed in the language of Markov Random Fields (MRF's), the resulting energy minimization problems were widely viewed as intractable. Recently, algorithms such as graph cuts and loopy belief propagation (LBP) have proven to be very powerful: for example, such methods form the basis for almost all the top-performing stereo methods. Unfortunately, most papers define their own energy function, which is minimized with a specific algorithm of their choice. As a result, the tradeoffs among different energy minimization algorithms are not well understood. In this paper we describe a set of energy minimization benchmarks, which we use to compare the solution quality and running time of several common energy minimization algorithms. We investigate three promising recent methods - graph cuts, LBP, and tree-reweighted message passing - as well as the well-known older iterated conditional modes (ICM) algorithm. Our benchmark problems are drawn from published energy functions used for stereo, image stitching and interactive segmentation. We also provide a general-purpose software interface that allows vision researchers to easily switch between optimization methods with minimal overhead. We expect that the availability of our benchmarks and interface will make it significantly easier for vision researchers to adopt the best method for their specific problems. Benchmarks, code, results and images are available at http://vision.middlebury.edu/MRF.}, author = {Szeliski, Richard S and Zabih, Ramin and Scharstein, Daniel and Veksler, Olga and Vladimir Kolmogorov and Agarwala, Aseem and Tappen, Marshall F and Rother, Carsten}, pages = {16 -- 29}, publisher = {Springer}, title = {{A comparative study of energy minimization methods for Markov random fields}}, doi = {10.1007/11744047_2}, volume = {3952}, year = {2006}, } @inproceedings{3184, abstract = {Algorithms for discrete energy minimization play a fundamental role for low-level vision. Known techniques include graph cuts, belief propagation (BP) and recently introduced tree-reweighted message passing (TRW). So far, the standard benchmark for their comparison has been a 4-connected grid-graph arising in pixel-labelling stereo. This minimization problem, however, has been largely solved: recent work shows that for many scenes TRW finds the global optimum. Furthermore, it is known that a 4-connecled grid-graph is a poor stereo model since it does not take occlusions into account. We propose the problem of stereo with occlusions as a new test bed for minimization algorithms. This is a more challenging graph since it has much larger connectivity, and it also serves as a better stereo model. An attractive feature of this problem is that increased connectivity does not result in increased complexity of message passing algorithms. Indeed, one contribution of this paper is to show that sophisticated implementations of BP and TRW have the same time and memory complexity as that of 4-connecled grid-graph stereo. The main conclusion of our experimental study is that for our problem graph cut outperforms both TRW and BP considerably. TRW achieves consistently a lower energy than BP. However, as connectivity increases the speed of convergence of TRW becomes slower. Unlike 4-connected grids, the difference between the energy of the best optimization method and the lower bound of TRW appears significant. This shows the hardness of the problem and motivates future research.}, author = {Vladimir Kolmogorov and Rother, Carsten}, pages = {1 -- 15}, publisher = {Springer}, title = {{Comparison of energy minimization algorithms for highly connected graphs}}, doi = {10.1007/11744047_1}, volume = {3952 LNCS}, year = {2006}, } @article{3185, abstract = {This paper describes models and algorithms for the real-time segmentation of foreground from background layers in stereo video sequences. Automatic separation of layers from color/contrast or from stereo alone is known to be error-prone. Here, color, contrast, and stereo matching information are fused to infer layers accurately and efficiently. The first algorithm, Layered Dynamic Programming (LDP), solves stereo in an extended six-state space that represents both foreground/background layers and occluded regions. The stereo-match likelihood is then fused with a contrast-sensitive color model that is learned on-the-fly and stereo disparities are obtained by dynamic programming. The second algorithm, Layered Graph Cut (LGC), does not directly solve stereo. Instead, the stereo match likelihood is marginalized over disparities to evaluate foreground and background hypotheses and then fused with a contrast-sensitive color model like the one used in LDP. Segmentation is solved efficiently by ternary graph cut. Both algorithms are evaluated with respect to ground truth data and found to have similar performance, substantially better than either stereo or color/contrast alone. However, their characteristics with respect to computational efficiency are rather different. The algorithms are demonstrated in the application of background substitution and shown to give good quality composite video output.}, author = {Vladimir Kolmogorov and Criminisi, Antonio and Blake, Andrew and Cross, Geoffrey and Rother, Carsten}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {9}, pages = {1480 -- 1492}, publisher = {IEEE}, title = {{Probabilistic fusion of stereo with color and contrast for bilayer segmentation}}, doi = {10.1109/TPAMI.2006.193}, volume = {28}, year = {2006}, } @inproceedings{3186, abstract = {We introduce a new approach to modelling gradient flows of contours and surfaces. While standard variational methods (e.g. level sets) compute local interface motion in a differential fashion by estimating local contour velocity via energy derivatives, we propose to solve surface evolution PDEs by explicitly estimating integral motion of the whole surface. We formulate an optimization problem directly based on an integral characterization of gradient flow as an infinitesimal move of the (whole) surface giving the largest energy decrease among all moves of equal size. We show that this problem can be efficiently solved using recent advances in algorithms for global hypersurface optimization [4, 2, 11]. In particular, we employ the geo-cuts method [4] that uses ideas from integral geometry to represent continuous surfaces as cuts on discrete graphs. The resulting interface evolution algorithm is validated on some 2D and 3D examples similar to typical demonstrations of level-set methods. Our method can compute gradient flows of hypersurfaces with respect to a fairly general class of continuous functional and it is flexible with respect to distance metrics on the space of contours/surfaces. Preliminary tests for standard L2 distance metric demonstrate numerical stability, topological changes and an absence of any oscillatory motion.}, author = {Boykov, Yuri and Vladimir Kolmogorov and Cremers, Daniel and Delong, Andrew}, pages = {409 -- 422}, publisher = {Springer}, title = {{An integral solution to surface evolution PDEs via geo cuts}}, doi = {10.1007/11744078_32}, volume = {3953}, year = {2006}, } @inproceedings{3188, abstract = {We introduce the term cosegmentation which denotes the task of segmenting simultaneously the common parts of an image pair. A generative model for cosegmentation is presented. Inference in the model leads to minimizing an energy with an MRF term encoding spatial coherency and a global constraint which attempts to match the appearance histograms of the common parts. This energy has not been proposed previously and its optimization is challenging and NP-hard. For this problem a novel optimization scheme which we call trust region graph cuts is presented. We demonstrate that this framework has the potential to improve a wide range of research: Object driven image retrieval, video tracking and segmentation, and interactive image editing. The power of the framework lies in its generality, the common part can be a rigid/non-rigid object (or scene), observed from different viewpoints or even similar objects of the same class.}, author = {Rother, Carsten and Vladimir Kolmogorov and Minka, Thomas P and Blake, Andrew}, pages = {993 -- 1000}, publisher = {IEEE}, title = {{Cosegmentation of image pairs by histogram matching - Incorporating a global constraint into MRFs}}, doi = {10.1109/CVPR.2006.91}, year = {2006}, } @inproceedings{3189, abstract = {This paper presents an algorithm capable of real-time separation of foreground from background in monocular video sequences. Automatic segmentation of layers from colour/contrast or from motion alone is known to be error-prone. Here motion, colour and contrast cues are probabilistically fused together with spatial and temporal priors to infer layers accurately and efficiently. Central to our algorithm is the fact that pixel velocities are not needed, thus removing the need for optical flow estimation, with its tendency to error and computational expense. Instead, an efficient motion vs non-motion classifier is trained to operate directly and jointly on intensity-change and contrast. Its output is then fused with colour information. The prior on segmentation is represented by a second order, temporal, Hidden Markov Model, together with a spatial MRF favouring coherence except where contrast is high. Finally, accurate layer segmentation and explicit occlusion detection are efficiently achieved by binary graph cut. The segmentation accuracy of the proposed algorithm is quantitatively evaluated with respect to existing ground-truth data and found to be comparable to the accuracy of a state of the art stereo segmentation algorithm. Fore-ground/background segmentation is demonstrated in the application of live background substitution and shown to generate convincingly good quality composite video.}, author = {Criminisi, Antonio and Cross, Geoffrey and Blake, Andrew and Vladimir Kolmogorov}, pages = {53 -- 60}, publisher = {IEEE}, title = {{Bilayer segmentation of live video}}, doi = {10.1109/CVPR.2006.69}, volume = {1}, year = {2006}, } @article{3190, abstract = {Algorithms for discrete energy minimization are of fundamental importance in computer vision. In this paper, we focus on the recent technique proposed by Wainwright et al. (Nov. 2005)- tree-reweighted max-product message passing (TRW). It was inspired by the problem of maximizing a lower bound on the energy. However, the algorithm is not guaranteed to increase this bound - it may actually go down. In addition, TRW does not always converge. We develop a modification of this algorithm which we call sequential tree-reweighted message passing. Its main property is that the bound is guaranteed not to decrease. We also give a weak tree agreement condition which characterizes local maxima of the bound with respect to TRW algorithms. We prove that our algorithm has a limit point that achieves weak tree agreement. Finally, we show that, our algorithm requires half as much memory as traditional message passing approaches. Experimental results demonstrate that on certain synthetic and real problems, our algorithm outperforms both the ordinary belief propagation and tree-reweighted algorithm in (M. J. Wainwright, et al., Nov. 2005). In addition, on stereo problems with Potts interactions, we obtain a lower energy than graph cuts.}, author = {Vladimir Kolmogorov}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {10}, pages = {1568 -- 1583}, publisher = {IEEE}, title = {{Convergent tree reweighted message passing for energy minimization}}, doi = {10.1109/TPAMI.2006.200}, volume = {28}, year = {2006}, } @inproceedings{3214, abstract = {The Feistel-network is a popular structure underlying many block-ciphers where the cipher is constructed from many simpler rounds, each defined by some function which is derived from the secret key. Luby and Rackoff showed that the three-round Feistel-network – each round instantiated with a pseudorandom function secure against adaptive chosen plaintext attacks (CPA) – is a CPA secure pseudorandom permutation, thus giving some confidence in the soundness of using a Feistel-network to design block-ciphers. But the round functions used in actual block-ciphers are – for efficiency reasons – far from being pseudorandom. We investigate the security of the Feistel-network against CPA distinguishers when the only security guarantee we have for the round functions is that they are secure against non-adaptive chosen plaintext attacks (nCPA). We show that in the information-theoretic setting, four rounds with nCPA secure round functions are sufficient (and necessary) to get a CPA secure permutation. Unfortunately, this result does not translate into the more interesting pseudorandom setting. In fact, under the so-called Inverse Decisional Diffie-Hellman assumption the Feistel-network with four rounds, each instantiated with a nCPA secure pseudorandom function, is in general not a CPA secure pseudorandom permutation.}, author = {Maurer, Ueli M and Oswald, Yvonne A and Krzysztof Pietrzak and Sjödin, Johan}, pages = {391 -- 408}, publisher = {Springer}, title = {{Luby Rackoff ciphers from weak round functions }}, doi = {10.1007/11761679_24}, volume = {4004}, year = {2006}, } @inproceedings{3215, abstract = {Most cryptographic primitives such as encryption, authentication or secret sharing require randomness. Usually one assumes that perfect randomness is available, but those primitives might also be realized under weaker assumptions. In this work we continue the study of building secure cryptographic primitives from imperfect random sources initiated by Dodis and Spencer (FOCS’02). Their main result shows that there exists a (high-entropy) source of randomness allowing for perfect encryption of a bit, and yet from which one cannot extract even a single weakly random bit, separating encryption from extraction. Our main result separates encryption from 2-out-2 secret sharing (both in the information-theoretic and in the computational settings): any source which can be used to achieve one-bit encryption also can be used for 2-out-2 secret sharing of one bit, but the converse is false, even for high-entropy sources. Therefore, possibility of extraction strictly implies encryption, which in turn strictly implies 2-out-2 secret sharing.}, author = {Dodis, Yevgeniy and Krzysztof Pietrzak and Przydatek, Bartosz}, pages = {601 -- 616}, publisher = {Springer}, title = {{Separating sources for encryption and secret sharing}}, doi = {10.1007/11681878_31}, volume = {3876}, year = {2006}, }