Security in Cloud Computing

01 / Security in Cloud ComputingCryptography across a trust boundary

Outsourcing storage or computation transfers work, not automatically trust. A provider may return an old file, keep only part of it, learn sensitive inputs or compute a result incorrectly. An encrypted upload addresses only some of these concerns. This course asks which cryptographic functionality is needed at each boundary and what evidence a verifier actually obtains.

Here cloud computing includes cryptographic cooperation across independently controlled machines: client–server services, two-party protocols, outsourced computation and peer-to-peer systems. A commercial provider is one deployment, not a prerequisite. The emphasis is on algorithms, information flow and proof obligations, rather than configuration of a particular cloud product.

The central question is not simply whether data are encrypted. It is: which parties can jointly obtain a useful result without granting any one of them excessive knowledge or authority? A related but different question is how replicas agree when some participants lie, stop responding or send contradictory messages.

Course route

The prerequisite is System Security I. The companion System Security II develops simulation, rewinding, forking and game-based reductions. Here those tools explain why an outsourced task may be accepted, which inputs remain private, and where additional assumptions enter.

Separate the promises

These study materials can be read independently of a current teaching schedule.

02 / Security in Cloud ComputingMathematical and system model

Let $G=\langle g\rangle$ have prime order $q$, and let $\mathbb Z_q$ be its scalar field. A user has secret $a$ and public key $A=g^a$. A fresh nonce is $x$, its commitment is $X=g^x$, and a Schnorr challenge and response are $c,s$. Every concatenation $\|$ denotes an unambiguous encoding, with separate domains for different protocols.

Hash notation and output types

The group subscript names the actual output group. When a derivation uses a generic group $G$, write $\H_G$; use $\H_{G_2}$ if the output is in $G_2$. This does not identify distinct source groups or change a proof's assumptions. All hash inputs are unambiguously encoded byte strings; writing a tuple or group point as an input abbreviates its specified encoding. Independent roles use separate domains, even when they share the symbol $\H$.

A public deterministic hash-to-group function must not provide a publicly computable discrete logarithm of its output relative to the generator. Merely returning a point of the right type is insufficient. In the BLS WebAssembly demo, $\H_{G_1}$ denotes the group-hashing role implemented with MCL's hashAndMapToG1; scalar hashing has a different interface, hashToFr. The notation alone does not assert compatibility with an RFC 9380 suite or a standard BLS byte format. See RFC 9380 and MCL WebAssembly.

For pairing-based storage, use additive groups $G_1,G_2$ with generators $P,Q$, a multiplicative target group $G_T$, and $e:G_1\times G_2\to G_T$. Thus $e(a\cdot P,b\cdot Q)=e(P,Q)^{a\cdot b}$. File blocks $m_i$ are field elements obtained by an explicitly specified encoding, possibly after erasure coding. They are not arbitrary strings that can silently be used as scalars.

The data owner prepares authenticated material. The storage server holds it and answers challenges. An auditor checks evidence. A computation protocol may instead have two parties, each with private input. Distinguish an honest-but-curious participant, which follows the algorithm but studies its view, from a malicious participant, which chooses arbitrary messages and may abort.

For a two-party functionality $f=(f_1,f_2)$ with inputs $u,v$, a simulation-based privacy goal asks for efficient simulators such that

Here $\approx_c$ means computational indistinguishability, and the view contains local coins, input and received messages. Public sizes and other allowed leakage must also be supplied to the simulators. The display is a semi-honest teaching definition. Malicious security additionally needs an account of effective inputs, inconsistent messages and aborts.

03 / Security in Cloud ComputingParticipants, intermediaries and the ideal functionality

Data owners, computing parties and output recipients need not be the same entities. Two hospitals can compute directly, or send shares to three independently operated servers. A relay carrying their messages is not necessarily entitled to read them. A cloud machine may implement one role, several roles, or only the communication channel.

An ideal functionality is a specification, not an extra server that the implementation must deploy. For parties $P_1,\ldots,P_n$ with inputs $z_1,\ldots,z_n$, specify a function

Only $P_i$ receives $y_i$; an empty output means no result is authorised for that party. In the ideal description a trusted box receives the inputs and distributes these outputs. The real protocol aims to realise this contract without that trusted box, subject to its assumptions. The MPC introduction by Evans, Kolesnikov and Rosulek explains this real/ideal distinction and its common adversary models.

Does this design need a third party?

Thus “three parties” is not a security property. Three processes on one administrator's laptop do not establish non-collusion. Conversely, an OT protocol between two endpoints does not secretly require a third endpoint merely because its definition uses an ideal OT box.

Write a contract before choosing a protocol

For a joint incident count, specify the reporting period, eligible organisations, duplicate handling, range of counts, recipients and permitted leakage. A valid encrypted negative count is still an invalid contribution if the contract permits only nonnegative counts. A protocol can protect the submitted values without proving that those values accurately describe the world.

Distinguish privacy, correctness, fairness and guaranteed output delivery. Privacy permits deductions from the authorised result. Security with abort allows a dishonest participant to prevent completion. Fairness asks whether one party can obtain its output while denying another its output. A general two-party computation does not automatically provide fairness or delivery just because it protects inputs.

04 / Security in Cloud ComputingOblivious transfer, one of two

In 1-out-of-2 oblivious transfer, the sender holds two messages $(M_0,M_1)$ and the receiver holds a choice bit $b$. The receiver learns $M_b$ but should learn nothing about the other message beyond what follows from its own input and output. The sender should not learn $b$. This is not ordinary encryption: the sender deliberately offers two alternatives without learning which was obtained.

The following semi-honest teaching flow illustrates the DH algebra used in simplest-OT constructions. Choose a validated prime-order group with hard DH problems. The sender samples nonzero $a$ and sends $A=g^a$. The receiver samples $x$ and sends $B=g^x\cdot A^b$. The sender computes

while the receiver computes $Z=A^x$. If $b=0$, then $Z=Z_0$; if $b=1$, then $Z=Z_1$. Derive separate keys $K_i=\mathsf{KDF}(\mathtt{OT}\|sid\|A\|B\|i\|Z_i)$ and encrypt $M_i$ with the agreed authenticated-encryption profile. The receiver derives only its selected key from the corresponding $Z$.

For uniform $x\in\mathbb Z_q$, both choices give a uniform $B\in G$. That explains receiver privacy: the sender cannot distinguish the receiver's choice bit in this semi-honest flow. Sender privacy protects the unchosen message from the receiver. It requires a computational argument, not merely observing that one key was not used in a program. Malicious points, key relations, repeated sessions and a sender choosing malformed messages require additional analysis.

The original lecture uses Chou and Orlandi's simplest OT, paper 2015/267. Consult its current security statement rather than inferring universal composability from this abbreviated exchange. The teaching flow above claims neither a complete malicious-secure protocol nor a production implementation.

05 / Security in Cloud ComputingOne-of-many transfer and private queries

In 1-out-of-$n$ OT the receiver chooses an index $j$ and learns exactly the corresponding sender message under the specified privacy model. Running an independent 1-out-of-2 OT for each bit of an index is not by itself a construction: the sender's ciphertexts and keys must be composed so that one consistent index, rather than pieces of many messages, can be recovered. Naor and Pinkas, Computationally Secure Oblivious Transfer, is the original course reference.

The desired output remains one selected item, not the entire database. This distinguishes OT from basic private information retrieval: PIR hides which item is requested from the server, but its definition need not protect all other database contents from the client. Database privacy must be requested separately. Likewise, encrypting a client's network connection hides its traffic from outsiders, not its query from the service receiving it.

06 / Security in Cloud ComputingGarbled circuits: one AND gate, then a computation

Consider a Boolean AND gate with input bits $u,v$ and output $w=u\land v$. For each wire assign two independent opaque labels: $K_U^0,K_U^1$, $K_V^0,K_V^1$ and $K_W^0,K_W^1$. A label encodes a wire value; it should not reveal the bit by its visible representation.

For each input pair $(i,j)$, the garbler prepares a protected row encoding $K_W^{i\land j}$ under a key derived from $K_U^i$, $K_V^j$ and the unique gate identifier. This is an explanatory view of garbling, not a security claim for an arbitrary home-made encryption wrapper. The evaluator receives exactly one label for each input wire and can evaluate the corresponding row, obtaining one output label.

The table above explains the truth function. Do not transmit such a truth-labelled table to the evaluator. Real garbling permutes or otherwise encodes row selection and uses a proven garbling scheme. Point-and-permute uses selection bits attached to labels whose relation to the semantic bits is hidden.

The garbler can directly send labels for its own input. Labels for the evaluator's input are obtained through OT: the garbler offers the two wire labels and the evaluator chooses one without exposing its bit. Intermediate labels become inputs to later gates; only authorised final outputs are decoded. This is the composition that turns the single AND gate from the old lab into a full computation.

For semi-honest security, justify why the evaluator learns only its active labels and why the garbler learns no OT choices. Malicious security additionally addresses incorrect circuits, inconsistent inputs and selective failures; it does not follow from the four-row truth table. Bellare, Hoang and Rogaway's foundations of garbled circuits provides a precise framework for these separate properties.

07 / Security in Cloud ComputingSecret sharing and private aggregation

Use a prime field $\mathbb Z_q$. In this chapter $z$ is an input value, not the Schnorr nonce from the signature chapters. Write $[z]_j$ for the share held by computing party $P_j$, and $[z]$ for the whole distributed representation. Brackets here denote shares, not rounding or public disclosure.

Additive sharing: no individual share is the input

Choose $[z]_1,\ldots,[z]_{n-1}$ independently and uniformly, and set

All $n$ shares sum to $z$. Any $n-1$ shares have a distribution independent of $z$ before other permitted information is considered. This is an $n$-out-of-$n$ scheme: it hides the secret from a proper subset but cannot reconstruct if a share is withheld. Privacy against collusion and tolerance of missing shares are different properties.

To add two shared values, each party adds its own shares. For a public scalar $\lambda$, each party multiplies its share by $\lambda$:

No interaction is needed for these two operations. Opening a result means collecting enough result shares, according to the sharing scheme, at the authorised recipient. Opening every intermediate value defeats the purpose.

Worked private sum

Three organisations report $12$, $7$ and $9$ incidents. They use three computing parties and the small teaching field $\mathbb Z_{101}$. The following fixed shares illustrate the arithmetic; an actual protocol must sample fresh shares.

The collector receives only the last row, whose sum modulo $101$ is $28$. Each computing party sees one column, not all three input sharings. For honest-but-curious parties, fresh independent sharing and private authenticated delivery are essential assumptions. These equations do not detect a party replacing its result share.

To interpret a field result as an ordinary integer count, choose $q$ above the largest permitted total and enforce the input bounds in a malicious-secure design. Otherwise $28$ and $129$ are indistinguishable modulo $101$. Even a correctly computed total reveals one organisation's count to a coalition that already knows every other count. That inference belongs to the output, not to a broken sharing algorithm.

Shamir sharing: a reconstruction threshold

Shamir's construction replaces additive shares with evaluations of a random polynomial. For reconstruction threshold $k$, choose random coefficients and set

using distinct nonzero field points. Any $k$ correct shares reconstruct $z=p_z(0)$ by interpolation; fewer than $k$ reveal no information about $z$. Plain interpolation does not establish that received shares are correct. Verification or error correction needs additional redundancy and a protocol.

For a small example, $p_z(X)=12+7\cdot X$ over $\mathbb Z_{101}$ gives shares $19,26,33$ at points $1,2,3$. The first two reconstruct $2\cdot19-26=12$. If the second share is changed to $27$, the same unchecked calculation gives $11$. Threshold reconstruction is not, by itself, Byzantine robustness.

08 / Security in Cloud ComputingMultiplying shares with Beaver triples

Local multiplication is not enough: $([z]_1+[z]_2)\cdot([w]_1+[w]_2)$ includes cross terms missing from $[z]_1\cdot[w]_1+[z]_2\cdot[w]_2$. A multiplication protocol must account for them while preserving privacy.

Beaver's circuit-randomisation method uses a fresh shared triple $([u],[v],[w])$, where $u,v$ are independent random field elements and $w=u\cdot v$. Here $u,v,w$ denote preprocessing values. For private operands $z,h$, open the masked differences $d=z-u$ and $e=h-v$. Then compute

For additive sharing, the public value $d\cdot e$ is added to one designated share, with zero added to the others. Adding it to every share would multiply that term by $n$. Expanding the right-hand side gives

The opened differences are masked only while the masks remain hidden and independent. A used triple is consumed, never recycled.

A numerical trace to check the implementation

Take $q=101$, $z=8$, $h=9$, $u=4$, $v=6$, $w=24$. Then $d=4$, $e=3$, and

One two-party sharing of the triple is $[u]=(17,88)$, $[v]=(23,84)$ and $[w]=(31,94)$. Adding the public term to $P_1$ gives output shares

Their sum is $72$ modulo $101$. The two output shares, rather than $72$ itself, can enter the next multiplication. Only the final authorised answer needs to be opened.

Where do the triples come from?

A trusted dealer is one option, not a necessity. A dealer that retains $u,v$ and later obtains $d,e$ can recover $z,h$. Distributed preprocessing instead generates correlations through a protocol. MASCOT, by Keller, Orsini and Scholl, uses OT-based techniques and consistency checks for malicious arithmetic computation with a dishonest majority. Its preprocessing is not simply a third machine sending random numbers.

The displayed algebra describes a multiplication with correctly generated private triples and honest openings. For active security, the chosen MPC system must also authenticate shares, check triples and openings, bind messages to sessions, and handle aborts. These checks belong to the construction, not to an optional final comparison with a plaintext answer.

09 / Security in Cloud ComputingSecure multiparty computation as a complete protocol

A computation becomes an MPC protocol only when input sharing, every gate and output release use compatible representations and security guarantees. Let $C$ be the corrupted computing parties. Their joint view includes their inputs, shares, randomness and messages. The privacy claim concerns the whole coalition, not each member examined separately.

From a function to an execution

1. Fix the contract. Specify the function, public parameters, party identities, input encodings, recipients, allowed leakage and abort policy.
2. Choose a computation domain. Boolean circuits suit comparisons and bitwise operations. Arithmetic circuits suit sums and products. Conversion between the two requires a protocol, not a cast.
3. Establish keys and channels. Authenticate peers and bind transcripts to a fresh session and the agreed function. A private channel protects transport, not a dishonest endpoint.
4. Input and compute. Share inputs or obtain wire labels. Keep intermediate data secret. Use fresh, checked preprocessing where required.
5. Release outputs. Open or decode only specified results to specified recipients. Perform the integrity checks required before accepting them.

Data-oblivious execution also matters. A program branch or memory address derived from a secret may reveal it even when its value is never printed. Use an appropriate circuit or oblivious access mechanism when such information is not permitted leakage. “Oblivious” does not mean that a participant learns nothing: it learns its own input, authorised output and declared public information.

Fault bounds belong to a model

In the classical synchronous private-channel setting, Ben-Or, Goldwasser and Wigderson give information-theoretic MPC with a passive threshold $t<n/2$ and an active threshold $t<n/3$. The protocol includes more than secret reconstruction: multiplication and consistency must remain secure as well. These are not universal bounds for all MPC. Computational dishonest-majority protocols can protect honest parties even when all but one party are corrupted, typically with abort rather than guaranteed output delivery.

In a three-party deployment tolerating one corruption, assigning two servers to the same organisation changes the practical trust assumption. In two-party computation with abort, a correctly protected computation may still fail to finish because either endpoint disconnects. Adding an arbitrary proxy does not repair that issue.

Example: a private threshold decision

Suppose organisations hold bounded counts $z_i$ and authorise only the bit

where $\tau$ is a public threshold and $\mathbf 1[\cdot]$ is one when its condition holds, zero otherwise. The sum must stay secret until a secure comparison produces the output bit. Opening the sum first and then printing only $b$ leaks more than the contract permits. A field element also has no intrinsic integer order: the comparison needs a bounded integer encoding and a suitable comparison circuit.

Changing $\tau$ repeatedly can reveal the total by binary search. Restricting outputs is therefore both a circuit-design decision and a query-policy decision.

For implementation work, MP-SPDZ provides multiple explicit security profiles. Select the adversary model before benchmarking. Its emulation mode is useful for arithmetic debugging but is not an execution among independent distrustful parties. Record the protocol, field or ring, party count, corruption bound and whether preprocessing is included in measurements.

10 / Security in Cloud ComputingPrivate set intersection: matching through Diffie–Hellman

Two organisations want to identify shared records without exchanging their complete databases. Alice holds a set $S=\{s_1,\ldots,s_r\}$ and Bob holds $T=\{t_1,\ldots,t_s\}$. In client-output PSI, Alice receives $S\cap T$ and Bob receives no result. In PSI-cardinality, Alice instead receives only $|S\cap T|$. In both cases, the following protocols expose set sizes. A protocol with hidden sizes needs an additional, explicitly analysed padding strategy.

Use the running example $S=\{\mathtt{alpha},\mathtt{delta},\mathtt{kappa}\}$ and $T=\{\mathtt{beta},\mathtt{delta},\mathtt{kappa},\mathtt{omega}\}$. Ordinary PSI releases $\{\mathtt{delta},\mathtt{kappa}\}$. PSI-cardinality releases $2$. The two outputs support different applications and different privacy claims.

Encode, hash to the group, then blind

Agree on an identifier type and canonical byte encoding first. Leading zeros may matter in an account identifier. Case folding may be appropriate for one field and incorrect for another. Include a protocol and identifier-domain label in the encoding. Deduplicate each input: repeated records change the functionality and can leak multiplicities.

Let $G$ be a prime-order group of order $q$ in which the relevant decisional Diffie–Hellman (DDH) assumption is appropriate. The notation is multiplicative; on an elliptic curve, $U^a$ denotes scalar multiplication $a\cdot U$. Use independent, fresh nonzero scalars $a,b\in\mathbb Z_q^*$, not the long-term signing keys from other chapters. Define

This is a hash-to-group map modelled as a random oracle in the teaching protocol. It must not reveal a known discrete logarithm of the output. For an elliptic-curve instantiation, start from a suitable RFC 9380 hash-to-curve suite, including its domain separation and subgroup rules, and specify handling of the negligible identity-output case. Do not substitute the defective replacement $\mathcal{H}_{\mathrm{bad}}(x)=g^{\H(x)}$ with a publicly computable scalar $\H(x)$.

Why does that substitution matter? If Bob sends $g^{b\cdot\H(t)}$ and Alice knows a matching candidate $t$ with nonzero $\H(t)$, she can compute $(g^{b\cdot\H(t)})^{\H(t)^{-1}}=g^b$. She can then test further dictionary candidates locally. The scalar hash is not the problem: the defective point map exposes the scalar relation to the generator. This is an algebraic failure of the encoding, not a reason to avoid properly defined hash-to-group. Likewise, a group with easy DDH, for example one equipped with a suitable symmetric pairing, cannot inherit a DDH-based privacy argument merely because its discrete logarithms are hard.

Message-by-message PSI flow

The following semi-honest commutative-blinding protocol is the DH-style private-matching approach: each element supplies its own group base, rather than every operation starting at one fixed generator. Agrawal, Evfimievski and Srikant, Information Sharing Across Private Databases, SIGMOD 2003, §§3 and 5, develops both intersection and intersection-size protocols in this family. Its publication record identifies the original reference.

Alice randomly orders her local list before sending it and retains its input-to-position map. The indices below refer to this order, not to a meaningful database order such as a ranking of patients or transactions.

The correctness calculation is

Multiplication of scalars commutes. Since $a\cdot b\ne0$ modulo $q$, exponentiation by $a\cdot b$ is a bijection on $G$. Thus $C_i=D_j$ exactly when $\H_G(s_i)=\H_G(t_j)$, and hence, except for hash collisions, when $s_i=t_j$. The equality calculation proves correctness, not the whole privacy theorem. Privacy also relies on the group and random-oracle assumptions and on following the specified message flow.

The group work and communication are linear in $r+s$; token lookup can use a hash table or sorting. Raw exponentiation is neither authenticated encryption nor a complete defence against an actively cheating participant. Use an authenticated channel and a protocol with the required malicious-security guarantees when inconsistent scalars, invalid group elements or dishonest datasets are in scope.

11 / Security in Cloud ComputingPSI-cardinality: count without releasing the matches

For the same example, PSI-cardinality authorises the number $2$, not the two identifiers. The public input sizes are $3$ and $4$ if the protocol leaks sizes. A private union count can then be derived as $3+4-2=5$. If the union is nonempty, the Jaccard similarity is $2/5$. For two empty sets, specify a convention separately rather than dividing by zero.

A specialised DH protocol with server-side shuffling

The central reference is De Cristofaro, Gasti and Tsudik, Fast and Private Computation of Cardinality of Set Intersection and Union, CANS 2012, pp. 218–231. Use the corrected full text, Figure 1 and §4. The authors' revision note records the hash-to-group correction identified by Tan and Lv. The historical publication date must not be taken to mean that an uncorrected parameter or hash definition should be copied.

Retain $S,T,G,q,a,b$ from the PSI chapter. Also define a separately domain-separated token hash $\mathcal D_{\rm tok}:\{0,1\}^*\to\{0,1\}^{2\lambda}$ for security parameter $\lambda$, applied to canonical group encodings. Bob chooses independent secret uniform permutations $\pi$ of Alice's $r$ positions and $\tau$ of his $s$ positions. Here Bob, not Alice, shuffles the returned client values.

1. Alice blinds her set. Send $A_i=\H_G(s_i)^a$.
2. Bob reblinds and removes the positions. Return $C_\ell=A_{\pi(\ell)}^b$, without $\pi$ or the original indices.
3. Bob prepares comparison tokens. Send $V_j=\mathcal D_{\rm tok}(\H_G(t_{\tau(j)})^b)$, without the names or the intermediate group points.
4. Alice removes only her exponent. Compute $U_\ell=C_\ell^{a^{-1}}$ and $W_\ell=\mathcal D_{\rm tok}(U_\ell)$, where $a^{-1}$ is inversion modulo $q$.
5. Alice counts. Output $c_{\cap}=|\{W_\ell\}_{\ell=1}^r\cap\{V_j\}_{j=1}^s|$. Bob receives no output unless a separate policy authorises releasing the count to him.

For a returned position $\ell$, the arithmetic is

Consequently equal input elements produce equal tokens. Alice compares tokens but does not receive the map $\ell\mapsto\pi(\ell)$. Shuffling removes record-to-token correspondence; it does not remove deductions from the count. The protocol's semi-honest privacy analysis is in the random-oracle model with its stated DH assumptions. Correctness also has a negligible collision error from the two hash functions. This description does not assert malicious security for the basic Figure 1 protocol.

Which shuffle is necessary?

For the running example, Alice knows there are two matches among her three records, but should not receive which two beyond deductions available from her input, the count and other permitted information. If the count equals $|S|$, she necessarily knows that every element of $S$ is present. If $|S|=1$, the count is a membership answer. Neither is a contradiction of the cardinality-only functionality.

A complete generic route through a circuit

Here is a deliberately small, quadratic-size construction at the functionality/circuit level. It can be evaluated by a secure two-party circuit protocol; the circuit alone is not cryptography. Encode each identifier in $\ell$ bits. Alice supplies up to $r$ records, Bob up to $s$ records. Padded records have secret validity bits $\nu_i,\eta_j$ so that a dummy identifier cannot become a match. Valid identifiers within each party's set must be distinct, either enforced by the circuit or by an explicitly justified input-validation mechanism.

Let $a_{ik}$ and $b_{jk}$ be bit $k$ of the two encoded identifiers. Define equality bits $E_{ij}$, Alice's match bits $M_i$, and the final count $c_{\cap}$:

The equality work is $O(r\cdot s\cdot\ell)$. Use an output counter wide enough for the maximum possible count. The circuit releases only $c_{\cap}$, not $E_{ij}$ or $M_i$. With generic secure circuit evaluation, only the chosen output labels are decoded. With arithmetic MPC, use equivalent checked bit operations and open only the count. A proof follows by composing a secure evaluator with this correctly specified circuit, under the evaluator's security and abort model.

PSI would deliberately reveal the matching records. PSI-CA keeps those records and the match vector internal. Simply running ordinary PSI and hiding the names on screen does not undo the information already delivered to the client.

A boundary case worth testing

Let Alice choose $S=\{\mathtt{delta}\}$. The count is either $0$ or $1$, so even ideal PSI-CA answers a membership question about Bob's set. The correct response is not to label the cryptography broken. Decide whether singleton or repeated adaptive queries are allowed, whether the dataset must be committed in advance, and whether a different, possibly noisy, output is required.

Output leakage cannot be encrypted away. Fresh exponents and permutations prevent carrying stable protocol labels across sessions; they do not stop deductions from a sequence of authorised counts. Input commitments, query policy or a separately specified noisy functionality address different risks.

12 / Security in Cloud ComputingOPRF-based matching and its output boundary

An oblivious pseudorandom function lets a client obtain a keyed function value on its input without learning the key, while the server does not learn that input. RFC 9497 specifies OPRF and verifiable variants over prime-order groups. A VOPRF adds evidence that the evaluation used the specified key; it does not authenticate the truth of the client's dataset.

At the application level, suppose Bob holds a key $k$ and set $T$. Alice obtains tokens $F_k(s_i)$ through OPRF, while Bob supplies a shuffled token set for $T$. Token comparison identifies Alice's matches. Alice knows which input each OPRF invocation used, so this is a PSI composition, not a count-only protocol. It is also not a complete malicious-secure PSI construction: the OPRF alone does not enforce dataset membership, input limits or correct construction of Bob's token list.

De Cristofaro and Tsudik, Practical Private Set Intersection Protocols with Linear Complexity, Financial Cryptography 2010, is a related specialised-protocol reference. Its construction and assumptions should not be conflated with the commutative-blinding sketch or with the standardised RFC 9497 API.

Do not replace keyed tokens with a public hash of an email address or another small-domain identifier. An observer can enumerate guesses locally. Even a secure OPRF service needs a policy restricting submitted inputs: authorised online queries can still test guesses.

13 / Security in Cloud ComputingOblivious polynomial evaluation

In this course OPE means oblivious polynomial evaluation, not order-preserving encryption. The sender holds a polynomial $P(z)=\sum_{i=0}^{d}p_i\cdot z^i$ over a specified finite field. The receiver holds $\alpha$ and obtains $P(\alpha)$ without revealing $\alpha$ to the sender or learning more about the coefficients than the permitted output entails.

For example, let $P(z)=3+2\cdot z+z^2$ over $\mathbb Z_{101}$ and $\alpha=5$. The result is $P(5)=38$. Computing this value locally is elementary. Making it the only permitted information flow is the cryptographic task. Sending all coefficients solves correctness but destroys sender privacy. Sending $\alpha$ in clear destroys receiver privacy.

A readable circuit route

Horner's rule expresses evaluation as a sequence of multiply-add steps:

Execute that field-arithmetic circuit in a suitable secure-computation protocol, giving only $v_0$ to the receiver. Inputs must be range-checked or encoded as field elements according to the chosen malicious or semi-honest profile. For a Boolean garbling, modular multiplication and addition must themselves be compiled into an explicit circuit. A displayed formula is not yet an implementation of private multiplication.

This is the generic secure-circuit route. Its security comes from the chosen evaluator, not from an assumption that polynomial points are hidden in noise. The next two chapters explain the different Naor–Pinkas route: first its hiding assumption, then the protocol that combines it with OT.

Privacy allows deductions from the output. A degree-$d$ polynomial is determined by $d+1$ evaluations at distinct points. Therefore repeated permitted queries can reveal the entire polynomial without violating a per-execution ideal functionality. A service must decide how many evaluations it intends to authorise.

14 / Security in Cloud ComputingHidden polynomial points: what is assumed?

Interpolation is easy when the correct points are known. Finding useful information when those points are hidden is a different problem. This distinction motivates Naor and Pinkas's Oblivious Transfer and Polynomial Evaluation, STOC 1999, and the expanded Oblivious Polynomial Evaluation, SIAM Journal on Computing 35(5), 1254–1281, 2006. The definitions below follow the expanded author's text, §2.2, not the broken early same-coordinate variant.

A hidden constant term, not an invisible drawing

Work over a finite field $\mathbb F$. Let $k\ge1$ bound the degree of a receiver's auxiliary polynomial, let $n$ be the number of deliberately planted points, and let $m$ be an expansion factor. There are $N=n\cdot m$ transmitted points, requiring $|\mathbb F|>N$. These parameters describe this construction; $k$ is not a signing key or a security level in bits.

For a possible private input $\alpha\in\mathbb F$, generate a distribution $\mathcal D_\alpha$ as follows:

1. Choose $S(X)=\alpha+\sum_{j=1}^k u_j\cdot X^j$, with independent uniform coefficients $u_j\in\mathbb F$.
2. Choose $N$ pairwise distinct nonzero abscissas $x_i\in\mathbb F$ and a secret uniform index set $I$ of size $n$.
3. Set $y_i=S(x_i)$ for $i\in I$. At every other index choose $y_i$ independently and uniformly in $\mathbb F$.
4. Reveal the list $\mathcal D_\alpha=((x_i,y_i))_{i=1}^N$, but not $I$, $S$ or $\alpha$.

Random filler points may accidentally lie on $S$ as well; do not exclude them by a biased sampling rule. The planted points are not marked or presented as a separate contiguous block. A finite-field polynomial is not a smooth real curve whose visually nearby points can be selected by eye.

The relevant computational indistinguishability assumption says, for an appropriate asymptotic parameter family and all candidate constants $\alpha_0,\alpha_1$,

Equivalently, every probabilistic polynomial-time distinguisher $\mathcal A$ should have negligible difference

The source calls this Assumption 1. It concerns hiding $S(0)$, which will be the receiver's query. It is stronger than merely failing to reconstruct all of $S$: an algorithm could conceivably learn one bit of $S(0)$ without recovering every coefficient. Conversely, indistinguishability from a list of entirely independent random points would be a stronger statement than is required here. Do not silently replace one statement with the other.

Why parameters and the point layout matter

If $k+1$ correctly identified points are available, interpolation recovers $S$. If every transmitted point is correct, the hiding disappears. Even without labels, list-decoding algorithms recover low-degree polynomials in substantial parameter regimes. In the usual asymptotic form, more than about $\sqrt{k\cdot N}$ agreements enters the Guruswami–Sudan list-decoding regime discussed in the source. Being below that threshold does not prove security; exhaustive and other attacks still matter. The paper does not supply a modern concrete parameter recommendation for deployment.

The expanded paper also gives Assumption 2: the sender sees $n$ groups of $m$ candidate points, with one planted point in each group. This exposes more structure and requires its own assumption. All $N$ abscissas remain distinct across the groups. The grouped protocol can then use one 1-out-of-$m$ OT per group.

An early version instead reused the same abscissa for candidates within each group. Bleichenbacher and Nguyen, Noisy Polynomial Interpolation and Noisy Chinese Remaindering, EUROCRYPT 2000, analyses attacks exploiting this structure. The expanded OPE paper explicitly distinguishes its revised assumption from that early variant. This course studies the construction and its conditional proof; it does not recommend historical noisy-polynomial parameters as a production primitive.

15 / Security in Cloud ComputingOPE through hidden points, masking and OT

Here is the construction behind the assumption. The sender Bob knows $P(Y)=\sum_{j=0}^{d}p_j\cdot Y^j$, with public degree bound $d\ge1$. The receiver Alice knows $\alpha\in\mathbb F$. Capital $X,Y$ denote formal variables; $x_i,y_i$ are field elements. The auxiliary $S$ below is a polynomial, not Alice's set from the PSI chapters.

Use the expanded Naor–Pinkas text, Protocols 3.1–3.2 for this basic construction. We explain the semi-honest execution. Protecting against a malicious receiver for general $d$ needs the additional construction in the paper; OT alone does not force its chosen points to be consistent with one valid query.

Two different polynomials hide two different inputs

Alice samples $S(X)$ of degree at most $k$ subject to $S(0)=\alpha$. Set $D=k\cdot d$ and $n=D+1$. Independently, Bob samples a mask

and defines the bivariate polynomial

Alice's selected evaluations will lie on the univariate composition

Its degree is at most $D$, and its constant term is exactly the answer:

Alice hides where she wants to evaluate; Bob masks the other information in his polynomial. Alice's $S$ and Bob's $M$ serve different purposes. Omitting either changes the privacy argument.

The actual exchange

1. Hide the useful locations. Alice creates the $N=n\cdot m$ candidate pairs from the preceding chapter, with $n=D+1$ planted pairs at the secret indices $I$. She sends all pairs to Bob.
2. Evaluate candidates. Bob computes a table $z_i=Q(x_i,y_i)$. He does not know which indices are useful to Alice. This table stays with him.
3. Transfer only the useful evaluations. Run one $n$-out-of-$N$ OT over Bob's table. Alice selects $I$ and receives only the corresponding $z_i$. The OT hides the chosen indices from Bob and restricts Alice to the authorised number of entries.
4. Interpolate at zero. For $i\in I$, $z_i=Q(x_i,S(x_i))=R(x_i)$. From these $D+1$ evaluations Alice recovers $R(0)=P(\alpha)$.

The Lagrange weights at zero are public once Alice fixes her selected abscissas:

All operations, including inverses, are in $\mathbb F$. Pairwise distinct abscissas make every denominator nonzero. Excluding $x_i=0$ prevents an unmasked direct query $Q(0,y)=P(y)$ from bypassing the intended evaluation pattern.

Worked arithmetic: one answer survives the mask

Use the deliberately insecure teaching field $\mathbb Z_{101}$ with $P(Y)=3+2\cdot Y+Y^2$, $\alpha=5$, $S(X)=5+4\cdot X$, and $M(X)=7\cdot X+9\cdot X^2$. Here $d=2$, $k=1$, $D=2$, and three selected evaluations suffice. Substitution gives

The Lagrange weights at zero for $1,2,3$ are $3,-3,1$. Hence

The last display identifies the same field element; in ordinary integer arithmetic the intermediate value is $-63$, not $38$. For readability the table reveals both parties' secrets to the reader. In an execution Alice must not receive Bob's mask or the coefficients of $P$. Bob must not receive $S$, $I$ or $\alpha$. Small parameters and hand-picked points verify the algebra, not the hiding assumption.

Why learning R does not reveal P

Reconstructing $R$ is intended. Every nonconstant coefficient of $P(S(X))$ is hidden by an independent coefficient of $M$. For a fixed, honestly generated $S$, changing $P$ to any $P'$ with $P'(\alpha)=P(\alpha)$ can be absorbed by a change of mask:

The difference has degree at most $D$ and zero constant term, so $M'$ is an equally valid uniform mask. The observed $R$ is unchanged. This explains sender privacy for the honest query shape; OT prevents Alice from obtaining additional table entries that the argument did not authorise. Revealing the complete table is not an implementation of this OT step.

Receiver privacy has two separate obligations: the noisy-point distribution must hide $S(0)$, and the OT transcript must hide which entries Alice selected. Neither obligation replaces the other. A malicious Alice can choose candidates that do not come from one degree-$k$ polynomial; the basic construction can then expose a linear combination of coefficients that need not be a legitimate $P(\alpha)$. The expanded paper's Protocol 3.4 addresses that issue under its stated definition. Its private-computation notion does not by itself bind a dishonest sender to one precommitted polynomial or supply universally composable security.

The conceptual chain is now complete: OT controls which values arrive; the noisy-point assumption hides the query; the zero-constant mask hides the unwanted coefficients; interpolation recovers the authorised answer. The following chapters turn to a different tool, encrypted computation, and then to delegation and agreement among machines.

16 / Security in Cloud ComputingHomomorphic computation: what can the server evaluate?

An owner encrypts inputs, a server evaluates a permitted function on the ciphertexts, and the owner decrypts the result. For an encryption scheme with evaluation algorithm $\operatorname{Eval}$, the correctness target is

This equation is subject to the scheme's message space, permitted circuit, parameters and error bound. For approximate arithmetic, replace equality with the specified numerical accuracy. The server's ability to evaluate a function does not force it to evaluate the requested function. Confidentiality and verifiable computation are separate goals.

Boneh, Goh and Nissim give a foundational pairing-based construction supporting additions and one multiplication level. The later prime-order construction used by Herumi is a separate design. Brakerski, Gentry and Vaikuntanathan develop leveled fully homomorphic encryption. Cheon, Kim, Kim and Song introduce approximate arithmetic in CKKS. The choice is about the required function and numerical contract, not a ranking in which every more general scheme is automatically preferable.

Polynomial-based PSI is a different construction

Freedman, Nissim and Pinkas, Efficient Private Matching and Set Intersection, EUROCRYPT 2004, uses a polynomial whose roots encode a set, together with homomorphic evaluation. At the algebraic level, represent distinct identifiers by field elements and form

Membership becomes the test $P_S(t)=0$. The useful blinding identity is that $r\cdot P_S(t)+t$ equals $t$ at a root and is uniform in the field for a nonroot when $r$ is uniform. Additive homomorphism permits evaluation from encrypted coefficients using public powers of $t$ and fresh encryption randomness. The full protocol specifies encodings, randomisation and output handling so that nonmatching replies do not masquerade as identifiers.

This explains the connection between encrypted polynomial evaluation and set matching. It is not the noisy-point Naor–Pinkas OPE construction. Releasing raw evaluations of a set polynomial would also be a different functionality: sufficiently many evaluations permit interpolation and may expose the set itself.

Depth is not the number of multiplication calls

The inner product $z=\sum_{i=1}^t x_i\cdot y_i$ has multiplicative depth one: all products can be formed in parallel and then summed. The expression $(x_1\cdot y_1)\cdot x_2$ has depth two. A scheme may support a thousand first-level products but no second multiplication of an already multiplied ciphertext.

Fix bounds before encrypting. If $|x_i|\le B_x$ and $|y_i|\le B_y$, then $|z|\le t\cdot B_x\cdot B_y$. The result, not just each input, must fit the plaintext and decoding range. In approximate schemes, instead track scale and accumulated error. Modular wraparound and numerical approximation are not interchangeable explanations for an unexpected answer.

A malicious computation service

A server can return an encryption of zero, replay an earlier result or evaluate another function. An encrypted answer by itself does not certify the input set, model version or computation. Conversely, authorising arbitrary decryption requests can defeat privacy because homomorphic encryption is deliberately malleable. A complete service needs authenticated job context, input validation, a defined output policy and, where required, a separate proof of correct computation. Zero-knowledge proofs that inputs lie in a range help with that input constraint; they do not prove the whole subsequent computation.

17 / Security in Cloud ComputingHerumi's two-level encryption in WebAssembly

The relevant project is Herumi's she-wasm, built on the pairing library MCL. Its research basis is Attrapadung, Hanaoka, Mitsunari, Sakai, Shimizu and Teruya, Efficient Two-level Homomorphic Encryption in Prime-order Bilinear Groups and A Fast Implementation in WebAssembly, ASIACCS 2018, pp. 685–697. It is two-level homomorphic encryption, not arbitrary-depth FHE.

Source ciphertexts

This section uses a decryption key with two scalars $k_1,k_2\in\mathbb Z_q$, public points $K_1=k_1\cdot P$ and $K_2=k_2\cdot Q$, and fresh encryption randomness $t_1,t_2$. For small integer messages $m_1,m_2$ represented in $\mathbb Z_q$, the source ciphertexts have the form

The owner computes $S_1-k_1\cdot T_1=m_1\cdot P$ and recovers $m_1$ by a bounded discrete-logarithm search. This last step is practical only for the configured small message range. It is not an algorithm for solving arbitrary group discrete logarithms. Source ciphertext addition adds both components; fresh random encryptions of the same message need not have the same bytes.

A multiplication uses four pairings

For one ciphertext from each source group, the server computes a target ciphertext $D\in G_T^4$:

All four pairings have a $G_1$ first argument and a $G_2$ second argument. The server needs public ciphertexts, not the secret scalars. The owner cancels the randomness using

Indeed, the exponent is the product of the two unmasked source exponents: $(m_1+t_1\cdot k_1-t_1\cdot k_1)\cdot(m_2+t_2\cdot k_2-t_2\cdot k_2)$. Bounded decoding now recovers $m_1\cdot m_2$. Multiplying target ciphertext tuples componentwise adds their plaintext products, because exponents add in $G_T$.

Run the real implementation

Open the author's browser cross-tabulation demonstration for a WebAssembly implementation, or run the accompanying local inner-product example. The example uses the published she-wasm package, fresh keys and encryptions, and checks decrypted sums and products. The library's SHE API distinguishes source addition, public scalar multiplication and ciphertext multiplication.

npm install she-wasm@1.8.0
node cloud-homomorphic-example.cjs

The file name above is the downloadable release name. Install in a separate exercise directory. This is a local educational example, not a hosted decryption service. Its small decoding range and example curve configuration are not a production security recommendation.

const left = publicKey.encG1(2);
const right = publicKey.encG2(3);
const product = she.mul(left, right);   // CipherTextGT
const twice = she.mulInt(product, 2);  // public scalar, same level
const result = secretKey.dec(twice);   // 12, within the decoding range

For $(2,4)$ and $(3,-1)$ the encrypted inner product decrypts to $2\cdot3+4\cdot(-1)=2$. Both vectors are encrypted under the same key in this example. Distinct owners' independently generated keys cannot simply be mixed. If a protocol supplies an encryption of the same claimed value in both groups, equality of those plaintexts is an additional statement to prove or trust, not a consequence of their types.

18 / Security in Cloud ComputingDelegation and proxy re-encryption

A proxy can be useful without being trusted to decrypt. Transporting a ciphertext, computing on it and changing its authorised recipient are three different operations. Homomorphic evaluation addresses the second; proxy re-encryption addresses the third.

In a proxy re-encryption interface, Alice authorises a transformation from her public key $pk_A$ to Bob's $pk_B$ by issuing a re-encryption key $rk_{A\to B}$. The intended correctness relation is

Alice creates the authorisation, the proxy transforms an eligible ciphertext, and Bob decrypts. The proxy is not given Alice's secret key. Ateniese, Fu, Green and Hohenberger study this approach for secure distributed storage. Directionality, allowed transformation levels and resistance to collusion are properties of the particular scheme, not consequences of the interface equation.

For a document service, ask four separate questions: can the proxy read the document, can it redirect it to an unauthorised recipient, can it omit or replay it, and can a former recipient retain plaintext? Revoking future transformations does not erase plaintext already obtained by Bob.

Other intermediary roles should be named precisely:

• Threshold key holders jointly approve a decryption or signature under a dedicated threshold protocol. Reconstructing the complete secret at a coordinator is a different design.
• An MPC helper holds shares and participates under a stated corruption threshold.
• A relay forwards authenticated messages but may observe timing and endpoints or withhold delivery.
• A trusted execution environment introduces hardware and attestation assumptions; it is not equivalent to a non-colluding MPC party.

None of these labels means that the intermediary can be ignored in the threat model. Record its key material, observable transcript and effect on availability.

19 / Security in Cloud ComputingByzantine agreement: consistent decisions despite faults

Imagine independent replicas of a service receiving “accept” or “reject” from a coordinator. A Byzantine coordinator may send “accept” to one replica and “reject” to another. A faulty replica may also invent messages, remain silent or equivocate. A crash stops participation; a Byzantine fault permits arbitrary behaviour.

For the designated-sender broadcast problem, require agreement among honest recipients, validity of the sender's value when the sender is honest, and termination under the network assumptions. Consensus starts with proposals from several parties and needs its own validity condition. Neither problem says that private proposals stay hidden.

What changes when messages are signed?

Lamport, Shostak and Pease distinguish synchronous oral-message and signed-message models. “Oral” does not mean unauthenticated network traffic: a receiver knows the immediate sender, but cannot transfer cryptographic evidence of what someone else said. With up to $t$ faults, the oral-message model needs $N\geq3t+1$. The paper's signed-message broadcast tolerates more faults under its synchronous round and authentication assumptions. This does not remove timing assumptions or imply the same result for arbitrary asynchronous consensus.

Consider the oral-message case $N=4$, $t=1$. Coordinator A sends a value to B, C and D; those recipients relay what they received to one another. Each honest recipient takes a majority over its three entries, using a fixed default for missing values.

Every honest recipient decides “reject”. In the other case, where A is honest and one recipient lies, the direct value from A and the report of the other honest recipient agree and form a majority. This two-round example handles one fault; it is not a general protocol obtained by repeating majority votes indefinitely.

Why waiting is part of the model

In a fully asynchronous network there is no known delay bound: an absent message may come from a failed process or a slow honest process. Fischer, Lynch and Paterson show that deterministic consensus cannot guarantee termination in every admissible asynchronous execution even with one possible crash. This is not a claim that every run fails. Systems obtain progress under additional conditions, for example eventual synchrony, or use suitable randomised protocols. A timeout is an operational suspicion, not a proof of Byzantine behaviour.

Membership before voting

Peer-to-peer connectivity does not supply trustworthy voting identities. Counting connections allows one adversary to create many apparent voters, a Sybil attack. A fixed consortium can define authorised member keys and reconfiguration rules. An open system needs an explicit mechanism governing voting power. Signatures authenticate votes by keys; they do not establish that those keys represent independent people.

20 / Security in Cloud ComputingQuorums, certificates and replicated services

Let $N$ be the number of replicas, $t$ the maximum faulty replicas, and $Q$ the required number of distinct authenticated voters in a certificate. Two sets of size $Q$ in the same membership epoch overlap in at least $2Q-N$ members. To force an honest member into that overlap, require

To form a certificate even when all faulty replicas withhold votes, also require $Q\leq N-t$. Combining these constraints gives $N>3t$ for this quorum design. At $N=3t+1$, choosing $Q=2t+1$ meets both:

This counting argument assumes an honest replica does not endorse conflicting certificates in the relevant phase, slot and view. Across view changes, a protocol must carry forward sufficient evidence to preserve that rule. Quorum intersection alone is not a consensus protocol.

A normal-case PBFT execution

Castro and Liskov's PBFT orders requests among $3t+1$ replicas. In the normal case:

1. Pre-prepare. The primary proposes a request digest for a sequence number and view.
2. Prepare. Backups exchange matching prepares. A replica becomes prepared with the proposal and $2t$ matching prepares from distinct backups.
3. Commit. Replicas exchange commits. A prepared replica waits for $2t+1$ matching commits, counting its own, and executes in sequence.
4. Reply. The client accepts $t+1$ matching replies from distinct replicas, so at least one reply is honest.

These phases are described in the algorithm. View changes preserve the necessary evidence when the primary stops making progress. Safety does not require a fixed message-delay bound; liveness needs the additional timing conditions stated in the service model. A signature on a proposal does not replace prepare, commit or view-change logic.

For example, with four replicas and one fault, three matching commit votes form a certificate. Two votes are insufficient: certificates $\{A,B\}$ and $\{B,C\}$ could intersect only at Byzantine B, which signs both. Three-vote certificates must intersect in two replicas, at least one honest. Seven replicas tolerating two faults instead need five-vote certificates under the same design.

Combine agreement with private computation deliberately

A replicated service can agree on a session identifier, participant list, function digest, commitments to inputs and output-release policy. An MPC protocol can then compute on private inputs associated with that session. The shared log does not need the plaintext inputs. However, a hash commitment to a guessable input needs appropriate hiding; a bare hash of “yes” or “no” is not hiding.

The MPC result must be linked to the agreed session by the construction's integrity mechanism. Recording an arbitrary number in a consensus log proves that replicas agreed on that number, not that a private computation produced it correctly. Conversely, a correct private result does not ensure that every replica records it at the same position. Agreement, input privacy and computation integrity require compatible but distinct evidence.

21 / Security in Cloud ComputingAnonymous access and ring signatures

A service may need proof that a requester belongs to an authorised set without learning which member is requesting access. Let $L=(A_1,\ldots,A_n)$ be a canonical list of public keys. An anonymous identification protocol proves knowledge of a secret for an eligible key during a live session. A ring signature gives publicly verifiable evidence for a message without a live verifier.

For a simple one-of-$n$ Schnorr OR composition, each branch has a commitment $X_i$, challenge $c_i$ and response $s_i$ satisfying $g^{s_i}=X_i\cdot A_i^{c_i}$. The signer simulates the branches whose secrets it does not know. The real branch absorbs the remaining challenge so that

The proof course gives the complete teaching algorithm and extraction calculation. This OR composition is a readable entry point; it is not an assertion that all ring constructions use the same signature format. Herranz and Sáez, INDOCRYPT 2003, analyse ring-specific forking and anonymity.

One member, several secrets, or every member?

A one-of-$n$ ring signature shows that at least one eligible secret was used. A $k$-of-$n$ identification relation involves knowledge of at least $k$ eligible secrets. It does not by itself imply participation by $k$ different people: one person may know several keys. A multisignature, discussed next, has a different meaning again: a specified group jointly approves the same message.

The research paper Anonymous Deniable Identification in Ephemeral Setup and Leakage Scenarios, by Krzywiecki, Kutyłowski, Pezda and Słowik, studies an anonymous identification setting with explicit ephemeral-state concerns. The published brief announcement and the full paper should be distinguished. Deniability concerns the evidentiary meaning of a transcript; it does not mean that the verifier rejects an honest prover.

Hierarchies are not just larger rings

In hierarchical signatures, a new node may depend on earlier authenticated nodes as well as public-key leaves. A verifier must check those dependencies; the set of possible leaf signers is determined by the construction and its admissibility conditions, not by the colour of a visualised node. The hierarchical-ring-signature demo shows this functional layer with real cryptographic checks. It is linked to the 2025 paper. The demonstration's administratively known signer is not public evidence that an observer learns the signer.

22 / Security in Cloud ComputingMultisignatures and rogue-key attacks

Suppose several users must jointly approve a cloud policy update. Adding ordinary Schnorr equations suggests aggregating public keys, commitments and responses. The algebra is attractive, but naive public-key aggregation is unsafe when adversaries choose keys after seeing honest keys.

If Alice has public key $A$, an attacker can choose a known scalar $b$ and register $B=g^b\cdot A^{-1}$. The naive aggregate is $A\cdot B=g^b$, whose secret the attacker knows. It can sign alone for that aggregate even though it does not know the discrete logarithm of its registered $B$. This is a rogue-key attack on the meaning of joint approval.

MuSig addresses this issue by binding coefficients to the full public-key list. In explanatory multiplicative notation, let $L$ encode the ordered keys and define $\alpha_i=\H(\mathtt{key}\|L\|A_i)$ and $A_{\rm agg}=\prod_i A_i^{\alpha_i}$. With properly generated nonces $x_i$, commitments $X_i=g^{x_i}$ and $X=\prod_i X_i$, the partial responses have the shape

The challenge binds the aggregate key, commitment and message. These equations explain aggregation; they are not a complete signing protocol. The original three-round MuSig includes nonce commitments before nonce disclosure, together with the required checks. Nonce reuse, concurrent-session handling and premature disclosure can invalidate a protocol that still satisfies the final equation. See Maxwell, Poelstra, Seurin and Wuille.

For an implementation, pick one complete published version. Do not combine MuSig's aggregation equation with a simplified round structure or borrow a nonce rule from another variant without its proof. The local paper Multi-Signature Scheme Resistant to Randomness Injection Attacks: A Bitcoin Case is a relevant research connection because it asks what happens when the randomness interface itself is adversarial.

23 / Security in Cloud ComputingRemote possession: why an old checksum is insufficient

A server can retain a checksum after deleting a file. Returning that checksum proves neither present possession nor an ability to deliver the data. A useful audit is fresh: its unpredictable challenge forces a response tied to the stored object, its identity and its version.

The owner may authenticate individual blocks and ask for a random subset. This elementary approach is easy to reason about but its communication grows with the sample and block sizes. Homomorphic authenticators compress several block checks into one aggregate response. They must still bind the file identifier, block index and version so that valid material from another object cannot be substituted.

The original course introduces Sebé et al., Efficient Remote Data Possession Checking, Golle, Jarecki and Mironov's communication and storage complexity work, and Ateniese et al., Provable Data Possession at Untrusted Stores. Their constructions and assumptions differ. The linear pairing-based example below is a separate teaching profile, not the RSA-based Ateniese construction with its notation renamed.

What random sampling detects

Suppose $d$ of $N$ blocks are missing before the audit and $t$ distinct indices are chosen uniformly. If the server cannot fabricate an acceptable answer for a missing block, then

The numerator is zero when $t>N-d$. Sampling with replacement instead gives $1-(1-d/N)^t$. These are different experiments. A sample chosen predictably, or a server allowed to adapt the missing set after seeing the sample, does not satisfy the premise.

The model above measures coverage, not cryptographic authenticity. A real audit also needs a sound response check. Repetition improves confidence only under a specified server strategy and challenge distribution; an old passing report is not a permanent guarantee of availability.

24 / Security in Cloud ComputingA compact linear audit and retrievability

This pedagogical profile uses the homomorphic-authenticator structure associated with Shacham and Waters' compact proofs of retrievability. Fix an authenticated file identifier $fid$, a block count $N$, a version, a nonzero secret $a$, public $A_2=a\cdot Q$, and a nonidentity public point $U\in G_1$. Validate the public parameters and group encodings. Hash each index and its context to $H_i=\H_{G_1}(\mathtt{block}\|fid\|\mathrm{version}\|i)\in G_1$. Generate tags

The auditor samples indices $I$ and nonzero coefficients $\nu_i\in\mathbb Z_q^*$. The server returns one scalar and one point:

The verifier checks

To see completeness, substitute the tags into $\tau$. Distributing scalar multiplication gives $\tau=a\cdot(\sum_i\nu_i\cdot H_i+\mu\cdot U)$. Bilinearity moves the factor $a$ to the second argument, producing the verification equation. Every term before the pairing is a $G_1$ point; $\mu$ is a scalar, not a point.

Why one valid response is not the whole file

Each valid response provides a linear equation in the blocks. Collecting independent equations gives a matrix equation $V\cdot\mathbf m=\boldsymbol\mu$. Recovering all encoded blocks requires sufficient rank, not merely many copies of the same equation. A retrievability theorem must connect the prover's response success to an extractor that obtains enough information, and then to the decoding guarantees of the selected erasure code.

A single sparse audit cannot establish full rank. Nor does a signature on an aggregate prove that the server maintains a particular number of independently recoverable replicas. These are additional properties with their own models.

Privacy caveat. The displayed response exposes $\mu$, a linear combination of plaintext blocks. Repeated independent queries may reveal the blocks. This profile is not a privacy-preserving public audit. Encryption or masking changes the construction and needs its own verification and extraction argument; merely encrypting a field somewhere is not a proof of either property.

25 / Security in Cloud ComputingMulti-copy PDP: an attack and its repair

Bartosz Drzazga, Łukasz Krzywiecki and Hannes Salin, Cryptanalysis of Deterministic and Probabilistic Multi-Copy PDP Schemes For Cloud Storage: Attacks and Countermeasures, TrustCom 2021, pp. 172–179, studies a particularly useful failure mode: a verifier accepts although the server no longer retains the promised copies. The attack exploits the verification equation, not a broken pairing or a hash collision.

Below, the paper's multiplicative source-group notation is translated into the additive notation used in this course. There are $n$ copies, each with $\ell$ scalar blocks $b_{i,j}\in\mathbb Z_q$. The copy index is $i$, the block index is $j$, and $fid$ identifies the file. The secret is $a$, public key $A_2=a\cdot Q$, and $U\in G_1$ is a public nonidentity point. Indices, file identifiers and hash domains must have unambiguous encodings.

Deterministic scheme: one block can stand in for all blocks

Here the hash-to-group function itself remains proper; the flaw is the tag's missing block binding, not a defective hash primitive. The vulnerable tag uses the same point $H=\H_{G_1}(fid)$ for every block:

For challenge coefficients $r_{i,j}$, put $R=\sum_{i,j}r_{i,j}$. An honest answer contains

The vulnerable verifier checks $e(\tau,Q)=e(R\cdot H+\mu\cdot U,A_2)$. Now let a dishonest server keep only one block $b_*=b_{1,1}$ and its tag $\tau_*=\tau_{1,1}$. It responds to every challenge with

Substitution gives $\widehat\tau=a\cdot(R\cdot H+\widehat\mu\cdot U)$, so the verification equation accepts. The response need not equal the true weighted sum of the deleted blocks. The verifier has no remaining index-specific term that could distinguish them. Fresh challenges do not repair missing bindings.

There is a second algebraic warning. Two tags under the same $H$, for distinct scalars $b_1\ne b_2$, reveal

The inverse is in $\mathbb Z_q$. This does not reveal the scalar $a$, but gives a group element sufficient for manipulations that the tag design was supposed to prevent.

Probabilistic scheme: copy information disappears in a sum

The probabilistic scheme hashes the column index, $H_j=\H_{G_1}(fid\|j)$, but aggregates tags across the copies:

A challenge selects columns $J$ and weights $r_j$. The server reports per-copy responses $\mu_i=\sum_{j\in J}r_j\cdot b_{i,j}$, but the verifier uses them only through $\xi=\sum_i\mu_i$. Its equation is

A dishonest server retains only the column sums $B_j$ and aggregated tags $\tau_j$. It computes $\xi=\sum_j r_j\cdot B_j$ and invents reported copy responses whose sum is $\xi$. The check accepts. The individual copies have been replaced by a lossy representation.

What the countermeasure changes

Bind both indices in each tag:

For challenged pairs $S$, use independently sampled coefficients $r_{i,j}$ and check

The deterministic variant challenges all copy–block pairs. The probabilistic repair selects copies $I$ and columns $J$, with $S=I\times J$, and weights the individual pairs. Merely adding a copy index to the hash while keeping a check that sees only the old column sums does not establish the repaired guarantee. The tag structure, challenge and response must change together.

The retained single tag now contributes $R\cdot H_{1,1}$ instead of the required $W$. These are no longer identically equal. Likewise, a stored column sum is not enough to answer independently weighted copy–block queries. This explains why the two displayed attacks stop working; it is not a replacement for a security reduction.

The paper analyses its countermeasures under its stated $T_l$ assumption. An implementation report must retain that assumption and the specified adversary model rather than calling every pairing-based repair “secure under discrete logarithms.” Recovery also needs sufficiently many independent response equations. Neither this argument nor a passing audit proves geographically independent physical storage. The repair has a cost: individual bindings, tags and weighted hashes must be processed instead of collapsing away the copy dimension.

26 / Security in Cloud ComputingVersions, replicas and research extensions

The verifier must know which version is current. A server returning an older, correctly authenticated version has not forged its tags. Bind the version in the tag context and keep a trusted current-version record, or use an authenticated update mechanism whose freshness is independently established.

Dynamic data complicates index binding. If inserting a block shifts every later index, naively index-bound tags may all need to change. Stable block identifiers or an authenticated index structure can address this, but their roots and updates become additional trusted inputs to verification. State this cost explicitly in an implementation report.

Similarly, two server addresses do not prove two independent copies. The endpoints might consult one shared store. Replication and proof-of-storage results depend on the resource, communication or timing model. Network distance and a response deadline are operational assumptions, not consequences of a pairing equation.

The local research thread Distributed Data Possession Schemes: Blockchain-Based Scalability connects to the question of organising possession evidence at scale. Read the precise construction and model before treating its guarantees as those of another PDP or PoR scheme. An append-only log can organise commitments and order, but it cannot manufacture missing data or replace an audit's soundness argument.

Design exercise. Specify an outsourced file service with append, overwrite and delete operations. For each operation record which metadata changes, who authenticates it, which audit messages become stale and how rollback is detected. Keep confidentiality, current-version integrity, retrievability and replication as separate claims.

27 / Security in Cloud ComputingCloud forensics: evidence, acquisition and trust

Cloud forensics reconstructs events from resources whose physical infrastructure the investigator may not control. Preserving an object, authenticating its source and interpreting its meaning are different tasks. An intact log can contain an incorrect event. A valid signature on a report identifies the signing key; it does not establish that all relevant events were recorded.

NIST SP 800-201, Cloud Computing Forensic Reference Architecture, provides a framework for forensic readiness: decide what evidence can be obtained, by whom, before an incident. NISTIR 8006 catalogues cloud-specific obstacles. In practice, start with the service model. An IaaS tenant may acquire its virtual disks but not the hypervisor. In SaaS, an export API and provider records may be the principal acquisition interfaces. No permission to administer a tenant implies permission to collect another tenant's data.

Which layer supplied the evidence?

In their 2012 IaaS acquisition study, Josiah Dykstra and Alan Sherman examine the tools and trust dependencies of cloud acquisition. An in-guest collector depends on the guest it is investigating. A provider-side interface moves acquisition outside that guest, but introduces reliance on the provider and its control plane.

Their FROST prototype demonstrates this distinction in OpenStack through virtual-disk, API-log and guest-firewall-log acquisition. It is a research case study, not a claim that the historical prototype is a maintained forensic product. Its lesson is architectural: choose the collection layer deliberately, and state which potentially compromised components remain below it.

The following acquisition plan is a teaching checklist, not a promise that every provider exposes each item.

A reproducible investigation

NIST SP 800-86 separates collection, examination, analysis and reporting. Apply that separation to a small cloud incident as follows:

1. Define the question and scope. Name the affected tenant, service, resources and time window. Record the authorisation and exclusions. Do not collect unrelated personal data merely because an API permits it.
2. Preserve before investigating destructively. Record the current configuration and retention settings. Capture available volatile evidence before stopping an instance where authorised and technically possible. Record every containment action: isolation or key revocation changes the system too.
3. Acquire through documented interfaces. Keep exported content, request parameters, pagination details and provider-returned identifiers. Record failures and inaccessible intervals. An export that stopped after its first page is not a complete event history.
4. Freeze the acquired set. Compute content hashes, keep an acquisition manifest and restrict modification of the originals. Examine working copies. Record transfers of custody and recheck hashes after transfers.
5. Build a timeline with uncertainty. Retain original timestamps and time zones alongside UTC normalisation. Distinguish event time, ingestion time and acquisition time. Events closer than the clock uncertainty cannot safely be ordered by timestamp alone.
6. Report facts separately from inference. State which artefacts support each conclusion, which alternative explanations remain, and which evidence is missing. Make the analysis reproducible without exposing credentials or other tenants' content.

For example, a successful API call deleting a VM, followed by loss of application heartbeats, supports a narrower statement than “Alice destroyed the evidence.” The API record may identify a role session, while Alice's credential could have been delegated or stolen. Check the session creation, policy and application records before attributing a human action. This example is a reasoning exercise, not a forensic conclusion about a real account.

Integrity checks have a starting point

Let an evidence entry be an unambiguously encoded record $E_j$. With a collision-resistant, fixed-length bit-string digest $\mathcal D_{\rm log}$ applied to encoded records, a simple chain is

Retaining an independently authenticated checkpoint containing the final hash and entry count makes later changes detectable under the hash assumption. A chain stored only beside the evidence can be replaced with that evidence. A signature authenticates a checkpoint's origin, not the truth of each event or the absence of events omitted before signing.

CloudTrail log-file integrity validation is a concrete provider example using signed digest files. Enabling digest delivery and actually validating a delivered log set are separate steps. A successful integrity check concerns the protected files; it is not a proof that every action in the cloud was logged. Keep exported evidence and any verification material needed to repeat the check.

28 / Security in Cloud ComputingChoosing and composing the mechanisms

Start a design review at the interfaces. A garbled output label is not a field share. A target-group ciphertext from the two-level scheme cannot be fed into another pairing multiplication. A count-only service must not return the match vector. A consensus certificate must identify the membership epoch, phase and request it covers. A protocol that silently changes any of these types changes its claim.

29 / Security in Cloud ComputingLaboratory sequence and proof checkpoints

Use synthetic files and datasets. Small fields are helpful for debugging, but label them as insecure. A common implementation interface should distinguish scalars, $G_1$ points, $G_2$ points and encoded bytes. All experiments run locally; no exercise needs another person's files or credentials.

1. Oblivious transfer. Reproduce the semi-honest 1-out-of-2 teaching equations first. Show which shared group element the chosen receiver can compute. For 1-out-of-$n$, select and cite one complete original protocol rather than extrapolating the two-message diagram.
2. Garbled AND. Build the gate using a selected garbling implementation, obtain the evaluator's label through OT, and verify all four input combinations. The evaluator must not receive both labels of its private input wire. Record exactly which party learns the output.
3. Private aggregation. Reproduce the sum over $\mathbb Z_{101}$, then resample shares for the same inputs. Inspect one column at a time. Test modular wraparound, a missing share and a changed share. Explain which cases plain additive sharing cannot handle.
4. Multiplication and mask reuse. Reproduce the Beaver trace and verify that the public term is added only once. Chain two multiplications using different triples. Reuse a mask deliberately on synthetic inputs and recover the input difference from the openings.
5. Three-party MPC. Implement the private threshold decision in a selected framework profile. Keep the sum unopened. Compare a passive run with the guarantees of a malicious profile; record corruption threshold, checks, aborts, bytes and rounds. Do not describe three local processes as three independent trust domains.
6. PSI and PSI-CA. Trace both displayed DH protocols on the same synthetic sets, with a proper hash-to-group implementation. Record every message, permutation owner and local input-to-position map. In the cardinality protocol, remove Bob's shuffle of the returned client list and show that Alice can identify matching records. Compare with a count-only secure circuit. Test deduplication, empty sets, no matches, all matches, invalid group encodings and singleton queries. Treat padding and malicious input validation as additional design obligations. An observer that holds both parties' secrets is a test harness, not a participant's permitted view.
7. Polynomial evaluation and hidden points. First check Horner evaluation. Then reproduce the OPE example, including $D=k\cdot d$, selected evaluations, Lagrange weights and $R(0)$. Add random decoys at distinct nonzero abscissas; explicitly separate the sender's view, the receiver's view and the instructor's complete trace. In a tiny field, exhaustively enumerate low-degree candidate polynomials to demonstrate why a small example does not provide cryptographic hiding. Compare global $n$-out-of-$N$ selection with one selection per group. An array lookup can model ideal OT for arithmetic tests, but must not be described as a secure OT implementation. Finally explain which assumption hides $\alpha$, which mask hides $P$, and what repeated authorised evaluations reveal.
8. Encrypted inner product. Run the SHE example. Add tests for zero, negative inputs, repeated encryption, source addition and sums of products. State a bound on the result before choosing the decoding range. Show, at the API type boundary, why a target ciphertext cannot be multiplied by another encrypted input. Test incorrect returned results separately from decryption correctness.
9. Delegation review. Draw owner, proxy and recipient roles for an encrypted-document service. Select a published proxy re-encryption construction and state its directionality, ciphertext types and collusion guarantee. Test wrong recipients and explain why revocation cannot retract plaintext already delivered.
10. Byzantine messages and quorum sets. Simulate the four-replica example with authenticated sender labels, one equivocator and missing messages. Enumerate certificate intersections for $(N,t,Q)=(4,1,2),(4,1,3),(7,2,5)$. Separate this counting experiment from implementing PBFT, which also requires phase, view-change and log rules.
11. Anonymous access. Implement the one-of-$n$ OR composition or reproduce one explicitly selected original-paper identification scheme. Keep unforgeability, anonymity and leakage resistance as three separately tested or argued properties.
12. Joint signatures. Demonstrate the rogue-key attack against naive aggregation. Then reproduce one complete published multisignature variant, including nonce handling. Test mismatched key lists and attempted nonce reuse.
13. Possession baseline. Divide a synthetic file into indexed blocks. Implement random sampling and authenticated block checking. Compare measured detection frequency with the exact without-replacement formula. Include a server that has deleted a fixed fraction of blocks.
14. Linear audit. Implement the displayed pairing-based tag and aggregation equations with MCL. Test altered blocks, altered tags, wrong file identifiers, wrong versions and changed coefficients. Explain why an unmasked audit leaks linear equations.
15. Extraction experiment. On a small field, collect honest linear responses, compute matrix rank and recover the block vector only after enough independent equations. Show that repeated identical challenges do not increase rank. This illustrates linear algebra, not the full extractor theorem against an arbitrary malicious prover.
16. PDP attack and repair. Implement both attacks in the multi-copy chapter using synthetic scalar blocks. Record the state retained by the dishonest server and a passing transcript. Apply the corresponding repair, then test the same attack, wrong copy indices and changed challenge coefficients. A failed attack is a regression test, not a security proof.
17. Forensic acquisition and timeline. Create synthetic control-plane and application logs with a known clock offset, one omitted interval and one changed record. Produce an acquisition manifest, content hashes, working copies and a UTC timeline. Explain which modification your integrity checks detect and why an event absent before acquisition cannot be recovered from its hash. No real tenant or personal data is needed.