Search

A Behavioral Authentication (BA) system constructs a behavioral profile for a user and uses it to verify their identity claims. It is primarily used as a second factor in user authentication. A BA system starts with an initial database of user profiles, and uses a verification algorithm to accept or reject a verification request, that consists of a claimed identity and behavioral data by measuring the distance between the profile of the claimed identity and the presented behavioral data. As new users join the system, the size of profile database grows and for a user $u$ , the probability of other users with “close” profiles increases, and this results in an increase in the error probability of verification algorithm. We analyze this problem in distance-based verification systems, and introduce the notion of scalability of BA systems that requires the system error probability to remain (almost) unchanged as the size of the profile database grows. To achieve scalability, we propose personalization of verification algorithm. More specifically, for a user $u$ the verification algorithm considers a set of doppelgangers that consists of users that have “close” profiles to $u$ , and uses the set to form additional verification checks for verification requests against $u$ . We use extensive experiments to validate the above, including the increase in the verification error with the increase in the database size, and implement and evaluate our proposed scalable verification algorithm in reducing this error. To our knowledge, this is the first systematic treatment of scalability of BA systems. Our notion of scalability and the approach to achieving it are general and applicable to other distance-based authentication systems.

Outsourcing computation has gained significant popularity in recent years due to the development of cloud computing and mobile services. In a basic outsourcing model, a client delegates computation of a function f on an input x to a server. There are two main security requirements in this setting: guaranteeing the server performs the computation correctly, and protecting the client’s input (and hence the function value) from the server. The verifiable computation model of Gennaro, Gentry and Parno achieves the above requirements, but the resulting schemes lack efficiency. This is due to the use of computationally expensive primitives such as fully homomorphic encryption (FHE) and garbled circuits, and the need to represent f as a Boolean circuit. Also, the security model does not allow verification queries, which implies the server cannot learn if the client accepts the computation result. This is a weak security model that does not match many real life scenarios. In this paper, we construct efficient (i.e., without using FHE, garbled circuits and Boolean circuit representations) verifiable computation schemes that provide privacy for the client’s input, and prove their security in a strong model that allows verification queries. We first propose a transformation that provides input privacy for a number of existing schemes for verifiable delegation of multivariate polynomial f over a finite field. Our transformation is based on noisy encoding of x and keeps x semantically secure under the noisy curve reconstruction (CR) assumption. We then propose a construction for verifiable delegation of matrix-vector multiplication, where the delegated function f is a matrix and the input to the function is a vector. The scheme uses PRFs with amortized closed-form efficiency and achieves high efficiency. We outline applications of our results to outsourced two-party protocols.

Secret key agreement (SKA) is a basic cryptographic primitive that establishes a shared secret key between parties. In the two-party source model of SKA, Alice and Bob want to share a secret key. They each have private samples of two correlated variables that are partially leaked to Eve. In a one-way SKA protocol, Alice sends a single message to Bob over a public channel, allowing the two parties to calculate a shared secret key that will be essentially unknown to Eve. The length of the key is a function of the number of samples $n$ . In this paper, we prove a tight second-order asymptotic approximation of the key length of one-way SKA protocols, and propose an approach to construct a computationally efficient one-way SKA protocol with near-optimum finite key length. We compare our results with related work, and discuss future research directions.

Outsourcing computation has gained significant attention in recent years in particular due to the prevalence of cloud computing. There are two main security concerns in outsourcing computation: guaranteeing that the server performs the computation correctly, and protecting the privacy of the client’s data. The verifiable computation of Gennaro, Gentry and Parno addresses both concerns for outsourcing the computation of a function f on an input x to the cloud. The GGP scheme is privately delegatable, privately verifiable, and based on the expensive cryptographic primitives such as fully homomorphic encryption (FHE). In this paper we consider the problem of outsourcing matrix-vector multiplications of the form $$F{\mathbf{x}}$$, where F is a matrix and $$\mathbf{x}$$ is a column vector, and construct publicly delegatable and publicly verifiable schemes. Our schemes are either input private or function private, highly efficient, and provably secure under the well-established assumptions such as the discrete-logarithm assumption. We decompose a polynomial computation, such as computing a univariate polynomial of arbitrary degree, a bivariate polynomial of arbitrary degree, a quadratic multivariate polynomial, and in general any multivariate polynomial, into a two-step computation in which the computaionally expensive step is a matrix-vector multiplication. We use the matrix schemes to outsource the computation of high-degree polynomials and obtain the first high-degree polynomial outsourcing schemes that simultaneously have public delegation, public verification and input privacy/function privacy.

Digital signature schemes form the basis of trust in Internet communication. Shor (FOCS 1994) proposed quantum algorithms that can be used by a quantum computer to break the security of today’s widely used digital signature schemes, and this has fuelled intensive research on the design and implementation of post-quantum digital signatures. Hash-based digital signatures base their security on one-way functions that in practice are instantiated by hash functions. Hash-based signatures are widely studied and are part of NIST’s post-quantum standardization effort.

Policy-based signatures (PBS) were proposed by Bellare and Fuchsbauer (PKC 2014) to allow an {\em authorized} member of an organization to sign a message on behalf of the organization. The user's authorization is determined by a policy managed by the organization's trusted authority, while the signature preserves the privacy of the organization's policy. Signing keys in PBS do not include user identity information and thus can be passed to others, violating the intention of employing PBS to restrict users' signing capability. In this paper, we introduce the notion of {\em traceability} for PBS by including user identity in the signing key such that the trusted authority will be able to open a suspicious signature and recover the signer's identity should the needs arise. We provide rigorous definitions and stringent security notions of traceable PBS (TPBS), capturing the properties of PBS suggested by Bellare-Fuchsbauer and resembling the "full traceability" requirement for group signatures put forward by Bellare-Micciancio-Warinschi (Eurocrypt 2003). As a proof of concept, we provide a modular construction of TPBS, based on a signature scheme, an encryption scheme and a zero-knowledge proof system. Furthermore, to demonstrate the feasibility of achieving TPBS from concrete, quantum-resistant assumptions, we give an instantiation based on lattices., 37 pages,5 figures

Key agreement (KA) is a fundamental cryptographic primitive. Assuming that Alice and Bob do not have any prior shared correlation, it has been proved that key agreement with security against a computationally unbounded adversary is impossible if communication is either over a fully public channel, or the channel is fully controlled by the adversary. In this paper we consider a setting where communication is over a partially corrupted channel, and there is no prior shared correlation. We formalize security and reliability of key agreement protocols in this setting, derive bounds on the rate of secret key agreement, and give constructions that achieve the respective bounds. Our results show that secret key agreement, and hence secret message transmission, is possible, as long as a small fraction of the transmitted symbols in each round remain untouched by the adversary. Our results can be extended to key agreement between nodes in a network, when the two nodes are connected by a set of disjoint paths, and in each round a subset of paths is eavesdropped and another subset (possibly with overlap) is tampered with. We relate our results to previous works, and discuss future directions

Moving target defense (MTD) strategies have been widely studied for securing computer systems. We consider using MTD strategies to provide long-term cryptographic security for message transmission against an eavesdropping adversary who has access to a quantum computer. In such a setting, today’s widely used cryptographic systems including Diffie-Hellman key agreement protocol and RSA cryptosystem will be insecure and alternative solutions are needed. We will use a physical assumption, existence of multiple communication paths between the sender and the receiver, as the basis of security, and propose a cryptographic system that uses this assumption and an MTD strategy to guarantee efficient long-term information theoretic security even when only a single path is not eavesdropped. Following the approach of Maleki et al., we model the system using a Markov chain, derive its transition probabilities, propose two security measures, and prove results that show how to calculate these measures using transition probabilities. We define two types of attackers that we call risk-taking and risk-averse and compute our proposed measures for the two types of adversaries for a concrete MTD strategy. We will use numerical analysis to study tradeoffs between system parameters, discuss our results, and propose directions for future research.

Distance bounding (DB) protocols allow a prover to convince a verifier that they are within a distance bound. A public key distance bounding relies on the public key of the users to prove their identity and proximity claim. There has been a number of approaches in the literature to formalize security of public key distance bounding protocols. In this paper we extend an earlier work that formalizes security of public key DB protocols using an approach that is inspired by the security definition of identification protocols, and is referred to it as distance-bounding identification (\(\mathtt {DBID}\)). We first show that if protocol participants have access to a directional antenna, many existing protocols that have been proven secure, will become insecure, and then show to revise the previous model to include this new capability of the users. DBID approach provides a natural way of modelling man-in-the-middle attack in line with identification protocols, as well as other attacks that are commonly considered in distance bounding protocols. We compare the existing public key DB models, and prove the security of the scheme known as \(\mathtt {ProProx}\), in our model.

We propose a modular construction of a semantically secure wiretap code that achieves secrecy capacity for a large class of wiretap channels. Security of the construction is proved by interpreting the construction as an instance of an invertible extractor, and use the framework in Bellare et al. [1] to complete the proof. The construction has computation for encoding and decoding equivalent to hashing, and the smallest effective transmission rate among known modular capacity achieving constructions. We also give a modular construction of invertible Universal Hash Functions (UHF) from an XOR Universal Hash Functions that is of independent interest.

Tamper resilient cryptography has recently gained attention, and novel coding solutions have been proposed. One such solutions is Tamper Detection (TD) codes that are used to detect tampering with a codeword when the tampering function belongs to a specified family of functions. We consider TD codes when the class of functions consists of functions where the adversary first selects a subset of size \(\rho n\) of the codeword components to see, and then uses this view to choose a noise vector that will be added (algebraically) to the codeword (n is the codeword length). We show it is impossible to construct codes that protect against tampering of all functions in this class. By removing the set of bad functions from the class, we obtain a subset of this family for which tamper detection codes exist, and give a construction of tamper detection codes for this subset. We discuss our results and directions for future work.

In this paper we develop a range of practical cryptographic protocols for secure decision tree learning, a primary problem in privacy preserving data mining. We focus on particular variants of the well-known ID3 algorithm allowing a high level of security and performance at the same time. Our approach is basically to design special-purpose secure multiparty computations, hence privacy will be guaranteed as long as the honest parties form a sufficiently large quorum. Our main ID3 protocol will ensure that the entire database of transactions remains secret except for the information leaked from the decision tree output by the protocol. We instantiate the underlying ID3 algorithm such that the performance of the protocol is enhanced considerably, while at the same time limiting the information leakage from the decision tree. Concretely, we apply a threshold for the number of transactions below which the decision tree will consist of a single leaf—limiting information leakage. We base the choice of the “best” predicting attribute for the root of a decision tree on the Gini index rather than the well-known information gain based on Shannon entropy, and we develop a particularly efficient protocol for securely finding the attribute of highest Gini index. Moreover, we present advanced secure ID3 protocols, which generate the decision tree as a secret output, and which allow secure lookup of predictions (even hiding the transaction for which the prediction is made). In all cases, the resulting decision trees are of the same quality as commonly obtained for the ID3 algorithm. We have implemented our protocols in Python using VIFF, where the underlying protocols are based on Shamir secret sharing. Due to a judicious use of secret indexing and masking techniques, we are able to code the protocols in a recursive manner without any loss of efficiency. To demonstrate practical feasibility we apply the secure ID3 protocols to an automated health care system of a real-life rehabilitation organization.

One-time signature OTS schemes are important cryptographic primitives that can be constructed using one-way functions, and provide post-quantum security. They have found diverse applications including forward security and broadcast authentication. OTS schemes are time-efficient, but their space complexity is high: the sizes of signatures and keys are linear in the message size. Regular schemes e.g., based on discrete logarithm or factoring problems, and their variants, however, have very low space complexity but are not time-efficient. Therefore, in particular, they are not suitable for resource-constraint devices. Many widely used signature schemes are not post-quantum. In this paper, we give a signature scheme that has the advantages of the previous two approaches. It provides constant-size short signatures, and is much more time-efficient than schemes in the second approach. We prove that our scheme is post-quantum secure as long as the SVP in ideal lattices is hard in the presence of a quantum computer. We use SWIFFT: a family of provable collision-resistant functions, which have efficient implementations, comparable with that of SHA-256, hence our proposed scheme could be used on resource-constrained devices.

Traditional data authentication systems are sensitive to single bit changes and so are unsuitable for message spaces that are naturally "fuzzy" where "similar" messages are considered "the same" or indistinguishable. In this paper, we study unconditionally secure approximate authentication. We generalize traditional universal hashing to fuzzy universal hashing and use it to construct secure approximate authentication for multiple messages.

Traditional hash functions are designed to protect against even the slightest modification of a message. Thus, one bit changed in a message would result in a totally different message digest when a hash function is applied. This feature is not suitable for applications whose message spaces admit a certain fuzziness, such as multimedia communications or biometric authentication applications. In these applications, approximate hash functions must be designed so that the distance between messages are proportionally reflected in the distance between message digests. Most of the previous designs of approximate hash functions employ traditional hash functions. In an ingenious approximate message authentication scheme for an N-ary alphabet recently proposed by Ge, Arce and Crescenzo, the approximate hash functions are based on the majority selection function. This scheme is suitable for N-ary messages with arbitrary alphabet size N. In this paper, we show a hidden property of the majority selection function, which allows us to successfully break this scheme. We show that an adversary, by observing just one message and digest pair, without any knowledge of the secret information, can generate N - 1 new valid message and digest pairs. In order to resist the attack, we propose some modifications to the original design. The corrected scheme is as efficient as the original scheme and it is secure against the attack. By a new combinatorial approach, we calculate explicitly the security parameters of the corrected scheme.

The authors give a generic construction for universal (mutli) designated-verifier signature schemes from a large class of signature schemes, referred to as Class ℂ. The resulting schemes are efficient and have two important properties. Firstly, they are provably DV-unforgeable, non-transferable and also non-delegatable. Secondly, the signer and the designated verifier can independently choose their cryptographic settings. The authors also propose a generic construction for (hierarchical) identity-based signature schemes from any signature scheme in ℂ and prove that the construction is secure against adaptive chosen message and identity attacks. The authors discuss possible extensions of our constructions to identity-based ring signatures and identity-based designated-verifier signatures from any signature in ℂ. Finally, the authors show that it is possible to combine the above constructions to obtain signatures with combined functionalities.

Authentication codes provide message integrity guarantees in an information theoretic sense within a symmetric key setting. Information theoretic bounds on the success probability of an adversary who has access to previously authenticated messages have been derived by Simmons and Rosenbaum, among others. In this paper, we consider a strong attack scenario where the adversary is adaptive and has access to authentication and verification oracles. We derive information theoretic bounds on the success probability of the adversary and on the key size of the code. This brings the study of unconditionally secure authentication systems on a par with the study of computationally secure ones. We characterize the codes that meet these bounds and compare our result with the earlier ones.

In an erasure adversarial wiretap channel (eAWTP-channel), the adversary can select a fraction ρr of the codeword to read, and a fraction ρe of the codeword to erase. The model can be seen as an extension of the wiretap II model where the adversary not only selects its view of the transmitted word, but also can erase a fraction of the codeword. eAWTP codes provide security and reliability for communication over eAWTP channels. We derive an upper bound on the rate of eAWTP codes, and give an efficient construction of a code family that achieves the bound, hence deriving secrecy capacity of the channel. We then show that the construction can also be used for AWTP channels in which instead of erasing code components, the adversary can add noise to the codeword. The construction is the only AWTP code with constant alphabet size.

Random number generators have direct applications in information security, online gaming, gambling, and computer science in general. True random number generators need an entropy source which is a physical source with inherent uncertainty, to ensure unpredictability of the output. In this paper we propose a new indirect approach to collecting entropy using human errors in the game play of a user against a computer. We argue that these errors are due to a large set of factors and provide a good source of randomness. To show the viability of this proposal, we design and implement a game, conduct a user study in which we collect user input in the game, and extract randomness from it. We measure the rate and the quality of the resulting randomness that clearly show effectiveness of the approach. Our work opens a new direction for construction of entropy sources that can be incorporated into a large class of video games.

Limited View Adversary Codes (LV codes) provide protection against an adversary who has partial view of the communication channel and can use this view to corrupt the sent codeword by constructing an adversarial error vector that will be added to the codeword. For a codeword of length N, the adversary sees a subset of ρ r N of the codeword components and adds an adversarial error vector of weight ρ w N to the codeword. A δ-LV code ensures correct recovery of the sent message with probability at least 1 − δ. The motivation for studying these codes is modelling adversarial corruptions in wireless communications as well as networks that are partially controlled by an adversary, with the aim of providing reliable communication.

A shuffle takes a list of ciphertexts and outputs a permuted list of re-encryptions of the input ciphertexts. Mix-nets, a popular method for anonymous routing, can be constructed from a sequence of shuffles and decryption. We propose a formal model for security of verifiable shuffles and a new verifiable shuffle system based on the Paillier encryption scheme, and prove its security in the proposed dmodel. The model is general and can be extended to provide provable security for verifiable shuffle decryption.

To protect copyrighted digital data against piracy, codes with different secure properties such as frameproof codes, secure frameproof codes, codes with identifiable parent property (IPP codes), traceability codes (TA codes) are introduced. In this paper, we study these codes together with related combinatorial objects called separating and perfect hash families. We introduce for the first time the notion of difference function families and use these difference function families to give generalized recursive techniques that can be used for any kind of secure codes and hash families. We show that some previous recursive techniques are special cases of these new techniques.

In threshold cryptography, the goal is to distribute the computation of basic cryptographic primitives across a number of nodes in order to relax trust assumptions on individual nodes, as well as to introduce a level of fault-tolerance against node compromise. Most threshold cryptography has previously looked at the distribution of public key primitives, particularly threshold signatures and threshold decryption mechanisms. In this paper, we look at the application of threshold cryptography to symmetric primitives, and in particular the encryption or decryption of a symmetric key block cipher. We comment on some previous work in this area and then propose a model for shared encryption / decryption of a block cipher. We will present several approaches to enable such systems and will compare them.

Secure code and secure frameproof code (SFP) are introduced to provide protection against illegal producing of copyrighted digital material. In this paper we present a general method of converting a binary 2-SFP code to a 2-secure code, that is providing a tracing algorithm and calculating e, the chance of error in tracing. We express the error associated with this tracing in terms of n, the number of codewords in the code and d, the minimum Hamming distance of the code. We also characterize the set of pirate words such that the algorithm fails to trace. To illustrate the method, we first show that the dual Hamming code [6] is a 2-SFP code and we apply the proposed method for this code to obtain a 2-secure code.

Authentication of image data is a challenging task. Unlike data authentication systems that detect a single bit change in the data, image authentication systems must remain tolerant to changes resulting from acceptable image processing or compression algorithms while detecting malicious tampering with the image. Tolerance to the changes due to lossy compression systems is particularly important because in the majority of cases images are stored and transmitted in compressed form, and so it is important for verification to succeed if the compression is within the allowable range. In this paper we consider an image authentication system that generates an authentication tag that can be appended to an image to allow the verifier to verify the authenticity of the image. We propose a secure, flexible, and efficeint image authentication algorithm that is tolerant to image degradation due to JPEG lossy compression within designed levels. (JPEG is the most widely used image compression system and is the de facto industry standard.) By secure we mean that the cost of the best known attack againt the system is high, by flexible we mean that the level of protection can be adjusted so that higher security can be obtained with increased length of the authentication tag, and by efficient we mean that the computation can be performed largely as part of the JPEG compression, allowing the generation of the authentication tag to be efficiently integrated into the compression system. The authentication tag consists of a number of feature codes that can be computed in parallel, and thus computing the tag is effectively equivalent to computing a single feature code. We prove the soundness of the algorithm and show the security of the system. Finally, we give the results of our experiments.

We consider a new type of traitor tracing scheme, called sequential traitor tracing, that protects against rebroadcasting of decrypted content. Sequential traceability (TA) schemes trace all up to c traitors and remove the shortcomings of dynamic tracing schemes. We give two general constructions and show the relationship between c-TA codes and sequential tracing schemes.

Shared generation of authenticator systems (or SGA-systems) generalise Simmons' traditional authentication codes when authenticators for source states are produced by collaboration of a group of senders, rather than a single sender. In this paper we study threshold SGA-systems. We derive information-theoretic and combinatorial lower bounds on the probability of success and the size of the key space, and give two key efficient constructions for SGA-systems based on den Boer A-codes and error-correcting codes. We also give a recursive construction method using perfect hash families to construct SGA-systems for large groups.

Homomorphic MACs allow the holder of a secret key to construct authenticators for data blocks such that an untrusted server that computes a function of the data, can also compute an authenticator that can be verified by the key holder, guaranteeing correctness of the computation. Homomorphic MACs that allow verifiable computation of multivariate polynomials of degree ≤ 2 have been proposed by Backes, Fiore and Reischuk (CCS 2013). We generalize their construction such that polynomials of degree l>2 can also be computed. Our generalization uses multilinear map abstraction and has security based on the l-linear assumption.

We investigate the problem of algebraic manipulation detection (AMD) over a communication channel that partially leaks information to an adversary. We assume the adversary is computationally unbounded and there is no shared key or correlated randomness between the sender and the receiver. We introduce leakage-resilient (LR)-AMD codes to detect algebraic manipulation in this model.

We derive lower bounds on the maximum number of codewords in a class of frame-proof codes and traceability schemes, and give constructions for both with more codewords than the best known.

Channels with adversarial errors have been widely considered in recent years. In this paper we propose a new type of adversarial channel that is defined by two parameters ρr and ρw, specifying the read and write power of the adversary: for a codeword of length n, adversary can read ρrn components and add an error vector of weight up to ρwn to the codeword. We give our motivations, define performance criteria for codes that provide reliable communication over these channels, and describe two constructions, one deterministic and one probabilistic, for these codes. We discuss our results and outline our direction for future research.

Proofs of Retrievability (PoR) allows a client (verifier) to store a file at an untrusted remote storage, and later be able to check the integrity of the file through an interactive challenge-response protocol. A challenge specifies a random subset of blocks and the response is a function of the challenged block. An unbounded-use PoR scheme allows an arbitrary number of challenge-response interactions. Efficient PoR schemes must minimize the communication complexity of the challenge-response protocol, the storage overhead and computation of response by the prover. The security of a PoR scheme is against an erasing adversary and by showing the existence of an extractor which can extract the file from the set of challenges and their corresponding correct responses. In this paper, we modify the unbounded-use PoR scheme of Shacham and Waters (2008) such that the number of challenged data blocks in each round is determined by a probability distribution over a set of possible values. For the security parameter l, the average number of challenged blocks is O(logl), and so is smaller that the original scheme of Shacham and Waters, and in the worst case, is O(l). The response to a challenge is obtained by XORing the challenged data blocks and so is very fast. We show that to ensure security the original verification method of Shacham and Waters must be slightly modified.

In this paper, we construct a new threshold-attribute-based signature (t-ABS) scheme that is significantly more efficient than all previous t-ABS schemes. The verification algorithm requires the computation of only 3 pairing operations, independently of the attribute set of the signature, and the size of the signature is also independent of the number of attributes. The security of all our schemes is reduced to the computational Diffie-Hellman problem. We also show how to achieve shorter public parameters based on the intractability of computational Diffie-Hellman assumption in the random oracle model.

Verifiable computation (VC) allows a computationally weak client to outsource evaluation of a function on many inputs to a powerful but untrusted server. The client invests a large amount of off-line computation to obtain an encoding of its function which is then given to the server. The server returns both the evaluation of the function on the client's input and a proof with which the client can verify the correctness of the evaluation using substantially less effort than doing the evaluation on its own. We consider privacy preserving VC schemes whose executions reveal no information on the client's input or function to the server. We construct VC schemes with input privacy for univariate polynomial evaluation and matrix multiplication and then extend them to achieve function privacy. Our main tool is the recently proposed mutilinear maps. We show that the proposed VC schemes can be used to implement verifiable outsourcing of private information retrieval (PIR).

True Randomness Generators (TRG) use the output of an entropy source to generate a sequence of symbols that is sufficiently close to a uniformly random sequence, and so can be securely used in applications that require unpredictability of each symbol. A TRG algorithm generally consists of (i) an entropy source and (ii) an extractor algorithm that uses a random seed to extract the randomness of the entropy source. We propose a TRG that uses the user input in a game played between the user and the computer both as the output of an entropy source, and the random seed required for the extractor. An important property of this TRG is that the (randomness) quality of its output can be flexibly adjusted. We describe the theoretical foundation of the approach and design and implement a game that instantiates the approach. We give the results of our experiments with users playing the game, and analysis of the resulting output strings. Our results support effectiveness of the approach in generating high quality randomness. We discuss our results and propose directions for future work.

We study authentication codes (A-codes) when the enemy has access to the content of the intercepted cryptogram. This is similar to plaintext attack in secrecy systems. Enemy's success is defined in two ways. The first is as in Simmons' model. We will also consider chosen-content attacks in which the success is by constructing a fraudulent cryptogram with a given content. We will obtain information theoretic bounds, define perfect protection and obtain lower bounds on the number of encoding rules for codes with perfect protection against chosen-content impersonation and chosen-content plaintext substitution. We characterize these A-codes when the number of encoding rules is minimum. We give methods of making an A-code resistant against plaintext and chosen-context plaintext attack.

Shannon's definition of perfect secrecy captures the strongest notion of security for an encryption system and requires that the ciphertext leaks no information about the plaintext to an eavesdropper with unbounded computational power. The only known system with perfect secrecy in this model is one-time pad. Two important limitations of one-time pad in practice are, (i) the size of key space must not be less than the size of plaintext space, and (ii) the key must be chosen uniformly at random for each message to be encrypted. A number of follow up work attempt to relax these limitations by introducing relaxed or new definitions of secrecy. In this paper we propose a new relaxation of secrecy that we call perfect guessing secrecy, or guessing secrecy for short. This is a natural definition that requires that the adversary's success chance of the plaintext using his best guessing strategy does not change after seeing the ciphertext. Unlike perfect secrecy, guessing secrecy does allow some leakage of information but requires that the best guess of the plaintext remain the same after seeing the ciphertext. We define guessing secrecy and prove a number of results. We show that similar to perfect secrecy, in guessing secrecy the size of the key space can not be less than the size of plaintext space. Moreover, when the two sets are of equal size, one can find two families of distributions on the plaintext space and key space, such that perfect guessing secrecy is guaranteed for any pair of distributions, one from each family. In other words, perfect guessing secrecy can be guaranteed with non-uniform keys also. We also show the relation between perfect secrecy and perfect guessing secrecy. We discuss our results and propose direction of future research.

In the Secure Message Transmission (SMT) problem, a sender $\cal S$ is connected to a receiver $\cal R$ through n node-disjoint paths in the network, a subset of which are controlled by an adversary with unlimited computational power. $\cal{S}$ wants to send a message m to $\cal{R}$ in a private and reliable way. Constructing secure and efficient SMT protocols against a threshold adversary who can corrupt at most t out of n wires, has been extensively researched. However less is known about SMT problem for a generalized adversary who can corrupt one out of a set of possible subsets. In this paper we focus on 1-round (0,δ)-SMT protocols where privacy is perfect and the chance of protocol failure (receiver outputting NULL ) is bounded by δ. These protocols are especially attractive because of their possible practical applications. We first show an equivalence between secret sharing with cheating and canonical 1-round (0, δ)-SMT against a generalized adversary. This generalizes a similar result known for threshold adversaries. We use this equivalence to obtain a lower bound on the communication complexity of canonical 1-round (0, δ)-SMT against a generalized adversary. We also derive a lower bound on the communication complexity of a general 1-round (0, 0)-SMT against a generalized adversary. We finally give a construction using a linear secret sharing scheme and a special type of hash function. The protocol has almost optimal communication complexity and achieves this efficiency for a single message (does not require block of message to be sent).

This paper provides a reflective overview of the research published in [3,4], which introduces a new realistic scenario for information theoretically secure key establishment. The scenario is when two parties are communicating over "noisy" channels that are eavesdropped by other parties in the environment. We define the secret key capacity as the highest achievable secret key rate, i.e., the highest number of secret key bits that the two parties can share on average per use of the channel. We study the above problem in two settings when the two parties have, or do not have, access to sources of local randomness. In each case, we derive lower and upper bounds on the SK capacity and derive the capacity for special cases. We also compare the bounds in the two settings and discuss the role of local randomness in increasing key rate.

We propose a fully private fingerprint matching protocol that compares two fingerprints based on the most widely-used minutia-based fingerprint matching algorithm. The protocol enables two parties, each holding a private fingerprint, to find out if their fingerprints belong to the same individual. Unlike previous works, we do not make any simplifying assumption on the matching algorithm or use generic multiparty computation protocols in our constructions. We employ a commonly-used algorithm that works by first comparing minutia pairs from the two fingerprints based on their types, locations, and orientations, and then checking if the number of matching minutia pairs is more than a threshold, and we propose a concrete, scalable, and modular protocol. We prove security against honest-but-curious adversaries and discuss how security against malicious adversaries can be achieved using standard cryptographic techniques. Our protocol is realized using common cryptographic primitives and do not require pairing- or lattice-based cryptography.

In this paper we consider 1-round almost perfectly secure message transmission protocols with optimal transmission rate, and give constructions for two levels of connectivity, n=2t+k and $n = (2+c)t, c > \frac{1}{t}$ . Here n and t are the total number of wires and the number of corrupted wires, respectively, and k and c are constants. The first protocol has a modular construction that with appropriate instantiations of each module results in optimal protocols for n=2t+k. The second protocol is the first construction for optimal protocol when n=(2+c)t.

In the Secure Message Transmission (SMT) problem, a sender \(\mathcal{S}\) wants to send a message m to a receiver \(\mathcal{R}\) in a private and reliable way. \(\mathcal{S}\) and \(\mathcal{R}\) are connected by nwires, t of which controlled by the adversary. The n wires represent n node disjoint communication paths between the sender and the receiver. The adversary is assumed to have unlimited computational power. An Almost Perfectly Secure Message Transmission (APSMT, for short) provides perfect privacy for the transmitted message, and the probability that the received message is different from the sent one is bounded by δ and, δ = 0 corresponds to perfect SMT. It has been shown that APSMT is possible if n ≥ 2t + 1 and for 1-round perfect SMT, n ≥ 3t + 1. SMT protocols and techniques have found applications in practice, including key distribution and key strengthening in wireless sensor networks. In this paper we show two general methods of constructing 1-round APSMT protocols for different levels of network connectivity. We consider two cases: \(n = (2 + c)t,c > \frac{1} {t}\) where a fraction of wires are corrupted, and \(n = 2t + k,k \geq 1\) where a constant number of extra wires (over the required minimum) exists. The proposed methods use the whole, or part of, the previously constructed protocols to construct new protocols with flexible connectivity, whose privacy, reliability and efficiency can be derived from the component parts. The new protocols are efficient and in some cases have optimal transmission rates. The flexibility that is provided by these constructions facilitate application of APSMT in practical applications.

International audience; In this paper, we improve on a previous result by Gagné et al. [9] for automatically proving the semantic security of symmetric modes of operation for block ciphers. We present a richer assertion language that uses more flexible invariants, and a more complete set of rules for establishing the invariants. In addition, all our invariants are given a meaningful semantic definition, whereas some invariants of the previous result relied on more ad hoc definitions. Our method can be used to verify the semantic security of all the encryption modes that could be proven secure in [9], in addition to other modes, such as Propagating Cipher-Block Chaining (PCBC).

We define a semantic model for purpose, based on which purpose-based privacy policies can be meaningfully expressed and enforced in a business system. The model is based on the intuition that the purpose of an action is determined by its situation among other inter-related actions. Actions and their relationships can be modeled in the form of an action graph which is based on the business processes in a system. Accordingly, a modal logic and the corresponding model checking algorithm are developed for formal expression of purpose-based policies and verifying whether a particular system complies with them. It is also shown through various examples, how various typical purpose-based policies as well as some new policy types can be expressed and checked using our model.

We study the problem of unconditionally secure Secret Key Establishment (SKE) when Alice and Bob are connected by two noisy channels that are eavesdropped by Eve. We consider the case that Alice and Bob do not have any sources of initial randomness at their disposal. We start by discussing special cases of interest where SKE is impossible and then provide a simple SKE construction over binary symmetric channels that achieves some rates of secret key. We next focus on the Secret Key (SK) capacity and provide lower and upper bounds on this capacity. We prove the lower bound by proposing a multi-round SKE protocol, called the main protocol. The main protocol consists of an initialization round and the repetition of a two-round SKE sub-protocol, called the basic protocol. We show that the two bounds coincide when channels do not leak information to the adversary. We apply the results to the case that communicants are connected by binary symmetric channels.

We use simulated annealing to provide an automated method for the cryptanalysis of mono-alphabetic substitution ciphers. We prove the convergence of the algorithm and study its performance for a specific cooling schedule. We discuss the merits of this approach and show that it provides a simple, fast and elegant solution to the cryptanalysis problem which is also promising for more complex types of block ciphers.

An overview was given of security applications where noisy data plays a substantial role. Secure Sketches and Fuzzy Extractors were discussed at tutorial level, and two simple Fuzzy Extractor constructions were shown. One of the latest developments was presented: quantum-readout PUFs.

We study the applicability of random graph theory in modeling secure connectivity of wireless sensor networks. Specifically, our work focuses on the highly influential random key predistribution scheme by Eschenauer and Gligor to examine the appropriateness of the modeling in finding system parameters for desired connectivity. We use extensive simulation and theoretical results to identify ranges of the parameters where i) random graph theory is not applicable, ii) random graph theory may lead to estimates with excessive errors, and iii) random graph theory gives very accurate results. We also investigate the similarities and dissimilarities in the structure of random graphs and key graphs (i.e., graphs describing key sharing information between sensor nodes). Our results provide insights into research relying on random graph modeling to examine behaviors of key graphs.

International audience; We presents a compositional Hoare logic for proving semantic security of modes of operation for symmetric key block ciphers. We propose a simple programming language to specify encryption modes and an assertion language that allows to state invariants and axioms and rules to establish such invariants. The assertion language consists of few atomic predicates. We were able to use our method to verify semantic security of several encryption modes including Cipher Block Chaining (CBC), Cipher Feedback mode (CFB), Output Feedback (OFB), and Counter mode (CTR).

In this paper we propose threshold attribute-based signatures (t-ABS). A t-ABS scheme enables a signature holder to prove possession of signatures by revealing only the relevant attributes of the signer, hence providing signer-attribute privacy for the signature holder. We define t-ABS schemes, formalize their security and propose two t-ABS schemes: a basic scheme secure against selective forgery and a second one secure against existential forgery, both provable in the standard model, assuming hardness of the CDH problem. We show that our basic t-ABS scheme can be augmented with two extra protocols that are used for efficiently issuing and verifying t-ABS signatures on committed values. We call the augmented scheme a threshold attribute based c-signature scheme (t-ABCS). We show how a t-ABCS scheme can be used to realize a secure threshold attribute-based anonymous credential system (t-ABACS) providing issuer-attribute privacy. We propose a security model for t-ABACS, give a concrete scheme using t-ABCS scheme, and prove that the credential system is secure if the t-ABCS scheme is secure.