We study authenticated encryption (AE) modes dedicated to very short messages, which are crucial for Internet of Things applications. One of the most popular class of AE is built on block ciphers, namely a mode of operation. The computational cost of a mode is typically measured by its rate, indicating the number of input blocks processed per block cipher call in asymptotic terms. While certain modes demonstrate efficiency in terms of rate, such as$\mathsf { OCB}$, this metric does not always accurately portray the total computational burden as it ignores overhead. Consequently, modes efficient in terms of rate may not always perform optimally with short messages. This observation motivates us to study modes that are efficient on short inputs rather than focusing on rate. Since the existing general-purpose AE modes need at least three block cipher calls for nonempty messages, we explore the design space for AE modes that use at most two calls. We propose a family of AE modes, dubbed$ \mathsf {Manx}$, which work when the total input length is less than$2n$bits, using an n-bit block cipher. Notably, the second construction of$ \mathsf {Manx}$can encrypt almost n-bit plaintexts and saves one or two block cipher calls compared to standard modes, such as$\mathsf { GCM}$or$\mathsf { OCB}$, while preserving comparable provable security. In addition to the conventional security against nonce-respecting adversary, we prove that$ \mathsf {Manx}$have security against nonce-misusing adversary with a different security level for each family member. We also present benchmarks on popular 8/32-bit microprocessors, namely 8-bit AVR, 32-bit ARM Cortex-M0, and ARM Cortex-M4, using AES and lightweight block ciphers. Our results show the clear advantage of$ \mathsf {Manx}$over the previous modes for such short messages. In particular,$ \mathsf {Manx2}$has significant performance gain from the existing representative schemes thanks to the simple structure and parallelizability. For example, using AES-128,$ \mathsf {Manx2}$is faster than$\mathsf { OCB}$by a factor of 1.5 to 1.7 to process a 64-bit nonce and a 120-bit plaintext.

Challenge-response entity authentication can be implemented with a MAC function. In such an entity authentication scheme, if a server has to authenticate a large number of entities simultaneously, for example, in an IoT network, aggregate MAC is applicable. Aggregate MAC allows multiple tags (responses to the challenge) of entities to be aggregated into a single short tag so that the server can authenticate the entities only with it. If the pair of a challenge and the corresponding aggregate tag is valid, then all the involved entities are valid. However, a drawback of this method is that the server cannot identify invalid entities if they exist. We propose group-testing aggregate entity authentication by adapting group testing for entity authentication using aggregate MAC to solve this problem. We formalize its security requirements and reduces the security of our generic construction to that of aggregate MAC and group testing. We also extend our generic construction to produce a secure scheme from a weaker but efficient and plausible aggregate MAC scheme.

Abstract Broadcast Encryption (BE) is public-key encryption allowing a sender to encrypt a message by specifing recipients, and only the specified recipients can decrypt the message. In several BE applications, since the privacy of recipients allowed to access the message is often as important as the confidentiality of the message, anonymity is introduced as an additional but important security requirement for BE. Kiayias and Samari (IH 2013) presented an asymptotic lower bound on the ciphertext sizes in BE schemes satisfying anonymity (ANO-BE for short). More precisely, their lower bound is derived under the assumption that ANO-BE schemes have a special property. However, it is insufficient to show their lower bound is asymptotically tight since it is unclear whether existing ANO-BE schemes meet the special property. In this work, we derive asymptotically tight lower bounds on the ciphertext size in ANO-BE by assuming only properties that most existing ANO-BE schemes satisfy. With a similar technique, we first derive asymptoticallyPlease provide MSC codes. For more details, please visit http://www.ams.org/msc/. tight lower bounds on the authenticator sizes in Anonymous Broadcast Authentication (ABA). Furthermore, we extend the above result and present (non-asymptotically) tight lower and upper bounds on thePlease check and confirm the Running title. ciphertext sizes in ANO-BE. We show that a variant of ANO-BE scheme proposed by Li and Gong (ACNS 2018) is optimal. We also provide tight bounds on the authenticator sizes in ABA via the same approach as ANO-BE, and propose an optimal construction for ABA.

In the age of Internet of Things (IoT), exploitation of security vulnerabilities is increasing, including self-propagating IoT malware. As an answer, specific research on IoT malware is being developed. Many studies use Markov chain models of malware propagation to predict the behavior of epidemics qualitatively and quantitatively. However, most studies approximate random propagation as a simple multiplicative term and no exact derivation of the Markov chain for random propagation was done so far. Moreover, systems of malware mitigation operating at the network level are rare and the majority of proposals focus on local networks like wireless sensor networks. In this article, we present a simple derivation of the exact Markov chain for random propagation of malware. Our model assumes a binomial form, compatible with binomial distributions in stochastic studies. To validate this derivation we implemented a stochastic simulation for the simplest compartmental epidemic model, susceptible–infected–susceptible (SIS). Predictions of the proposed Markov chain match simulation results with less than 0.2% error, well within stochastic variability and much smaller than the error of literature models. To complement our model of propagation, we developed and derived the Markov chain of a new system of malware mitigation, based on grouping random devices with identified infections during malware cleaning. Our mitigation system works at the network level and counteracts the vulnerability of mass deployment of IoT devices with aggressive but calculated mass disconnection. The system is able to artificially reduce$R_{0}$(the basic reproduction number) below 1 and prevent malware taking over the network—all without changing the rate of detection.

Message authentication code (MAC) is one of the most fundamental cryptographic primitives, and aggregate message authentication code (AMAC) is an authentication technique that can compress multiple MAC tags into a short tag for messages from multiple senders. Although AMAC cannot specify an invalid message, AMAC with detecting functionality (AMAD) enables us to compress multiple MAC tags and to identify an invalid message. In this paper, we propose construction of AMAD from biorthogonal codes, and show that our AMAD achieves a better compression rate than other constructions of AMAD.

We propose a physical-layer security approach based on the concept of steganography for IoT networks. Similar to the covert communications, the transmitter (Alice) attempts to send her secret signal to the legitimate receiver (Bob) avoiding being detected by the warden (Willie). Instead of sending the weak signal that is barely detectable by Willie, we hide secret signal in the cover signal that is transmitted over the same channel such that its existence may not be easily detected without any knowledge of prior information. Considering the practical applications to IoT networks, the DFT-precoded OFDM is adopted for the cover signal and conventional OFDM for the secret signal. Through theoretical analysis and corresponding simulations, the detection error probability of Willie is evaluated over an AWGN channel, revealing that judicious selection of cover signal power may increase the detection error probability of Willie and thus improve the covertness.

This paper analyzes the formalizations of information-theoretic security for the fundamental primitives in cryptography: symmetric-key encryption and key agreement. Revisiting the previous results, we can formalize information-theoretic security using different methods, by extending Shannon's perfect secrecy, by information-theoretic analogues of indistinguishability and semantic security, and by the frameworks for composability of protocols. We show the relationships among the security formalizations and obtain the following results. First, in the case of encryption, there are significant gaps among the formalizations, and a certain type of relaxed perfect secrecy or a variant of information-theoretic indistinguishability is the strongest notion. Second, in the case of key agreement, there are significant gaps among the formalizations, and a certain type of relaxed perfect secrecy is the strongest notion. In particular, in both encryption and key agreement, the formalization of composable security is not stronger than any other formalizations. Furthermore, as an application of the relationships in encryption and key agreement, we simultaneously derive a family of lower bounds on the size of secret keys and security quantities required under the above formalizations, which also implies the importance and usefulness of the relationships.

The traditional theory of information-theoretically secure authentication codes (A-codes) developed by Simmons and others usually assumes that a uniformly random source for truly random keys is available. However, if we consider the scenario without the assumption, previously known bounds on key-entropy are not tight. In this paper, tighter lower bounds of A-codes with non-uniformly random secret keys are investigated and derived in terms of the Rényi entropy.

Constructions of symmetric-key encryption with guessing secrecy are discussed. In the previous works, only a construction of symmetric-key encryption with average guessing secrecy is proposed for one-bit plaintexts. In this paper, we analyze a symmetric-key encryption with average guessing secrecy through OTP (one-time pad) constructions for a wide class of probability distributions of plaintexts and keys. As a result, we show a necessary and sufficient condition that such class of distributions satisfies average guessing secrecy in OTP constructions. On the other hand, we prove that optimal guessing secrecy is essentially equivalent to perfect secrecy under several natural restrictions. Therefore, only average guessing secrecy is meaningful for considering guessing secrecy other than perfect secrecy.

Fundamental results on secret sharing schemes (SSSs) are discussed in the setting where security and share size are measured by (conditional) min-entropies. We first formalize a unified framework of SSSs based on (conditional) Rέnyi entropies, which includes SSSs based on Shannon and min entropies etc. as special cases. By deriving the lower bound of share sizes in terms of Rέnyi entropies based on the technique introduced by Iwamoto-Shikata, we obtain the lower bounds of share sizes measured by min entropies as well as by Shannon entropies in a unified manner. As the main contributions of this paper, we show two existential results of non-perfect SSSs based on min-entropies under several important settings. We first show that there exists a nonperfect SSS for arbitrary binary secret information and arbitrary monotone access structure. In addition, for every integers k and n (k ≤ n), we prove that the ideal non-perfect (k, n)-threshold scheme exists even if the distribution of the secret is not uniformly distributed.

In this paper, we investigate relationships between the following formalizations of information-theoretic security for key agreement protocols which may have agreement-errors: formalizations extended (or relaxed) from Shannon's perfect secrecy by using mutual information and statistical distance; and the ones of composable security by Maurer et al. and Canetti. Then, we explicitly show that those are essentially equivalent. We also derive lower bounds on the adversary's (or distinguisher's) advantage and the size of a correlated randomness resource required under all of the above formalizations at once through our relationships. In addition, we observe impossibility results which easily follow from the lower bounds.

In this paper, we study key-agreement which realizes the protection against key-exposure problems in the information-theoretic security setting. And we newly define a model and security notions for information-theoretically secure key-insulated key-agreement (KI-KA for short). In addition, we show tight lower bounds of sizes of entities' secret-keys required for KI-KA. We also propose constructions of KI-KA which are provably secure and optimal. Furthermore, we provide some applications of KI-KA.

In this paper, we study unconditionally secure stegosystems against active attacks over an insecure channel in which an adversary can read and write a message. More specifically, we propose an information-theoretic model for steganography in the presence of active adversaries by extending both Simmons' and Cachin's works; and we show a generic construction of stegosystems secure against active attacks by using authenticated encryption in unconditional setting. Although the idea behind this construction is already used in different models (i.e., computational models and/or information-theoretic models with passive adversaries) of steganography, our contribution lies in showing the construction methodology provides provable and unconditional security against active adversaries.

Anonymous channels or similar techniques that achieve sender's anonymity play important roles in many applications, e.g. electronic voting. However, they will be meaningless if cryptographic primitives containing sender's identity are carelessly used during the transmission. In computationally secure settings, this problem may be easily overcome by using public key encryption and group signatures. However, in an unconditionally secure setting, in which no computational difficulty is assumed, this is not an easy case as such. As the increasing computational power approaches the point where security policy can no longer assume the difficulty of solving factoring or discrete logarithm problems, it must shift its focus to assuring the solvency of unconditionally secure schemes that provide long-term security. The main contribution of this paper is to study the security primitives for the above problem. In this paper, we first define the unconditionally secure asymmetric encryption scheme, which is an encryption scheme with unconditional security and where it is impossible for a receiver to deduce the identity of a sender from the encrypted message. We also investigate tight lower bounds on required memory sizes from an information theoretic viewpoint and show an optimal construction based on polynomials. It is remarkable to see that these bounds are considerably different from those in Shannon's model of the conventional unconditionally secure symmetric encryption. Other than the polynomial-based scheme, we also show a construction based on combinatorial theory, a non-malleable scheme and a multi-receiver scheme. Then, we define and formalize the group authentication code (GA-code), which is an unconditionally secure authentication code with anonymity like group signatures. In this scheme, any authenticated user will be able to generate and send an authenticated message while the receiver can verify the legitimacy of the message—that it has been sent from a legitimate user but at the same time retains his anonymity. However, by cooperating with the group authority, such as in the case of disputes, the receiver is able to obtain information of the user's identity. For GA-code, we show two concrete constructions.

Summary form only given. We discuss information-theoretic methods to prove the security of cryptosystems. We study what is called, unconditionally secure (or information-theoretically secure) cryptographic schemes in search for a system that can provide long-term security and that does not impose limits on the adversary's computational power.