@inproceedings{18344, abstract = {Analysis of intrinsic symmetries of non-rigid and articulated shapes is an important problem in pattern recognition with numerous applications ranging from medicine to computational aesthetics. Considering articulated planar shapes as closed curves, we show how to represent their extrinsic and intrinsic symmetries as self-similarities of local descriptor sequences, which in turn have simple interpretation in the frequency domain. The problem of symmetry detection and analysis thus boils down to analysis of descriptor sequence patterns. For that purpose, we show two efficient computational methods: one based on Fourier analysis, and another on dynamic programming.}, author = {Hooda, Amit and Bronstein, Michael M. and Bronstein, Alexander and Horaud, Radu P.}, booktitle = {Scale Space and Variational Methods in Computer Vision}, isbn = {9783642247842}, issn = {1611-3349}, location = {Ein-Gedi, Israel}, pages = {665–676}, publisher = {Springer Nature}, title = {{Shape palindromes: Analysis of intrinsic symmetries in 2D articulated shapes}}, doi = {10.1007/978-3-642-24785-9_56}, volume = {6667}, year = {2012}, } @inproceedings{18345, abstract = {In classical signal processing, it is common to analyze and process signals in the frequency domain, by representing the signal in the Fourier basis, and filtering it by applying a transfer function on the Fourier coefficients. In some applications, it is possible to design an optimal filter. A classical example is the Wiener filter that achieves a minimum mean squared error estimate for signal denoising. Here, we adopt similar concepts to construct optimal diffusion geometric shape descriptors. The analogy of Fourier basis are the eigenfunctions of the Laplace-Beltrami operator, in which many geometric constructions such as diffusion metrics, can be represented. By designing a filter of the Laplace-Beltrami eigenvalues, it is theoretically possible to achieve invariance to different shape transformations, like scaling. Given a set of shape classes with different transformations, we learn the optimal filter by minimizing the ratio between knowingly similar and knowingly dissimilar diffusion distances it induces. The output of the proposed framework is a filter that is optimally tuned to handle transformations that characterize the training set.}, author = {Aflalo, Yonathan and Bronstein, Alexander and Bronstein, Michael M. and Kimmel, Ron}, booktitle = {3rd International Conference on Scale Space and Variational Methods in Computer Vision}, isbn = {9783642247842}, issn = {1611-3349}, location = {Ein-Gedi, Israel}, pages = {689--700}, publisher = {Springer Nature}, title = {{Deformable shape retrieval by learning diffusion kernels}}, doi = {10.1007/978-3-642-24785-9_58}, volume = {6667}, year = {2012}, } @inproceedings{18346, abstract = {Understanding of articulated shape motion plays an important role in many applications in the mechanical engineering, movie industry, graphics, and vision communities. In this paper, we study motion-based segmentation of articulated 3D shapes into rigid parts. We pose the problem as finding a group-valued map between the shapes describing the motion, forcing it to favor piecewise rigid motions. Our computation follows the spirit of the Ambrosio-Tortorelli scheme for Mumford-Shah segmentation, with a diffusion component suited for the group nature of the motion model. Experimental results demonstrate the effectiveness of the proposed method in non-rigid motion segmentation.}, author = {Rosman, Guy and Bronstein, Michael M. and Bronstein, Alexander and Wolf, Alon and Kimmel, Ron}, booktitle = {3rd International Conference on Scale Space and Variational Methods in Computer Vision}, isbn = {9783642247842}, issn = {1611-3349}, location = {Ein-Gedi, Israel}, pages = {725--736}, publisher = {Springer Nature}, title = {{Group-valued regularization framework for motion segmentation of dynamic non-rigid shapes}}, doi = {10.1007/978-3-642-24785-9_61}, volume = {6667}, year = {2012}, } @inproceedings{18347, abstract = {Multi-part shape matching is an important class of problems, arising in many fields such as computational archaeology, biology, geometry processing, computer graphics and vision. In this paper, we address the problem of simultaneous matching and segmentation of multiple shapes. We assume to be given a reference shape and multiple parts partially matching the reference. Each of these parts can have additional clutter, have overlap with other parts, or there might be missing parts. We show experimental results of efficient and accurate assembly of fractured synthetic and real objects.}, author = {Litany, Or and Bronstein, Alexander and Bronstein, Michael M.}, booktitle = {Computer Vision, ECCV 2012 - Workshops and Demonstrations}, isbn = {9783642338625}, issn = {1611-3349}, location = {Florence, Italy}, number = {Part 1}, pages = {1--11}, publisher = {Springer Nature}, title = {{Putting the pieces together: Regularized multi-part shape matching}}, doi = {10.1007/978-3-642-33863-2_1}, volume = {7583}, year = {2012}, } @inproceedings{18348, abstract = {We present a novel method for estimation of articulated motion in depth scans. The method is based on a framework for regularization of vector- and matrix- valued functions on parametric surfaces. We extend augmented-Lagrangian total variation regularization to smooth rigid motion cues on the scanned 3D surface obtained from a range scanner. We demonstrate the resulting smoothed motion maps to be a powerful tool in articulated scene understanding, providing a basis for rigid parts segmentation, with little prior assumptions on the scene, despite the noisy depth measurements that often appear in commodity depth scanners.}, author = {Rosman, Guy and Bronstein, Alexander and Bronstein, Michael M. and Tai, Xue-Cheng and Kimmel, Ron}, booktitle = {Computer Vision, ECCV 2012 - Workshops and Demonstrations}, isbn = {9783642338625}, issn = {1611-3349}, location = {Florence, Italy}, number = {Part 1}, pages = {52--62}, publisher = {Springer Nature}, title = {{Group-valued regularization for analysis of articulated motion}}, doi = {10.1007/978-3-642-33863-2_6}, volume = {7583}, year = {2012}, } @inproceedings{18349, abstract = {The rapid development of 3D acquisition technology has brought with itself the need to perform standard signal processing operations such as filters on 3D data. It has been shown that the eigenfunctions of the Laplace-Beltrami operator (manifold harmonics) of a surface play the role of the Fourier basis in the Euclidean space; it is thus possible to formulate signal analysis and synthesis in the manifold harmonics basis. In particular, geometry filtering can be carried out in the manifold harmonics domain by decomposing the embedding coordinates of the shape in this basis. However, since the basis functions depend on the shape itself, such filtering is valid only for weak (near all-pass) filters, and produces severe artifacts otherwise. In this paper, we analyze this problem and propose the fractional filtering approach, wherein we apply iteratively weak fractional powers of the filter, followed by the update of the basis functions. Experimental results show that such a process produces more plausible and meaningful results.}, author = {Kovnatsky, Artiom and Bronstein, Michael M. and Bronstein, Alexander}, booktitle = {Computer Vision, ECCV 2012 - Workshops and Demonstrations}, isbn = {9783642338625}, issn = {0302-9743}, location = {Florence, Italy}, number = {Part 1}, pages = {83--91}, publisher = {Springer Nature}, title = {{Stable Spectral Mesh Filtering}}, doi = {10.1007/978-3-642-33863-2_9}, volume = {7583}, year = {2012}, } @inproceedings{18350, abstract = {We introduce an (equi-)affine invariant geometric structure by which surfaces that go through squeeze and shear transformations can still be properly analyzed. The definition of an affine invariant metric enables us to evaluate a new form of geodesic distances and to construct an invariant Laplacian from which local and global diffusion geometry is constructed. Applications of the proposed framework demonstrate its power in generalizing and enriching the existing set of tools for shape analysis.}, author = {Raviv, Dan and Bronstein, Alexander and Bronstein, Michael M. and Kimmel, Ron and Sochen, Nir}, booktitle = {15th International Workshop on Theoretical Foundations of Computer Vision}, isbn = {9783642340901}, issn = {1611-3349}, location = {Dagstuhl, Germany}, pages = {177--190}, publisher = {Springer Nature}, title = {{Equi-affine invariant geometries of articulated objects}}, doi = {10.1007/978-3-642-34091-8_8}, volume = {7474}, year = {2012}, } @article{18364, abstract = {Region feature detectors and descriptors have become a successful and popular alternative to point descriptors in image analysis due to their high robustness and repeatability, leading to a significant interest in the shape analysis community in finding analogous approaches in the 3D world. Recent works have successfully extended the maximally stable extremal region (MSER) detection algorithm to surfaces. In many applications, however, a volumetric shape model is more appropriate, and modeling shape deformations as approximate isometries of the volume of an object, rather than its boundary, better captures natural behavior of non-rigid deformations. In this paper, we formulate a diffusion-geometric framework for volumetric stable component detection and description in deformable shapes. An evaluation of our method on the SHREC'11 feature detection benchmark and SCAPE human body scans shows its potential as a source of high-quality features. Examples demonstrating the drawbacks of surface stable components and the advantage of their volumetric counterparts are also presented.}, author = {Litman, R. and Bronstein, Alexander and Bronstein, M.M.}, issn = {0097-8493}, journal = {Computers & Graphics}, number = {5}, pages = {569--576}, publisher = {Elsevier}, title = {{Stable volumetric features in deformable shapes}}, doi = {10.1016/j.cag.2012.03.034}, volume = {36}, year = {2012}, } @inproceedings{18378, abstract = {In this work, we present intrinsic shape context (ISC) descriptors for 3D shapes. We generalize to surfaces the polar sampling of the image domain used in shape contexts: for this purpose, we chart the surface by shooting geodesic outwards from the point being analyzed; `angle' is treated as tantamount to geodesic shooting direction, and radius as geodesic distance. To deal with orientation ambiguity, we exploit properties of the Fourier transform. Our charting method is intrinsic, i.e., invariant to isometric shape transformations. The resulting descriptor is a meta-descriptor that can be applied to any photometric or geometric property field defined on the shape, in particular, we can leverage recent developments in intrinsic shape analysis and construct ISC based on state-of-the-art dense shape descriptors such as heat kernel signatures. Our experiments demonstrate a notable improvement in shape matching on standard benchmarks.}, author = {Kokkinos, I. and Bronstein, M. M. and Litman, R. and Bronstein, Alexander}, booktitle = {2012 IEEE Conference on Computer Vision and Pattern Recognition}, isbn = {9781467312264}, issn = {1063-6919}, location = {Providence, RI, United States}, publisher = {IEEE}, title = {{Intrinsic shape context descriptors for deformable shapes}}, doi = {10.1109/cvpr.2012.6247671}, year = {2012}, } @inproceedings{18379, abstract = {We consider the problem of minimum distortion intrinsic correspondence between deformable shapes, many useful formulations of which give rise to the NP-hard quadratic assignment problem (QAP). Previous attempts to use the spectral relaxation have had limited success due to the lack of sparsity of the obtained “fuzzy” solution. In this paper, we adopt the recently introduced alternative L 1 relaxation of the QAP based on the principles of game theory. We relate it to the Gromov and Lipschitz metrics between metric spaces and demonstrate on state-of-the-art benchmarks that the proposed approach is capable of finding very accurate sparse correspondences between deformable shapes.}, author = {Rodola, E. and Bronstein, Alexander and Albarelli, A. and Bergamasco, F. and Torsello, A.}, booktitle = {2012 IEEE Conference on Computer Vision and Pattern Recognition}, isbn = {978-1-4673-1226-4}, issn = {1063-6919}, location = {Providence, RI, United States}, publisher = {IEEE}, title = {{A game-theoretic approach to deformable shape matching}}, doi = {10.1109/cvpr.2012.6247674}, year = {2012}, } @article{18412, abstract = {SIFT-like local feature descriptors are ubiquitously employed in computer vision applications such as content-based retrieval, video analysis, copy detection, object recognition, photo tourism, and 3D reconstruction. Feature descriptors can be designed to be invariant to certain classes of photometric and geometric transformations, in particular, affine and intensity scale transformations. However, real transformations that an image can undergo can only be approximately modeled in this way, and thus most descriptors are only approximately invariant in practice. Second, descriptors are usually high dimensional (e.g., SIFT is represented as a 128--dimensional vector). In large-scale retrieval and matching problems, this can pose challenges in storing and retrieving descriptor data. We map the descriptor vectors into the Hamming space in which the Hamming metric is used to compare the resulting representations. This way, we reduce the size of the descriptors by representing them as short binary strings and learn descriptor invariance from examples. We show extensive experimental validation, demonstrating the advantage of the proposed approach.}, author = {Strecha, C. and Bronstein, Alexander and Bronstein, M. M. and Fua, P.}, issn = {2160-9292}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {1}, pages = {66--78}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{LDAHash: Improved matching with smaller descriptors}}, doi = {10.1109/tpami.2011.103}, volume = {34}, year = {2012}, } @inbook{18737, abstract = {Supermassive black holes (SMBHs) are common in local galactic nuclei, and SMBHs as massive as several billion solar masses already exist at redshift z = 6. These earliest SMBHs may grow by the combination of radiation-pressure-limited accretion and mergers of stellar-mass seed BHs, left behind by the first generation of metal-free stars, or may be formed by more rapid direct collapse of gas in rare special environments where dense gas can accumulate without first fragmenting into stars. This chapter offers a review of these two competing scenarios, as well as some more exotic alternative ideas. It also briefly discusses how the different models may be distinguished in the future by observations with JWST, LISA and other instruments.}, author = {Haiman, Zoltán}, booktitle = {The First Galaxies}, editor = {Wiklind, Tommy and Mobasher, Bahram and Brumm, Volker}, isbn = {9783642323614}, issn = {2214-7985}, pages = {293--341}, publisher = {Springer Berlin Heidelberg}, title = {{The Formation of the First Massive Black Holes}}, doi = {10.1007/978-3-642-32362-1_6}, year = {2012}, } @article{12644, abstract = {In the Dry Andes of central Chile, summer water resources originate mostly from snowmelt and ice melt. We use the physically based, spatially distributed hydrological model TOPKAPI to study the exchange between glaciers and climate in the upper Aconcagua River Basin during the summer season and identify the model parameters that are robust and transferable and those that are more dependent on calibration. TOPKAPI has recently been adapted to incorporate an enhanced temperature index approach for snow and ice melting. We suggest a calibration procedure that allows calibration of parameters in three steps by separating parameters governing distinct processes. We evaluate the parameters' transferability in time and in space by applying the model at two spatial scales. TOPKAPI's ability to simulate the relevant processes is tested against meteorological, ablation, and glacier runoff data measured on Juncal Norte Glacier during two glacier ablation seasons. The model was applied successfully to the climatic setting of the Dry Andes once its parameters were recalibrated. We found a clear distinction between parameters that are stable in time and those that need recalibration. The parameters of the melt model are transferable from one season to the other, while the parameters governing the extrapolation of meteorological input data and the routing of glacier meltwater need recalibration from one season to the other. Sensitivity analysis revealed that the model is most sensitive to the temperature lapse rate governing the extrapolation of air temperature from point measurements to the glacier scale and to the melt parameter that multiplies the shortwave radiation balance.}, author = {Ragettli, S. and Pellicciotti, Francesca}, issn = {0043-1397}, journal = {Water Resources Research}, number = {3}, publisher = {American Geophysical Union}, title = {{Calibration of a physically based, spatially distributed hydrological model in a glacierized basin: On the use of knowledge from glaciometeorological processes to constrain model parameters}}, doi = {10.1029/2011wr010559}, volume = {48}, year = {2012}, } @article{12646, abstract = {Assessment of water resources from remote mountainous catchments plays a crucial role for the development of rural areas in or in the vicinity of mountain ranges. The scarcity of data, however, prevents the application of standard approaches that are based on data-driven models. The Hindu Kush–Karakoram–Himalaya mountain range is a crucial area in terms of water resources, but our understanding of the response of its high-elevation catchments to a changing climate is hindered by lack of hydro-meteorological and cryospheric data. Hydrological modeling is challenging here because internal inconsistencies—such as an underestimation of precipitation input that can be compensated for by an overestimation of meltwater—might be hidden due to the complexity of feedback mechanisms that govern melt and runoff generation in such basins. Data scarcity adds to this difficulty by preventing the application of systematic calibration procedures that would allow identification of the parameter set that could guarantee internal consistency in the simulation of the single hydrological components. In this work, we use simulations from the Hunza River Basin in the Karakoram region obtained with the hydrological model TOPKAPI to quantify the predictive power of discharge and snow-cover data sets, as well as the combination of both. We also show that short-term measurements of meteorological variables such as radiative fluxes, wind speed, relative humidity, and air temperature from glacio-meteorological experiments are crucial for a correct parameterization of surface melt processes. They enable detailed simulations of the energy fluxes governing glacier–atmosphere interaction and the resulting ablation through energy-balance modeling. These simulations are used to derive calibrated parameters for the simplified snow and glacier routines in TOPKAPI. We demonstrate that such parameters are stable in space and time in similar climatic regions, thus reducing the number of parameters requiring calibration.}, author = {Pellicciotti, Francesca and Buergi, Cyrill and Immerzeel, Walter Willem and Konz, Markus and Shrestha, Arun B.}, issn = {1994-7151}, journal = {Mountain Research and Development}, number = {1}, pages = {39--50}, publisher = {International Mountain Society}, title = {{Challenges and uncertainties in hydrological modeling of remote Hindu Kush–Karakoram–Himalayan (HKH) basins: Suggestions for calibration strategies}}, doi = {10.1659/mrd-journal-d-11-00092.1}, volume = {32}, year = {2012}, } @article{12647, abstract = {Accurate quantification of the spatial distribution of precipitation in mountain regions is crucial for assessments of water resources and for the understanding of high-altitude hydrology, yet it is one of the largest unknowns due to the lack of high-altitude observations. The Hunza basin in Pakistan contains very large glacier systems, which, given the melt, cannot persist unless precipitation (snow input) is much higher than what is observed at the meteorological stations, mostly located in mountain valleys. Several studies, therefore, suggest strong positive vertical precipitation lapse rates; in the present study, we quantify this lapse rate by using glaciers as a proxy. We assume a neutral mass balance for the glaciers for the period from 2001 to 2003, and we inversely model the precipitation lapse by balancing the total accumulation in the catchment area and the ablation over the glacier area for the 50 largest glacier systems in the Hunza basin in the Karakoram. Our results reveal a vertical precipitation lapse rate that equals 0.21 ± 0.12% m−1, with a maximum precipitation at an elevation of 5500 masl. We showed that the total annual basin precipitation (828 mm) is 260% higher than what is estimated based on interpolated observations (319 mm); this has major consequences for hydrological modeling and water resource assessments in general. Our results were validated by using previously published studies on individual glaciers as well as the water balance of the Hunza basin. The approach is more widely applicable in mountain ranges where precipitation measurements at high altitude are lacking.}, author = {Immerzeel, Walter Willem and Pellicciotti, Francesca and Shrestha, Arun B.}, issn = {1994-7151}, journal = {Mountain Research and Development}, keywords = {General Environmental Science, Development, Environmental Chemistry}, number = {1}, pages = {30--38}, publisher = {International Mountain Society}, title = {{Glaciers as a proxy to quantify the spatial distribution of precipitation in the Hunza basin}}, doi = {10.1659/mrd-journal-d-11-00097.1}, volume = {32}, year = {2012}, } @article{12648, abstract = {Distributed glacier melt models generally assume that the glacier surface consists of bare exposed ice and snow. In reality, many glaciers are wholly or partially covered in layers of debris that tend to suppress ablation rates. In this paper, an existing physically based point model for the ablation of debris-covered ice is incorporated in a distributed melt model and applied to Haut Glacier d'Arolla, Switzerland, which has three large patches of debris cover on its surface. The model is based on a 10 m resolution digital elevation model (DEM) of the area; each glacier pixel in the DEM is defined as either bare or debris-covered ice, and may be covered in snow that must be melted off before ice ablation is assumed to occur. Each debris-covered pixel is assigned a debris thickness value using probability distributions based on over 1000 manual thickness measurements. Locally observed meteorological data are used to run energy balance calculations in every pixel, using an approach suitable for snow, bare ice or debris-covered ice as appropriate. The use of the debris model significantly reduces the total ablation in the debris-covered areas, however the precise reduction is sensitive to the temperature extrapolation used in the model distribution because air near the debris surface tends to be slightly warmer than over bare ice. Overall results suggest that the debris patches, which cover 10% of the glacierized area, reduce total runoff from the glacierized part of the basin by up to 7%.}, author = {Reid, T. D. and Carenzo, M. and Pellicciotti, Francesca and Brock, B. W.}, issn = {0148-0227}, journal = {Journal of Geophysical Research: Atmospheres}, keywords = {Paleontology, Space and Planetary Science, Earth and Planetary Sciences (miscellaneous), Atmospheric Science, Earth-Surface Processes, Geochemistry and Petrology, Soil Science, Water Science and Technology, Ecology, Aquatic Science, Forestry, Oceanography, Geophysics}, number = {D18}, publisher = {American Geophysical Union}, title = {{Including debris cover effects in a distributed model of glacier ablation}}, doi = {10.1029/2012jd017795}, volume = {117}, year = {2012}, } @misc{13075, abstract = {Little is known about the stability of trophic relationships in complex natural communities over evolutionary timescales. Here, we use sequence data from 18 nuclear loci to reconstruct and compare the intraspecific histories of major Pleistocene refugial populations in the Middle East, the Balkans and Iberia in a guild of four Chalcid parasitoids (Cecidostiba fungosa, C. semifascia, Hobbya stenonota and Mesopolobus amaenus) all attacking Cynipid oak galls. We develop a likelihood method to numerically estimate models of divergence between three populations from multilocus data. We investigate the power of this framework on simulated data, and - using triplet alignments of intronic loci - quantify the support for all possible divergence relationships between refugial populations in the four parasitoids. Although an East to West order of population divergence has highest support in all but one species, we cannot rule out alternative population tree topologies. Comparing the estimated times of population splits between species, we find that one species, M. amaenus, has a significantly older history than the rest of the guild and must have arrived in central Europe at least one glacial cycle prior to other guild members. This suggests that although all four species may share a common origin in the East, they expanded westwards into Europe at different times.}, author = {Lohse, Konrad and Barton, Nicholas H and Stone, Graham and Melika, George}, publisher = {Dryad}, title = {{Data from: A likelihood-based comparison of population histories in a parasitoid guild}}, doi = {10.5061/DRYAD.0G0FS}, year = {2012}, } @article{1987, abstract = {In the living cell, proteins are able to organize space much larger than their dimensions. In return, changes of intracellular space can influence biochemical reactions, allowing cells to sense their size and shape. Despite the possibility to reconstitute protein self-organization with only a few purified components, we still lack knowledge of how geometrical boundaries affect spatiotemporal protein patterns. Following a minimal systems approach, we used purified proteins and photolithographically patterned membranes to study the influence of spatial confinement on the self-organization of the Min system, a spatial regulator of bacterial cytokinesis, in vitro. We found that the emerging protein pattern responds even to the lateral, two-dimensional geometry of the membrane such that, as in the three-dimensional cell, Min protein waves travel along the longest axis of the membrane patch. This shows that for spatial sensing the Min system does not need to be enclosed in a three-dimensional compartment. Using a computational model we quantitatively analyzed our experimental findings and identified persistent binding of MinE to the membrane as requirement for the Min system to sense geometry. Our results give insight into the interplay between geometrical confinement and biochemical patterns emerging from a nonlinear reaction-diffusion system. }, author = {Schweizer, Jakob and Martin Loose and Bonny, Mike and Kruse, Karsten and Mönch, Ingolf and Schwille, Petra }, journal = {PNAS}, number = {38}, pages = {15283 -- 15288}, publisher = {National Academy of Sciences}, title = {{Geometry sensing by self-organized protein patterns}}, doi = {10.1073/pnas.1206953109}, volume = {109}, year = {2012}, } @inproceedings{2048, abstract = {Leakage resilient cryptography attempts to incorporate side-channel leakage into the black-box security model and designs cryptographic schemes that are provably secure within it. Informally, a scheme is leakage-resilient if it remains secure even if an adversary learns a bounded amount of arbitrary information about the schemes internal state. Unfortunately, most leakage resilient schemes are unnecessarily complicated in order to achieve strong provable security guarantees. As advocated by Yu et al. [CCS’10], this mostly is an artefact of the security proof and in practice much simpler construction may already suffice to protect against realistic side-channel attacks. In this paper, we show that indeed for simpler constructions leakage-resilience can be obtained when we aim for relaxed security notions where the leakage-functions and/or the inputs to the primitive are chosen non-adaptively. For example, we show that a three round Feistel network instantiated with a leakage resilient PRF yields a leakage resilient PRP if the inputs are chosen non-adaptively (This complements the result of Dodis and Pietrzak [CRYPTO’10] who show that if a adaptive queries are allowed, a superlogarithmic number of rounds is necessary.) We also show that a minor variation of the classical GGM construction gives a leakage resilient PRF if both, the leakage-function and the inputs, are chosen non-adaptively.}, author = {Faust, Sebastian and Pietrzak, Krzysztof Z and Schipper, Joachim}, booktitle = { Conference proceedings CHES 2012}, location = {Leuven, Belgium}, pages = {213 -- 232}, publisher = {Springer}, title = {{Practical leakage-resilient symmetric cryptography}}, doi = {10.1007/978-3-642-33027-8_13}, volume = {7428}, year = {2012}, } @inproceedings{2049, abstract = {We propose a new authentication protocol that is provably secure based on a ring variant of the learning parity with noise (LPN) problem. The protocol follows the design principle of the LPN-based protocol from Eurocrypt’11 (Kiltz et al.), and like it, is a two round protocol secure against active attacks. Moreover, our protocol has small communication complexity and a very small footprint which makes it applicable in scenarios that involve low-cost, resource-constrained devices. Performance-wise, our protocol is more efficient than previous LPN-based schemes, such as the many variants of the Hopper-Blum (HB) protocol and the aforementioned protocol from Eurocrypt’11. Our implementation results show that it is even comparable to the standard challenge-and-response protocols based on the AES block-cipher. Our basic protocol is roughly 20 times slower than AES, but with the advantage of having 10 times smaller code size. Furthermore, if a few hundred bytes of non-volatile memory are available to allow the storage of some off-line pre-computations, then the online phase of our protocols is only twice as slow as AES. }, author = {Heyse, Stefan and Kiltz, Eike and Lyubashevsky, Vadim and Paar, Christof and Pietrzak, Krzysztof Z}, booktitle = { Conference proceedings FSE 2012}, location = {Washington, DC, USA}, pages = {346 -- 365}, publisher = {Springer}, title = {{Lapin: An efficient authentication protocol based on ring-LPN}}, doi = {10.1007/978-3-642-34047-5_20}, volume = {7549}, year = {2012}, }