Abstract Balogh et al. proposed deterministic secure multiparty computation called private PEZ protocols . In their work, a general construction of private PEZ protocols for computing an arbitrary function with n inputs is presented, but the function’s inputs must be binary . Binary domains are sufficient for computing functions with arbitrary domains because we can use the binary expansion of the inputs. However, such an expansion makes the protocol inefficient because unnecessary privacy is considered among the expanded bits of each input. Hence, we remove the binary expansion technique in this paper and propose a new private PEZ protocol directly applicable to functions with arbitrary domains. The proposed private PEZ protocol for an arbitrary function is much more efficient than Balogh et al.’s protocol. Concretely, an efficiency measure called the length of an initial string is exponentially improved in the domain size m : the order obtained from our construction is $$\mathcal {O}((2m)^{m^{n-1}})$$ O ( ( 2 m ) m n - 1 ) , while the construction of Balogh et al. yields $$\mathrm {\Omega }\bigg (\bigg (2^{\frac{m}{2}}\bigg )^{m^{n-1}}\bigg )$$ Ω ( ( 2 m 2 ) m n - 1 ) . The key idea of our protocol is called the divide and cue strategy, based on a recursive structure of views in private PEZ protocols.

Several relative entropy-based methods have been studied in cyber-attack detection of control systems. Most existing studies set the threshold values of relative entropy by trial and error such that their error probabilities become small. Meanwhile, the relationship between threshold values and error probabilities in likelihood ratio tests is clarified by Information theory. Information theory also clarifies the relationship between relative entropy and likelihood ratio test. To theoretically set the threshold, the authors have investigated the relationship between relative entropy and the likelihood ratio test using experimental data from DoS attacks and man-in-the-middle attacks on control communication (Modbus TCP). This paper investigates the relationship between threshold values and error probabilities in actual experiments. Error probabilities are classified as false positive rates and false negative rates. Neyman-Pearson lemma shows how to construct a detector that considers the trade-off between false positive and false negative rates. Stein’s lemma shows how to give optimal threshold values. We build a detector from the two lemmas that consider the trade-off with probability models of delay time between Response and ACK of Modbus TCP. We conduct experiments and discuss optimal threshold-setting methods in the sense that the false positive rates cannot be further reduced when false positive rates are fixed.

Cyber attacks on control system communication are increasing. In information systems, a lot of security counter-measure focusing on the distribution of communication packets has been studied so far. Such attack detection methods evaluate normal and abnormal packets based on the likelihood and the relative entropy. Whether the methods for information systems are also effective for control systems is another question. Then, this paper conducts attack detection experiments based on the likelihood and the relative entropy of DoS and spoofing attacks on Modbus TCP communication used in industrial control systems.

Dynamic searchable symmetric encryption (SSE) enables clients to update and search encrypted data stored on a server and provides efficient search operations instead of leakages of inconsequential information. The amount of permitted leakage is a crucial factor of dynamic SSE; more leakage allows us to design an efficient scheme, while leakage attacks tell us that the leakage has a real-world impact. Leakage-abuse attacks (NDSS 2012) and subsequent works suggest that dynamic SSE schemes should not unnecessarily reveal extra information during the search procedure, and in particular, file-injection attacks (USENIX Security 2016) showed that forward privacy, which restricts the leakage during the addition procedure, is a vital security notion for dynamic SSE. In this paper, we propose a new dynamic SSE scheme with a good balance of efficiency and security levels; our scheme achieves both high efficiency and forward-privacy and only requires the decent leakage, i.e., only allows the leakage of search and access patterns during search operations. Specifically, we first show there is still no such scheme by uncovering a flaw in the security proof of Etemad et al.'s scheme (PoPETs 2018) and showing that extra leakage is required to fix it. We then propose the first forward-private dynamic SSE scheme that only requires symmetric-key primitives and the standard, decent leakage to prove the security. Although the client's information is slightly larger than existing schemes, our experimental results show that our scheme is comparable to Etemad et al.'s scheme, which is the most-efficient-ever scheme with forward privacy, in terms of efficiency.

A multiple assignment scheme (MAS) is a method to construct secret sharing schemes (SSSs) for general access structures. There are MASs using threshold and ramp SSSs. The paper proposes new MASs using ideal SSSs realizing compartmented access structures and those using SSSs realizing multi-level access structures. Since the ideal SSSs realizing compartmented access structures and SSSs realizing multi-level access structures are natural generalizations of threshold and ramp SSSs, respectively, the new MASs cannot be less efficient than those using threshold or ramp SSSs.

Paral and Devadas introduced a simple key generation scheme with a physically unclonable function (PUF) that requires no error correction, e.g., by using a fuzzy extractor. Their scheme, called a pattern matching key generation (PMKG) scheme, is based on pattern matching between auxiliary data, assigned at the enrollment in advance, and a substring of PUF output, to reconstruct a key. The PMKG scheme repeats a round operation, including the pattern matching, to derive a key with high entropy. Later, to enhance the efficiency and security, a circular PMKG (C-PMKG) scheme was proposed. However, multiple round operations in these schemes make them impractical. In this paper, we propose a single-round circular PMKG (SC-PMKG) scheme. Unlike the previous schemes, our scheme invokes the PUF only once. Hence, there is no fear of information leakage by invoking the PUF with the (partially) same input multiple times in different rounds, and, therefore, the security consideration can be simplified. Moreover, we introduce another hash function to generate a check string which ensures the correctness of the key reconstruction. The string enables us not only to defeat manipulation attacks but also to prove the security theoretically. In addition to its simple construction, the SC-PMKG scheme can use a weak PUF like the SRAM-PUF as a building block if our system is properly implemented so that the PUF is directly inaccessible from the outside, and, therefore, it is suitable for tiny devices in the IoT systems. We discuss its security and show its feasibility by simulations and experiments.

Private operations (private permutations) were independently introduced by Nakai et al. and Marcedone et al. for implementing card-based cryptographic protocols efficiently. Recently, Nakai et al. showed that, if the private operations are available, secure computations of AND and OR operations for two inputs can be realized simultaneously by using four cards, and the protocol is applied to four-card majority voting protocol with three inputs. In this paper, it is shown that only three cards are sufficient to construct the majority voting protocol with three inputs. Specifically, we propose two constructions of three-input majority voting protocols. First, assuming that players are allowed to announce their outputs, we show that one card can be reduced from Nakai et al.'s protocol without any additional private operations and communications. Our second construction requires two more private operations and communications, whereas it removes the assumption on announcement from the first construction.

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.

Low uniqueness and vulnerability to machine-learning attacks are known as two major problems of Arbiter-Based Physically Unclonable Function (APUF) implemented on FPGAs. In this paper, we implement Double APUF (DAPUF) that duplicates the original APUF in order to overcome the problems. From the experimental results on Xilinx Virtex-5, we show that the uniqueness of DAPUF becomes almost ideal, and the prediction rate of the machine-learning attack decreases from 86% to 57%.

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.

Arbiter-basedPhysically Unclonable Function (PUF) is one kind of the delay-based PUFs that use the time difference of two delay-line signals.One of the previous work suggests that Arbiter PUFs implemented on Xilinx Virtex-5 FPGAs generate responses with almost no difference, i.e. with low uniqueness.In order to overcome this problem, Double Arbiter PUF was proposed, which is based on a novel technique for generating responses with high uniqueness from duplicated Arbiter PUFs on FPGAs.It needs the same costs as 2-XOR Arbiter PUF that XORs outputs of two Arbiter PUFs.Double Arbiter PUF is different from 2-XOR Arbiter PUF in terms of mode of operation for Arbiter PUF: the wire assignment between an arbiter and output signals from the final selectors located just before the arbiter.In this paper, we evaluate these PUFs as for uniqueness, randomness, and steadiness.We consider finding a new mode of operation for Arbiter PUF that can be realized on FPGA.In order to improve the uniqueness of responses, we propose 3-1 Double Arbiter PUF that has another duplicated Arbiter PUF, i.e. having 3 Arbiter PUFs and output 1-bit response.We compare 3-1 Double Arbiter PUF to 3-XOR Arbiter PUF according to the uniqueness, randomness, and steadiness, and show the difference between these PUFs by considering the mode of operation for Arbiter PUF.From our experimental results, the uniqueness of responses from 3-1 Double Arbiter PUF is approximately 50%, which is better than that from 3-XOR Arbiter PUF.We show that we can improve the uniqueness by using a new mode of operation for Arbiter PUF.

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.

A new model for a Client-Server Communication (CSC) system satisfying information theoretic security is proposed, and its fundamental properties are discussed. Our CSC allows n users to upload their respective messages to a server securely by using symmetric key encryptions with their own keys, and all ciphertexts are decrypted by the server. If we require all messages to be perfectly secure in CSC against the corrupted clients and adversaries without any keys, it is proved that a one time pad or more inefficient encryption must be used for each communication link between a client and the server. This means that, in order to realize more efficient CSC, it is necessary to leak out some information of each message. Based on these observations, we introduce a new model for such a secure CSC formally, and discuss its fundamental properties. In addition, we propose the optimal construction of CSC under several constraints on security parameters called security rates.

We propose a weak security notion for visual secret sharing (VSS) schemes. Under such a weak security notion, VSS schemes are designed to be secure against attackers' eyesight, but are not unconditionally secure, in general. In this paper, we theoretically discuss the relation between unconditionally secure (US) and weakly secure (WS) VSS schemes and present two constructions of WS-VSS schemes for color images. We show that WS-VSS schemes can achieve clearer color reproduced images with a smaller pixel expansion compared to those using US-VSS schemes, while we clarify that the basis matrices in both types of VSS schemes for black-white binary images are the same. These results suggest that the proposed VSS schemes can be regarded as ramp (or nonperfect) VSS schemes for color secret images.

This paper presents a comprehensive analysis of differential fault analysis (DFA) attacks on the Advanced Encryption Standard (AES) from an information-theoretic perspective. Injecting faults into cryptosystems is categorized as an active at tack where attackers induce an error in operations to retrieve the secret internal information, e.g., the secret key of ciphers. Here, we consider DFA attacks as equivalent to a special kind of passive attack where attackers can obtain leaked information without measurement noise. The DFA attacks are regarded as a conversion process from the leaked information to the secret key. Each fault model defines an upper bound for the amount of leaked information. The optimal DFA attacks should be able to exploit fully the leaked information in order to retrieve the secret key with a practical level of complexity. This paper discusses a new DFA methodology to achieve the optimal DFA attack by deriving the amount of the leaked information for various fault models from an information-theoretic perspective. We review several previous DFA at tacks on AES variants to check the optimality of their attacks. We also propose improved DFA attacks on AES-192 and AES-256 that reach the theoretical limits.

Coding theorems on a$(2,2)$-threshold scheme with an opponent are discussed in an asymptotic setup, where the opponent tries to impersonate one of the two participants. A situation is considered where$n$secrets$S^{n}$from a memoryless source is blockwisely encoded to two shares and the two shares are decoded to$S^{n}$with permitting negligible decoding error. We introduce correlation level of the two shares and characterize the minimum attainable rates of the shares and a uniform random number for realizing a$(2, 2)$-threshold scheme that is secure against the impersonation attack by the opponent. It is shown that if the correlation level between the two shares equals to$\ell \geq 0$, the minimum attainable rates coincide with$H(S)+\ell $, where$H(S)$denotes the entropy of the source, and the maximum attainable exponent of the success probability of the impersonation attack equals to$\ell $. It is also shown that a simple scheme using an ordinary$(2,2)$-threshold scheme attains all the bounds as well.

This paper is concerned with several security notions for information theoretically secure encryptions defined by the variational (statistical) distance. To ensure the perfect secrecy (PS), the mutual information is often used to evaluate the statistical independence between a message and a cryptogram. On the other hand, in order to recognize the information theoretically secure encryptions and computationally secure ones comprehensively, it is necessary to reconsider the notion of PS in terms of the variational distance. However, based on the variational distance, three kinds of definitions for PS are naturally introduced, but their relations are not known. In this paper, we clarify that one of three definitions for PS with the variational distance, which is a straightforward extension of Shannon's perfect secrecy, is stronger than the others, and the weaker two definitions of PS are essentially equivalent to the statistical versions of indistinguishability and semantic security.

It is known that a secret sharing scheme (SSS) with perfect cheating detection cannot be realized because such a SSS requires infinite share rates. However, this impossibility comes from the fact that block coding is not used and any decoding error is not allowed in the SSS. Hence, in this paper, we consider a SSS constructed by block coding with an arbitrarily small decoding error probability. It is shown that the perfect cheating detection with finite rates is possible for the 2-out-of-2 SSS in a certain asymptotic sense. Furthermore, the supremum of the achievable exponent in the maximum success probability of impersonation attack turns out to be the mutual information between the two shares.

Ramp secret sharing (SS) schemes can be classified into strong ramp SS schemes and weak ramp SS schemes. The strong ramp SS schemes do not leak out any part of a secret explicitly even in the case where some information about the secret leaks from a non-qualified set of shares, and hence, they are more desirable than weak ramp SS schemes. However, it is not known how to construct the strong ramp SS schemes in the case of general access structures. In this paper, it is shown that a strong ramp SS scheme can always be constructed from a SS scheme with plural secrets for any feasible general access structure. As a byproduct, it is pointed out that threshold ramp SS schemes based on Shamir's polynomial interpolation method are not always strong

This paper shows the derivation procedure of optimal secret sharing scheme (SSS) for a given access structure in the multiple assignment schemes based on integer programming.