A t-private n-server Information-Theoretic Distributed Point Function ((t,n)-ITDPF) allows one to convert any point function f_{alpha,beta}(x): [N] -> G into n shares (secret keys), such that each server can compute an additive share of f_{alpha,beta}(x) with a key while any <= t servers learn absolutely no information about the function. This paper constructs a novel share conversion based on the private information retrieval (PIR) of Ghasemi, Kopparty, and Sudan (STOC 2025) and proposes a perfectly secure 1-private ITDPF with output group G = Z_p, where p can be any prime. Compared with the existing perfectly secure ITDPFs for the same output group, the proposed ITDPF is more efficient with asymptotically shorter secret keys.

Private Information Retrieval (PIR) allows clients to retrieve database entries without leaking retrieval indices, yet malicious servers seriously compromise retrieval correctness. Existing Authenticated PIR (APIR) schemes resist selective-failure attacks but rely on computational hardness assumptions. In contrast, information-theoretic PIR with Result Verification (itPIR-RV) achieves integrity without computational assumptions, yet only provides relaxed query privacy with no defense against selective-failure attacks. This paper focuses on unconditionally secure information-theoretic APIR (itAPIR) constructions. We propose the rigorous information-theoretic security definition for itAPIR with statistical privacy against selective-failure attacks and integrity as core properties, formalize the hierarchical relation between itAPIR and itPIR-RV as a relaxed variant with identical integrity but basic query privacy, and prove a conversion theorem that valid itPIR-RV schemes can be directly upgraded to secure itAPIR with no extra overhead. Our work bridges the theoretical gap, simplifies itAPIR design, and enables quantum-resistant PIR in malicious server environments.

Abstract Authenticated private information retrieval (APIR) is the state-of-the-art error-detecting private information retrieval (ED-PIR), using Distributed Point Functions (DPFs) for subpolynomial complexity and privacy. However, its finite field structure restricts it to prime-order DPFs, leading to prohibitively large key sizes under information-theoretic settings, while its dual-DPF-key design introduces unnecessary communication overhead, limiting its practicality for large-scale deployments. This paper proposes a novel ring-based information-theoretic ED-PIR (itED-PIR) scheme that overcomes these limitations by leveraging prime-power-order information-theoretic DPFs (itDPFs). Built over a prime-power ring, the proposed scheme breaks APIR’s field-induced constraint to enable more efficient DPF utilization, significantly reducing key size growth and rendering the scheme feasible for high-security scenarios. Additionally, a single-itDPF-key design halves query-side communication overhead by eliminating APIR’s redundant dual-key setup, without compromising privacy or verifiability. Beyond immediate efficiency gains, this work establishes a lightweight, flexible framework for constructing DPF-based malicious-resilient private information retrieval, opening new avenues for privacy-preserving data retrieval in distributed storage systems and post-quantum privacy protocols.

As machine learning as a service (MLaaS) gains increasing popularity, it raises two critical challenges: privacy and verifiability. For privacy, clients are reluctant to disclose sensitive private information to access MLaaS, while model providers must safeguard their proprietary models. For verifiability, clients lack reliable mechanisms to ensure that cloud servers execute model inference correctly. Decision trees are widely adopted in MLaaS due to their popularity, interpretability, and broad applicability in domains like medicine and finance. In this context, outsourcing decision tree evaluation (ODTE) enables both clients and model providers to offload their sensitive data and decision tree models to the cloud securely. However, existing ODTE schemes often fail to address both privacy and verifiability simultaneously. To bridge this gap, we propose $\sf PVODTE$, a novel two-server private and verifiable ODTE protocol that leverages homomorphic secret sharing and a MAC-based verification mechanism. $\sf PVODTE$ eliminates the need for server-to-server communication, enabling independent computation by each cloud server. This ``non-interactive'' setting addresses the latency and synchronization bottlenecks of prior arts, making it uniquely suitable for wide-area network (WAN) deployments. To our knowledge, $\sf PVODTE$ is the first two-server ODTE protocol that eliminates server-to-server communication. Furthermore, $\sf PVODTE$ achieves security against \emph{malicious} servers, where servers cannot learn anything about the client's input or the providers' decision tree models, and servers cannot alter the inference result without being detected.

XML configurations are integral to the Android development framework, particularly in the realm of UI display. However, these configurations can introduce compatibility issues (bugs), resulting in divergent visual outcomes and system crashes across various Android API versions (levels). In this study, we systematically investigate LLM-based approaches for detecting and repairing configuration compatibility bugs. Our findings highlight certain limitations of LLMs in effectively identifying and resolving these bugs, while also revealing their potential in addressing complex, hard-to-repair issues that traditional tools struggle with. Leveraging these insights, we introduce the LLM-CompDroid framework, which combines the strengths of LLMs and traditional tools for bug resolution. Our experimental results demonstrate a significant enhancement in bug resolution performance by LLM-CompDroid, with LLM-CompDroid-GPT-3.5 and LLM-CompDroid-GPT-4 surpassing the state-of-the-art tool, ConfFix, by at least 9.8% and 10.4% in both Correct and Correct@k metrics, respectively. In addition, our real-world evaluation shows that LLM-CompDroid successfully repairs 21 configuration compatibility bugs with a 100% success rate, demonstrating its practical utility. This innovative approach holds promise for advancing the reliability and robustness of Android applications, making a valuable contribution to the field of software development.

Homomorphic secret sharing (HSS) allows multiple input clients to secretly share their private inputs to a function among several servers such that each server can homomorphically compute the function over its share to produce a share of the function's output. In HSS-enabled applications such as secure multi-party computation (MPC), security requires that the output shares leak no more information about the inputs than the function output. Such security is ensured by the context-hiding property of HSS. The typical rerandomization technique achieves context hiding but increases the share size. To address this, we formalize the context-hiding property of HSS for individual functions, examine the context-hiding property of Shamir-based HSS for monomials, and extend the study to polynomials.

Federated learning, as a solution to address the increasingly severe data isolation problem, holds great promise. However, it faces two significant security challenges: how to ensure the data privacy of participants and how to guarantee the correctness of the aggregation results. In addition, existing secure federated learning schemes have their limitations and drawbacks. Some schemes cannot handle participant dropouts, and others do not consider the privacy of the global model. Moreover, they all rely on a trusted authority, resulting in impracticality. To address these challenges, we introduce TSVFL, a two-server verifiable and privacy-preserving federated learning scheme. It tolerates participant dropouts during the training process and enables secure federated learning model training without needing a trusted authority. Comprehensive security analysis demonstrates that TSVFL effectively protects the data privacy of participants against various potential inference attacks and ensures training integrity. Furthermore, extensive experiments on real-world datasets confirm that TSVFL achieves lossless accuracy and practical performance.

In this paper, we propose a new matrix commitment scheme that allows one to commit to any matrix and open any subset of the matrix entries. The proposed scheme is a vector commitment (VC) scheme that supports subvector opening, if we interpret the matrix as a vector. It gives the first VC scheme that is maintainable and incrementally aggregatable, and has constant-size public parameters. We implement the proposed scheme with groups of hidden orders that require a trusted setup. The experimental results show that it is around 1000 times faster in setup or 10 times faster in committing/opening than the existing schemes that are most relevant. With these interesting features, our scheme can significantly reduce the storage cost and result in meaningful applications in the domain of stateless cryptocurrencies and other data-intensive systems that require secure and verifiable storage solutions.

A$k-\mathbf{server}$verifiable computation (VC) scheme allows a client to outsource a computation$F(x)$to$k$servers, receive a partial result from each server, efficiently reconstruct$F(x)$from the partial results and then verify its correctness. Such a scheme is$t-\mathbf{private}$if no collusion of$t$servers can learn information about the client's input$x$and$t-\mathbf{secure}$if no collusion of$t$servers can mislead the client into outputting a wrong value by supplying wrong partial results. In a publicly verifiable scheme, the verifier, may be different from the client and unexpectedly learn too much information about$x$from the$k$partial results. We say that a publicly verifiable scheme is context-hiding if the verifier cannot learn more information about$x$from the partial results than what$F(x)$trivially implies. In this paper, we formally define the context-hiding property and show that some existing schemes do not satisfy this property. We also design a new$k-\mathbf{server}$VC scheme that is information-theoretically$t- \mathbf{private}$, computationally$t-\mathbf{secure}$and context-hiding.

Private Information Retrieval (PIR) protocols allow a client to retrieve any file of interest while keeping the files identity hidden from the database servers. While many existing PIR protocols assume servers to be honest but curious, we investigate the scenario of dishonest servers that provide incorrect answers to mislead clients into obtaining wrong results. We propose a unified framework for polynomial PIR protocols encompassing various existing protocols that optimize the download rate or total communication cost. We introduce a way to transform a polynomial PIR to a verifiable one without increasing the number of involved servers by doubling the queries. The security guarantees can be information-theoretic or computational, and the verification keys can be public or private. Moreover, in one of our protocols, the ratio between the additional download overhead associated with verification and the normal download cost approaches zero as the file size goes to infinity.

Large language models (LLMs) have demonstrated impressive capabilities across various natural language processing (NLP) tasks, such as machine translation, question answering, summarization, and so on. Additionally, LLMs are also highly valuable in supporting software engineering tasks, particularly in the field of code generation. Automatic code generation is a process of automatically generating source code or executable code based on given specifications or requirements, improving developer productivity. In this study, we perform a systematic empirical assessment to the quality of code generation usingChatGPT, a recent state-of-the-art product LLM. We leverage 728 algorithm problems in five languages (i.e., C, C++, Java, Python, and JavaScript) and 18 CWEs with 54 code scenarios for the code generation task. Our evaluation encompasses a comprehensive analysis of code snippets generated byChatGPT, focusing on three critical aspects: correctness, complexity, and security. We also specifically investigateChatGPT’s ability to engage in multi-round fixing process (i.e.,ChatGPT’s dialog ability, chatting between users andChatGPTfor fixing generated buggy code) of facilitating code generation. By delving into the generated code and examining the experimental results, this work provides valuable insights into the performance ofChatGPTin tackling code generation tasks over the three critical aspects. The experimental results demonstrate that (1)ChatGPTis better at generating functionally correct code for problems before 2021 in different languages than problems after 2021 with 48.14% advantage in Accepted rate on judgment platform, butChatGPT’s ability to directly fix erroneous code with multi-round fixing process to achieve correct functionality is relatively weak; (2) the distribution of cyclomatic and cognitive complexity levels for code snippets in different languages varies. Furthermore, the multi-round fixing process withChatGPTgenerally preserves or increases the complexity levels of code snippets; (3) in algorithm scenarios with languages of C, C++, and Jave, and CWE scenarios with languages of C and Python3, the code generated byChatGPThas relevant vulnerabilities. However, the multi-round fixing process for vulnerable code snippets demonstrates promising results, with more than 89% of vulnerabilities successfully addressed; and (4) code generation may be affected byChatGPT’s non-determinism factor, resulting in variations of code snippets in functional correctness, complexity, and security. Overall, our findings uncover potential issues and limitations that arise in theChatGPT-based code generation and lay the groundwork for improving AI and LLM-based code generation techniques.

Existing Android malware detection systems primarily concentrate on detecting malware apps, leaving a gap in the research concerning the detection of malicious components in apps. In this work, we propose a novel approach to detect fine-granularity malicious components for Android apps and build a prototype called AMCDroid. For a given app, AMCDroid first models app behavior to a homogenous graph based on the call graph and code statements of the app. Then, the graph is converted to a statement tree sequence for malware detection through the AST-based Neural Network with Feature Mapping (ASTNNF) model. Finally, if the app is detected as malware, AMCDroid applies fine-granularity malicious component detection (MCD) algorithm which is based on many-objective genetic algorithm to the homogenous graph for detecting malicious component in the app adaptively. We evaluate AMCDroid on 95,134 samples. Compared with the other two state-of-the-art methods in malware detection, AMCDroid gets the highest performance on the test set with 0.9699 F1-Score, and shows better robustness in facing obfuscation. Moreover, AMCDroid is capable of detecting fine-granularity malicious components of (obfuscated) malware apps. Especially, its average F1-Score exceeds another state-of-the-art method by 50%.

An$(n,m,t)$-homomorphic secret sharing (HSS) scheme for a function family$\mathcal F$allows$n$clients to share their data$x_{1}, \ldots,x_{n}$among$m$servers and then distribute the computation of any function$f\in {\mathcal F}$to the servers such that: (i) any$t$colluding servers learn no information about the data; (ii) each server is able to compute a partial result and$f(x_{1}, \ldots,x_{n})$can be reconstructed from the servers’ partial results. HSS schemes cannot guarantee correct reconstruction, if some servers are malicious and provide wrong partial results. Recently, verifiable HSS (VHSS) has been introduced to achieve an additional property: (iii) any$t$colluding servers cannot persuade the client(s) to accept their partial results and reconstruct a wrong value. The property (iii) is usually achieved by the client verifying the servers’ partial results. A VHSS scheme is compact if the verification is substantially faster than locally computing$f(x_{1},\ldots,x_{n})$. Of the existing VHSS schemes for polynomials, some are not compact; the others are compact but impose very heavy workload on the servers, even for low degree polynomials (e.g., they are at least 4000× slower than the existing HSS schemes in order to evaluate polynomials of degree$\leq 5$, which have many applications such as privacy-preserving machine learning). In this paper, we propose both a single-client VHSS (SVHSS) model and a multi-client VHSS (MVHSS) model. Our SVHSS allows a client to use a secret key to share its data among servers; our MVHSS allows multiple clients to share their data with a public key. For any integers$m,t>0$, we constructed both an$(m,t)$-SVHSS scheme and an$(m,t)$-MVHSS scheme that satisfy the properties of (i)-(iii). Our constructions are based on level-$k$homomorphic encryptions. The$(m,t)$-SVHSS and$(m,t)$-MVHSS are compact and allow the computations of degree-$d$polynomials for$d\leq ((k+1)m-1)/t$and$d\leq ((k+1)(m-t)-1)/t$, respectively. Experiments show that our schemes are much more efficient than the existing compact VHSS for low degree polynomials. For example, to compute polynomials of degree$\leq 5$, our MVHSS scheme is at least 420× faster. By applying SVHSS and MVHSS, we may add verifiability to privacy-preserving machine learning (PPML) algorithms. Experiments show that the resulting schemes are at least 52× and 20× faster than the existing verifiable PPML schemes.

There are two main security concerns in outsourcing computations. One is how to protect the privacy of the outsourced data, and the other is how to ensure the correctness of the outsourced computations. Homomorphic secret sharing (HSS) schemes allow a client to store a set of private data on two servers and then offload a computation on the data to servers. Such schemes ensure that each individual server learns no information about the data. While HSS schemes that allow the client to use a secret key to verify the correctness of the computation results exist and relieve both security concerns, the current literature lacks apublicly verifiableHSS scheme forpolynomial evaluations. In this paper, we consider a two-server publicly verifiable HSS (PVHSS) model, where any third party can use a public key to perform verifications. We propose both a basic construction and an improved construction of PVHSS for evaluating polynomials. Our PVHSS ensures that no single server is able to learn any information about the outsourced data or persuade the verifier to accept a wrong result. We also implement the proposed scheme. For polynomials of degree ≤20, our experiments show that: (1) the proposed PVHSS is 2×-144× faster than the existing non-verifiable or privately verifiable HSS on the server-side; (2) the proposed PVHSS is friendly to resource-restricted clients and takes less than 27ms to reconstruct and verify the results.

In single-cloud storage, ciphertext-policy attribute-based encryption (CP-ABE) allows one to encrypt any data under an access structure to a cloud server, specifying what attributes are required to decrypt. In multi-cloud storage, a secret sharing scheme (SSS) allows one to split any data into multiple shares, one to a single server, and specify which subset of the servers are able to recover the data. It is an interesting problem to remove some attributes/servers but still enable the remaining attributes/servers in every authorized set to recover the data. The problem is related to the contraction problem of access structures for SSSs. In this paper, we propose a method that can efficiently transform a given SSS for an access structure to SSSs for contractions of the access structure. We show its applications in solving the attribute removal problem in the CP-ABE based single-cloud storage and the data relocating problem in multi-cloud storage. Our method results in solutions that require either less server storage or even no additional server storage.

Outsourcing computations allows the resource-constrained clients (such as, IoT devices) to offload heavy computations to powerful cloud servers. At the same time, it brings many challenges such as data privacy, result verification and fair payment. In this paper, we propose a privacy-preserving multi-function verifiable computation (MFVC) model and construct an MFVC scheme for outsourcing matrix multiplication computations (MMC), which have many real-life applications, such as machine learning. Our scheme keeps one of the matrices in MMCsemantically secureand allows apublic verificationof the server's work. In particular, the client's work isfasterthan the native MMC for square matrices of order$\geq 7000$, while the best existing scheme requires matrices of order$\geq 270000$. We also propose a smart contract-based framework that equips the proposed scheme withfair paymentproperty. By offloading the verification to the blockchain, the client's work is faster than the native MMC for square matrices of order$\geq 6000$.

Multi-key homomorphic MACs (MKHomMACs) allow multiple clients to authenticate data with their own secret keys and outsource their data together with the tags to an untrusted server. Upon receiving any user 's request of computing a function on the data, the server is able to generate both the computation result and a short tag that vouches for the correctness of the result. MKHomMACs provide a solution with minimal communication and interaction to the problem of delegating computations over outsourced data. Fiore, Mitrokotsa, Nizzardo, and Pagnin (Asiacrypt 2016) constructed a PRF-based MKHomMAC where the result verification could be as costly as the delegated computation. In this paper, we show a PRF-based MKHomMAC for quadratic arithmetic circuits such that the verification can be substantially faster than the delegated computation in an amortized setting. The efficiency improvement is achieved by using PRFs with multi-key amortized closed-form efficiency.

A b Byzantine-robust K-out-of-ℓ private information retrieval ((b, K,ℓ)-BRPIR) scheme allows a user to retrieve any item of a database from ℓ servers, even if only K out of the ℓ servers respond and at most b out of the K responding servers provide false answers. The existing BRPIR schemes require either an exponential time decoding algorithm or a communication complexity no better than O(n1/(2k-1) k ℓ log ℓ) with k=K-2b. In this paper, we show a new (b,K,ℓ)-BRPIR scheme that has both a polynomial time decoding algorithm and a communication cost of ℓ • exp(O((log n)1-over 1 r (log log n) 1 overr)) for r=log (K/(2b+1)), which is more efficient when n→ ∞.

We present Matproofs, a matrix commitment scheme that allows one to commit to any matrix and then open any subset of the matrix entries. If we encode any vector as a matrix, by committing to the matrix Matproofs may function well as a vector commitment (VC) scheme. We show that Matproofs are simultaneously concise, aggregatable, easily updatable and maintainable. With these promising features, Matproofs give solutions to payment-only stateless cryptocurrencies with lower bandwidth and computational complexity. Compared with Hyperproofs, the only existing VC scheme that is simultaneously aggregatable, easily updatable and maintainable, Matproofs achieve the additional property of conciseness. Furthermore, in the worst case, the proof aggregation and verification in Matproofs are 700x and 10x faster than Hyperproofs, respectively.

Private information retrieval (PIR) allows a client to retrieve any block xifrom a database x = x1xnsuch that i remains hidden from the database servers. PIR •protocols with unconditional privacy and sublinear (in n) communication complexity can be constructed assuming multiple honest-but-curious servers. This assumption however cannot be guaranteed in many real life scenarios such as using cloud servers as database servers. In this paper, we consider an information-theoretic PIR with result verification (PIR-RV) model where the servers may be dishonest (i.e., cheating) and provide incorrect answers but the client can detect the existence of cheating servers. We construct a 2-server PIR-RV protocol with communication complexity ${\mathcal{O}}({n^{1/2}}{\text{log }}p)$ where p is a parameter and controls the probability that the client fails to detect. Our idea may be extended to construct k-server PIR-RV protocols for k ≥ 3.

The conflicts between input privacy and efficiency in single-server non-interactive verifiable computation (NIVC) makes it interesting to consider the multi-server models of NIVC. Although the existing multi-server NIVC schemes provide meaningful improvements, they either require the servers to communicate or leave the client’s data unprotected. It has been an open problem to design multi-server NIVC with both input privacy and non-communicating servers. In this paper we define a multi-server verifiable computation (MSVC) model where the client secret-shares its input x among non-communicating servers, each server locally computes a function F to get a partial result, and finally the client reconstructs F(x) from all partial results. We construct five MSVC schemes for outsourcing low-degree polynomials and thus answer the open question for such polynomials. Our schemes are t-private such that any t servers learn no information about x. Our schemes are t-secure such that any t servers cannot persuade the client to output wrong results. The privacy and security can be either information-theoretic or computational. Comparing with the existing schemes, our servers can be at least two orders faster.

Abstract A $k$-query locally decodable code (LDC) $C$ allows one to encode any $n$-symbol message $x$ as a codeword $C(x)$ of $N$ symbols such that each symbol of $x$ can be recovered by looking at $k$ symbols of $C(x)$, even if a constant fraction of $C(x)$ has been corrupted. Currently, the best known LDCs are matching vector codes (MVCs). A modulus $m=p_1^{\alpha _1}p_2^{\alpha _2}\cdots p_r^{\alpha _r}$ may result in an MVC with $k\leq 2^r$ and $N=\exp (\exp (O((\log n)^{1-1/r} (\log \log n)^{1/r})))$. The $m$ is good if it is possible to have $k<2^r$. The good numbers yield more efficient MVCs. Prior to this work, there are only finitely many good numbers. All of them were obtained via computer search and have the form $m=p_1p_2$. In this paper, we study good numbers of the form $m=p_1^{\alpha _1}p_2^{\alpha _2}$. We show that if $m=p_1^{\alpha _1}p_2^{\alpha _2}$ is good, then any multiple of $m$ of the form $p_1^{\beta _1}p_2^{\beta _2}$ must be good as well. Given a good number $m=p_1^{\alpha _1}p_2^{\alpha _2}$, we show an explicit method of obtaining smaller good numbers that have the same prime divisors. Our approach yields infinitely many new good numbers.

Catalano and Fiore propose a scheme to transform a linearly-homomorphic encryption into a homomorphic encryption scheme capable of evaluating quadratic computations on ciphertexts. Their scheme is based on the linearly-homomorphic encryption (such as Goldwasser-Micali, Paillier and ElGamal) and need to perform large integer operation on servers. Then, their scheme have numerous computations on the servers. At the same time, their scheme cannot verify the computations and cannot evaluate more than degree-4 computations. To solve these problems, we no longer use linearly-homomorphic encryption which based on number theory assumptions. We use label and pseudorandom function to encrypt message, which significantly reduce the computations on the servers and enable us to use homomorphic MACs technology to realize verifiable computations naturally. We also extend the method to construct$d$-server schemes, which allow the client to delegate degree-$d$computations on outsourced data.

Integrated broadcast-broadband services allow viewers to simultaneously receive broadcast content over the airwaves and additional information related to the content over the Internet. This integration provides opportunities for new services to be tailored and offered to individual viewers. Viewing histories provide a rich variety of data for service providers to learn the preferences of individual viewers and fine-tune their offerings. Each person’s viewing history, however, is privacy-sensitive data and may reveal information that the viewer does not want revealed. In this paper, we propose a system that allows viewers to specify a policy that they would like to be applied to their viewing history, when shared with service providers, by using attribute-based encryption (ABE). A ciphertext is associated with a policy, and it can be decrypted only by service providers who conform to the policy. To reduce the computations of the user terminal, we develop a system with provable security that allows the encryption to be outsourced to a cloud server, without the need to trust the cloud server. To the best of our knowledge, our construction gives the first outsourcing scheme of ABE encryption that is secure against a malicious cloud server. Although our solution is described for integrated broadcast-broadband services, the architecture and results could also be used for sharing viewing histories of OTT (Over-The-Top) services such as Netflix and location histories of mobile services. We implemented our scheme and showed that it significantly reduces the computation cost of a user terminal: about one third that of the Waters’ ABE scheme.

Verifiable computation (VC) allows a client to outsource (delegate) the computation of a function f on an input x to a server and then verify the server's results with substantially less time than computing f ( x ) from scratch. The security of VC requires no efficient adversary can persuade the client to accept any wrong results. Morillo and Obrador (PST 2013) proposed three VC schemes for outsourcing the computation of polynomial functions and claimed that all schemes are secure under the decisional subgroup membership assumption. The authors show a simple attack against the security of their first scheme and then extend the attack to the other two schemes. Morillo and Obrador (PST 2013) also claimed that their third scheme keeps the client's input private under the square root assumption. The authors show that this is not true under the standard definition of input privacy. In particular, a curious server can extract the client's input x , if the x is not too large. The authors’ results show that Morillo–Obrador schemes cannot be used in the polynomial delegation.

Integrated broadcast-broadband services allow viewers to simultaneously receive broadcast content over the airwaves and additional information related to the content over the Internet. This integration provides opportunities for new services to be tailored and offered to individual viewers. Viewing histories provide a rich variety of data for service providers to learn the preferences of individual viewers and fine-tune their offerings. Each person's viewing history, however, is privacy-sensitive data and may reveal information that the viewer does not want revealed. In this paper, we propose a system that allows viewers to specify a policy that they would like to be applied to their viewing history, when shared with service providers, by using attribute-based encryption (ABE). A ciphertext is associated with a policy, and it can be decrypted only by service providers who conform to the policy. To reduce the computations of the user terminal, we develop a system with provable security that allows the encryption to be outsourced to a cloud server, without the need to trust the cloud server. Although our solution is described for integrated broadcast-broadband services, the architecture and results could also be used for sharing viewing histories of services such as Netflix. We implemented our scheme and showed that it significantly reduces the computation cost of a user terminal.

Baranyai's theorem is well known in the theory of hypergraphs. A corollary of this theorem says that one can partition the family of all u-subsets of an n-element set into (n-1;u-1) subfamilies such that each subfamily forms a partition of the n-element set, where n is divisible by u. In this paper, we present a coding-theoretic application of Baranyai's theorem. More precisely, we propose a combinatorial construction of locally decodable codes. Locally decodable codes are error-correcting codes that allow the recovery of any message symbol by looking at only a few symbols of the codeword. The number of looked codeword symbols is called query complexity. Such codes have attracted a lot of attention in recent years. The Walsh-Hadamard code is a well-known binary two-query locally decodable code of exponential length that can recover any message bit using 2 bits of the codeword. Our construction can give locally decodable codes over small finite fields for any constant query complexities. In particular, it gives a ternary two-query locally decodable code of length asymptotically shorter than the Walsh-Hadamard code.