Some embodiments are directed to a requesting device and a data device configured for multi-party computation to select a close record from a database. The data device performs a filtering of its candidate records by selecting candidate records from the database for which a received set of similarity values for a target record are close to a set of similarity values for a candidate record. For one or more selected candidate records, the requesting device and the data device performing a multiparty computation protocol to jointly compute a second closeness measure between the target record and the selected candidate record.