PaperlayerView exact revision on arXiv

Source-linked AI summary

Drynx: Decentralized, Secure, Verifiable System for Statistical Queries and Machine Learning on Distributed Datasets

David Froelicher, Juan R. Troncoso-Pastoriza, Joao Sa Sousa, Jean-Pierre Hubaux

arXiv:1902.03785v3cs.CR

TL;DR

Sensitive data are difficult to share for statistical and machine-learning analysis while preserving privacy. Drynx uses distributed computation with cryptographic and privacy protections, and the paper concludes it supports statistics and machine-learning models on distributed datasets without individually trusted entities.

  • Problem

    Privacy concerns and legal constraints make sharing sensitive personal data difficult, despite its importance for research and analysis.

    Source: §I · p. 1

  • Method

    Drynx combines distributed computing nodes with interactive protocols, homomorphic encryption, zero-knowledge proofs, and differential privacy to execute queries and machine-learning tasks on distributed datasets.

    Source: §I · p. 1, 1) Data Confidentiality · p. 6

  • Results

    Drynx enables statistical computation and machine-learning training on distributed datasets in a strong adversarial model where no entity is individually trusted.

    Source: §X · p. 16

  • Takeaways & Limitations

    Drynx offers configurable tradeoffs among security, privacy, and efficiency for privacy-preserving computations of widely used statistics on sensitive distributed data.

    Source: §X · p. 16

    Authentication and authorization are outside the scope of the paper.

    Source: §VIII · p. 13

Abstract

from arXiv · show

Data sharing has become of primary importance in many domains such as big-data analytics, economics and medical research, but remains difficult to achieve when the data are sensitive. In fact, sharing personal information requires individuals' unconditional consent or is often simply forbidden for privacy and security reasons. In this paper, we propose Drynx, a decentralized system for privacy-conscious statistical analysis on distributed datasets. Drynx relies on a set of computing nodes to enable the computation of statistics such as standard deviation or extrema, and the training and evaluation of machine-learning models on sensitive and distributed data. To ensure data confidentiality and the privacy of the data providers, Drynx combines interactive protocols, homomorphic encryption, zero-knowledge proofs of correctness, and differential privacy. It enables an efficient and decentralized verification of the input data and of all the system's computations thus provides auditability in a strong adversarial model in which no entity has to be individually trusted. Drynx is highly modular, dynamic and parallelizable. Our evaluation shows that it enables the training of a logistic regression model on a dataset (12 features and 600,000 records) distributed among 12 data providers in less than 2 seconds. The computations are distributed among 6 computing nodes, and Drynx enables the verification of the query execution's correctness in less than 22 seconds.

I. INTRODUCTION

Drynx addresses the difficulty of sharing sensitive data for analysis while protecting privacy, and the limitations of centralized or weakly trusted decentralized alternatives. It combines distributed computation with privacy and correctness protections for statistical queries and machine-learning models.

I. INTRODUCTION

  • Sensitive-data sharing remains difficult because privacy concerns and legal or ethical constraints can prohibit or discourage sharing, despite its value for research.The introduction notes that cross-border sharing is further complicated by heterogeneous national legislation.Source: §I · p. 1

II. RELATED WORK

  • Centralized databases create a high-value target and single point of failure, while many decentralized alternatives assume trusted or honest-but-curious parties or support only limited computations.The cited breach example describes personal information from more than 143 million consumers being compromised.Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

  • Drynx supports statistical queries and machine-learning model training and evaluation on distributed data while protecting confidentiality, providers’ privacy, released results, and computation correctness.It also limits the influence of strong outliers and permits a fraction of system entities to be malicious without requiring any entity to be individually trusted.Source: §I · pp. 1–2

III. BACKGROUND

  • Drynx combines interactive protocols, homomorphic encryption, zero-knowledge proofs, and distributed differential privacy in a modular, dynamic system.The background section introduces the cryptographic tools, blockchains, differential privacy, and verifiable shuffles used in the approach.Source: §I · pp. 1–2, §III · p. 3

I. INTRODUCTION

  • Drynx proposes techniques for lightweight query-execution auditability, including distributed storage and verification of query-validity, computation-correctness, and input-range proofs.The implementation of the solution is exemplified using a blockchain.Source: §I · p. 2

A. Use Cases

  • The medical use cases cover hospital-to-hospital analysis and studies using data collected directly from people’s wearables.The examples include statistical computation and model training across hospital patient datasets, and studies such as heart research using wearable data.Source: A. Use Cases · p. 3

B. ElGamal Homomorphic Encryption

This section outlines cryptographic and privacy tools used in Drynx, including encryption, proofs, interactive protocols, differential privacy, and verifiable shuffles.

B. ElGamal Homomorphic Encryption

  • Elliptic Curve ElGamal provides Drynx’s additively homomorphic encryption, allowing encrypted linear combinations to be computed and fixed-point values to be encrypted.The paper notes that Drynx can use other cryptosystems, while ECEG supports efficient zero-knowledge correctness proofs.Source: B. ElGamal Homomorphic Encryption · p. 3

C. Zero-Knowledge Proofs

  • Zero-knowledge proofs verify computation integrity and that an encrypted secret lies in a specified range without disclosing the secret.The input-range proof uses a base-u decomposition and commitments to the digits; both proof types can be made non-interactive with Fiat–Shamir.Source: C. Zero-Knowledge Proofs · p. 3

D. Interactive Protocols

  • The collective public key is formed from computing nodes’ public keys, while its private key is never reconstructed, so decryption requires participation by all computing nodes.The text states that an attacker would have to compromise all computing nodes to decrypt a message encrypted under the collective key.Source: D. Interactive Protocols · p. 3

E. Blockchains

  • A blockchain is an append-only ledger maintained by nodes, with blocks validated by consensus and linked by cryptographic hashes.Each block contains a timestamp, nonce, and application-specific data.Source: E. Blockchains · p. 3

F. Differential Privacy

  • Differential privacy makes a randomized statistic behave similarly on datasets differing in one element, with ε and δ controlling the privacy level.The text describes adding noise to a function’s output, including Laplace noise scaled by the function’s sensitivity.Source: F. Differential Privacy · p. 3

G. Verifiable Shuffles

  • A verifiable shuffle permutes and re-randomizes ElGamal ciphertexts so an adversary without the decryption key and randomization factors cannot link outputs to inputs.Honest-verifier zero-knowledge proofs establish that the shuffle was performed correctly without revealing the permutation or factors.Source: G. Verifiable Shuffles · p. 4

IV. SYSTEM OVERVIEW

Drynx divides query, data, computation, and verification roles across entities, then evaluates encodable operations on distributed data under a strong threat model. Its functional scope spans statistics and regression models, with proofs supporting efficient audit.

C. Functional Requirements

A. System Model

  • A querier sends queries to computing nodes and data providers; providers return encrypted responses for aggregation and processing by computing nodes.The system assumes providers use sufficiently homogeneous data formats and a shared query language.Source: A. System Model · p. 4

B. Threat Model

  • Drynx assumes malicious queriers and data providers, at least one honest-but-curious computing node, and a threshold of honest verifying nodes.The computing-node guarantee follows an Anytrust model; the verifier threshold depends on the consensus algorithm.Source: B. Threat Model · p. 4

C. Functional Requirements

  • Encodable operations combine data providers’ local computations with collective aggregation, which is limited by the homomorphism of the cryptographic scheme.Computing nodes aggregate encoding outputs, with querier post-processing when needed.Source: C. Functional Requirements · p. 5
  • Drynx encodings support statistics including variance, standard deviation, min/max, and set operations, plus training and evaluation of linear and logistic regression models.The paper also lists sum, count, frequency count, average, and cosine similarity.Source: C. Functional Requirements · p. 5

D. Security Requirements

Drynx’s security requirements cover confidentiality, provider and individual privacy, and correct, robust query execution. Its design adds query auditability and offers concurrent verification and a probabilistic verification option.

D. Security Requirements

  • Query execution is correct when computations are correctly executed and results are robust against strong outliers, whether maliciously or erroneously input.Data inputs remain confidential, and no entity should infer information about a provider or an individual.Source: D. Security Requirements · p. 5

V. DRYNX DESIGN

  • Drynx introduces verifying nodes for query auditability and uses range proofs to check that data providers’ encoded results fall within predefined ranges.This is presented as limiting trust in data providers within a stronger threat model.Source: §V · p. 5
  • Drynx’s design combines a confidentiality-protecting query pipeline with neutral encodings and distributed differential privacy to protect data providers’ privacy.The design also describes proofs for results robustness and computation correctness.Source: §V · p. 5
  • Multiple query-execution and verification steps can run concurrently, while probabilistic verification offers a security-performance tradeoff.Source: §V · p. 5

A. Drynx Security Design

Drynx’s confidentiality design encrypts provider responses under a collective computing-node key, aggregates them without decryption, then switches the result to the querier’s key. Its security argument relies on at least one honest computing node.

1) Data Confidentiality:

  • Encrypted data providers’ responses are collectively aggregated under the computing nodes’ key, then converted to encryption under the querier’s key without decryption.The querier decrypts and decodes the resulting query answer.Source: 1) Data Confidentiality · p. 6
  • The tree-structured key-switching protocol reduces execution time by allowing computing nodes’ local operations to run in parallel.The collective aggregation requires #CN−1 aggregations and communications.Source: 1) Data Confidentiality · p. 6
  • Under the assumption that at least one computing node is honest, semantic security prevents an adversary controlling the remaining nodes, providers, and querier from distinguishing real from simulated data.The argument is sketched using the real/ideal simulation paradigm.Source: 1) Data Confidentiality · pp. 6–7
  • The collective key prevents decryption unless all computing nodes collude, while the final key-switching output is decryptable only with the participating nodes and querier.Source: 1) Data Confidentiality · p. 7

2) DPs’ Privacy:

Drynx aims to protect providers’ and individuals’ privacy through private participation choices, restricted result disclosure, and distributed differential privacy. It also uses neutral responses and collective obfuscation to address privacy risks in specific query types.

2) DPs’ Privacy:

  • Overall, Drynx seeks to let providers choose whether to answer, disclose only the encoded operation result to the querier, and prevent inference about an individual provider or person.Source: 2) DPs’ Privacy · p. 7
  • A provider can decline a query without revealing that choice by sending a neutral response indistinguishable from a non-neutral encrypted response.Source: 2) DPs’ Privacy · p. 7
  • Collective Tree Obfuscation addresses bit-wise operations by obfuscating a summed binary result, so the querier learns only whether the final value is zero.Without obfuscation, a naive sum can reveal how many providers answered 1 or 0.Source: 2) DPs’ Privacy · p. 7
  • Drynx uses Collective Differential Privacy to prevent inference about providers or individuals from query results.The choice of privacy parameters depends on the application’s privacy policy and is outside the paper’s scope.Source: 2) DPs’ Privacy · p. 7

3) Query Execution Correctness:

Drynx audits query execution by combining input-range proofs, proofs of computing-node operations, and parallel verification by verifier nodes. Signed proofs and verification results are stored in a proof blockchain, allowing an auditor to check a query or verify the proofs independently.

3) Query Execution Correctness:

  • Input-range proofs constrain data-provider values, while zero-knowledge proofs establish correctness of computing-node computations.The range-proof scheme adapts a [0,ul)-range proof to the Anytrust model by combining computing nodes’ signatures, so the data provider uses at least one signature whose secret it does not know.Source: 3) Query Execution Correctness · pp. 8–9
  • Verifier nodes check signed query proofs in parallel with execution, store proofs and verification outcomes, and use consensus to record each query and the verifier maps in a proof blockchain.An auditor can check the verifier signatures and agreement, or retrieve universally verifiable proofs and verify them independently.Source: 3) Query Execution Correctness · pp. 8–9
  • For each query, verifier nodes derive the expected proofs, verify prover signatures and proofs, and store the results in query-proofs maps.A block is created even when proofs are wrong, making it possible to determine which parties were involved in incorrectly computed queries.Source: 3) Query Execution Correctness · pp. 8–9

B. Drynx Optimized Design

Drynx’s optimized pipeline runs query execution and verification concurrently, with independent steps able to proceed in parallel. Probabilistic verification samples proofs and sub-proofs to improve verification performance while retaining a high probability of checks by multiple verifier nodes.

1) Full Query Execution Pipeline:

  • Query execution and verification run concurrently, and independent query steps can run in parallel; differential-privacy noise is added after aggregation but can be precomputed when its parameters are predefined.Computing nodes aggregate each data provider’s response as it arrives.Source: 1) Full Query Execution Pipeline · p. 9, Figure 4 · p. 10

2) Probabilistic Query Verification:

  • Verifier nodes sample proofs with threshold T and sub-proofs with threshold Tsub, improving verification performance while preserving a high probability of detecting misbehavior.A proof counts as incorrect if any of its sub-proofs is incorrect.Source: 2) Probabilistic Query Verification · p. 10
  • With 7 verifier nodes, T=1, Tsub=0.3, and fh=5, each sub-proof is verified by at least fh nodes with probability 98.48%.The probability that a proof is checked is pver=1−(1−T)^NVN; for a sub-proof it is pversub=1−((1−T)+T(1−Tsub))^NVN.Source: 2) Probabilistic Query Verification · p. 10

VI. SECURITY ANALYSIS

Drynx’s security analysis describes how encryption, differential privacy, range validation, and computation proofs protect data and query results. Its encodings support statistical operations and regression models, while iterative range reduction trades performance against privacy.

VI. SECURITY ANALYSIS

  • Data remain encrypted during Drynx operations, and its proofs do not affect confidentiality beyond information inferable from the proven facts.Data providers can privately choose whether to answer; differential privacy protects providers and individuals from inferences based on released results by adding verifiable noise whose value is unknown to every entity.Source: §VI · p. 10
  • Range proofs bound data-provider inputs and proofs establish computing-node correctness, limiting the influence of malicious or erroneous outliers on query results.Data providers may still submit incorrect values, but range limits constrain their effect.Source: §VI · p. 10

VII. ENCODINGS

  • Drynx adapts logistic-regression training to its framework, enabling verifiable, privacy-preserving training in the presence of a strong adversary.Its logistic-regression encoding approximates the original cost function.Source: §VII · pp. 11–12
  • Drynx supports numerical statistics, including sum, mean, variance, standard deviation, cosine similarity, and R2, by aggregating data providers’ local partial computations.For variance, the querier computes the overall value after decrypting the aggregated local sums and sums of squares.Source: §VII · p. 11, Table I · p. 11
  • Bit-wise encodings implement operations such as OR, AND, min, max, set intersection, and set union; encrypted random integers can yield an error with probability below 1/(#G−1).Encrypting bits eliminates that error probability but requires more computations and proofs.Source: §VII · p. 11
  • For iterative min or max, binary-search range reduction uses one ciphertext per data provider per query and reduces the possible-answer range by half.With a range of [0,1000) and entropy limit 100, the workload falls by a factor of 7.8 while leaking a range of 100 possible minimum values.Source: §VII · p. 12

VIII. DISCUSSION AND EXTENSIONS

Drynx lets applications select security and privacy features and supports participants taking multiple roles. Its discussion also identifies operational and accuracy boundaries, and places authentication and authorization outside the paper’s scope.

VIII. DISCUSSION AND EXTENSIONS

  • Applications can enable or disable Drynx security features, including range validation and differential privacy, according to their requirements.Omitting range validation preserves the remaining security guarantees when results robustness is not required.Source: §VIII · p. 12
  • A hospital can act as a data provider, computing node, and verifier node without hindering Drynx’s security.As a computing node, it can ensure its data confidentiality without trusting another hospital.Source: §VIII · p. 13
  • If a computing node becomes unresponsive during a query, aggregation and key switching cannot finish; the querier can restart with another computing-node set.An unresponsive data provider only reduces the number of responses included in the statistic.Source: §VIII · p. 13
  • Output precision depends on fixed-point representation, logistic-regression cost approximation, optional differential-privacy noise, and the input ranges used to bound malicious providers.The paper states that hard accuracy numbers for malicious providers depend on the operation, ranges, and numbers of providers and records.Source: §VIII · p. 13
  • Authentication and authorization are outside the paper’s scope, though Drynx can integrate off-the-shelf federated or distributed solutions.The paper cites,, as examples.Source: §VIII · p. 13

IX. PERFORMANCE EVALUATION

Drynx’s evaluation examines its implementation, execution environment, scaling behavior, and verification costs. It reports that runtime scales almost linearly in several system dimensions, with proof generation and verification incorporated into the evaluation.

B. System Evaluation

  • Runtime scales almost linearly with the numbers of computing nodes, verifying nodes, and data providers, while more nodes also distribute trust and increase security.For a fixed number of data providers, runtime grows more slowly with records per provider than with the number of providers because providers can locally pre-aggregate data.Source: §IX · p. 13, B. System Evaluation · p. 13
  • The evaluation used a simulated network with 100 Mbps links and 20 ms latency across 13 machines, each with two 12-core Xeon CPUs and 256 GB RAM.The default setup used 6 computing nodes and 7 verifying nodes.Source: B. System Evaluation · p. 13
  • 98.5%: with verification thresholds T=1.0 and Tsub=0.3, each sub-proof is verified by the threshold number of verifying nodes with this probability.The evaluation reports runtime without the distributed differential-privacy protocol because it can be precomputed or run in parallel.Source: B. System Evaluation · p. 13
  • 2.9 seconds: with Laplacian noise and a list of 100 values, distributed differential privacy takes this long, with 8.1 seconds of proof-verification overhead.Increasing the noise-list size improves privacy by reducing δ, but increases the time to generate and shuffle the list.Source: B. System Evaluation · p. 13
  • Figure 5h’s optimized maximum aggregates runtime across all necessary query executions and their proof overheads.The implementation is a modular Go library, and the system supports either permissioned or permissionless blockchains.Source: A. System Implementation · p. 13, Figure 5 · p. 14

1) Drynx Evaluation:

Drynx’s evaluation reports competitive performance against prior systems while providing stronger security guarantees. Its results also show how execution, verification, and resource costs vary with system configuration.

1) Drynx Evaluation:

  • 0.4 seconds: the auditor can verify the query by checking the signature and proof map in its blockchain block, while verification runs in parallel with query execution.The example’s block is 56 kB and contains the query and its corresponding proof map.Source: 1) Drynx Evaluation · p. 14
  • Runtime grows more slowly with records per data provider than with the number of providers, because providers can pre-aggregate locally; runtime also increases with the numbers of providers, computing nodes, and verifying nodes.More computing and verifying nodes distribute trust and increase security.Source: 1) Drynx Evaluation · p. 14
  • A verification setting of T=1 and Tsub=0.2 reduces verification workload by close to 0.8, while each sub-proof is still verified by five verifying nodes with 83.48% probability.The passage identifies proof communication as the most time-consuming part of verification.Source: 1) Drynx Evaluation · p. 15
  • Computational, bandwidth, and storage costs increase with more computing or verifying nodes, trading off efficiency and scalability against security and workload distribution.Proof-verification overhead also increases with input size, and obfuscated bit-wise operations take longer.Source: Table II · p. 15, 1) Drynx Evaluation · p. 16

2) Comparison with Existing Works:

  • Drynx performs as well as or better than UnLynx and Prio in logistic-regression training while providing better security guarantees.The comparison covers functionality and threat models as well as performance.Source: Figure 6 · p. 15, 2) Comparison with Existing Works · p. 16
  • 0.4 seconds versus 1.4 seconds: an auditor checks Drynx’s stored proof-block entry in this time, while auditing UnLynx requires requesting and verifying proofs from each entity.For Drynx’s sum query, range verification adds 0.6 seconds to a total execution time of 2 seconds.Source: 2) Comparison with Existing Works · p. 16
  • About two times faster: Drynx achieves this for min computation in Prio’s threat model; with obfuscation in its stronger threat model, Drynx scales similarly to Prio.Without obfuscation, Drynx significantly outperforms Prio for min while accepting a small error probability of 1/(#G).Source: 2) Comparison with Existing Works · p. 16

X. CONCLUSION

  • Drynx supports statistical queries and machine-learning training on distributed datasets without requiring any entity to be individually trusted.The conclusion also highlights query auditability, end-to-end data confidentiality, provider privacy, and configurable security, privacy, and efficiency tradeoffs.Source: §X · p. 16

APPENDIX A TABLE OF SYMBOLS

The appendix identifies a recurrent-symbol table and develops an error-probability expression for bit-wise operations. The supplied passages do not provide the table’s symbol entries.

APPENDIX A TABLE OF SYMBOLS

  • Table III is identified as a table of recurrent symbols, but its entries are not specified in the supplied passage.The appendix also includes author biographies, which do not add technical content to this section summary.Source: Table III · p. 19

APPENDIX B ERROR PROBABILITY

  • The appendix derives an expression for the bit-wise-operation error probability Pn, where n is the number of data providers; the probability is stated to be below 1/(#G−1).The expression applies when data providers are asked to answer with random values.Source: Appendix B · p. 19

Related papers

Loading 1902.03785v3…