Search

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. This innovative approach holds promise for advancing the reliability and robustness of Android applications, making a valuable contribution to the field of software development.

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., Comment: IEEE Transactions on Services Computing

Large language models (LLMs) have demonstrated impressive capabilities across various NLP tasks. 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 using ChatGPT. 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 by ChatGPT, focusing on three critical aspects: correctness, complexity, and security. We also specifically investigate ChatGPT's ability to engage in multi-round fixing process (i.e., ChatGPT's dialog ability) of facilitating code generation. By delving into the generated code and examining the experimental results, this work provides valuable insights into the performance of ChatGPT in tackling code generation tasks over the three critical aspects. Overall, our findings uncover potential issues and limitations that arise in the ChatGPT-based code generation and lay the groundwork for improving AI and LLM-based code generation techniques.

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)$ have 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 {\em good} if it is possible to have $k<2^r$. The good numbers yield more efficient MVCs. Prior to this work, there are only {\em 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 {\em infinitely many} new good numbers., Comment: The Computer Journal

The problem of securely outsourcing computation to cloud servers has attracted a large amount of attention in recent years. The verifiable computation of Gennaro, Gentry, Parno (Crypto'10) allows a client to verify the server's computation of a function with substantially less time than performing the outsourced computation from scratch. In a multi-function model (Parno, Raykova, Vaikuntanathan; TCC'12) of verifiable computation, the process of encoding function and the process of preparing input are decoupled such that any client can freely submit a computation request on its input, without having to generate an encoding of the function in advance. In this paper, we propose a multi-matrix verifiable computation scheme that allows the secure outsourcing of the matrix functions over a finite field. Our scheme is outsourceable. When it is used to outsource $m$ linear functions, the scheme is roughly $m$ times faster and has less communication cost than the previously best known scheme by Fiore and Gennaro (CCS'12), both in the client-side computation and in the server-side computation. We also show the cost saving with detailed implementations., Comment: Cluster Computing-The Journal of Networks, Software Tools and Applications

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., Comment: IEEE Transactions on Cloud Computing

Outsourcing computation has gained significant popularity in recent years due to the prevalence of cloud computing. There are two main security concerns in outsourcing computation: how to guarantee the cloud server performs the computation correctly and how to keep the client's data secret. The {\em single-server verifiable computation} (SSVC) of Gennaro, Gentry and Parno (Crypto'10) enables a client to delegate the computation of a function $f$ on any input $x$ with both concerns highly relieved, but only results in {\em computationally secure} schemes that {\em lack practical efficiency}. While the SSVC schemes use a single server, in this paper we develop a {\em multi-server verifiable computation} (MSVC) model where the client shares both $f$ and $x$ among multiple servers, each server performs a set of computations on its shares, and finally the client reconstructs $f(x)$ from all servers' results. In this MSVC model we propose a generic construction for outsourcing computations of the form $F{\bf x}$, where $F$ is a matrix and $\bf x$ is a vector. Our generic construction achieves {\em information-theoretic security, input privacy} and {\em function privacy}. By optimizing the parameters, we obtain both a 3-server scheme,which uses the least number of servers, and a 4-server scheme, which incurs the least workload. By decomposing many polynomial computations as a two-stage computation, where the first-stage has the form $F{\bf x}$ and the second-stage is fast, and delegating the first-stage computation, we obtain MSVC schemes for these polynomials. We implement our MSVC schemes and show that they are among the most {\em practical} ones to date., Comment: Information and Computation

Homomorphic secret sharing (HSS) allows multiple input clients to secret-share their data among multiple servers such that each server is able to locally compute a function on its shares to obtain a partial result and all partial results enable the reconstruction of the function's value on the outsourced data by an output client. The existing HSS schemes for {\em high-degree} polynomials either {\em require a large number of servers} or {\em lack verifiability}, which is essential for ensuring the correctness of the outsourced computations. In this paper, we propose a two-server verifiable HSS (VHSS) model and construct a scheme that supports the computation of high-degree polynomials. The degree of the outsourced polynomials can be as high as a polynomial in the system's security parameter. Despite of using only 2 servers, our VHSS ensures that each single server learns no information about the outsourced data and no single server is able to persuade the client to output a wrong function value. Our VHSS is significantly more efficient. When computing degree-7 polynomials, our scheme could be 3-10 times faster than the previously best construction., Comment: Proceedings of the 23rd Information Security Conference (ISC 2020)

{\em Verifiable computation} (VC) allows a computationally weak client to outsource the evaluation of a function on many inputs to a powerful but untrusted server. The client invests a large amount of off-line computation and gives an encoding of its function to the server. The server returns both an evaluation of the function on the client's input and a proof such that the client can verify the evaluation using substantially less effort than doing the evaluation on its own. We consider how to privately outsource computations using {\em privacy preserving} VC schemes whose executions reveal no information on the client's input or function to the server. We construct VC schemes with {\em input privacy} for univariate polynomial evaluation and matrix multiplication and then extend them such that the {\em function privacy} is also achieved. Our tool is the recently developed {mutilinear maps}. The proposed VC schemes can be used in outsourcing {private information retrieval (PIR)}., Comment: 23 pages, A preliminary version appears in the 12th International Conference on Cryptology and Network Security (CANS 2013)

Baranyai's theorem is a well-known theorem 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\choose u-1}$ sub-families such that each sub-family form 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 (or equivalently, the corollary). More precisely, we propose the first purely combinatorial construction of locally decodable codes. Locally decodable codes are error-correcting codes that allow the recovery of any message bit by looking at only a few bits of the codeword. Such codes have attracted a lot of attention in recent years. We stress that our construction does not improve the parameters of known constructions. What makes it interesting is the underlying combinatorial techniques and their potential in future applications., Comment: 7 pages

\textit{Matching families} are one of the major ingredients in the construction of {\em locally decodable codes} (LDCs) and the best known constructions of LDCs with a constant number of queries are based on matching families. The determination of the largest size of any matching family in $\mathbb{Z}_m^n$, where $\mathbb{Z}_m$ is the ring of integers modulo $m$, is an interesting problem. In this paper, we show an upper bound of $O((pq)^{0.625n+0.125})$ for the size of any matching family in $\mathbb{Z}_{pq}^n$, where $p$ and $q$ are two distinct primes. Our bound is valid when $n$ is a constant, $p\rightarrow \infty$ and $p/q\rightarrow 1$. Our result improves an upper bound of Dvir {\it et al.}, Comment: 10 pages

Extended private information retrieval (EPIR) was defined by \cite{BCPT07} at CANS'07 and generalized by \cite{BC09} at AFRICACRYPT'09. In the generalized setting, EPIR allows a user to evaluate a function on a database block such that the database can learn neither which function has been evaluated nor on which block the function has been evaluated and the user learns no more information on the database blocks except for the expected result. An EPIR protocol for evaluating polynomials over a finite field $L$ was proposed by Bringer and Chabanne in \cite{BC09}. We show that the protocol does not satisfy the correctness requirement as they have claimed. In particular, we show that it does not give the user the expected result with large probability if one of the coefficients of the polynomial to be evaluated is primitive in $L$ and the others belong to the prime subfield of $L$., Comment: 23 pages

Let $m,n>1$ be integers and $\mathbb{P}_{n,m}$ be the point set of the projective $(n-1)$-space (defined by [2]) over the ring $\mathbb{Z}_m$of integers modulo $m$. Let $A_{n,m}=(a_{uv})$ be the matrix with rows and columns being labeled by elements of $\mathbb{P}_{n,m}$, where $a_{uv}=1$ if the inner product $< u,v >=0$ and $a_{uv}=0$ otherwise. Let $B_{n,m}=A_{n,m}A_{n,m}^t$. The eigenvalues of $B_{n,m}$ have been studied by [1, 2, 3], where their applications in the study of expanders and locally decodable codes were described. In this paper, we completely determine the eigenvalues of $B_{n,m}$ for general integers $m$ and $n$., Comment: 12 pages

We develop the algebraic theory behind the constructions of Yekhanin (2008) and Efremenko (2009), in an attempt to understand the ``algebraic niceness'' phenomenon in $\mathbb{Z}_m$. We show that every integer $m = pq = 2^t -1$, where $p$, $q$ and $t$ are prime, possesses the same good algebraic property as $m=511$ that allows savings in query complexity. We identify 50 numbers of this form by computer search, which together with 511, are then applied to gain improvements on query complexity via Itoh and Suzuki's composition method. More precisely, we construct a $3^{\lceil r/2\rceil}$-query LDC for every positive integer $r<104$ and a $\left\lfloor (3/4)^{51}\cdot 2^{r}\right\rfloor$-query LDC for every integer $r\geq 104$, both of length $N_{r}$, improving the $2^r$ queries used by Efremenko (2009) and $3\cdot 2^{r-2}$ queries used by Itoh and Suzuki (2010). We also obtain new efficient private information retrieval (PIR) schemes from the new query-efficient LDCs., Comment: to appear in Computational Complexity