In this paper we consider evolving 2-threshold secret sharing schemes. In such schemes, the number of participants grows over time and is potentially unbounded, any two participants reconstruct the secret, and no single participant can figure out any partial information about it. They are referred to as$(2,\infty)$-threshold secret sharing schemes. The cost of a$(2,\infty)$-threshold secret sharing scheme can be measured as the maximum, over all possible$n\ge 2$, of the ratio between the sum of the lengths of the shares for the first n participants and the sum of the lengths of the shares for a (standard) optimal$(2,n)$-threshold secret sharing scheme. It is known that such a cost measure is lower bounded by$3/2$. Moreover, currently, the best known$(2,\infty)$-threshold secret sharing scheme has cost 1.59375. Our contribution improves the state-of-the-art in several ways:•We describe a new$(2,\infty)$-threshold secret sharing scheme whose cost is 1.5859375, improving on the previous best known scheme. • Motivated by the fact that in some applications one knows a lower bound on the number of participants, we generalize the cost measure, by considering the maximum over all possible$n\ge z_{0}$, where$z_{0}$is any integer greater than or equal to 2. • We provide constructions of optimal schemes for the generalized cost measure and through a theoretical analysis we prove some interesting properties for the lower bound of the cost. • By using algorithmic techniques, for reasonably small cases, we exhaustively study the problem of finding tight lower bounds. In particular, we obtain a lower bound of 1.534375, improving the lower bound of$3/2$. We close the paper summarizing our findings and discussing some open issues.

The rapid progress of Internet technology has led to a strong increase in the use of online social networks for disseminating information on the Internet. In this scenario, it is crucial to establish approaches that can effectively reduce the diffusion of false information (fake news) that can potentially cause harm to society. A defensive approach, based on integer-order differential equations, has been recently developed to analyze the effects of verification and blocking of users for containing the spread of fake news. Starting from it, we introduce a novel fractional model providing a more accurate, powerful, and realistic representation of the transmission of fake news messages. The model aims to predict the spread of such messages, by better considering the effect of the system's status evolution over time. The use of fractional differential equations to schematize the propagation of fake news results in incorporating a greater amount of memory information and better considering hereditary properties of the system of interest, also capturing its hidden nonlinear dynamics, mainly related to fractality and multiscale nature.

In this paper, we introduce an information-theoretic approach to the access control problem within a scenario where a trusted central authority is tasked with user registration, and a set of guards is responsible for granting anonymous access to a restricted resource. More precisely, we consider access schemes with centralized user registration, where a trusted authority is responsible for the generation of access tokens assigned to users, while preserving user anonymity with respect to the guards. We first propose an information-theoretic model for anonymous access schemes with centralized user registration, then we show a lower bound on the size of the private information that each guard has to store. Finally, we propose a simple and optimal construction for anonymous access schemes with centralized registration.

Hierarchical structures are frequently used to manage access to sensitive data in various contexts, ranging from organizational settings to IoT networks.

Distributed Secret Sharing is a (multi) secret sharing model in which the shares are distributed over storage nodes of a network and each participant is able to reconstruct a specific secret by accessing a subset of the storage nodes. In this work, we provide new Distributed (multi) Secret Sharing Protocols for a specific class of access structures, namely those that can be described with a graph. The protocols improve on previous results allowing a faster encoding and decoding phase while maintaining optimal storage requirements. Moreover, our protocols can manage any kind of graph, while previous protocols have been designed only for complete graphs, and we provide a complete characterization of graph-based protocols. We also prove some tight bounds on the size of the information held in the storage nodes and communication complexity by using an information-theoretic approach. Finally, we also introduce a computationally secure technique for the general case that allows improvements in the size of the needed disk space if secrecy is computational, that is, if the scheme is robust against resource-bounded adversaries.

Aone-message unilateral entity authentication schemeallows one party, called theprover, to authenticate himself, i.e., to prove his identity, to another party, called theverifier, by sending a singleauthentication message. We consider schemes where the prover and the verifier do not share any secret information, such as a password, in advance. We propose thefirst theoretical characterizationfor one-message unilateral entity authentication schemes, by formalizing the security requirements for such schemes with respect to different kinds ofpassiveandactiveadversarial behaviours. In particular, we consider bothstaticandadaptiveadversaries for each kind of attack (passive/active). Afterwards, we explore the relationships between the security notions resulting from different adversarial behaviours for one-message unilateral entity authentication schemes. Finally, we propose three different constructions for one-message unilateral entity authentication schemes and we analyze their security with respect to the different definitions introduced in this paper.

Alphabetic codes and binary search trees are combinatorial structures that abstract search procedures in ordered sets endowed with probability distributions. In this paper, we design new linear-time algorithms to construct alphabetic codes, and we show that the obtained codes are not too far from being optimal. Moreover, we exploit our results on alphabetic codes to provide new bounds on the average cost of optimal binary search trees. Our results improve on the best-known bounds on the average cost of optimal binary search trees present in the literature.

We define and implement a novel side-channel attack that exploits a smartphone’s accelerometer to eavesdrop entire words that the device itself is reproducing through its loudspeakers. The proposed approach consists of two modules: (i) a deep learning-based system that, using a Convolutional Neural Network (CNN), learns to recognize a set of significant speech units, using the spectrogram representation of the corresponding acceleration signals; (ii) an evolutionary-based segmentation method that, given the accelerometer measurements corresponding to an input speech, finds the best way to split it so that the proposed CNN maintains a high classification performance on each of the segments obtained, guarantying the recognition of a significant percentage of words from the original speech. Results of experiments performed to assess the effectiveness of the proposed attack, show its ability to recognize a percentage of words which is higher for short speeches and diminishes as the speeches get longer. We experimented with speeches of lengths ranging from 5 to 60 s, obtaining a recognition percentage going from about 80% for the shortest speeches, down to about 54% for the longest ones.

In Distributed Secret Sharing schemes, secrets are encoded with shares distributed over multiple nodes of a network. Each involved party has access to a subset of the nodes and thus to a subset of the shares and is able to reconstruct a specific secret. Usually, these schemes are evaluated by measuring the required storage overhead, as well as the encoding and decoding complexities. In this paper, we provide new Distributed (multi) Secret Sharing Protocols for$(k,n)$-threshold access structures that improve on previous results, characterized by nearly-optimal storage overhead, achieving both storage optimality and a better encoding/decoding complexity. The protocols are also simpler than previous ones and allow for easier encoding.

Over the last years, our lifestyle has been positively upset by the sudden advent of technology. The Internet of Things (IoT), offering universal and ubiquitous connectivity to both people and objects, revealed to be the silver bullet for enabling a vast number of previously unexpected applications. In particular, media streaming providers are growing in business and scope, and we can forecast that soon, video streaming will substitute TV broadcasting activities. With the increasing success of multi-user smart environments, empowered by new-generation smart devices and IoT architectures, multimedia contents (i.e., images and videos) need to be effectively accessed anytime and anywhere. Recent advances in computer vision technologies have made the development of intelligent monitoring systems for video surveillance and ambient-assisted living. Such a scenario permits better integration among technologies, multimedia content, and end-users. However, there are several challenges, and some are still open. More precisely, due to the sensitivity of some multimedia content (e.g., video-surveillance streams), it is paramount to preserve users’ privacy. Again, it is necessary to guarantee the integrity of usage rights during any multimedia transmission process, starting from the video encoding phase. In this way, the private content is disclosed only when the stream is decoded on the other endpoint, by the legitimate user. In this article, we present a secure video transmission strategy that can address the challenges mentioned above. The proposed strategy takes advantage of both watermarking and video scrambling techniques to make it possible for the secure and privacy-preserving transmission of multimedia streaming. Through our proposal, multimedia streaming is of low quality and thus unusable. However, it can be fully recovered and enjoyed only by authorized users. Finally, due to its low complexity and energy-efficiency, our proposal is particularly suitable for onboard implementations.

Summary Conventional privacy‐enforcement mechanisms, such as encryption‐based ones, are frequently used to prevent third‐party eavesdroppers to intercept confidential information exchanged between two or more parties. However, the use of such mechanisms can be perceivable and it alerts the involved intercepting entities that could devote some effort in trying to remove the protection, eg, by cracking the encryption keys used or by exploiting the vulnerabilities of the technological solution used to protect the data. Sometimes, from the security point of view, avoiding to draw the attention or suspect to intermediate intercepting entities, may be better than protecting a data in a conventional manner. In such direction, one of the most effective approaches is hiding the secret information to be exchanged inside other data, through steganographic techniques. In this work, we exploit, for this specific purpose, the hierarchical structure of a compressed archive, as well as the algorithms and parameters used to create and maintain such archive. It is important to point out that, by doing this, the secret information is in no way semantically related to the contents of the compressed archive. This can be extremely useful in many cloud‐based situations where several confidential data is moved across multiple independent data center, which are under the control of different and not always fully trusted authorities. The effectiveness of this proposal has been assessed by using a properly designed and implemented prototype, where extensive tests have been performed within the context of a proof‐of‐concept.

There is an increasing involvement of the Internet of Things (IoT) in many of our daily activities, with the aim of improving their efficiency and effectiveness. We are witnessing the advent of smart cities, in which IoT is exploited to improve the management of a city's assets, as well as smart factories, where IoT is paving the way for the forth industrial revolution. These applications and many other ones imply several non-functional requirements to be satisfied by the adopted IoT solution, where security assumes paramount importance. Secure communications among the IoT nodes are strongly needed due to the use of wireless technologies that are easy to eavesdrop, in order to steal valuable information. Accordingly, confidentiality is a fundamental prerequisite, but the existing solutions based on transport-level encryption are ineffective, while the ones with application-level encryption may be too expensive in terms of energy consumption. In this work, we propose a series of solutions and methods to achieve confidentiality with end-to-end guarantees, by using group-based keys within the context of a clustered and distributed key management framework. We have implemented such solutions on top of TinyOS, and assessed their achievable quality by means of the TOSSIM simulator.

In the last decade Digital Forensics has experienced several issues when dealing with network evidence. Collecting network evidence is difficult due to its volatility. In fact, such information may change overtime, may be stored on a server out jurisdiction or geographically far from the crime scene. On the other hand, the explosion of the Cloud Computing as the implementation of the Software as a Service (SaaS) paradigm is pushing users toward remote data repositories such as Dropbox, Amazon Cloud Drive, Apple iCloud, Google Drive, Microsoft OneDrive. In this paper is proposed a novel methodology for the collection of network evidence. In particular, it is focused on the collection of information from online services, such as web pages, chats, documents, photos and videos. The methodology is suitable for both expert and non-expert analysts as it “drives” the user through the whole acquisition process. During the acquisition, the information received from the remote source is automatically collected. It includes not only network packets, but also any information produced by the client upon its interpretation (such as video and audio output). A trusted-third-party, acting as a digital notary, is introduced in order to certify both the acquired evidence (i.e., the information obtained from the remote service) and the acquisition process (i.e., all the activities performed by the analysts to retrieve it). A proof-of-concept prototype, called LINEA, has been implemented to perform an experimental evaluation of the methodology.

In classical secret sharing schemes a dealer shares a secret among a set of participants in such a way that qualified subsets can reconstruct the secret, while forbidden ones do not get any kind of information about it. The basic parameter to optimize is the size of the shares, that is, the amount of secret information that the dealer has to give to participants. In this paper we formalize a notion of probabilistic secret sharing schemes, in which qualified subsets can reconstruct the secret but only with a certain controlled probability. We show that, by allowing a bounded error in the reconstruction of the secret, it is possible to drastically reduce the size of the shares the participants get (with respect to classical secret sharing schemes). We provide efficient constructions both for threshold access structures on a finite set of participants and for evolving threshold access structures, where the set of participants is potentially infinite. Some of our constructions yield shares of constant size (i.e., not depending on the number of participants) and an error probability of successfully reconstructing the secret which can be made as close to 1 as desired.

In the last years, several academic research efforts have focused on security requirements, threat models, and attack taxonomies concerning the application of the Internet of Things (IoT) in critical systems. Since such systems are strongly data intensive, it is of pivotal importance to provide integrity for the messages moving throughout the IoT infrastructure by means of publish/subscribe services. Integrity provisioning in industrial IoT scenarios has received marginal attention with respect to other primary security features. The existing solutions are lacking the needed focus on the peculiarities of the event notification and on the demand introduced by resource-constrained devices. This work contributes by applying group signatures so as to avoid managing certificates, violating the spatial decoupling, or implying an excessive resource usage. A proof-of-concept prototype of the proposed solution has been realized for platforms based on TinyOS, and simulations with TOSSIM have been conducted in order to empirically assess its performance and effectiveness.

A one-message unilateral entity authentication scheme allows one party, called the prover, to authenticate himself, i.e., to prove his identity, to another party, called the verifier, by sending a single authentication message.

Functional magnetic resonance imaging (fMRI) provides an effective and noninvasive tool for researchers to understand cerebral functions and correlate them with brain activities. In addition, with the ever-increasing diffusion of the Internet, such images may be exchanged in several ways, allowing new research and medical services. On the other hand, ensuring the security of exchanged fMRI data becomes a main concern due to their special characteristics arising from strict ethics and legislative and diagnostic implications. Again, the risks increase when dealing with open environments like the Internet. For this reason, security mechanisms that ensure protection of such data are strongly required. However, we remark that the mechanisms commonly employed for data protection are doomed to fail when dealing with imaging data. In this article, we propose a novel watermarking scheme explicitly addressed for this type of imaging. Such a scheme can be used for several purposes, particularly to ensure authenticity and integrity. Moreover, we show how to integrate our scheme within commercial off-the-shelf fMRI system. Finally, the validity and the efficiency of our scheme has been assessed through testing.

Differently from attacks aimed at gaining control of the resources of a mobile device, energy-related attacks have the essential goal of significantly raising the energy demand on the victim side, without apparently affecting its activities. It is a fundamental point to highlight how such a goal can possibly be accomplished by mounting well-known canonical attacks and waiting for the system defenses to detect and stop them. In such an endeavor, defenses require additional amounts of energy which eventually render the mobile device completely useless. In the System on Chip (SoC) architecture, many components, each with a separate function, are integrated. As the total energy adsorption is the composition of the energy consumptions of individual components, each component may be the target of an energy-based attack. This work analyzes and discusses the effects and implication of new energy-based Denial of Service attacks based on the proper solicitation of hardware-layer encode/decode capabilities by using specifically crafted multimedia resources, in order to introduce an anomalous battery drain, and hence significantly shorten the overall battery lifetime in mobile smart devices. These attacks do not require physical access nor compromise of the target device, and they take advantage of new HTML5 functionalities that can be properly triggered during normal browsing activity. The more significant result is that the Digital Signal Processor (DSP) offers an exploitable attack surface to be kept into consideration early in the design process. Countermeasures include special filtering rules that prevent “irrelevant” content from reaching the DSP or, in a more far-reached perspective, the introduction of a power-draw controller on the SoC with the purpose of monitoring energy consumption and raising alerts.

A hierarchical key assignment scheme is a method to assign some private information and encryption keys to a set of classes in a partially ordered hierarchy, in such a way that the private information of a higher class can be used to derive the keys of all classes lower down in the hierarchy. In this paper we analyze the security of hierarchical key assignment schemes according to different notions: security with respect to key indistinguishability and against key recovery, as well as the two recently proposed notions of security with respect to strong key indistinguishability and against strong key recovery . We first explore the relations between all security notions and, in particular, we prove that security with respect to strong key indistinguishability is not stronger than the one with respect to key indistinguishability. Afterwards, we propose a general construction yielding a hierarchical key assignment scheme offering security against strong key recovery, given any hierarchical key assignment scheme which guarantees security against key recovery.

Access control ensures that only the authorized users of a system are allowed to access certain resources or tasks. Usually, according to their roles and responsibilities, users are organized in hierarchies formed by a certain number of disjoint classes. Such hierarchies are implemented by assigning a key to each class, so that the keys for descendant classes can be efficiently derived from classes higher in the hierarchy. However, pure hierarchical access may represent a limitation in many real-world cases. In fact, sometimes it is necessary to ensure access to a resource or task by considering both its directly responsible user and a group of users possessing certain credentials. In this paper, we first propose a novel model that generalizes the conventional hierarchical access control paradigm, by extending it to certain additional sets of qualified users. Afterward, we propose two constructions for hierarchical key assignment schemes in this new model, which are provably secure with respect to key indistinguishability. In particular, the former construction relies on both symmetric encryption and perfect secret sharing, whereas, the latter is based on public-key threshold broadcast encryption.

A hierarchical key assignment scheme is a method to assign some private information and encryption keys to a set of classes in a partially ordered hierarchy, in such a way that the private information of a higher class can be used to derive the keys of all classes lower down in the hierarchy. Sometimes, it is necessary to make dynamic updates to the hierarchy, in order to implement an access control policy which evolves with time. All security models for hierarchical key assignment schemes have been designed to cope with static hierarchies and do not consider the issue of performing dynamic updates to the hierarchy. In this paper, we define the concept of hierarchical key assignment schemes supporting dynamic updates, formalizing the relative security model. In particular, we provide the notion of security with respect to key indistinguishability, by considering the dynamic changes to the hierarchy. Moreover, we show how to construct a hierarchical key assignment scheme supporting dynamic updates, by using as a building block a symmetric encryption scheme. The proposed construction is provably secure with respect to key indistinguishability, and provides efficient key derivation and updating procedures, while requiring each user to store only a single private key.

Functional Magnetic Resonance Imaging provides researchers with an effective and non-invasive tool to understand cerebral functions and correlate them with brain activities. With the ever increasing diffusion of the Internet such images may be exchanged in several ways, thus allowing new research and medical services. On the other hand, ensuring the security of exchanged fMRI data becomes a main concern, due to the special characteristics arising from strict ethics, legislative and diagnostic implications. So it is very important to prevent unauthorized manipulation and misappropriation of such images. The risks are increased when dealing with open environments like the Internet. For this reason, security mechanisms which ensure protection of such data are required. In this paper we introduce a watermarking scheme explicitly designed for this kind of images. In particular, such a scheme belongs to the category of fragile reversible watermarking. The validity of this scheme has been demonstrated through testing. Finally, by using the proposed scheme, we show how to create a distributed security solution that models a multi-domain environment, for ensuring authenticity and integrity of such images.

Abstract The Web is experiencing an explosive growth in the last years. New technologies are introduced at a very fast pace with the aim of narrowing the gap between web‐based applications and traditional desktop applications. The results are web applications that look and feel almost like desktop applications while retaining the advantages of being originated from the Web. However, these advancements come at a price. The same technologies used to build responsive, pleasant, and fully featured web applications can also be used to write web malware able to escape detection systems. In this article, we present new obfuscation techniques, on the basis of some of the features of the upcoming HTML5 standard, which can be used to deceive malware detection systems. The proposed techniques have been experimented on a reference set of obfuscated malware. Our results show that the malware rewritten using our obfuscation techniques goes undetected while being analyzed by a large number of detection systems. The same detection systems were able to correctly identify the same malware in its original unobfuscated form. We also provide some hints about how the existing malware detection systems can be modified in order to cope with these new techniques. Copyright © 2014 John Wiley & Sons, Ltd.

Authentication protocols prevent resources to be accessed by unauthorized users. Password authentication is one of the simplest and most convenient authentication mechanism over insecure networks and, in particular, the one-time authentication mechanism, in which the password is valid only for one login session or transaction are a good compromise between simplicity of use and security. Nowadays many of such protocols have been proposed to implement that type of authentication. However, most of them have several drawbacks because they are characterized by considerable overhead in the Key Setup, Key Scheduling and Key Update phases. In addition, they are often vulnerable to several known attacks and are not particularly suitable to be used by mobile terminals. Furthermore, they often rely on smart-card and other hardware tokens, thus requiring an active participation by the user. In this paper, we present a robust one-time authentication protocol, based on two cryptographically strong building blocks, namely, the Authenticated Key Exchange key exchange and the keyed Hash Message Authentication Code (HMAC), that provides several advantages with respect to most of the available solutions at the state of the art. First, it enables transparent mutual authentication between two endpoints. Moreover, Key Setup, Key Scheduling and Key Update operations are accomplished independently by both endpoints, without requiring any interaction among them, thus ensuring the fully independence by any Trusted Third Party. Finally, the proposed protocol is cryptographically secure, under standard assumptions against most of the already known OTP attacks.

People using smartphones to connect to the Internet for day-life activities has overtaken the number of people using canonical PCs. This lead to a huge quantity of security threats that usually tend to penetrate the defenses of a smartphone in order to gain control of its resources. Differently, energy-based attacks have the objective of increasing the energy consumption of the victim device. It is important to highlight that this objective could be possibly achieved by just activating the system's defenses as a consequence of canonical attacks and letting the system defenses detect and (try to) defeat them. These activities consume additional energy and could led the mobile device to its complete uselessness. In this paper, an energy-based attack based on soliciting hardware-level encoding/decoding functions through properly crafted multimedia files is analyzed and its impact evaluated. Such kind of attacks are performed without accessing the device by taking advantage of the new HTML5 functionalities. A series of experiments have been performed in order to understand which are the codecs that have a more relevant impact on energy consumption, and, as a consequence, that make the attack more effective.

Visual cryptography is a special type of secret sharing. Two models of visual cryptography have been independently studied: 1) deterministic visual cryptography, introduced by Naor and Shamir, and 2) random grid visual cryptography, introduced by Kafri and Keren. In this paper, we show that there is a strict relation between these two models. In particular, we show that to any random grid scheme corresponds a deterministic scheme and vice versa. This allows us to use results known in a model also in the other model. By exploiting the (many) results known in the deterministic model, we are able to improve several schemes and to provide many upper bounds for the random grid model and by exploiting some results known for the random grid model, we are also able to provide new schemes for the deterministic model. A side effect of this paper is that future new results for any one of the two models should not ignore, and in fact be compared with, the results known in the other model.

The growing intelligence and popularity of smartphones and the advances in Mobile Ubiquitous Computing have resulted in rapid proliferation of data-sharing applications. Instances of these applications include pervasive social networking, games, file sharing and so on. In such scenarios, users are usually involved in selecting the peers with whom communication should take place, continuously facing trust issues. Unfortunately, providing trust support in a pervasive world is challenging due to peer mobility and lack in central control. We propose a novel approach that establishes trust leveraging users' profiles: humans today produce rich strings of unique data twenty-four hours a day. These information enables a task-aware trust model, namely a finer-grained model in which users are classified as trusted or not depending on the intended business activity. However, simply collecting user's interests may be insufficient to provide a reasonable trust management system. In order to enable the system to recognize malicious users, we include a recommendation subsystem based on the Wilson score confidence interval. It has been designed to be lightweight, minimizing battery depletion. It also protects user privacy. To make our approach fully deployable, it supports two modalities: a TPM-based one and a TPM-less one. The former gives more security guarantees and ensures a fully distributed approach. The latter, requires a Trusted Authority to avoid feedbacks to get tampered and is no more fully distributed.

In the last decade Digital Forensics has experienced several issues when dealing with network evidence. An analyst, which is in charge of managing evidence flowing over a network have to face problems due to the volatile nature of such information. In facts, such data may change over time, may be lying on a server out of the his jurisdiction, or geographically far from where the crime was committed. In this paper two methods to allow remote collection of network evidence produced by online services such as web pages, chats, documents, photos and videos are presented. They enable the analyst to drive the acquisition process through the online services considered potential sources of evidence. During the process, all data flowing through the network is automatically collected (i.e., all the IP packets). The second one also collects the graphical representation of the acquisition (e.g., how the browser visualizes such data). Both methods introduce a trusted third party (acting as a digital notary) which is in charge of collecting and ``certifying'' network evidence. Before closing the acquisition process, a detailed report of the collected evidence is generated and made available to the analyst along with the collected data. Cryptographic primitives are used to demonstrate ex post data integrity, how it has been acquired and the acquisition time. As a proof of concept two prototypes have been implemented. To enhance the Court confidence of the collected evidence, at the same time, the service could be run across multiple coordinated servers acquiring the same data from different point of the network.

The growing need for user privacy protection has lead to the development of general notions and efficient tools for building privacy-preserving applications. Among them, the notion of key privacy in public-key encryption, which guarantees that an adversary is unable to tell with which public key a certain ciphertext has been produced, plays a key-role in the design of several anonymous protocols. Apparently, it seems to be unrelated to the security of the encrypted content, and it looks like just an additional property the encryption scheme can enjoy. In this paper we show that for a robust encryption scheme key privacy under chosen ciphertext attack implies non-malleability and, hence, security under chosen ciphertext attacks. Then, we look at two privacy-preserving protocols: secret sets and anonymous broadcast encryption. We prove that secret sets and anonymous broadcast are equivalent w.r.t. non-adaptive adversaries: the first can be used to design the second and vice versa. Finally, we revisit some previous constructions for secret sets, and we show the security properties they enjoy within a rigorously defined adversarial model.

A recent research trend, motivated by the massive deployment of RFID technology, looks at cryptographic protocols for securing communication between entities in which some of the parties have very limited computing capabilities. In this paper, we focus our attention on SASI, a new RFID authentication protocol, designed for providing Strong Authentication and Strong Integrity. SASI is a good representative of a family of RFID authentication protocols, referred to as Ultralightweight RFID authentication protocols. These protocols, suitable for passive Tags with limited computational power and storage, involve simple bitwise operations such as and, or, exclusive or, modular addition, and cyclic shift operations. They are efficient, fit the hardware constraints, and can be seen as an example of the above research trend. However, the main concern is the real security of these protocols, which are often supported only by apparently reasonable and intuitive arguments. The contribution we provide with this work is the following: we start by showing some weaknesses in the SASI protocol, and then, we describe how such weaknesses, through a sequence of simple steps, can be used to compute in an efficient way all secret data used for the authentication process. Specifically, we describe three attacks: 1) a desynchronization attack, through which an adversary can break the synchronization between the RFID Reader and the Tag; 2) an identity disclosure attack, through which an adversary can compute the identity of the Tag; and 3) a full disclosure attack, which enables an adversary to retrieve all secret data stored in the Tag. Then, we present some experimental results, obtained by running several tests on an implementation of the protocol, in order to evaluate the performance of the proposed attacks, which confirm that the attacks are effective and efficient. It comes out that an active adversary by interacting with a Tag more or less three hundred times, makes the authentication protocol completely useless. Finally, we close the paper with some observations. The cryptoanalysis of SASI gets some new light on the ultralightweight approach, and can also serve as a warning to researchers working on the field and tempted to apply these techniques. Indeed, the results of this work, rise serious questions regarding the limits of the ultralightweight family of protocols, and on the benefits of these ad hoc protocol design strategies and informal security analysis.

Nowadays, Short Message Service (SMS) still represents the most used mobile messaging service. SMS messages are used in many different application fields, even in cases where security features, such as authentication and confidentiality between the communicators, must be ensured. Unfortunately, the SMS technology does not provide a built-in support for any security feature. This work presents SEESMS (Secure Extensible and Efficient SMS), a software framework written in Java which allows two peers to exchange encrypted and digitally signed SMS messages. The communication between peers is secured by using public-key cryptography. The key-exchange process is implemented by using a novel and simple security protocol which minimizes the number of SMS messages to use. SEESMS supports the encryption of a communication channel through the ECIES and the RSA algorithms. The identity validation of the contacts involved in the communication is implemented through the RSA, DSA and ECDSA signature schemes. SEESMS is able to certify the phone number of the peers using the framework. Additional cryptosystems can be coded and added to SEESMS as plug-ins. Special attention has been devoted to the implementation of an efficient framework in terms of energy consumption and execution time. This efficiency is obtained in two steps. First, all the cryptosystems available in the framework are implemented using mature and fully optimized cryptographic libraries. Second, an experimental analysis was conducted to determine which combination of cryptosystems and security parameters were able to provide a better trade-off in terms of speed/security and energy consumption. This experimental analysis has also been useful to expose some serious performance issues affecting the cryptographic libraries which are commonly used to implement security features on mobile devices.

In this paper, we consider the problem of cheating for visual cryptography schemes. Although the problem of cheating has been extensively studied for secret sharing schemes, little work has been done for visual secret sharing. We provide a formal definition of cheating for visual cryptography and new (2, n)-threshold and (n, n)-threshold schemes that are immune to deterministic cheating.

In this paper we propose a novel approach to the learning of cryptographic protocols, based on a collaborative role-based visualization system, DISCERN, that helps students to understand a protocol by actively engaging them in a simulation of its execution. In DISCERN, each student shares a visual e

Over the last few years, many universities and educational institutions have introduced computer security related courses to their degree programs. The majority of these courses feature intensive laboratory activity based on live experiments of attack and defense techniques by means of team games organized as "cyber-wars". In this paper we argue that, although it is a useful tool for teaching and learning these techniques, the exercise paradigm does not cover all the aspects of security relating to a real-world scenario, with it not allowing students to experience the realistic needs of maintaining network services. In this paper we present the "role-game of the Internet" which was designed as part of the lab activity of our Network Security Course. In our game, instead of fighting against each other, student-teams had to cooperate in order to accomplish a list of business-like tasks over a simulation of the Internet while preserving the security and availability of featured network services.

We investigate structural properties of interactive perfect zero-knowledge (PZK) proofs. Specifically, we look into the closure properties of PZK languages under monotone boolean formula composition. This gives rise to new protocol techniques. We show that interactive PZK for random self-reducible (RSR) (and for co-RSR) languages is closed under monotone boolean formula composition. Namely, we present PZK proofs for monotone boolean formulae whose atoms are statements about membership in a PZK language which is RSR (or whose complement is RSR). We also discuss extensions, recent applications, and generalizations of the techniques.

A time-bound hierarchical key assignment scheme is a method to assign time-dependent encryption keys to a set of classes in a partially ordered hierarchy, in such a way that each class can derive the keys of all classes lower down in the hierarchy, according to temporal constraints.

A time-bound hierarchical key assignment scheme is a method to assign time-dependent encryption keys to a set of classes in a partially ordered hierarchy, in such a way that the key of a higher class can be used to derive the keys of all classes lower down in the hierarchy, according to temporal constraints.In this paper we design and analyze time-bound hierarchical key assignment schemes which are provably-secure and efficient. We first consider the unconditionally secure setting and we show a tight lower bound on the size of the private information distributed to each class. Then, we consider the computationally secure setting and obtain several results: We first prove that a recently proposed scheme is insecure against collusion attacks. Hence, motivated by the need for provably-secure schemes, we propose two different constructions for time-bound hierarchical key assignment schemes. The first one is based on symmetric encryption schemes, whereas, the second one makes use of bilinear maps. These appear to be the first constructions of time-bound hierarchical key assignment schemes which are simultaneously practical and provably-secure.

Visual cryptography schemes allow the encoding of a secret image, consisting of black or white pixels, into n shares which are distributed to the participants. The shares are such that only qualified subsets of participants can ‘visually’ recover the secret image. The secret pixels are shared with techniques that subdivide each secret pixel into a certain number m, m ≥ 2 of subpixels. Such a parameter m is called pixel expansion. Recently Yang introduced a probabilistic model. In such a model the pixel expansion m is 1, that is, there is no pixel expansion. The reconstruction of the image however is probabilistic, meaning that a secret pixel will be correctly reconstructed only with a certain probability. In this paper we propose a generalization of the model proposed by Yang. In our model we fix the pixel expansion m ≥ 1 that can be tolerated and we consider probabilistic schemes attaining such a pixel expansion. For m = 1 our model reduces to the one of Yang. For big enough values of m, for which a deterministic scheme exists, our model reduces to the classical deterministic model. We show that between these two extremes one can trade the probability factor of the scheme with the pixel expansion. Moreover, we prove that there is a one-to-one mapping between deterministic schemes and probabilistic schemes with no pixel expansion, where contrast is traded for the probability factor.

This paper deals with the access control problem. We assume that valuable resources need to be protected against unauthorized users and that, to this aim, a password-based access control scheme is employed. Such an abstract scenario captures many applicative settings. The issue we focus our attention on is the following: password-based schemes provide a certain level of security as long as users choose good passwords, i.e., passwords that are hard to guess in a reasonable amount of time. In order to force the users to make good choices, a proactive password checker can be implemented as a submodule of the access control scheme. Such a checker, any time the user chooses/changes his own password, decides on the fly whether to accept or refuse the new password, depending on its guessability. Hence, the question is: how can we get an effective and efficient proactive password checker? By means of neural networks and statistical techniques, we answer the above question, developing suitable proactive password checkers. Through a series of experiments, we show that these checkers have very good performance: error rates are comparable to those of the best existing checkers, implemented on different principles and by using other methodologies, and the memory requirements are better in several cases. It is the first time that neural network technology has been fully and successfully applied to designing proactive password checkers

Self-healing key distribution schemes allow group managers to broadcast session keys to large and dynamic groups of users over unreliable channels. Roughly speaking, even if during a certain session some broadcast messages are lost due to network faults, the self-healing property of the scheme enables each group member to recover the key from the broadcast messages he has received before and after that session. Such schemes are quite suitable in supporting secure communication in wireless networks and mobile wireless ad-hoc networks. Recent papers have focused on self-healing key distribution, and have provided definitions, stated in terms of the entropy function, and some constructions. The contribution of this paper is the following: We analyze current definitions of self-healing key distribution and, for two of them, we show that no protocol can achieve the definition. We show that a lower bound on the size of the broadcast message, previously derived, does not hold. We propose a new definition of self-healing key distribution, and we show that it can be achieved by concrete schemes. We give some lower bounds on the resources required for implementing such schemes, i.e., user memory storage and communication complexity. We prove that the bounds are tight

Visual cryptography schemes allow the encoding of a secret image into n shares which are distributed to the participants, such that only qualified subsets of participants can "visually" recover the secret image. In colored threshold visual cryptography schemes, the secret image is composed of pixels taken from a given set of c colors. We study c-color (k, n)-threshold visual cryptography schemes and provide a characterization of contrast optimal schemes. More specifically, we prove that there exists a contrast optimal scheme that is a member of a special set of schemes, which we call canonical schemes, and that satisfy strong symmetry properties. Then we use canonical schemes to provide a constructive proof of optimality, with respect to the pixel expansion, of c-color (n, n)-threshold visual cryptography schemes.

A (k,n)-threshold visual cryptography scheme (VCS) is a method to encode a secret image SI into n shadow images called shares such that any k or more shares enable the "visual" recovery of the secret image. However, by inspecting less than k shares one cannot gain any information on the secret image. The "visual" recovery consists of copying the shares onto transparencies and then stacking them. Any k shares will reveal the secret image without any cryptographic computation. In this paper we analyze the contrast of the reconstructed image for a (k,n)-threshold VCS. We define a canonical form for a (k,n)-threshold VCS and provide a characterization of a (k,,n)-threshold VCS. We completely characterize a contrast optimal (n-1,n)-threshold VCS in canonical form. Moreover, for $n\geq 4$, we provide a contrast optimal (3,n)-threshold VCS in canonical form. We first describe a family of (3,n)-threshold VCS achieving various values of contrast and pixel expansion. Then we prove an upper bound on the contrast of any (3,n)-threshold VCS and show that a scheme in the described family has optimal contrast. Finally, for k=4,5 we present two schemes with contrast asymptotically equal to 1/64 and 1/256, respectively.

We consider the guessing problem proposed by Massey (see Proc. Int. Symp. Information Theory, p.204, 1994) of a cryptanalyst that wants to break a ciphertext with a brute-force attack. The best strategy he can use is to try out all possible keys, one at time in order of decreasing probability, after narrowing the possibilities by some cryptanalysis. In this correspondence we provide both upper and lower bounds on the entropy of the probability distribution on the secret keys in terms of the number of secret keys and of the average number of trials of the cryptanalyst.

A (t,k,n,S) ramp scheme is a protocol to distribute a secret s chosen in S among a set P of n participants in such a way that: (1) sets of participants of cardinality greater than or equal to k can reconstruct the secret s; (2) sets of participants of cardinality less than or equal to t have no information on s, whereas (3) sets of participants of cardinality greater than t and less than k might have "some" information on s. In this correspondence we analyze multiple ramp schemes, which are protocols to share many secrets among a set P of participants, using different ramp schemes. In particular, we prove a tight lower bound on the size of the shares held by each participant and on the dealer's randomness in multiple ramp schemes.

Identification schemes allow a user to identify herself to a verifying authority in a secure way (i.e., without revealing her secret key). Group identification schemes allow a user to identify herself as a member of a group of users in a secure and anonymous way (i.e., without revealing her identity nor her secret key). Several identification schemes and group identification schemes have been proposed in the literature. In this paper we consider the problem of constructing communication-efficient group identification schemes. Assuming factoring Blum integers is hard, we construct a secure and anonymous group identification scheme having communication complexity \\Theta(m+n), where m is the size of the group and n is the security parameter (previous results achieved complexity \\Theta(mn)). In fact, we show our protocol to be perfect zero-knowledge. We extend this scheme to the case of groups of t ? 1 users and obtain a protocol that improves on the communication complexity of previous ...

While compressing a file with a Huffman code, it is possible that the size of the file grows temporarily. This happens when the source letters with low frequencies (to which long codewords are assigned) are encoded first. The maximum data expansion is the average growth in bits per source letter resulting from the encoding of a source letter with a long codeword. It is a measure of the worst case temporary growth of the file. In this paper we study the maximum data expansion of Huffman codes. We provide some new properties of the maximum data expansion δ of Huffman codes and using these properties we prove that δ < 1.256.

In this correspondence, we prove that the maximum data expansion /spl delta/ of Huffman codes is upper-bounded by /spl delta/<1.39. This bound improves on the previous best known upper bound /spl delta/<2. We also provide some characterizations of the maximum data expansion of optimal codes.

/spl acute/A secret sharing scheme permits a secret to be shared among participants in such a way that only qualified subsets of participants can recover the secret, but any nonqualified subset has absolutely no information on the secret. We derive new limitations on the information rate of secret sharing schemes, that measures how much information is being distributed as shares as compared to the size of the secret key, and the average information rate, that is the ratio between the secret size and the arithmetic mean of the size of the shares. By applying the substitution technique, we are able to construct many new examples of access structures where the information rate is bounded away from 1. The substitution technique is a method used to obtain a new access structure by replacing a participant in a previous structure with a new access structure.>

We investigate structural properties of statistical zero knowledge (SZK) both in the interactive and in the non-interactive model. Specifically, we look into the closure properties of SZK languages under monotone logical formula composition. This gives rise to new protocol techniques. We show that interactive SZK for random self reducible languages (RSR) (and for co-RSR) is closed under monotone Boolean operations. Namely, we give SZK proofs for monotone Boolean formulae whose atoms are statements about an SZK language which is RSR (or a complement of RSR). All previously known languages in SZK are in these classes. We then show that if a language L has a non-interactive SZK proof system then honest-verifier interactive SZK proof systems exist for all monotone Boolean formulae whose atoms are statements about the complement of L. We also discuss extensions and generalizations.>

Article Free Access Share on How to share a function securely Authors: Alfredo De Santis Dip. di Informatica ed Applicazioni Università di Salerno, Baronissi (SA), Italy Dip. di Informatica ed Applicazioni Università di Salerno, Baronissi (SA), ItalyView Profile , Yvo Desmedt Dept. of EE&CS, Univ. of Wisconsin Milwaukee, WI Dept. of EE&CS, Univ. of Wisconsin Milwaukee, WIView Profile , Yair Frankel GTE Laboratories Incorporated, Waltham, MA GTE Laboratories Incorporated, Waltham, MAView Profile , Moti Yung IBM T. J. Watson Research Center, Yorktown Heights, NY IBM T. J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 522–533https://doi.org/10.1145/195058.195405Published:23 May 1994Publication History 193citation1,775DownloadsMetricsTotal Citations193Total Downloads1,775Last 12 Months169Last 6 weeks18 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The external path length of a treeT is the sum of the lengths of the paths from the root to each external node. The maximal path length difference, $\Delta $, is the difference between the lengths of the longest and shortest such paths Tight lower and upper bounds are proved on the external path length of binary trees with N external nodes and maximal path length difference $\Delta $ is prescribed. In particular, an upper bound is given that, for each value of $\Delta $, can be exactly achieved for infinitely many values of N. This improves on the previously known upper bound that could only be achieved up to a factor proportional to N. An elementary proof of the known upper bound is also presented as a preliminary result. Moreover, a lower bound is proved that can be exactly achieved for each value of N and $\Delta \leqslant {N / 2}$.

Binary prefix codes with the constraint that each codeword must end with a "1" have been recently introduced by Berger and Yeung (1990). We analyze the performance of such codes by investigating their average codeword length. In particular, we show that a very simple strategy permits the construction of a "1"-ended binary prefix code whose average codeword length is less than H+1 for any discrete source with entropy H. We also prove a tight lower bound on the optimal average codeword length in terms of H and of the minimum letter probability of the source. Finally, we discuss the problem of finding an optimum feasible code.>

A zero-knowledge proof system of knowledge is a protocol between two parties called the prover and the verifier. The prover wants to convince the verifier that he 'knows' the proof of a given theorem without revealing any additional information. This is different from a zero-knowledge proof system of membership where the prover convinces the verifier only of the veridicity of the statement. Zero-knowledge proofs of knowledge are very useful tools in the design of secure protocols. Though, the concept of a proof of knowledge is a very subtle one and great care is needed to obtain a satisfying formalization. The authors investigate the concept of a zero-knowledge proof of knowledge with a non-interactive model. Here, the prover and the verifier share a short random string and the only communication allowed is from the prover to the verifier. Although this is a simpler model than the interactive one, still formalizing zero-knowledge proofs of knowledge is a delicate task.>

Some limitations are given on the redundancy of D-ary codes with maximal codeword length L. An upper bound that improves on a previous result of E.N. Gilbert (1971) is given. It is then shown that the redundancy of these constrained codes is very close to that of the unconstrained Huffman codes when the number of codewords N is such that ND/sup 1-L/ becomes negligible. A tight bound is given on the redundancy when only the most likely probabilities are known. In the binary case, a tight lower bound is given on the redundancy when only the least likely probability is known.>

The problem of constructing statistically synchronizable codes over arbitrary alphabets and for any finite source is considered. It is shown how to efficiently construct a statistically synchronizable code whose average codeword length is within the least likely codeword probability from that of the Huffman code for the same source. Moreover, a method is given for constructing codes having a synchronizing codeword. The method yields synchronous codes that exhibit high synchronizing capability and low redundancy.>

The codeword lengths of a maximal prefix code with minimum length among those with a given number of codewords differ by at most one. This paper studies the length of the optimal maximal prefix code with a given number N of codewords and the additional constraint that the difference of the lengths of the longest and shortest codeword must be equal to a given parameter Delta . An optimal algorithm is given that, for all N and Delta , constructs an (N, Delta )-MPC of minimum length. Then a lower bound is given for the length of the optimal (N, Delta )-MPC for Delta>

This paper investigates the possibility of disposing of interaction between prover and verifier in a zero-knowledge proof if they share beforehand a short random string. Without any assumption, it is proven that noninteractive zero-knowledge proofs exist for some number-theoretic languages for which no efficient algorithm is known. If deciding quadratic residuosity (modulo composite integers whose factorization is not known) is computationally hard, it is shown that the NP-complete language of satisfiability also possesses noninteractive zero-knowledge proofs.

An upper bound on the redundancy of D-ary Huffman codes in terms of the probability p/sub 1/ of the most likely source letter is provided. For large values of p/sub 1/, the bound improves the one given by R.G. Gallager (1978). Additionally, some results known for the binary case (D=2) are extended to arbitrary D-ary Huffman codes. As a consequence, a tight lower bound that corrects a bound recently proposed by J.D. Golic and M.M. Obradovic (1987) is derived.>

Upper and lower bounds are obtained for the redundancy of binary Huffman codes for a memoryless source whose least likely source letter probability is known. Tight upper bounds on redundancy in terms of the most and least likely source letter probabilities are provided.>

Bounds on the redundancy of Huffman codes in terms of the probability p/sub 1/ of the most likely source letter are provided. In particular, upper bounds are presented that are sharper than the bounds given recently by R.G. Gallager (ibid., vol.IT-24, no.6, p.668-74, Nov.1978) and by R.M. Capocelli et al. (ibid., vol. IT-32, no.6, p.854-857, Nov. 1986) for an interval 2/(2/sup l+1/+1)or=2. It is shown that the new bounds are the tightest possible for these intervals.>

The question of how to learn rules, when those rules make probabilistic statements about the future, is considered. Issues are discussed that arise when attempting to determine what a good prediction function is, when those prediction functions make probabilistic assumptions. Learning has at least two purposes: to enable the learner to make predictions in the future and to satisfy intellectual curiosity as to the underlying cause of a process. Two results related to these distinct goals are given. In both cases, the inputs are a countable collection of functions which make probabilistic statements about a sequence of events. One of the results shows how to find one of the functions, which generated the sequence, the other result allows to do as well in terms of predicting events as the best of the collection. In both cases the results are obtained by evaluating a function based on a tradeoff between its simplicity and the accuracy of its predictions.>

Upper bounds on the entropy of a countable integer-valued random variable are furnished in terms of the expectation of the logarithm function. In particular, an upper bound is derived that is sharper than that of P. Elias (ibid., vol.IT-21, no.2, p.194-203, 1975), for all values of E/sub p/(log). Bounds that are better only for large values of E/sub p/ than the previous known upper bounds are also provided.>

Proof is given that no regular or synchronizable universal codeword sets can achieve optimality. Some asymptotic properties of a remarkable class of regular codeword sets related to the Fibonacci representation of integers are also obtained.