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.

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.

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.

Abstract In this paper, we discuss security of public‐key cryptographic primitives in the case that the public key is fixed. In the standard argument, security of cryptographic primitives are evaluated by estimating the average probability of being successfully attacked where keys are treated as random variables. In contrast to this, in practice, a user is mostly interested in the security under his specific public key, which has been already fixed. However, it is obvious that such security cannot be mathematically guaranteed because for any given public key, there always potentially exists an adversary, which breaks its security. Therefore, the best what we can do is just to use a public key such that its effective adversary is not likely to be constructed in the real life and, thus, it is desired to provide a method for evaluating this possibility. The motivation of this work is to investigate (in)feasibility of predicting whether for a given fixed public key, its successful adversary will actually appear in the real life or not. As our main result, we prove that for any digital signature scheme or public key encryption scheme, it is impossible to reduce any fixed key adversary in any weaker security notion than the de facto ones (i.e., existential unforgery against adaptive chosen message attacks or indistinguishability against adaptive chosen ciphertext attacks) to fixed key adversaries in the de facto security notion in a black‐box manner. This result means that, for example, for any digital signature scheme, impossibility of extracting the secret key from a fixed public key will never imply existential unforgery against chosen message attacks under the same key as long as we consider only black‐box analysis. Copyright © 2016 John Wiley & Sons, Ltd.

In this paper, we present an efficient countermeasure against fault sensitivity analysis (FSA) based on configurable delay blocks (CDBs). FSA is a new type of fault attack, which exploits the relationship between fault sensitivity (FS) and secret information. Previous studies reported that it could break cryptographic modules equipped with conventional countermeasures against differential fault analysis (DFA), such as redundancy calculation, masked and-or, and wave dynamic differential logic. The proposed countermeasure can thwart both DFA and FSA attacks based on setup time violation faults. The proposed ideas are to use a CDB as a time base for detection and to combine the technique with Li's countermeasure concept that removes the dependency between FSs and secret data. The postmanufacture configuration of the CDBs allows minimization of the overhead in operating frequency that comes from manufacture variability. In this paper, we also present an implementation of the proposed countermeasure in application-specified integrated circuit, and describe its configuration method. We then investigate the hardware overhead of the proposed countermeasure for an advanced encryption standard processor and demonstrate its validity through an experiment.

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.

In this paper, we present an efficient countermeasure against Fault Sensitivity Analysis (FSA) based on a configurable delay blocks (CDBs). FSA is a new type of fault attack which exploits the relationship between fault sensitivity and secret information. Previous studies reported that it could break cryptographic modules equipped with conventional countermeasures against Differential Fault Analysis (DFA) such as redundancy calculation, Masked AND-OR and Wave Dynamic Differential Logic (WDDL). The proposed countermeasure can detect both DFA and FSA attacks based on setup time violation faults. The proposed ideas are to use a CDB as a time base for detection and to combine the technique with Li's countermeasure concept which removes the dependency between fault sensitivities and secret data. Post-manufacture configuration of the delay blocks allows minimization of the overhead in operating frequency which comes from manufacture variability. In this paper, we present an implementation of the proposed countermeasure, and describe its configuration method. We also investigate the hardware overhead of the proposed countermeasure implemented in ASIC for an AES module and demonstrate its validity through an experiment using a prototype FPGA implementation.

This paper proposes a new fault-based attack called fault sensitivity analysis (FSA) attack. In the FSA attack, fault injections are used to test out the sensitive information leakage called fault sensitivity. Fault sensitivity means the critical fault injection intensity that corresponds to the threshold between devices' normal and abnormal behaviors. We demonstrate that without using the values of the faulty outputs, attackers can obtain the information of the secret key based on the data-dependency of the collected fault sensitivity data. This paper explains the successful FSA attacks against three Advanced Encryption Standard (AES) hardware implementations, where two of them are resistant to the differential fault analysis. This paper also discusses the countermeasures against the proposed FSA attacks.

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.

The first contribution of our paper is that we propose a platform, a design strategy, and evaluation criteria for a fair and consistent hardware evaluation of the second-round SHA-3 candidates. Using a SASEBO-GII field-programmable gate array (FPGA) board as a common platform, combined with well defined hardware and software interfaces, we compare all 256-bit version candidates with respect to area, throughput, latency, power, and energy consumption. Our approach defines a standard testing harness for SHA-3 candidates, including the interface specification for the SHA-3 module on our testing platform. The second contribution is that we provide both FPGA and 90-nm CMOS application-specific integrated circuit (ASIC) synthesis results and thereby are able to compare the results. Our third contribution is that we release the source code of all the candidates and by using a common, fixed, publicly available platform, our claimed results become reproducible and open for a public verification.

In this paper, we present a fault-based security evaluation for an Elliptic Curve Cryptography (ECC) implementation using the Montgomery Powering Ladder (MPL). We focus in particular on the Lopez-Dahab algorithm, which is used to calculate a point on an elliptic curve efficiently without using the y - coordinate. Several previous fault analysis attacks cannot be applied to the ECC implementation employing the Lopez-Dahab algorithm in a straight-forward manner. In this paper, we evaluate the security of the Lopez-Dahab algorithm using Fault Sensitivity Analysis (FSA). Although the initial work on FSA was applied only to an Advanced Encryption Standard (AES) implementation, we apply the technique to the ECC implementation. Consequently, we found a vulnerability to FSA for the ECC implementation using the Lopez-Dahab algorithm.

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.

A multiple designated verifiers signature (MDVS) is introduced in 2004 by Laguillaumie-Vergnaud, in which specific verifiers chosen by the signer (designated verifiers) are the only entities who can verify the signature. They also constructed two concrete MDVS schemes MDVS1 and MDVS2 from bilinear maps which are proved to be secure in the random oracle model. This paper proposes a new forgery attack against MDVS1 and MDVS2, which allows an adversary, from a valid signature sigma on a document, to forge a signature on the same document. Because of the definition of the unforgeability of MDVS schemes, when all designated verifiers are colluded, then can forge a signature on an arbitrary document (and thus the same document). However, the signer cannot distinguish who forged a signature (whether the adversary or the colluded designated verifiers) when the forged signature is given. Thus, the signer cannot convince the designated verifiers and this is critical for MDVS because the scheme is based on the trusty relationship between the signer and the designated verifiers. We also show the forgery attack against a DVS scheme proposed by Ohyama-Tanaka based on MDVS2.

Messerges, Dabbish and Sloan proposed a DPA attack which analyzes the address values of registers. This attack is called the Address-bit DPA (ADPA) attack. As countermeasures against ADPA, Itoh, Izu and Takenaka proposed algorithms that randomizes address bits. In this paper, we point out that one of their countermeasures has vulnerability even if the address bits are uniformly randomized. When a register is overwritten by the same data as one stored in the register during a data move process, the power consumption is lower than the case of being overwritten by the different data. This fact enables us to separate the power traces. As a result, in the case of the algorithm proposed in, we could invalidate the randomness of the random bits and perform ADPA to retrieve a secret key. Moreover, for the purpose of overcoming the vulnerability, we propose a new countermeasure algorithm.

To obtain a better trade-off between cost and security, practical DPA countermeasures are not likely to deploy full masking that uses one distinct mask bit for each signal. A common approach is to use the same mask on several instances of an algorithm. This paper proposes a novel power analysis method called Power Variance Analysis (PVA) to reveal the danger of such implementations. PVA uses the fact that the side-channel leakage of parallel circuits has a big variance when they are given the same but random inputs. This paper introduces the basic principle of PVA and a series of PVA experiments including a successful PVA attack against a prototype RSL-AES implemented on SASEBO-R.

The sanitizable signature attracts much attention since it allows to modify the original document for hiding partial information with keeping the validity of the signature and the integrity of unmodified parts of the document. The sanitizable signature is quite useful in governmental or military offices where there is a dilemma between is closure laws for public documents and privacy or diplomatic secrets. This paper proposes two new sanitizable signature schemes from bilinear maps with a new structure.

The information security is emphasized with a development of Internet systems. In the measures as securing digital information, there are cryptosystems that protect secrecy of digital documents and digital signature scheme that ensure validity of digital documents. In the case of reality, i.e. hardware devices are used in cryptosystems, there is a possibility that secret information leaks via side-channel. Simple power analysis (SPA) attacks are one of the side-channel attacks. To prevent a SPA, one of the side-channel attacks, the Montgomery powering ladder (MPL) method has been considered as one of the countermeasures. In this paper, we show that a naive implementation of the MPL method is vulnerable for SPA attacks by observing the power consumption of the controller block of the RSA hardware. Furthermore, in order to avoid such information leakage, we propose a new hardware architecture for RSA using the MPL method to enhance SPA resistance.

This paper proposes a new algorithm for evaluating the number of chaining variable conditions(CVCs) in the selecting step of a distrubance vector (DV) for the analysis of SHA-1 collision attack. The algorithm is constructed by combining the following four strategies, Strict Bit Compression, DV expansion, Precise Counting Rules in Every Step and Differential Path Confirmation for Rounds 2 to 4, that can evaluate the number of CVCs morestrictly compared with the previous approach.

Though anonymity of ring signature schemes has been studied in many literatures for a long time, these papers showed different definitions and there is no consensus. Recently, Bender et al. proposed two new anonymity definitions of ring signature which is stronger than the traditional definition, that are called anonymity against attribution attacks/full key exposure. Also, ring signature schemes have two levels of unforgeability definitions, i.e., existential un-forgeability (eUF) and strong existential unforgeability (sUF). In this paper, we will redefine anonymity and unforgeability definitions from the standpoint of universally composable (UC) security framework. First, we will formulate new ideal functionalities of ring signature schemes for each security levels separately. Next, we will show relations between cryptographic security definitions and our UC definitions. Finally, we will give another proof of the Bender et al.'s ring signature scheme following the UC secure definition by constructing a simulator to an adversary of sUF, which can be adaptable to the case of sUF under the assumption of a standard single sUF signature scheme.

We discuss the security of the MR schemes and especially point out the vulnerability of the MR3 scheme. The probabilistic deposit mechanism utilized in the MR3 scheme contributes to the reduction of the bank's processing cost. However, as shown in our paper, it also decreases the security of the entire scheme.

Biophysical parameters and L-band polarimetry synthetic aperture radar observation data were taken for 59 test sites in Tomakomai national forest, which is located in the northern part of Japan. Correlations between the derived sigmaHH0, sigmaHV0, and sigmaVV0and the biophysical parameters are investigated and yield the following results. 1) The above-ground biomass-sigma0curves saturate above 50 tons/ha for sigmaVV0, 100 tons/ha for sigmaHH0, and over 100 tons/ha for sigmaHV0when all forest species are included in the curves. 2) The sigmaHH0-above-ground biomass curve for one forest species indicates a higher saturation level than that for the other forest species. Dependence on the forest species was absent for VV polarization and low for HV polarization. 3) A simple three-component scattering model indicates that volume scattering accounts for 80%-90% when the above-ground biomass exceeds 50 tons/ha. The surface-scattering components are up to ~20% for young stands, and the volume-scattering components are down to 70%. The origin of the dependency among the forest species was examined for the sigmaHH0-above-ground biomass. It is concluded that a possible cause of the dependency is the different characteristics of the stands rather than forest species

We examined relationship between forest parameters and /spl sigma//sup 0/ derived by airborne multi-polarization SAR (PiSAR). PiSAR observations and field measurements were simultaneously performed on November 2002 and August 2003. One data set was taken from stands with pure pine (Picea glehnii Masters) forest. More than 70% of the trees in biomass are Picea glehnii Masters in the data set with same stand age. The other data set was taken from the stands where mixture of species is proceeding in some degree. The former data set shows more tight correlations compared to the other and correlation coefficient reaches 0.98. We conclude that (1) the mixture of the species and stand age are two of the major reasons of data scattering between forest parameters and /spl sigma//sup 0/, and (2) the above ground biomass saturation level is about /spl sim/150 tons/ha for L-band /spl sigma//sub HH//sup 0/ and /spl sigma//sub HV//sup 0/ and /spl sim/70 tons/ha for /spl sigma//sub VV//sup 0/ in this akaezomatsu site, using a biomass expansion factor of 1.36 to convert from the trunk biomass to the above-ground biomass.

Formal models and security proofs are especially important for multisignatures: in contrast to threshold signatures, no precise definitions were ever provided for such schemes, and some proposals were subsequently broken.In this paper, we formalize and implement a variant of multi-signature schemes, Accountable-Subgroup Multisignatures (ASM). In essence, ASM schemes enable any subgroup, S, of a given group, G, of potential signers, to sign efficiently a message M so that the signature provably reveals the identities of the signers in S to any verifier.Specifically, we provide:The first formal model of security for multisignature schemes that explicitly includes key generation (without relying on trusted third parties);A protocol, based on Schnorr's signature scheme [33], that is both provable and efficient:Only three rounds of communication are required per signature.The signing time per signer is the same as for the single-signer Schnorr scheme, regardless of the number of signers.The verification time is only slightly greater than that for the single-signer Schnorr scheme.The signature length is the same as for the single signer Schnorr scheme, regardless of the number of signers.Our proof of security relies on random oracles and the hardness of the Discrete Log Problem.

The simultaneous secret exchange protocol is the key tool for contract signing protocols and certified mail protocols. This paper proposes efficient simultaneous secret exchange protocols (or gradual secret releasing protocols) that are based on general assumptions such as the existence of one-way permutations and one-way functions, while the existing efficient simultaneous secret exchange protocols are based on more constrained assumptions such as specific number theoretic problems and the existence of oblivious transfer primitives (or trap-door one-way permutations). Moreover, while the existing simultaneous secret exchange protocols have an additional requirement that the underlying commit (encryption) function is “ideal”, the above-mentioned “general assumptions” are provably sufficient for our schemes. Therefore, our protocols are provably secure under the general assumptions. In addition, our protocols are at least as efficient as the existing practical protocols, when efficient one-way permutations and one-way functions are used.