Source author record

Ying Miao

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT math.CO Computation Machine Learning

Catalog footprint

Research overview

9works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Capacity-Achieving Private Information Retrieval Schemes from Uncoded Storage Constrained Servers with Low Sub-packetization

This paper investigates reducing sub-packetization of capacity-achieving schemes for uncoded Storage Constrained Private Information Retrieval (SC-PIR) systems. In the SC-PIR system, a user aims to retrieve one out of $K$ files from $N$ servers while revealing nothing about its identity to any individual server, in which the $K$ files are stored at the $N$ servers in an uncoded form and each server can store up to $μK$ equivalent files, where $μ$ is the normalized storage capacity of each server. We first prove that there exists a capacity-achieving SC-PIR scheme for a given storage design if and only if all the packets are stored exactly at $M\triangleq μN$ servers for $μ$ such that $M=μN\in\{2,3,\ldots,N\}$ . Then, the optimal sub-packetization for capacity-achieving linear SC-PIR schemes is characterized as the solution to an optimization problem, which is typically hard to solve because of involving indicator functions. Moreover, a new notion of array called Storage Design Array (SDA) is introduced for the SC-PIR system. With any given SDA, an associated capacity-achieving SC-PIR scheme is constructed. Next, the SC-PIR schemes that have equal-size packets are investigated. Furthermore, the optimal equal-size sub-packetization among all capacity-achieving linear SC-PIR schemes characterized by Woolsey et al. is proved to be $\frac{N(M-1)}{\gcd(N,M)}$ . Finally, by allowing unequal size of packets, a greedy SDA construction is proposed, where the sub-packetization of the associated SC-PIR scheme is upper bounded by $\frac{N(M-1)}{\gcd(N,M)}$ . Among all capacity-achieving linear SC-PIR schemes, the sub-packetization is optimal when $\min\{M,N-M\}|N$ or $M=N$ , and within a multiplicative gap $\frac{\min\{M,N-M\}}{\gcd(N,M)}$ of the optimal one otherwise. In particular, for the case $N=d\cdot M\pm1$ where $d\geq 2$ , another SDA is constructed to obtain lower sub-packetization.

preprint2020arXiv

Algebraic Manipulation Detection Codes via Highly Nonlinear Functions

In this paper, we study the relationship between algebraic manipulation detection (AMD) codes and highly nonlinear functions. As applications, on one hand, a generic construction for systematic AMD codes is introduced based on highly nonlinear functions. Systematic AMD codes with new parameters can be generated from known highly nonlinear functions. Especially, several infinite classes of optimal systematic AMD codes, some with asymptotically optimal tag size, can be constructed. On the other hand, systematic AMD codes are used to construct highly nonlinear functions. The known construction by Cramer et al. [10] for systematic AMD codes turns out to be based on a special kind of functions with high nonlinearity.

preprint2020arXiv

Median regression with differential privacy

Median regression analysis has robustness properties which make it attractive compared with regression based on the mean, while differential privacy can protect individual privacy during statistical analysis of certain datasets. In this paper, three privacy preserving methods are proposed for median regression. The first algorithm is based on a finite smoothing method, the second provides an iterative way and the last one further employs the greedy coordinate descent approach. Privacy preserving properties of these three methods are all proved. Accuracy bound or convergence properties of these algorithms are also provided. Numerical calculation shows that the first method has better accuracy than the others when the sample size is small. When the sample size becomes larger, the first method needs more time while the second method needs less time with well-matched accuracy. For the third method, it costs less time in both cases, while it highly depends on step size.

preprint2016arXiv

Bounds on Traceability Schemes

The Stinson-Wei traceability scheme (known as traceability scheme) was proposed for broadcast encryption as a generalization of the Chor-Fiat-Naor traceability scheme (known as traceability code). Cover-free family was introduced by Kautz and Singleton in the context of binary superimposed code. In this paper, we find a new relationship between a traceability scheme and a cover-free family, which strengthens the anti-collusion strength from $t$ to $t^2$ , that is, a $t$ -traceability scheme is a $t^2$ -cover-free family. Based on this interesting discovery, we derive new upper bounds for traceability schemes. By using combinatorial structures, we construct several infinite families of optimal traceability schemes which attain our new upper bounds. We also provide a constructive lower bound for traceability schemes, the size of which has the same order with our general upper bound. Meanwhile, we consider parent-identifying set system, an anti-collusion key-distributing scheme requiring weaker conditions than traceability scheme but stronger conditions than cover-free family. A new upper bound is also given for parent-identifying set systems.

preprint2015arXiv

Bounds and Constructions for $\overline{3}$ -Separable Codes with Length $3$

Separable codes were introduced to provide protection against illegal redistribution of copyrighted multimedia material. Let $\mathcal{C}$ be a code of length $n$ over an alphabet of $q$ letters. The descendant code ${\sf desc}(\mathcal{C}_0)$ of $\mathcal{C}_0 = \{{\bf c}_1, {\bf c}_2, \ldots, {\bf c}_t\} \subseteq {\mathcal{C}}$ is defined to be the set of words ${\bf x} = (x_1, x_2, \ldots,x_n)^T$ such that $x_i \in \{c_{1,i}, c_{2,i}, \ldots, c_{t,i}\}$ for all $i=1, \ldots, n$ , where ${\bf c}_j=(c_{j,1},c_{j,2},\ldots,c_{j,n})^T$ . $\mathcal{C}$ is a $\overline{t}$ -separable code if for any two distinct $\mathcal{C}_1, \mathcal{C}_2 \subseteq \mathcal{C}$ with $|\mathcal{C}_1| \le t$ , $|\mathcal{C}_2| \le t$ , we always have ${\sf desc}(\mathcal{C}_1) \neq {\sf desc}(\mathcal{C}_2)$ . Let $M(\overline{t},n,q)$ denote the maximal possible size of such a separable code. In this paper, an upper bound on $M(\overline{3},3,q)$ is derived by considering an optimization problem related to a partial Latin square, and then two constructions for $\overline{3}$ -SC $(3,M,q)$ s are provided by means of perfect hash families and Steiner triple systems.

preprint2014arXiv

Codes with the Identifiable Parent Property for Multimedia Fingerprinting

Let ${\cal C}$ be a $q$ -ary code of length $n$ and size $M$ , and ${\cal C}(i) = \{{\bf c}(i) \ | \ {\bf c}=({\bf c}(1), {\bf c}(2), \ldots, {\bf c}(n))^{T} \in {\cal C}\}$ be the set of $i$ th coordinates of ${\cal C}$ . The descendant code of a sub-code ${\cal C}^{'} \subseteq {\cal C}$ is defined to be ${\cal C}^{'}(1) \times {\cal C}^{'}(2) \times \cdots \times {\cal C}^{'}(n)$ . In this paper, we introduce a multimedia analogue of codes with the identifiable parent property (IPP), called multimedia IPP codes or $t$ -MIPPC $(n, M, q)$ , so that given the descendant code of any sub-code ${\cal C}^{'}$ of a multimedia $t$ -IPP code ${\cal C}$ , one can always identify, as IPP codes do in the generic digital scenario, at least one codeword in ${\cal C}^{'}$ . We first derive a general upper bound on the size $M$ of a multimedia $t$ -IPP code, and then investigate multimedia $3$ -IPP codes in more detail. We characterize a multimedia $3$ -IPP code of length $2$ in terms of a bipartite graph and a generalized packing, respectively. By means of these combinatorial characterizations, we further derive a tight upper bound on the size of a multimedia $3$ -IPP code of length $2$ , and construct several infinite families of (asymptotically) optimal multimedia $3$ -IPP codes of length $2$ .

preprint2014arXiv

Multimedia IPP Codes with Efficient Tracing

Binary multimedia identifiable parent property codes (binary $t$ -MIPPCs) are used in multimedia fingerprinting schemes where the identification of users taking part in the averaging collusion attack to illegally redistribute content is required. In this paper, we first introduce a binary strong multimedia identifiable parent property code (binary $t$ -SMIPPC) whose tracing algorithm is more efficient than that of a binary $t$ -MIPPC. Then a composition construction for binary $t$ -SMIPPCs from $q$ -ary $t$ -SMIPPCs is provided. Several infinite series of optimal $q$ -ary $t$ -SMIPPCs of length $2$ with $t = 2, 3$ are derived from the relationships among $t$ -SMIPPCs and other fingerprinting codes, such as $\overline{t}$ -separable codes and $t$ -MIPPCs. Finally, combinatorial properties of $q$ -ary $2$ -SMIPPCs of length $3$ are investigated, and optimal $q$ -ary $2$ -SMIPPCs of length $3$ with $q \equiv 0, 1, 2, 5 \pmod 6$ are constructed.

preprint2014arXiv

New Bounds For Frameproof Codes

Frameproof codes are used to fingerprint digital data. It can prevent copyrighted materials from unauthorized use. In this paper, we study upper and lower bounds for $w$ -frameproof codes of length $N$ over an alphabet of size $q$ . The upper bound is based on a combinatorial approach and the lower bound is based on a probabilistic construction. Both bounds can improve previous results when $q$ is small compared to $w$ , say $cq\leq w$ for some constant $c\leq q$ . Furthermore, we pay special attention to binary frameproof codes. We show a binary $w$ -frameproof code of length $N$ can not have more than $N$ codewords if $N<\binom{w+1}{2}$ .

preprint2014arXiv

Strongly Separable Codes

Binary $t$ -frameproof codes ( $t$ -FPCs) are used in multimedia fingerprinting schemes where the identification of authorized users taking part in the averaging collusion attack is required. In this paper, a binary strongly $\bar{t}$ -separable code ( $\bar{t}$ -SSC) is introduced to improve such a scheme based on a binary $t$ -FPC. A binary $\bar{t}$ -SSC has the same traceability as a binary $t$ -FPC but has more codewords than a binary $t$ -FPC. A composition construction for binary $\bar{t}$ -SSCs from $q$ -ary $\bar{t}$ -SSCs is described, which stimulates the research on $q$ -ary $\bar{t}$ -SSCs with short length. Several infinite series of optimal $q$ -ary $\bar{2}$ -SSCs of length $2$ are derived from the fact that a $q$ -ary $\bar{2}$ -SSC of length $2$ is equivalent to a $q$ -ary $\bar{2}$ -separable code of length $2$ . Combinatorial properties of $q$ -ary $\bar{2}$ -SSCs of length $3$ are investigated, and a construction for $q$ -ary $\bar{2}$ -SSCs of length $3$ is provided. These $\bar{2}$ -SSCs of length $3$ have more than $12.5\%$ codewords than $2$ -FPCs of length $3$ could have.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ying Miao

Research overview

Is this your work?

9 publications

Capacity-Achieving Private Information Retrieval Schemes from Uncoded Storage Constrained Servers with Low Sub-packetization

Algebraic Manipulation Detection Codes via Highly Nonlinear Functions

Median regression with differential privacy

Bounds on Traceability Schemes

Bounds and Constructions for $\overline{3}$ -Separable Codes with Length $3$

Codes with the Identifiable Parent Property for Multimedia Fingerprinting

Multimedia IPP Codes with Efficient Tracing

New Bounds For Frameproof Codes

Strongly Separable Codes

See the researcher in context

Building this map preview

Ying Miao

Research overview

Is this your work?

9 publications

Capacity-Achieving Private Information Retrieval Schemes from Uncoded Storage Constrained Servers with Low Sub-packetization

Algebraic Manipulation Detection Codes via Highly Nonlinear Functions

Median regression with differential privacy

Bounds on Traceability Schemes

Bounds and Constructions for 3‾\overline{3}3-Separable Codes with Length 333

Codes with the Identifiable Parent Property for Multimedia Fingerprinting

Multimedia IPP Codes with Efficient Tracing

New Bounds For Frameproof Codes

Strongly Separable Codes

See the researcher in context

Building this map preview

Bounds and Constructions for $\overline{3}$ -Separable Codes with Length $3$