Data stream management system

A data stream management system (DSMS) is a computer software system to manage continuous data streams. It is similar to a database management system (DBMS), which is, however, designed for static data in conventional databases. A DBMS also offers a flexible query processing so that the information needed can be expressed using queries. However, in contrast to a DBMS, a DSMS executes a continuous query that is not only performed once, but is permanently installed. Therefore, the query is continuously executed until it is explicitly uninstalled. Since most DSMS are data-driven, a continuous query produces new results as long as new data arrive at the system. This basic concept is similar to complex event processing so that both technologies are partially coalescing. == Functional principle == One important feature of a DSMS is the possibility to handle potentially infinite and rapidly changing data streams by offering flexible processing at the same time, although there are only limited resources such as main memory. The following table provides various principles of DSMS and compares them to traditional DBMS. == Processing and streaming models == One of the biggest challenges for a DSMS is to handle potentially infinite data streams using a fixed amount of memory and no random access to the data. There are different approaches to limit the amount of data in one pass, which can be divided into two classes. For the one hand, there are compression techniques that try to summarize the data and for the other hand there are window techniques that try to portion the data into (finite) parts. === Synopses === The idea behind compression techniques is to maintain only a synopsis of the data, but not all (raw) data points of the data stream. The algorithms range from selecting random data points called sampling to summarization using histograms, wavelets or sketching. One simple example of a compression is the continuous calculation of an average. Instead of memorizing each data point, the synopsis only holds the sum and the number of items. The average can be calculated by dividing the sum by the number. However, it should be mentioned that synopses cannot reflect the data accurately. Thus, a processing that is based on synopses may produce inaccurate results. === Windows === Instead of using synopses to compress the characteristics of the whole data streams, window techniques only look on a portion of the data. This approach is motivated by the idea that only the most recent data are relevant. Therefore, a window continuously cuts out a part of the data stream, e.g. the last ten data stream elements, and only considers these elements during the processing. There are different kinds of such windows like sliding windows that are similar to FIFO lists or tumbling windows that cut out disjoint parts. Furthermore, the windows can also be differentiated into element-based windows, e.g., to consider the last ten elements, or time-based windows, e.g., to consider the last ten seconds of data. There are also different approaches to implementing windows. There are, for example, approaches that use timestamps or time intervals for system-wide windows or buffer-based windows for each single processing step. Sliding-window query processing is also suitable to being implemented in parallel processors by exploiting parallelism between different windows and/or within each window extent. == Query processing == Since there are a lot of prototypes, there is no standardized architecture. However, most DSMS are based on the query processing in DBMS by using declarative languages to express queries, which are translated into a plan of operators. These plans can be optimized and executed. A query processing often consists of the following steps. === Formulation of continuous queries === The formulation of queries is mostly done using declarative languages like SQL in DBMS. Since there are no standardized query languages to express continuous queries, there are a lot of languages and variations. However, most of them are based on SQL, such as the Continuous Query Language (CQL), StreamSQL and ESP. There are also graphical approaches where each processing step is a box and the processing flow is expressed by arrows between the boxes. The language strongly depends on the processing model. For example, if windows are used for the processing, the definition of a window has to be expressed. In StreamSQL, a query with a sliding window for the last 10 elements looks like follows: This stream continuously calculates the average value of "price" of the last 10 tuples, but only considers those tuples whose prices are greater than 100.0. In the next step, the declarative query is translated into a logical query plan. A query plan is a directed graph where the nodes are operators and the edges describe the processing flow. Each operator in the query plan encapsulates the semantic of a specific operation, such as filtering or aggregation. In DSMSs that process relational data streams, the operators are equal or similar to the operators of the Relational algebra, so that there are operators for selection, projection, join, and set operations. This operator concept allows the very flexible and versatile processing of a DSMS. === Optimization of queries === The logical query plan can be optimized, which strongly depends on the streaming model. The basic concepts for optimizing continuous queries are equal to those from database systems. If there are relational data streams and the logical query plan is based on relational operators from the Relational algebra, a query optimizer can use the algebraic equivalences to optimize the plan. These may be, for example, to push selection operators down to the sources, because they are not so computationally intensive like join operators. Furthermore, there are also cost-based optimization techniques like in DBMS, where a query plan with the lowest costs is chosen from different equivalent query plans. One example is to choose the order of two successive join operators. In DBMS this decision is mostly done by certain statistics of the involved databases. But, since the data of a data streams is unknown in advance, there are no such statistics in a DSMS. However, it is possible to observe a data stream for a certain time to obtain some statistics. Using these statistics, the query can also be optimized later. So, in contrast to a DBMS, some DSMS allows to optimize the query even during runtime. Therefore, a DSMS needs some plan migration strategies to replace a running query plan with a new one. === Transformation of queries === Since a logical operator is only responsible for the semantics of an operation but does not consist of any algorithms, the logical query plan must be transformed into an executable counterpart. This is called a physical query plan. The distinction between a logical and a physical operator plan allows more than one implementation for the same logical operator. The join, for example, is logically the same, although it can be implemented by different algorithms like a Nested loop join or a Sort-merge join. Notice, these algorithms also strongly depend on the used stream and processing model. Finally, the query is available as a physical query plan. === Execution of queries === Since the physical query plan consists of executable algorithms, it can be directly executed. For this, the physical query plan is installed into the system. The bottom of the graph (of the query plan) is connected to the incoming sources, which can be everything like connectors to sensors. The top of the graph is connected to the outgoing sinks, which may be for example a visualization. Since most DSMSs are data-driven, a query is executed by pushing the incoming data elements from the source through the query plan to the sink. Each time when a data element passes an operator, the operator performs its specific operation on the data element and forwards the result to all successive operators. == Examples == AURORA, StreamBase Systems, Inc. Archived 23 March 2009 at the Wayback Machine Hortonworks DataFlow IBM Streams NIAGARA Query Engine NiagaraST: A Research Data Stream Management System at Portland State University Odysseus, an open source Java-based framework for Data Stream Management Systems Pipeline DB PIPES Archived 24 December 2016 at the Wayback Machine, webMethods Business Events QStream SAS Event Stream Processing SQLstream STREAM StreamGlobe StreamInsight TelegraphCQ WSO2 Stream Processor

Data classification (data management)

Data classification is the process of organizing data into categories based on attributes like file type, content, or metadata. The data is then assigned class labels that describe a set of attributes for the corresponding data sets. The goal is to provide meaningful class attributes to former less structured information, enabling organizations to manage, protect, and govern their data more effectively. Data classification can be viewed as a multitude of labels that are used to define the type of data, especially on confidentiality and integrity issues. == Approaches == Classification techniques might be used for reports generated by ERP systems or where the data includes specific personal information that is identified. Many organizations also employ context-based classification that considers factors such as data source, user identity, and application context. == Regulatory frameworks == Data classification schemes are mandated or implied by numerous regulatory frameworks that require organizations to identify, categorize, and protect sensitive information according to its level of sensitivity. The Health Insurance Portability and Accountability Act (HIPAA) Security Rule requires covered entities to conduct an accurate and thorough assessment of potential risks and vulnerabilities to the confidentiality, integrity, and availability of protected health information under 45 CFR 164.308(a)(1)(ii)(A), which necessitates classification of data to distinguish protected health information from other organizational data."Security Standards: Administrative Safeguards". U.S. Department of Health and Human Services. Retrieved April 1, 2026. The December 2024 HIPAA Security Rule notice of proposed rulemaking (90 FR 898) would mandate comprehensive technology asset inventories and require mapping of how electronic protected health information moves through an organization, formalizing data classification as an explicit compliance obligation."HIPAA Security Rule To Strengthen the Cybersecurity of Electronic Protected Health Information". Federal Register. January 6, 2025. Retrieved April 1, 2026. NIST Special Publication 800-60 provides guidelines for mapping information types to security categories, establishing a structured methodology for federal agencies to classify data and apply appropriate security controls based on the potential impact of a security breach."NIST SP 800-60 Vol. 1 Rev. 1: Guide for Mapping Types of Information and Information Systems to Security Categories". National Institute of Standards and Technology. August 2008. Retrieved April 1, 2026.

Smart-ID

Smart-ID is an electronic authentication tool developed by SK ID Solutions, an Estonian company. Users can log in to various electronic services and sign documents with an electronic signature. Smart-ID meets the European Union's eIDAS Regulation and the European Central Bank's standards for a secure authentication solution. Smart-ID is a Qualified Signature Creator Device (QSCD) that can issue a Qualified Electronic Signature (QES). The Smart-ID app is compatible with both iOS and Android devices and does not require a SIM card. By 2021, the Smart-ID application was launched in the Huawei AppGallery. As of May 2023, Smart-ID has 3,298,969 active users across the Baltic States (Latvia, Lithuania, and Estonia). Every month, the Smart-ID processes 79 million transactions. In March 2023, Smart-ID users made an exceptional 85 million transactions. == History == In November 2016, SK ID Solutions debuted the Smart-ID tool for the first time at its annual conference. In February 2017, eKool, Starman, and Tallinn Kaubamaja Grupp were the first to implement Smart-ID authentication in their e-services. In March 2017, Smart-ID was added as an authentication option to SEB bank and Swedbank's online banking in all three Baltic States. Dokobit, previously known as DigiDoc, began offering its clients the ability to use e-services using Smart-ID in April 2017. More than 100 service providers had implemented Smart-ID as an authentication solution for their services by November 2019. At its annual conference on November 8, 2018, SK ID Solutions revealed that Smart-ID had been certified as compatible with the QSCD[8] level, the highest level of qualified electronic signature in the European Union, following a rigorous certification process. As a result, the Smart-QES-level ID's electronic signature, the digital counterpart of a handwritten signature, is now available to all users who have registered with the tool. This signature is accepted by all European Union member states. On August 26, 2019, Estonian Information Systems Supervisory Authority experts reviewed Smart-ID (ISSA). Based on the methods provided in the eIDAS Regulation, the expert committee concluded that Smart-ID offers a high level of electronic identification assurance. SK ID Solutions and RIA struck an agreement in September 2019 that allows Smart-ID to authenticate Estonian state e-services via RIA's central authentication service, which is used by over 60 public authorities. Smart-ID accounts created three years ago have expired in January 2020. Therefore, renewing them and performing mandatory updates was necessary. In February 2020, SK ID Solutions announced that Smart-ID could be used to give digital signatures in the national digital signature software DigiDoc4, which up until this moment was only possible with ID cards via Mobile-ID. Users must have at least version 4.2.4.71 or later of the DigiDoc4 software installed on their computers to use this feature. Since February 2020, Smart-ID accounts can now be created with biometric information from an ID card or passport, but only by users who have previously used a Smart-ID account. Since October 2022, 13–17 years old minors in Lithuania are able to create a Smart-ID account using biometric information too. A parent or legal guardian must approve the registration. SK ID Solutions collaborated on the new solution with iProov from the United Kingdom and InnoValor from the Netherlands. TÜV Informationstechnik GmbH, a German certification company, assessed it. Since May 2023, Smart-ID can be used to submit company's annual reports in Estonia and digitally sign anything in the e-business register using your PIN2. == Overview == The Smart-ID app is available for download on Google Play and Apple's App Store. Android 4.4 and iOS 11 are the oldest supported operating system versions for Smart-ID. Smart-ID works on the premise of two-factor authentication, combining an intelligent device (something the user owns) with PINs (something the user knows). A new user must first authenticate themselves with an ID card or a mobile phone number and then confirm a PIN1 and PIN2 code, either manually or automatically produced. The first PIN is used to authenticate a person's identity when accessing e-banking or e-services, while the second PIN is used to support electronic signatures and authenticate transactions (e.g., transfers). The PIN1 code must be four digits long, while the PIN2 code must be five digits long. To log in to an e-service, the user must use Smart-ID as the authentication method and enter their unique Smart-ID user ID. A notification will open on the user's smart device where the software is installed and display a verification code. If the code matches the code presented to the user by the e-service, then the user can confirm the match by entering their PIN1 code. The user must verify the action with their PIN2 code when giving digital signatures. A Smart-ID account is valid for three years. The report can be updated, changed, and deleted at any given time, free of charge. Smart-ID is available in five languages: Estonian, Latvian, Lithuanian, Russian, and English. An international survey conducted in 2021 revealed that Smart-ID is the most reliable authentication solution in Baltic countries. In January 2023, the number of times Smart-ID was used to access State Authentication Service (TARA) in Estonia has surpassed those of Mobile-ID and ID-cards for the first time since July 2022. == Security == Smart-ID is based on Cybernetica's SplitKey authentication and digital signature platform technology, for which the company has filed a patent application. Public key cryptography, digital signature methods, and critical public infrastructures are all used in the technology. The user's PIN is not saved on the device and is only needed to decrypt the private key in the Smart-ID app. When the user inputs the PIN, the private key is cracked, and the answer is transmitted to the Smart-ID server, where a portion of the key given by the app is joined with the server's encrypted key. The app will block the user from accessing it for three hours if they input the incorrect PIN three times in a row. If this happens once again, the app will lock for 24 hours. If this happens a third time, the account will be permanently disabled. PINs cannot be changed or recovered once an account has been created. The user must create a new account if the account is permanently blocked. Smart-ID uses the Apple and Google messaging networks to notify the app when new data is saved on its servers. == Phishing == In February 2019, unknown criminals attempted to create Smart-ID accounts with stolen IDs obtained via phishing customers' text messages and website addresses, according to a monthly report by the Estonian Information System Manager in April 2019. The Latvian Information Technology Security Incident Assessment Body Cert was also notified of these intrusions on March 1. Fraudsters sent emails to potential victims pretending to be bank representatives. The mails linked users to a phishing page after redirecting them to a phony bank login page. Victims were asked to log in using their identification information and PIN1 code. The fraudsters then began the process of generating a new Smart-ID account. As a result, the victim had to input a PIN2 number, which permitted the fraudster to finish setting up a new tab with the victim's personal information. Fraudsters in Estonia were able to log in to multiple e-services utilizing Smart-ID using a Smart-ID account and the victim's data. On behalf of the victims, fraudsters also employed online banking services. Later, the Estonian Information System Manager identified several victims, some of whom had also experienced financial losses. The Estonian Information System Manager requested a full report on the event from SK ID Solutions. The organization opted not to criticize the corporation after receiving the information, although it did propose that the procedure of creating Smart-ID accounts be reviewed. According to the Estonian Banking Association, Estonian banks have not discontinued using Smart-ID and do not think it is required. Smart-ID was exposed to a thorough review process in September 2019 to determine this authentication instrument's level of security. Reviewers discovered no flaws, and SK ID Solutions and the Estonian Information System Manager signed a contract. Estonia later introduced Smart-ID and other authentication mechanisms to the central public services portal.

Cryptographic High Value Product

Cryptographic High Value Product (CHVP) is a designation used within the information security community to identify assets that have high value, and which may be used to encrypt / decrypt secure communications, but which do not retain or store any classified information. When disconnected from the secure communication network, the CHVP equipment may be handled with a lower level of controls than required for COMSEC equipment.

Knapsack problem

The knapsack problem is the following problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision-makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively. The knapsack problem has been studied for more than a century, with early works dating back to 1897. The subset sum problem is a special case of the decision and 0-1 problems where for each kind of item, the weight equals the value: w i = v i {\displaystyle w_{i}=v_{i}} . In the field of cryptography, the term knapsack problem is often used to refer specifically to the subset sum problem. The subset sum problem is one of Karp's 21 NP-complete problems. == Applications == Knapsack problems appear in real-world decision-making processes in a wide variety of fields, such as finding the least wasteful way to cut raw materials, selection of investments and portfolios, selection of assets for asset-backed securitization, and generating keys for the Merkle–Hellman and other knapsack cryptosystems. One early application of knapsack algorithms was in the construction and scoring of tests in which the test-takers have a choice as to which questions they answer. For small examples, it is a fairly simple process to provide the test-takers with such a choice. For example, if an exam contains 12 questions each worth 10 points, the test-taker need only answer 10 questions to achieve a maximum possible score of 100 points. However, on tests with a heterogeneous distribution of point values, it is more difficult to provide choices. Feuerman and Weiss proposed a system in which students are given a heterogeneous test with a total of 125 possible points. The students are asked to answer all of the questions to the best of their abilities. Of the possible subsets of problems whose total point values add up to 100, a knapsack algorithm would determine which subset gives each student the highest possible score. A 1999 study of the Stony Brook University Algorithm Repository showed that, out of 75 algorithmic problems related to the field of combinatorial algorithms and algorithm engineering, the knapsack problem was the 19th most popular and the third most needed after suffix trees and the bin packing problem. == Definition == The most common problem being solved is the 0-1 knapsack problem, which restricts the number x i {\displaystyle x_{i}} of copies of each kind of item to zero or one. Given a set of n {\displaystyle n} items numbered from 1 up to n {\displaystyle n} , each with a weight w i {\displaystyle w_{i}} and a value v i {\displaystyle v_{i}} , along with a maximum weight capacity W {\displaystyle W} , maximize ∑ i = 1 n v i x i {\displaystyle \sum _{i=1}^{n}v_{i}x_{i}} subject to ∑ i = 1 n w i x i ≤ W {\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W} and x i ∈ { 0 , 1 } {\displaystyle x_{i}\in \{0,1\}} . Here x i {\displaystyle x_{i}} represents the number of instances of item i {\displaystyle i} to include in the knapsack. Informally, the problem is to maximize the sum of the values of the items in the knapsack so that the sum of the weights is less than or equal to the knapsack's capacity. The bounded knapsack problem (BKP) removes the restriction that there is only one of each item, but restricts the number x i {\displaystyle x_{i}} of copies of each kind of item to a maximum non-negative integer value c {\displaystyle c} : maximize ∑ i = 1 n v i x i {\displaystyle \sum _{i=1}^{n}v_{i}x_{i}} subject to ∑ i = 1 n w i x i ≤ W {\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W} and x i ∈ { 0 , 1 , 2 , … , c } . {\displaystyle x_{i}\in \{0,1,2,\dots ,c\}.} The unbounded knapsack problem (UKP) places no upper bound on the number of copies of each kind of item and can be formulated as above except that the only restriction on x i {\displaystyle x_{i}} is that it is a non-negative integer. maximize ∑ i = 1 n v i x i {\displaystyle \sum _{i=1}^{n}v_{i}x_{i}} subject to ∑ i = 1 n w i x i ≤ W {\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W} and x i ∈ N . {\displaystyle x_{i}\in \mathbb {N} .} One example of the unbounded knapsack problem is given using the figure shown at the beginning of this article and the text "if any number of each book is available" in the caption of that figure. == Computational complexity == The knapsack problem is interesting from the perspective of computer science for many reasons: The decision problem form of the knapsack problem (Can a value of at least V be achieved without exceeding the weight W?) is NP-complete, thus there is no known algorithm that is both correct and fast (polynomial-time) in all cases. There is no known polynomial algorithm which can tell, given a solution, whether it is optimal (which would mean that there is no solution with a larger V). This problem is co-NP-complete. There is a pseudo-polynomial time algorithm using dynamic programming. There is a fully polynomial-time approximation scheme, which uses the pseudo-polynomial time algorithm as a subroutine, described below. Many cases that arise in practice, and "random instances" from some distributions, can nonetheless be solved exactly. There is a link between the "decision" and "optimization" problems in that if there exists a polynomial algorithm that solves the "decision" problem, then one can find the maximum value for the optimization problem in polynomial time by applying this algorithm iteratively while increasing the value of k. On the other hand, if an algorithm finds the optimal value of the optimization problem in polynomial time, then the decision problem can be solved in polynomial time by comparing the value of the solution output by this algorithm with the value of k. Thus, both versions of the problem are of similar difficulty. One theme in research literature is to identify what the "hard" instances of the knapsack problem look like, or viewed another way, to identify what properties of instances in practice might make them more amenable than their worst-case NP-complete behaviour suggests. The goal in finding these "hard" instances is for their use in public-key cryptography systems, such as the Merkle–Hellman knapsack cryptosystem. More generally, better understanding of the structure of the space of instances of an optimization problem helps to advance the study of the particular problem and can improve algorithm selection. Furthermore, notable is the fact that the hardness of the knapsack problem depends on the form of the input. If the weights and profits are given as integers, it is weakly NP-complete, while it is strongly NP-complete if the weights and profits are given as rational numbers. However, in the case of rational weights and profits it still admits a fully polynomial-time approximation scheme. === Unit-cost models === The NP-hardness of the Knapsack problem relates to computational models in which the size of integers matters (such as the Turing machine). In contrast, decision trees count each decision as a single step. Dobkin and Lipton show an 1 2 n 2 {\displaystyle {1 \over 2}n^{2}} lower bound on linear decision trees for the knapsack problem, that is, trees where decision nodes test the sign of affine functions. This was generalized to algebraic decision trees by Steele and Yao. If the elements in the problem are real numbers or rationals, the decision-tree lower bound extends to the real random-access machine model with an instruction set that includes addition, subtraction and multiplication of real numbers, as well as comparison and either division or remaindering ("floor"). This model covers more algorithms than the algebraic decision-tree model, as it encompasses algorithms that use indexing into tables. However, in this model all program steps are counted, not just decisions. An upper bound for a decision-tree model was given by Meyer auf der Heide who showed that for every n there exists an O(n4)-deep linear decision tree that solves the subset-sum problem with n items. Note that this does not imply any upper bound for an algorithm that should solve the problem for any given n. == Solving == Several algorithms are available to solve knapsack problems, based on the dynamic programming approach, the branch and bound approach or hybridizations of both approaches. === Dynamic programming in-advance algorithm === The unbounded knapsack problem (UKP) places no restriction on the number of copies of each kind of item. Besides, here we assume that x i > 0 {\displaystyle x_{i}>0} m [ w ′ ] = max ( ∑ i = 1 n v i x i ) {\displaystyle m[w']=\max \left(\sum _{i=1}^{n}v_{i}x_{i}\right)} subject to ∑

Linguatec

The Linguatec Sprachtechnologien GmbH is a language technology provider, specialized in the field of machine translation, speech synthesis and speech recognition. Linguatec was founded in Munich in 1996 and its headquarters are in Pasing. Linguatec has won the European Information Society Technologies Prize three times. On their website, they are now using the online service Voice Reader Web, so that the information can be read out in every language by means of a text-to-speech function. == Core areas == Machine translation The different versions of Personal Translator (seven language pairs) can be used "for home use" or for professional business use in the company network. In addition to this, specialist dictionaries are offered to broaden standard vocabulary. Speech synthesis The Voice Reader text-to-speech program reads in twelve languages: German, British English, American English, French, Quebec French, Spanish, Mexican Spanish, Italian, Dutch, Portuguese, Czech, Chinese. Speech recognition Voice Pro is based on ViaVoice technology from IBM. There are special software programs for doctors and lawyers. == Patents == 2005 pending patent application for a newly developed hybrid technology that uses the intelligence of neural networks for machine translation. == Awards == 2004 European IT Prize for Beyond Babel 2004 test winner Stiftung Warentest – best voice recognition 1998 European IT Prize – applied voice recognition 1996 European IT Prize – automated translation == Studies == 2005 University of Regensburg: Voice Reader user test 2002 Fraunhofer Institute for Industrial Engineering and Organization IAO: user study on the efficiency of machine translation

MDS matrix

An MDS matrix (maximum distance separable) is a matrix representing a function with certain diffusion properties that have useful applications in cryptography. Technically, an m × n {\displaystyle m\times n} matrix A {\displaystyle A} over a finite field K {\displaystyle K} is an MDS matrix if it is the transformation matrix of a linear transformation f ( x ) = A x {\displaystyle f(x)=Ax} from K n {\displaystyle K^{n}} to K m {\displaystyle K^{m}} such that no two different ( m + n ) {\displaystyle (m+n)} -tuples of the form ( x , f ( x ) ) {\displaystyle (x,f(x))} coincide in n {\displaystyle n} or more components. Equivalently, the set of all ( m + n ) {\displaystyle (m+n)} -tuples ( x , f ( x ) ) {\displaystyle (x,f(x))} is an MDS code, i.e., a linear code that reaches the Singleton bound. Let A ~ = ( I n A ) {\displaystyle {\tilde {A}}={\begin{pmatrix}\mathrm {I} _{n}\\\hline \mathrm {A} \end{pmatrix}}} be the matrix obtained by joining the identity matrix I n {\displaystyle \mathrm {I} _{n}} to A {\displaystyle A} . Then a necessary and sufficient condition for a matrix A {\displaystyle A} to be MDS is that every possible n × n {\displaystyle n\times n} submatrix obtained by removing m {\displaystyle m} rows from A ~ {\displaystyle {\tilde {A}}} is non-singular. This is also equivalent to the following: all the sub-determinants of the matrix A {\displaystyle A} are non-zero. Then a binary matrix A {\displaystyle A} (namely over the field with two elements) is never MDS unless it has only one row or only one column with all components 1 {\displaystyle 1} . Reed–Solomon codes have the MDS property and are frequently used to obtain the MDS matrices used in cryptographic algorithms. Serge Vaudenay suggested using MDS matrices in cryptographic primitives to produce what he called multipermutations, not-necessarily linear functions with this same property. These functions have what he called perfect diffusion: changing t {\displaystyle t} of the inputs changes at least m − t + 1 {\displaystyle m-t+1} of the outputs. He showed how to exploit imperfect diffusion to cryptanalyze functions that are not multipermutations. MDS matrices are used for diffusion in such block ciphers as AES, SHARK, Square, Twofish, Anubis, KHAZAD, Manta, Hierocrypt, Kalyna, Camellia and HADESMiMC, and in the stream cipher MUGI and the cryptographic hash function Whirlpool, Poseidon.