Information Harvesting (IH) was an early data mining product from the 1990s. It was invented by Ralphe Wiggins and produced by the Ryan Corp, later Information Harvesting Inc., of Cambridge, Massachusetts. Wiggins had a background in genetic algorithms and fuzzy logic. IH sought to infer rules from sets of data. It did this first by classifying various input variables into one of a number of bins, thereby putting some structure on the continuous variables in the input. IH then proceeds to generate rules, trading off generalization against memorization, that will infer the value of the prediction variable, possibly creating many levels of rules in the process. It included strategies for checking if overfitting took place and, if so, correcting for it. Because of its strategies for correcting for overfitting by considering more data, and refining the rules based on that data, IH might also be considered to be a form of machine learning. The advantage of IH, as compared with other data mining products of its time and even later, was that it provided a mechanism for finding multiple rules that would classify the data and determining, according to set criteria, the best rules to use.
Maximum inner-product search
Maximum inner-product search (MIPS) is a search problem, with a corresponding class of search algorithms which attempt to maximise the inner product between a query and the data items to be retrieved. MIPS algorithms are used in a wide variety of big data applications, including recommendation algorithms and machine learning. Formally, for a database of vectors x i {\displaystyle x_{i}} defined over a set of labels S {\displaystyle S} in an inner product space with an inner product ⟨ ⋅ , ⋅ ⟩ {\displaystyle \langle \cdot ,\cdot \rangle } defined on it, MIPS search can be defined as the problem of determining a r g m a x i ∈ S ⟨ x i , q ⟩ {\displaystyle {\underset {i\in S}{\operatorname {arg\,max} }}\ \langle x_{i},q\rangle } for a given query q {\displaystyle q} . Although there is an obvious linear-time implementation, it is generally too slow to be used on practical problems. However, efficient algorithms exist to speed up MIPS search. Under the assumption of all vectors in the set having constant norm, MIPS can be viewed as equivalent to a nearest neighbor search (NNS) problem in which maximizing the inner product is equivalent to minimizing the corresponding distance metric in the NNS problem. Like other forms of NNS, MIPS algorithms may be approximate or exact. MIPS search is used as part of DeepMind's RETRO algorithm.
Cover (telecommunications)
In telecommunications and tradecraft, cover is the technique of concealing or altering the characteristics of communications patterns for the purpose of denying an unauthorized receiver information that would be of value. The purpose of cover is not to make the communication secure, but to make it look like noise, rendering it uninteresting and not worth analysis. Even if an attacker recognizes the communication as interesting, cover makes traffic analysis more difficult since he must crack the cover before he can find out to whom it is addressed. Usually, the covered communication is also encrypted. In this way, enemies have no idea you sent a message; friends know you sent a message, but don't know what you said; the intended recipient knows what you said. Technically, cover sometimes refers to the specific process of modulo two additions of a pseudorandom bit stream generated by a cryptographic device with bits from the control message. Source: from Federal Standard 1037C and from MIL-STD-188
Feistel cipher
In cryptography, a Feistel cipher (also known as Luby–Rackoff block cipher) is a symmetric structure used in the construction of block ciphers, named after the German-born physicist and cryptographer Horst Feistel, who did pioneering research while working for IBM; it is also commonly known as a Feistel network. A large number of block ciphers use the scheme, including the US Data Encryption Standard, the Soviet/Russian GOST (aka Magma) and the more recent Blowfish and Twofish ciphers. In a Feistel cipher, encryption and decryption are very similar operations, and both consist of iteratively running a function called a "round function" a fixed number of times. == History == Many modern symmetric block ciphers are based on Feistel networks. Feistel networks were first seen commercially in IBM's Lucifer cipher, designed by Horst Feistel and Don Coppersmith in 1973. Feistel networks gained respectability when the U.S. Federal Government adopted the DES (a cipher based on Lucifer, with changes made by the NSA) in 1976. Like other components of the DES, the iterative nature of the Feistel construction makes implementing the cryptosystem in hardware easier (particularly on the hardware available at the time of DES's design). == Design == A Feistel network uses a round function, a function which takes two inputs – a data block and a subkey – and returns one output of the same size as the data block. In each round, the round function is run on half of the data to be encrypted, and its output is XORed with the other half of the data. This is repeated a fixed number of times, and the final output is the encrypted data. An important advantage of Feistel networks compared to other cipher designs such as substitution–permutation networks (SP-networks) is that the entire operation is guaranteed to be invertible (that is, encrypted data can be decrypted), even if the round function is not itself invertible. The round function can be made arbitrarily complicated, since it does not need to be designed to be invertible. Furthermore, the encryption and decryption operations are very similar, even identical in some cases, requiring only a reversal of the key schedule. Therefore, the size of the code or circuitry required to implement such a cipher is nearly halved. Unlike SP-networks, Feistel networks also do not depend on a substitution box that could cause timing side-channels in software implementations. == Theoretical work == The structure and properties of Feistel ciphers have been extensively analyzed by cryptographers. Michael Luby and Charles Rackoff analyzed the Feistel cipher construction and proved that if the round function is a cryptographically secure pseudorandom function, with Ki used as the seed, then 3 rounds are sufficient to make the block cipher a pseudorandom permutation, while 4 rounds are sufficient to make it a "strong" pseudorandom permutation (which means that it remains pseudorandom even to an adversary who gets oracle access to its inverse permutation). Because of this very important result of Luby and Rackoff, Feistel ciphers are sometimes called Luby–Rackoff block ciphers. Further theoretical work has generalized the construction somewhat and given more precise bounds for security. == Construction details == Let F {\displaystyle \mathrm {F} } be the round function and let K 0 , K 1 , … , K n {\displaystyle K_{0},K_{1},\ldots ,K_{n}} be the sub-keys for the rounds 0 , 1 , … , n {\displaystyle 0,1,\ldots ,n} respectively. Then the basic operation is as follows: Split the plaintext block into two equal pieces: ( L 0 {\displaystyle L_{0}} , R 0 {\displaystyle R_{0}} ). For each round i = 0 , 1 , … , n {\displaystyle i=0,1,\dots ,n} , compute L i + 1 = R i , {\displaystyle L_{i+1}=R_{i},} R i + 1 = L i ⊕ F ( R i , K i ) , {\displaystyle R_{i+1}=L_{i}\oplus \mathrm {F} (R_{i},K_{i}),} where ⊕ {\displaystyle \oplus } means XOR. Then the ciphertext is ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} . Decryption of a ciphertext ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} is accomplished by computing for i = n , n − 1 , … , 0 {\displaystyle i=n,n-1,\ldots ,0} R i = L i + 1 , {\displaystyle R_{i}=L_{i+1},} L i = R i + 1 ⊕ F ( L i + 1 , K i ) . {\displaystyle L_{i}=R_{i+1}\oplus \operatorname {F} (L_{i+1},K_{i}).} Then ( L 0 , R 0 ) {\displaystyle (L_{0},R_{0})} is the plaintext again. The diagram illustrates both encryption and decryption. Note the reversal of the subkey order for decryption; this is the only difference between encryption and decryption. === Unbalanced Feistel cipher === Unbalanced Feistel ciphers use a modified structure where L 0 {\displaystyle L_{0}} and R 0 {\displaystyle R_{0}} are not of equal lengths. The Skipjack cipher is an example of such a cipher. The Texas Instruments digital signature transponder uses a proprietary unbalanced Feistel cipher to perform challenge–response authentication. The Thorp shuffle is an extreme case of an unbalanced Feistel cipher in which one side is a single bit. This has better provable security than a balanced Feistel cipher but requires more rounds. There exists Type-1, Type-2, and Type-3 Feistel networks, where the Feistel function is one fourth the size of the block but operates a varying number of times within one round. === Other uses === The Feistel construction is also used in cryptographic algorithms other than block ciphers. For example, the optimal asymmetric encryption padding (OAEP) scheme uses a simple Feistel network to randomize ciphertexts in certain asymmetric-key encryption schemes. A generalized Feistel algorithm can be used to create strong permutations on small domains of size not a power of two (see format-preserving encryption). === Feistel networks as a design component === Whether the entire cipher is a Feistel cipher or not, Feistel-like networks can be used as a component of a cipher's design. For example, MISTY1 is a Feistel cipher using a three-round Feistel network in its round function, Skipjack is a modified Feistel cipher using a Feistel network in its G permutation, and Threefish (part of Skein) is a non-Feistel block cipher that uses a Feistel-like MIX function. == List of Feistel ciphers == Feistel or modified Feistel: Generalised Feistel: CAST-256 CLEFIA MacGuffin RC2 RC6 Skipjack SMS4
Media intelligence
Media intelligence uses data mining and data science to analyze public, social and editorial media content. It refers to marketing systems that synthesize billions of online conversations into relevant information. This allow organizations to measure and manage content performance, understand trends, and drive communications and business strategy. Media intelligence can include software as a service using big data terminology. This includes questions about messaging efficiency, share of voice, audience geographical distribution, message amplification, influencer strategy, journalist outreach, creative resonance, and competitor performance in all these areas. Media intelligence differs from business intelligence in that it uses and analyzes data outside company firewalls. Examples of that data are user-generated content on social media sites, blogs, comment fields, and wikis etc. It may also include other public data sources like press releases, news, blogs, legal filings, reviews and job postings. Media intelligence may also include competitive intelligence, wherein information that is gathered from publicly available sources such as social media, press releases, and news announcements are used to better understand the strategies and tactics being deployed by competing businesses. Media intelligence is enhanced by means of emerging technologies like ambient intelligence, machine learning, semantic tagging, natural language processing, sentiment analysis and machine translation. == Technologies used == Different media intelligence platforms use different technologies for monitoring, curating content, engaging with content, data analysis and measurement of communications and marketing campaign success. These technology providers may obtain content by scraping content directly from websites or by connecting to the API provided by social media, or other content platforms that are created for 3rd party developers to develop their own applications and services that access data. Technology companies may also get data from a data reseller. Some social media monitoring and analytics companies use calls to data providers each time an end-user develops a query. Others archive and index social media posts to provide end users with on-demand access to historical data and enable methodologies and technologies leveraging network and relational data. Additional monitoring companies use crawlers and spidering technology to find keyword references, known as semantic analysis or natural language processing. Basic implementation involves curating data from social media on a large scale and analyzing the results to make sense out of it.
Human image synthesis
Human image synthesis is technology that can be applied to make believable and even photorealistic renditions of human-likenesses, moving or still. It has effectively existed since the early 2000s. Many films using computer generated imagery have featured synthetic images of human-like characters digitally composited onto the real or other simulated film material. Towards the end of the 2010s deep learning artificial intelligence has been applied to synthesize images and video that look like humans, without need for human assistance, once the training phase has been completed, whereas the old school 7D-route required massive amounts of human work. == Timeline of human image synthesis == In 1971 Henri Gouraud made the first CG geometry capture and representation of a human face. Modeling was his wife Sylvie Gouraud. The 3D model was a simple wire-frame model and he applied the Gouraud shader he is most known for to produce the first known representation of human-likeness on computer. The 1972 short film A Computer Animated Hand by Edwin Catmull and Fred Parke was the first time that computer-generated imagery was used in film to simulate moving human appearance. The film featured a computer simulated hand and face (watch film here). The 1976 film Futureworld reused parts of A Computer Animated Hand on the big screen. The 1983 music video for song Musique Non-Stop by German band Kraftwerk aired in 1986. Created by the artist Rebecca Allen, it features non-realistic looking, but clearly recognizable computer simulations of the band members. The 1994 film The Crow was the first film production to make use of digital compositing of a computer simulated representation of a face onto scenes filmed using a body double. Necessity was the muse as the actor Brandon Lee portraying the protagonist was tragically killed accidentally on-stage. In 1999 Paul Debevec et al. of USC captured the reflectance field of a human face with their first version of a light stage. They presented their method at the SIGGRAPH 2000 In 2003 audience debut of photo realistic human-likenesses in the 2003 films The Matrix Reloaded in the burly brawl sequence where up-to-100 Agent Smiths fight Neo and in The Matrix Revolutions where at the start of the end showdown Agent Smith's cheekbone gets punched in by Neo leaving the digital look-alike unnaturally unhurt. The Matrix Revolutions bonus DVD documents and depicts the process in some detail and the techniques used, including facial motion capture and limbal motion capture, and projection onto models. In 2003 The Animatrix: Final Flight of the Osiris a state-of-the-art want-to-be human likenesses not quite fooling the watcher made by Square Pictures. In 2003 digital likeness of Tobey Maguire was made for movies Spider-man 2 and Spider-man 3 by Sony Pictures Imageworks. In 2005 the Face of the Future project was an established. by the University of St Andrews and Perception Lab, funded by the EPSRC. The website contains a "Face Transformer", which enables users to transform their face into any ethnicity and age as well as the ability to transform their face into a painting (in the style of either Sandro Botticelli or Amedeo Modigliani). This process is achieved by combining the user's photograph with an average face. In 2009 Debevec et al. presented new digital likenesses, made by Image Metrics, this time of actress Emily O'Brien whose reflectance was captured with the USC light stage 5 Motion looks fairly convincing contrasted to the clunky run in the Animatrix: Final Flight of the Osiris which was state-of-the-art in 2003 if photorealism was the intention of the animators. In 2009 a digital look-alike of a younger Arnold Schwarzenegger was made for the movie Terminator Salvation though the end result was critiqued as unconvincing. Facial geometry was acquired from a 1984 mold of Schwarzenegger. In 2010 Walt Disney Pictures released a sci-fi sequel entitled Tron: Legacy with a digitally rejuvenated digital look-alike of actor Jeff Bridges playing the antagonist CLU. In SIGGGRAPH 2013 Activision and USC presented a real-time "Digital Ira" a digital face look-alike of Ari Shapiro, an ICT USC research scientist, utilizing the USC light stage X by Ghosh et al. for both reflectance field and motion capture. The end result both precomputed and real-time rendering with the modernest game GPU shown here and looks fairly realistic. In 2014 The Presidential Portrait by USC Institute for Creative Technologies in conjunction with the Smithsonian Institution was made using the latest USC mobile light stage wherein President Barack Obama had his geometry, textures and reflectance captured. In 2014 Ian Goodfellow et al. presented the principles of a generative adversarial network. GANs made the headlines in early 2018 with the deepfakes controversies. For the 2015 film Furious 7 a digital look-alike of actor Paul Walker who died in an accident during the filming was done by Weta Digital to enable the completion of the film. In 2016 techniques which allow near real-time counterfeiting of facial expressions in existing 2D video have been believably demonstrated. In 2016 a digital look-alike of Peter Cushing was made for the Rogue One film where its appearance would appear to be of same age as the actor was during the filming of the original 1977 Star Wars film. In SIGGRAPH 2017 an audio driven digital look-alike of upper torso of Barack Obama was presented by researchers from University of Washington. It was driven only by a voice track as source data for the animation after the training phase to acquire lip sync and wider facial information from training material consisting 2D videos with audio had been completed. Late 2017 and early 2018 saw the surfacing of the deepfakes controversy where porn videos were doctored using deep machine learning so that the face of the actress was replaced by the software's opinion of what another persons face would look like in the same pose and lighting. In 2018 Game Developers Conference Epic Games and Tencent Games demonstrated "Siren", a digital look-alike of the actress Bingjie Jiang. It was made possible with the following technologies: CubicMotion's computer vision system, 3Lateral's facial rigging system and Vicon's motion capture system. The demonstration ran in near real time at 60 frames per second in the Unreal Engine 4. In 2018 at the World Internet Conference in Wuzhen the Xinhua News Agency presented two digital look-alikes made to the resemblance of its real news anchors Qiu Hao (Chinese language) and Zhang Zhao (English language). The digital look-alikes were made in conjunction with Sogou. Neither the speech synthesis used nor the gesturing of the digital look-alike anchors were good enough to deceive the watcher to mistake them for real humans imaged with a TV camera. In September 2018 Google added "involuntary synthetic pornographic imagery" to its ban list, allowing anyone to request the search engine block results that falsely depict them as "nude or in a sexually explicit situation." In February 2019 Nvidia open sources StyleGAN, a novel generative adversarial network. Right after this Phillip Wang made the website ThisPersonDoesNotExist.com with StyleGAN to demonstrate that unlimited amounts of often photo-realistic looking facial portraits of no-one can be made automatically using a GAN. Nvidia's StyleGAN was presented in a not yet peer reviewed paper in late 2018. At the June 2019 CVPR the MIT CSAIL presented a system titled "Speech2Face: Learning the Face Behind a Voice" that synthesizes likely faces based on just a recording of a voice. It was trained with massive amounts of video of people speaking. Since 1 July 2019 Virginia has criminalized the sale and dissemination of unauthorized synthetic pornography, but not the manufacture., as § 18.2–386.2 titled 'Unlawful dissemination or sale of images of another; penalty.' became part of the Code of Virginia. The law text states: "Any person who, with the intent to coerce, harass, or intimidate, maliciously disseminates or sells any videographic or still image created by any means whatsoever that depicts another person who is totally nude, or in a state of undress so as to expose the genitals, pubic area, buttocks, or female breast, where such person knows or has reason to know that he is not licensed or authorized to disseminate or sell such videographic or still image is guilty of a Class 1 misdemeanor.". The identical bills were House Bill 2678 presented by Delegate Marcus Simon to the Virginia House of Delegates on 14 January 2019 and three-day later an identical Senate bill 1736 was introduced to the Senate of Virginia by Senator Adam Ebbin. Since 1 September 2019 Texas senate bill SB 751 amendments to the election code came into effect, giving candidates in elections a 30-day protection period to the elections during which making and distributing digital look-alikes or synthetic fakes of the candidates is an offense. Th
Conditional disclosure of secrets
Conditional disclosure of secrets (CDS) is a primitive, studied in information-theoretic cryptography, that allows distributed, non-communicating parties to coordinate the release of information to a third party. CDS was initially introduced for use in the context of private information retrieval, and has been related to communication complexity and non-local quantum computation. == Definition of conditional disclosure of secrets == The conditional disclosure of secrets setting involves three players; Alice, Bob and the referee. Alice receives an input x ∈ { 0 , 1 } n {\displaystyle x\in \{0,1\}^{n}} and a secret z ∈ { 0 , 1 } {\displaystyle z\in \{0,1\}} , and Bob receives a string y ∈ { 0 , 1 } n {\displaystyle y\in \{0,1\}^{n}} . A choice of Boolean function f : { 0 , 1 } 2 n → { 0 , 1 } {\displaystyle f:\{0,1\}^{2n}\rightarrow \{0,1\}} is fixed in advance and known to all players. Alice and Bob cannot communicate with one another, but share a string of random bits which we label r {\displaystyle r} . Alice and Bob compute messages m A = m A ( x , z , r ) {\displaystyle m_{A}=m_{A}(x,z,r)} and m B = m B ( y , r ) {\displaystyle m_{B}=m_{B}(y,r)} , which they send to the referee. The referee knows ( x , y ) {\displaystyle (x,y)} . A CDS protocol consists of the encoding maps applied by Alice and Bob. A protocol is said to be ϵ {\displaystyle \epsilon } -correct if, for all ( x , y ) ∈ f − 1 ( 1 ) {\displaystyle (x,y)\in f^{-1}(1)} , the referee can determine z {\displaystyle z} with probability 1 − ϵ {\displaystyle 1-\epsilon } . A protocol is said to be δ {\displaystyle \delta } -secure if, for all ( x , y ) ∈ f − 1 ( 0 ) {\displaystyle (x,y)\in f^{-1}(0)} the distribution of the messages is δ {\displaystyle \delta } close to a simulator distribution (in total variation distance), where the simulator distribution is independent of z {\displaystyle z} . The communication complexity of a CDS protocol P is the total number of bits of message sent by Alice and Bob. The CDS communication cost of a function, C D S ϵ , δ ( f ) {\displaystyle CDS_{\epsilon ,\delta }(f)} is the minimal communication cost of an ϵ {\displaystyle \epsilon } -correct, δ {\displaystyle \delta } secure protocol that implements f {\displaystyle f} . The randomness complexity and randomness cost of implementing a function in the CDS model are defined similarly, but consider the number of bits of shared random bits held by Alice and Bob. == Basic properties of the primitive == === Amplification === Supposing we have an ϵ {\displaystyle \epsilon } -correct and δ {\displaystyle \delta } -secure CDS protocol, it is known that we can find a new protocol which reduces the correctness and privacy errors at the expense of an increased communication and randomness cost. More specifically, the following theorem has been proven Theorem (Amplification). A CDS protocol for f which supports a single-bit secret with privacy and correctness error of 1/3 can be transformed into a new CDS protocol with privacy and correctness error of 2 − Ω ( k ) {\displaystyle 2^{-\Omega (k)}} and communication/randomness complexity which are larger than those of the original protocol by a multiplicative factor of O(k). In fact, somewhat more than the above theorem is true in that the size of the secret can also be made to be of length k {\displaystyle k} , while simultaneously reducing the correctness and privacy errors as above. The proof involves first encoding the secret z {\displaystyle z} into a secret sharing scheme, and then running the original CDS protocol on each share of the resulting scheme. === Closure === If a CDS protocol for a function f {\displaystyle f} is known, then certain simple modifications of f {\displaystyle f} have CDS protocols with similar efficiency. The simplest case is to consider a CDS protocol for function f {\displaystyle f} and ask for a similarly efficient protocol for the negation of f {\displaystyle f} , labelled ¬ f {\displaystyle \neg f} . This is addressed by the following theorem Theorem (CDS is closed under complement). Suppose that f has a CDS protocol with randomness cost of ρ {\displaystyle \rho } bits, communication complexity of t {\displaystyle t} bits, and privacy and correctness errors δ = ϵ = 2 − k {\displaystyle \delta =\epsilon =2^{-k}} . Then ¬ f {\displaystyle \neg f} has a CDS scheme with similar privacy and correctness errors, and randomness and communication complexity of O ( k 3 ρ 2 t + k 3 ρ 3 ) {\displaystyle O(k^{3}\rho ^{2}t+k^{3}\rho ^{3})} . The cost of a CDS protocol is also closed under formula's, in the following sense. Consider two functions f 1 {\displaystyle f_{1}} and f 2 {\displaystyle f_{2}} . Then, the communication and randomness costs of f 1 ∧ f 2 {\displaystyle f_{1}\wedge f_{2}} as well as f 1 ∨ f 2 {\displaystyle f_{1}\vee f_{2}} are not much larger than the sum of the costs for f 1 {\displaystyle f_{1}} and f 2 {\displaystyle f_{2}} . See Applebaum et al. for a precise statement. == Upper and lower bounds on communication cost == Given a function f {\displaystyle f} we would like to understand the communication and randomness costs to implement f {\displaystyle f} in the CDS setting. Towards understanding this, protocols for implementing CDS have been developed (which give an upper bound on the cost) and lower bound strategies have been developed. For most functions, there is a large gap between the known upper and lower bound, so understanding the cost of CDS remains largely an open problem. This section presents some of what is known so far about the cost of CDS. === Secret sharing based upper bound === A subject with a close relationship to CDS is secret sharing. Secret sharing constructions provide an upper bound on the cost of CDS protocols. A secret sharing scheme encodes a secret, s {\displaystyle s} into a set of shares S 1 , . . . , S n {\displaystyle S_{1},...,S_{n}} . Associated to any secret sharing scheme is an access structure, which consists of a set of authorized sets A = A 1 , . . . , A k {\displaystyle {\mathcal {A}}={A_{1},...,A_{k}}} with A i ⊆ { S 1 , . . . , S n } {\displaystyle A_{i}\subseteq \{S_{1},...,S_{n}\}} . The authorized sets are those subsets of the A i {\displaystyle A_{i}} from which it is possible to recover the secret recorded into the scheme. A succinct way to describe an access structure is in terms of a function f A : { 0 , 1 } n → { 0 , 1 } {\displaystyle f_{\mathcal {A}}:\{0,1\}^{n}\rightarrow \{0,1\}} . Each subset of the shares K [ x ] ⊂ { S 1 , . . . , S n } {\displaystyle K[x]\subset \{S_{1},...,S_{n}\}} is labelled by a string x ∈ { 0 , 1 } n {\displaystyle x\in \{0,1\}^{n}} such that x i = 1 {\displaystyle x_{i}=1} if and only if S i ∈ K {\displaystyle S_{i}\in K} . Then we define f A {\displaystyle f_{\mathcal {A}}} to be such that f A ( x ) = 1 {\displaystyle f_{\mathcal {A}}(x)=1} if and only if K [ x ] ∈ A {\displaystyle K[x]\in {\mathcal {A}}} . In words, the function f A {\displaystyle f_{\mathcal {A}}} is 1 when given an authorized subset as input, and 0 otherwise. A basic result in the theory of secret sharing is that an access structure A {\displaystyle {\mathcal {A}}} can be realized in a secret sharing scheme if and only if f A {\displaystyle f_{\mathcal {A}}} is monotone. The size of a secret sharing scheme is defined as the total number of bits in the shares S i {\displaystyle S_{i}} . For monotone functions, there is an upper bound on the communication cost in CDS for any monotone function f {\displaystyle f} in terms of the size of any secret sharing scheme with access structure given by f {\displaystyle f} , C D S ϵ = 0 , δ = 0 ( f ) ≤ S h a r i n g S i z e ( f ) {\displaystyle CDS_{\epsilon =0,\delta =0}(f)\leq SharingSize(f)} For some concrete classes of secret sharing schemes, this relationship can be extended to general (non-monotone) Boolean functions. This leads to an upper bound on CDS cost in terms of the size of any span program that computes f {\displaystyle f} , C D S ϵ = 0 , δ = 0 ( f ) ≤ S P k ( f ) {\displaystyle CDS_{\epsilon =0,\delta =0}(f)\leq SP_{k}(f)} The class of problems with efficient (polynomial size) span program is the complexity class M o d k L {\displaystyle Mod_{k}L} , so problems in this class have efficient CDS protocols. === Sub-exponential upper bounds for all functions === Using a matching vector family based construction, it has been proven that ∀ f , C D S ϵ = 0 , δ = 0 ( f ) ≤ 2 O ( n log n ) {\displaystyle \forall f,\,\,\,\,\,\,CDS_{\epsilon =0,\delta =0}(f)\leq 2^{O({\sqrt {n\log n}})}} . The technique for this proof is similar to one used to prove upper bounds on private information retrieval. This upper bound on CDS also leads to sub-exponential upper bounds on the size of a large class of secret sharing schemes. === Lower bounds from communication complexity === In a CDS protocol, the referee is given the inputs ( x , y ) {\displaystyle (x,y)} . This means it is not clear if the messages sent by Alice a