Research Outputs
Permanent URI for this communityhttps://hdl.handle.net/20.500.14288/2
Browse
7 results
Search Results
Publication Metadata only An efficient 2-party private function evaluation protocol based on half gates(Oxford Univ Press, 2019) Bingol, Muhammed Ali; Kiraz, Mehmet Sabir; Levi, Albert; N/A; Biçer, Osman; PhD Student; Graduate School of Sciences and Engineering; N/APrivate function evaluation (PFE) is a special case of secure multi-party computation (MPC), where the function to be computed is known by only one party. PFE is useful in several real-life applications where an algorithm or a function itself needs to remain secret for reasons such as protecting intellectual property or security classification level. In this paper, we focus on improving 2-party PFE based on symmetric cryptographic primitives. In this respect, we look back at the seminal PFE framework presented by Mohassel and Sadeghian at Eurocrypt'13. We show how to adapt and utilize the well-known half gates garbling technique (Zahur et al., Eurocrypt'15) to their constant-round 2-party PFE scheme. Compared to their scheme, our resulting optimization significantly improves the efficiency of both the underlying Oblivious Evaluation of Extended Permutation (OEP) and secure 2-party computation (2PC) protocols, and yields a more than 40% reduction in overall communication cost (the computation time is also slightly decreased and the number of rounds remains unchanged).Publication Metadata only BindMe: a thread binding library with advanced mapping algorithms(Wiley, 2018) N/A; Department of Computer Engineering; Department of Computer Engineering; Soomro, Pirah Noor; Sasongko, Muhammad Aditya; Erten, Didem Unat; PhD Student; Researcher; Faculty Member; Department of Computer Engineering; Graduate School of Sciences and Engineering; College of Engineering; College of Engineering; N/A; N/A; 219274Binding parallel tasks to cores according to a placement policy is one of the key aspects to achieve good performance in multicore machines because it can reduce on-chip communication among parallel threads. Binding also prevents operating system from migrating threads, which improves data locality. However, there is no single mapping policy that works best among all different kinds of applications and platforms because each machine has a different topology and each application exhibits different communication pattern. Determining the best policy for a given application and machine requires extra programming effort. To relieve the programmer from that burden, we introduce BindMe, A thread binding library that assists programmer to bind threads to underlying hardware. BindMe incorporates state-of-the-art mapping algorithms, which use communication pattern in an application to formulate an efficient task placement policy. We also introduce ChoiceMap, A communication aware mapping algorithm that respects mutual priorities of parallel tasks and performs a fair mapping by reducing communication volume among cores. We have tested BindMe and ChoiceMap with various applications from NaS parallel benchmark and Rodinia bechmark. Our results show that choosing a mapping policy that best suits the application behavior can increase its performance and no single policy gives the best performance across different applications.Publication Metadata only FlexDPDP: flexlist-based optimized dynamic provable data possession(assoc Computing Machinery, 2016) N/A; N/A; N/A; Department of Computer Engineering; Department of Computer Engineering; Department of Computer Engineering; Esiner, Ertem; Kachkeev, Adilet; Küpçü, Alptekin; Özkasap, Öznur; Master Student; Master Student; N/A; Faculty Member; Faculty Member; Department of Computer Engineering; Graduate School of Sciences and Engineering; Graduate School of Sciences and Engineering; Graduate School of Sciences and Engineering; College of Engineering; College of Engineering; N/A; N/A; N/A; 168060; 113507With increasing popularity of cloud storage, efficiently proving the integrity of data stored on an untrusted server has become significant. authenticated skip lists and rank-based authenticated skip lists (RBaSL) have been used to provide support for provable data update operations in cloud storage. However, in a dynamic file scenario, An RBaSL based on block indices falls short when updates are not proportional to a fixed block size; such an update to the file, even if small, may result in O(n) updates on the data structure for a file with n blocks. To overcome this problem, we introduce FlexList, A flexible length-based authenticated skip list. FlexList translates variable-size updates to O(inverted right perpendicularu/Binverted left perpendicular) insertions, removals, or modifications, where u is the size of the update and B is the (average) block size. We further present various optimizations on the four types of skip lists (regular, Authenticated, rank-based authenticated, and FlexList). We build such a structure in O(n) time and parallelize this operation for the first time. We compute one single proof to answer multiple (non) membership queries and obtain efficiency gains of 35%, 35%, and 40% in terms of proof time, energy, and size, respectively. We propose a method of handling multiple updates at once, Achieving efficiency gains of up to 60% at the server side and 90% at the client side. We also deployed our implementation of FlexDPDP (dynamic provable data possession (DPDP) with FlexList instead of RBaSL) on PlanetLab, demonstrating that FlexDPDP performs comparable to the most efficient static storage scheme (provable data possession (PDP)) while providing dynamic data support.Publication Metadata only Real-time visio-haptic interaction with static soft tissue models having geometric and material nonlinearity(Elsevier, 2010) Peterlik, Igor; Matyska, Luděk; N/A; Department of Mechanical Engineering; Sedef, Mert; Başdoğan, Çağatay; Master Student; Faculty Member; Department of Mechanical Engineering; Graduate School of Sciences and Engineering; College of Engineering; N/A; 125489Realistic soft tissue models running in real-time are required for the development of computer-based surgical training systems. To construct a realistic soft tissue model, finite element (FE) modeling techniques are preferred over the particle-based techniques since the material properties can be integrated directly into the FE model to provide more accurate visual and haptic feedback to a user during the simulations. However, running even a static (time-independent) nonlinear FE model in real-time is a highly challenging task because the resulting stiffness matrix (K) is not constant and varies with the depth of penetration into the model. We propose a new computational approach allowing visio-haptic interaction with an FE model of a human liver having both nonlinear geometric and material properties. Our computational approach consists of two main steps: a pre-computation of the configuration space of all deformation configurations of the model, followed by the interpolation of the precomputed data for the calculation of the nodal displacements and reaction forces that are displayed to the user during the real-time interactions through a visual display and a haptic device, respectively. For the implementation of the proposed approach, no a priori assumptions or modeling simplifications about the mathematical complexity of the underlying soft tissue model, size and irregularity of the FE mesh are necessary. Moreover, it turns out that the deformation and force responses of the liver in the simulations are heavily influenced by the selected simulation parameters, such as the material model, boundary conditions and loading path, but the stability of the visual and haptic rendering in our approach does not depend on these parameters. In addition to showing the stability of our approach, the length of the precomputations as well as the accuracy of the interpolation scheme are evaluated for different interpolation functions and configuration space densities.Publication Metadata only Runtime verification of concurrency-specific correctness criteria(2012) Qadeer, Shaz; Department of Computer Engineering; Taşıran, Serdar; Faculty Member; Department of Computer Engineering; College of Engineering; N/AWe give an overview of correctness criteria specific to concurrent shared-memory programs and runtime verification techniques for verifying these criteria. We cover a spectrum of criteria, from ones focusing on low-level thread interference such as races to higher-level ones such as linearizability. We contrast these criteria in the context of runtime verification. We present the key ideas underlying the runtime verification techniques for these criteria and summarize the state of the art. Finally, we discuss the issue of coverage for runtime verification for concurrency and present techniques that improve the set of covered thread interleavings.Publication Metadata only Special section on the 2011 joint symposium on computational aesthetics (CAe), non-photorealistic animation and rendering (NPAR), and sketch-based interfaces and modeling (SBIM)(Pergamon-Elsevier Science Ltd, 2012) Isenberg, Tobias; Asente, Paul; Collomosse, John; Department of Computer Engineering; Sezgin, Tevfik Metin; Faculty Member; Department of Computer Engineering; College of Engineering; 18632N/APublication Metadata only The approximability of multiple facility location on directed networks with random arc failures(Springer, 2020) Hassin, Refael; Ravi, R.; Segev, Danny; Department of Industrial Engineering; Salman, Fatma Sibel; Faculty Member; Department of Industrial Engineering; College of Engineering; 178838We introduce and study the maximum reliability coverage problem, where multiple facilities are to be located on a network whose arcs are subject to random failures. Our model assumes that arcs fail independently with non-uniform probabilities, and the objective is to locate a given number of facilities, aiming to maximize the expected demand serviced. In this context, each demand point is said to be serviced (or covered) when it is reachable from at least one facility by an operational path. The main contribution of this paper is to establish tight bounds on the approximability of maximum reliability coverage on bidirected trees as well as on general networks. Quite surprisingly, we show that this problem is NP-hard on bidirected trees via a carefully-constructed reduction from the partition problem. On the positive side, we make use of approximate dynamic programming ideas to devise an FPTAS on bidirected trees. For general networks, while maximum reliability coverage is (1-1/e+epsilon)-inapproximable as an extension of the maxk-cover problem, even estimating its objective value is #P-complete, due to generalizing certain network reliability problems. Nevertheless, we prove that by plugging-in a sampling-based additive estimator into the standard greedy algorithm, a matching approximation ratio of 1-1/e-epsilon can be attained.