Suppose you want to know how much you should trust a stranger on a hosting or review platform. The most accurate answer is personal: it depends on how trusting you are, on which of your contacts have rated that stranger, and on how harsh or lenient each of those contacts usually is. Studies of real trust networks show that this personal answer beats a single global reputation score by a wide margin. Computing it, however, means combining other people's confidential opinions with your own private ones. Homomorphic encryption lets a server compute on data it cannot read, so it looks like the natural tool. The recent encrypted graph-learning systems built on it are still far too slow, or they leave the social graph itself unencrypted.
This note argues that the slowness is mostly self-inflicted. Subjective trust models do not need to run as deep encrypted circuits. Their nonlinear, personalized parts belong to individual people, and each of those people already holds the data needed to compute their part in plaintext. The only part that truly mixes private data from many people is a set of weighted sums. A weighted sum is the cheapest thing homomorphic encryption can do: one multiplication deep, with no rotations and no bootstrapping. We propose to build and test a trust-inference protocol on this decomposition. The central empirical question is how much predictive accuracy survives when each person estimates their own bias locally instead of fitting a joint model over everyone.
Core Claim
Two-hop subjective trust models can be rewritten so that every encrypted computation is a sum of products. Those models include the triad mixed-effects model of Overgoor et al., the thresholded propagation of MoleTrust from Massa and Avesani, and the bias terms of MATRI. After the rewrite, each nonlinear step is owned and computed locally by one party:
- Source effects stay with the querier. The querier's own "trustingness" (its personal baseline, a random intercept in mixed-effects terms) and the cutoff that drops low-trust contacts are both computed by the querier.
- Rater effects stay with the rater. Each rater's harsh-or-lenient baseline is subtracted from their own ratings before encryption.
- The final step happens after decryption. Division and combination with the fixed-effect coefficients are done by the querier on the decrypted aggregates.
Our key observation comes from Overgoor et al.. They found that the source's trustingness, and the source's trust in the intermediary, matter more than the intermediary's trust in the target. The most predictive terms are therefore exactly the ones that never need encryption.
The claim is falsifiable. On CouchSurfing, Overgoor et al. report mean squared error (MSE) of 0.7079 for global reputation and 0.5327 for the jointly fit mixed-effects model. We predict that the locally decomposed model, run under encryption, recovers at least 80% of that gap, i.e. an MSE no higher than about 0.568. We also predict that its per-query server cost depends on the size of the anonymity set the querier chooses, not on the size of the graph.
Setting and Threat Model
We adopt the decentralized personal-data-store setting of Libertas, where each user keeps their own outgoing ratings. Libertas supplies the deployment setting and its user-chosen trusted agents. Its trust model, however, is a hand-written list of whom to trust, with no inference. We replace that list with inferred subjective trust.
Each rater stores their outgoing ratings encrypted under a threshold key (a key that only a quorum of a few decryption agents can use together). The ratings are slot-packed: one ciphertext holds a vector over hashed target identifiers, so the storage layout reveals nothing about whom the rater rated. A single untrusted server does all the computation. Decryption agents only re-encrypt final results to the querier. This requires a non-collusion assumption, but only for decryption, not for every multiplication as in multi-party computation.
The querier encrypts its personal weights over a padded anonymity set of $K$ candidate raters. Each weight is its own thresholded trust in a contact, or zero for padding. The server never learns whose opinions the querier values. In return, the querier learns only aggregates, never an individual rater's score.
Research Program
The decomposed predictor
For source $u$ and target $v$, let $w_{ux}$ be $u$'s locally thresholded trust in rater $x$. Let $\tilde r_{xv} = r_{xv} - b_x$ be $x$'s rating of $v$ with $x$'s own locally estimated baseline $b_x$ removed. Let $\mathbb{1}_{xv}$ indicate that $x$ rated $v$. The server homomorphically computes two vectors over all targets at once:
$$S_v = \sum_{x \in \mathcal{K}_u} w_{ux}\,\tilde r_{xv}, \qquad N_v = \sum_{x \in \mathcal{K}_u} w_{ux}\,\mathbb{1}_{xv},$$
where $\mathcal{K}_u$ is $u$'s padded anonymity set of size $K$. With the same machinery and unit weights it also computes a global incoming-rating aggregate, which serves as a target effect for cold-start targets. The querier decrypts these and forms
$$\hat r_{uv} = \mu + b_u + \beta\, S_v / N_v + \gamma\, g_v.$$
Here $\mu$ is a global mean, $b_u$ is $u$'s own baseline, $g_v$ is the decrypted global target aggregate, and $\beta, \gamma$ are fixed-effect coefficients fit once on public or consented data.
Each term in $S$ and $N$ multiplies two ciphertexts that hold one value per slot and add up across raters. That costs one level of multiplication and no rotations, because targets already sit in matching slots. This is precisely the pattern that FicGCN and Penguin work hard to approximate through node reordering and packing ratios.
What would be built and analyzed
The project has four components.
- Plaintext replication. We first replicate the plaintext models: triad mixed-effects, MoleTrust, and MATRI. We then measure the accuracy cost of each relaxation separately: locally estimated baselines instead of jointly fit ones, two hops instead of more, and fixed coefficients instead of per-query fitting.
- Encrypted implementation. We implement the encrypted protocol with the CKKS scheme (approximate arithmetic on packed real-valued vectors). We measure latency, ciphertext and key bytes, and decryption error.
- Deeper propagation. For propagation beyond two hops, we test an interactive variant. The querier decrypts two-hop aggregates for its anonymity set, thresholds them locally, and issues one more round. This costs one round trip per hop, not one per network layer as in SecureNets. We also quantify the extra leakage: the querier learns aggregated two-hop trust in candidate intermediaries.
- Dynamic updates. A trust update by rater $x$ re-encrypts only $x$'s own ciphertexts. There is no global reordering step to invalidate, so the static-preprocessing limitation of FicGCN does not arise. We will measure update cost directly.
Baselines
Naive reference points. These are the global-mean and global-reputation predictors. On CouchSurfing, Overgoor et al. report MSE 0.7498 for the mean and 0.7079 for global reputation. On Epinions, Massa and Avesani show that global metrics hit an error ceiling of 0.5 on controversial targets, which make up over 20% of rated users. These predictors cost nothing cryptographically. Any encrypted personalized method must beat them clearly to justify itself.
Strongest accuracy competitor. This is the jointly fit mixed-effects triad model in plaintext, which reaches MSE 0.5327 on CouchSurfing in Overgoor et al.. On Advogato and Slashdot, we use MATRI, which Yao et al. report improves RMSE by 40.7% and MAE by 26.7% on Advogato, and prediction error by 19.4% on Slashdot, over its best competitor. No absolute MATRI error values were found on Lacuna, so we will rerun MATRI ourselves. These models serve as accuracy upper bounds, run in plaintext on identical train/test edge splits. Hyperparameters are tuned on the same validation split with the same search budget we give our decomposed model. Beating them is not required. Recovering 80% of the gap between global reputation and the strongest model is the success criterion.
Strongest encrypted-computation competitor. This is a Penguin-style encrypted graph network that encrypts both structure and features. Penguin reports 0.24 seconds amortized single-node latency on Cora and thousands of seconds on Pubmed (19,717 nodes). We will train a two-layer graph network on each trust graph and run it with Penguin's packing on the same hardware and thread count. We will compare per-query latency, bytes transferred, and accuracy. We will also include CryptoGCN, which reports a 3.10× latency speedup and 77.4% fewer homomorphic operations by keeping the adjacency matrix in plaintext, as a weaker-privacy reference point. Our protocol beats these systems if it is faster at equal or better accuracy while hiding the edges.
Ablations. Three ablations isolate the key ingredient, which is moving each person's effect to that person:
- Remove rater debiasing, so raw ratings are encrypted.
- Replace local baselines with jointly fit ones, as an oracle.
- Move the source's thresholding into the encrypted circuit via a polynomial approximation of the comparison. This shows the depth and latency cost the decomposition avoids.
Why not just…?
Why not just use additively homomorphic encryption or secure aggregation instead of CKKS? This is the most serious threat, and we accept it. The sums above need only one multiplication per term. An additive scheme can multiply ciphertexts by plaintext weights, but here the weights are encrypted to hide the querier's contacts. In that case an additive scheme needs either per-query participation by raters or extra interaction. We will implement an additive-scheme variant with the weights revealed to a separate agent and compare it head to head. If it matches CKKS on cost under an acceptable leakage model, the contribution is the decomposition and the accuracy study, not the choice of scheme, and we will say so.
Why not just mask matrices interactively as SecureNets does? SecureNets reports 69.78% less transmission than CryptoNets. However, it requires a client round trip at every nonlinear layer, and it targets a client outsourcing its own data, not combining many people's confidential ratings. Our protocol needs no interaction for two-hop trust and one round per extra hop. Our latency experiments under emulated wide-area-network delays will show where the crossover lies.
Why not just use delegated multi-party computation with differential privacy, as in Libertas? Libertas scales linearly in the number of providers, but setup time dominates simple computations. Its differential-privacy noise also blurs exactly the fine rating differences that personalization exploits. We will run an MPC sum with the noise levels Libertas would require and report accuracy loss on controversial targets.
Why not just download the local subgraph and run MoleTrust on the device? This exposes every intermediate rating and reveals the query target to whoever serves the subgraph. CouchSurfing's ratings are confidential by design (Overgoor et al.). Downloading is the right answer only when ratings are public, and then no encryption is needed at all.
Proposed Experiments
Datasets. Accuracy is measured on Epinions, Slashdot, Advogato, and PGP, using the splits of Yao et al.. We also attempt a CouchSurfing replication. If CouchSurfing is unavailable, the 80%-gap criterion is instead computed against our own plaintext mixed-effects and global models on Epinions and Advogato.
Metrics. We report MSE, RMSE, and MAE overall and on the controversial-target subset defined by Massa and Avesani. We also report coverage, measured against MoleTrust's 80–88%. Cryptographic cost is measured as server latency against anonymity-set size $K$ and graph size, ciphertext and key bytes, and update cost per edge change.
Communication cost. Haralampieva et al. flag rotation and evaluation keys as a communication bottleneck. Our circuit needs no rotation keys, and we will report the measured key-size difference against Penguin.
Decisive checks. The proposal succeeds or fails on three outcomes:
- Locally decomposed trust must close at least 80% of the global-to-mixed-effects gap.
- Encrypted query latency must grow linearly in $K$ and stay flat as the graph grows from Advogato to Epinions, while the Penguin-style baseline grows with the number of nodes.
- Encrypted predictions must match their plaintext counterparts to within CKKS decryption error.
If the first check fails, the decomposition is too lossy and personalized trust genuinely needs deep encrypted circuits. That result would redirect effort toward the bootstrapping speedups of Wang et al. rather than away from them.
References
- Trust Propagation with Mixed-Effects Models
- Controversial Users Demand Local Trust Metrics: An Experimental Study on Epinions.com Community
- Multi-Aspect + Transitivity + Bias: An Integral Trust Inference Model
- Libertas: Privacy-Preserving Collaborative Computation for Decentralised Personal Data Stores
- FicGCN: Unveiling the Homomorphic Encryption Efficiency from Irregular Graph Convolutional Networks
- Penguin: Parallel-Packed Homomorphic Encryption for Fast Graph Convolutional Network Inference
- SecureNets: Secure Inference of Deep Neural Networks on an Untrusted Cloud
- CryptoGCN: Fast and Scalable Homomorphically Encrypted Graph Convolutional Network Inference
- A Systematic Comparison of Encrypted Machine Learning Solutions for Image Classification
- Circuit Bootstrapping: Faster and Smaller