Browsing by Author "Murthy, S."

Filter results by typing the first few letters
Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Integer polynomial recovery from outputs and its application to cryptanalysis of a protocol for secure sorting
    (De Gruyter Open Ltd, 2022) Vivek, S.; Murthy, S.; Kumaraswamy, D.
    We investigate the problem of recovering integer inputs (up to an affine scaling) when given only the integer monotonic polynomial outputs. Given n integer outputs of a degree-d integer monotonic polynomial whose coefficients and inputs are integers within known bounds and n ≫ d, we give an algorithm to recover the polynomial and the integer inputs (up to an affine scaling). A heuristic expected time complexity analysis of our method shows that it is exponential in the size of the degree of the polynomial but polynomial in the size of the polynomial coefficients. We conduct experiments with real-world data as well as randomly chosen parameters and demonstrate the effectiveness of our algorithm over a wide range of parameters. Using only the polynomial evaluations at specific integer points, the apparent hardness of recovering the input data served as the basis of security of a recent protocol proposed by Kesarwani et al. for secure k-nearest neighbor computation on encrypted data that involved secure sorting. The protocol uses the outputs of randomly chosen monotonic integer polynomial to hide its inputs except to only reveal the ordering of input data. By using our integer polynomial recovery algorithm, we show that we can recover the polynomial and the inputs within a few seconds, thereby demonstrating an attack on the protocol of Kesarwani et al. © 2022 Srinivas Vivek et al.
  • No Thumbnail Available
    Item
    Revisiting Driver Anonymity in ORide
    (Springer Science and Business Media Deutschland GmbH, 2022) Kumaraswamy, D.; Murthy, S.; Vivek, S.
    Ride Hailing Services (RHS) have become a popular means of transportation, and with its popularity comes the concerns of privacy of riders and drivers. ORide is a privacy-preserving RHS proposed at the USENIX Security Symposium 2017 and uses Somewhat Homomorphic Encryption (SHE). In their protocol, a rider and all drivers in a zone send their encrypted coordinates to the RHS Service Provider (SP) who computes the squared Euclidean distances between them and forwards them to the rider. The rider decrypts these and selects the optimal driver with least Euclidean distance. In this work, we demonstrate a location-harvesting attack where an honest-but-curious rider, making only a single ride request, can determine the exact coordinates of about half the number of responding drivers even when only the distance between the rider and drivers are given. The significance of our attack lies in inferring locations of other drivers in the zone, which are not (supposed to be) revealed to the rider as per the protocol. We validate our attack by running experiments on zones of varying sizes in arbitrarily selected big cities. Our attack is based on enumerating lattice points on a circle of sufficiently small radius and eliminating solutions based on conditions imposed by the application scenario. Finally, we propose a modification to ORide aimed at thwarting our attack and show that this modification provides sufficient driver anonymity while preserving ride matching accuracy. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.