Information-theoretic security and computational security are fundamental paradigms of security in the theory of cryptography. The two paradigms interact with each other but have shown different progress, which motivates us to explore the intersection between them. In this paper, we focus on Multi-Party Computation (MPC) because the security of MPC is formulated by simulation-based security, which originates from computational security, even if it requires information-theoretic security. We provide several equivalent formalizations of the security of MPC under a semi-honest model from the viewpoints of information theory and statistics. The interpretations of these variants are so natural that they support the other aspects of simulation-based security. Specifically, the variants based on conditional mutual information and sufficient statistics are interesting because security proofs for those variants can be given by information measures and factorization theorem, respectively. To exemplify this, we show several security proofs of BGW (Ben-Or, Goldwasser, Wigderson) protocols, which are basically proved by constructing a simulator.

The total number of solar power-producing facilities whose Feed-in Tariff (FIT) Program-based ten-year contracts will expire by 2023 is expected to reach approximately 1.65 million in Japan. If the facilities that produce or consume renewable energy would increase to reach a large number, e.g., two million, blockchain would not be capable of processing all the transactions. In this work, we propose a blockchain-based electricity-tracking platform for renewable energy, called ‘ZGridBC,’ which consists of mutually cooperative two novel decentralized schemes to solve scalability, storage cost, and privacy issues at the same time. One is the electricity production resource management, which is an efficient data management scheme that manages electricity production resources (EPRs) on the blockchain by using UTXO tokens extended to two-dimension (period and electricity amount) to prevent double-spending. The other is the electricity-tracking proof, which is a massive data aggregation scheme that significantly reduces the amount of data managed on the blockchain by using zero-knowledge proof (ZKP). Thereafter, we illustrate the architecture of ZGridBC, consider its scalability, security, and privacy, and illustrate the implementation of ZGridBC. Finally, we evaluate the scalability of ZGridBC, which handles two million electricity facilities with far less cost per environmental value compared with the price of the environmental value proposed by METI (=0.3 yen/kWh).

Central bank digital currencies require the implementation of eKYC to verify whether a trading customer is eligible online. When an organization issues an ID proof of a customer for eKYC, that proof is usually achieved in practice by a hierarchy of issuers. However, the customer wants to disclose only part of the issuer's chain and documents to the trading partner due to privacy concerns. In this research, delegatable anonymous credential (DAC) and zero-knowledge range proof (ZKRP) allow customers to arbitrarily change parts of the delegation chain and message body to range proofs expressed in inequalities. That way, customers can protect the privacy they need with their own control. Zero-knowledge proof is applied to prove the inequality between two time stamps by the time stamp server (signature presentation, public key revocation, or non-revocation) without disclosing the signature content and stamped time. It makes it possible to prove that the registration information of the national ID card is valid or invalid while keeping the user's personal information anonymous. This research aims to contribute to the realization of a sustainable financial system based on self-sovereign identity management with privacy-enhanced PKI.

Proof of Work (PoW), which is a consensus algorithm for blockchain, entails a large number of meaningless hash calculations and wastage of electric power and computational resources. In 2021, it is estimated that the PoW of Bitcoin consumes as much electricity as Pakistan's annual power consumption (91TWh). This is a serious problem against sustainable development goals. To solve this problem, this study proposes Meaningful-PoW (mPoW), which involves a meaningful calculation, namely the application of a genetic algorithm (GA) to PoW. Specifically, by using the intermediate values that are periodically generated through GA calculations as an input to the Hashcash used in Bitcoin, it is possible to make this scheme a meaningful calculation (GA optimization problem) while maintaining the properties required for PoW. Furthermore, by applying a device-binding technology, mPoW can be ASIC resistant without the requirement of a large memory. Thus, we show that mPoW can reduce the excessive consumption of both power and computational resources.

For reliable storage services, we need a way not only to monitor the state of stored data but also to recover the original data when some data loss is discovered. To solve the problem, a novel technique called HAIL has been proposed. Unfortunately, HAIL cannot support dynamic data which is changed according to users' modification queries. There are many applications where dynamic data are used. So, we need a way to support dynamic data in cloud services to use cloud storage system for various applications. In this paper, we propose a new technique that can support the use of dynamic data in cloud storage systems. For dynamic data update, we design a new data chunk generation strategy which guarantee efficient data insertion, deletion, and modification. Our technique requires O(1) operations for each data update when existing techniques require O(n) operations where n is the size of data.

AONT (All-or-Nothing Transform) is a kind of (n, n)-threshold secret sharing scheme that distributes a message m into a set of n shares such that the message m can be reconstructed if and only if n shares are collected. At CRYPTO 2000, Desai proposed a simple and faster AONT based on the CTR mode of encryption (called CTRT) and proved its security in the ideal cipher model. Though AES-128, whose key length k = 128 and block length l = 128, can be used in CTRT as a block cipher, AES-256 and AES-192 cannot be used due to its intrinsic restriction of k ≤ l. In this paper, we propose an extended CTRT (for short, XCTRT) suitable for AES-256. By thoroughly evaluating all the tricky cases, we prove that XCTRT is secure in the ideal cipher model under the same CTRT security definition. Also, we discuss the security result of XCTRT in concrete parameter settings. For more flexibility of key length, we propose a variant of XCTRT dealing with l

Because processes run concurrently in multitask systems, the size of the state space grows exponentially. Therefore, it is not straightforward to formally verify that such systems enjoy desired properties. Real-time constrains make the formal verification more challenging. In this paper, we propose the following to address the challenge: (1) a way to model multitask real-time systems as observational transition systems (OTSs), a kind of state transition systems, (2) a way to describe their specifications in CafeOBJ, an algebraic specification language, and (3) a way to verify that such systems enjoy desired properties based on such formal specifications by writing proof scores, proof plans, in CafeOBJ. As a case study, we model Fischer's protocol, a well-known real-time mutual exclusion protocol, as an OTS, describe its specification in CafeOBJ, and verify that the protocol enjoys the mutual exclusion property when an arbitrary number of processes participates in the protocol*.

To maintain blockchain-based services with ensuring its security, it is an important issue how to decide a mining reward so that the number of miners participating in the mining increases. We propose a dynamical model of decision-making for miners using an evolutionary game approach and analyze the stability of equilibrium points of the proposed model. The proposed model is described by the 1st-order differential equation. So, it is simple but its theoretical analysis gives an insight into the characteristics of the decision-making. Through the analysis of the equilibrium points, we show the transcritical bifurcations and hysteresis phenomena of the equilibrium points. We also design a controller that determines the mining reward based on the number of participating miners to stabilize the state where all miners participate in the mining. Numerical simulation shows that there is a trade-off in the choice of the design parameters.

To prove the graph relations such as the connectivity and isolation for a certified graph, a system of a graph signature and proofs has been proposed. In this system, an issuer generates a signature certifying the topology of an undirected graph, and issues the signature to a prover. The prover can prove the knowledge of the signature and the graph in the zero-knowledge, i.e., the signature and the signed graph are hidden. In addition, the prover can prove relations on the certified graph such as the connectivity and isolation between two vertexes. In the previous system, using integer commitments on RSA modulus, the graph relations are proved. However, the RSA modulus needs a longer size for each element. Furthermore, the proof size and verification cost depend on the total numbers of vertexes and edges. In this paper, we propose a graph signature and proof system, where these are computed on bilinear groups without the RSA modulus. Moreover, using a bilinear map accumulator, the prover can prove the connectivity and isolation on a graph, where the proof size and verification cost become independent from the total numbers of vertexes and edges.

Hashcash, which is a Proof of Work (PoW) of bitcoin, is based on a preimage problem of hash functions of SHA-2 and RIPEMD. As these hash functions employ the Merkle-Damgard (MD) construction, a preimage can be found with negligible memory. Since such calculations can be accelerated by dedicated ASICs, it has a potential risk of a so-called 51% attack. To address this issue, we propose a new PoW scheme based on the key recovery problem of cascade block ciphers. By choosing the appropriate parameters, e.g., block sizes and key sizes of underlying block ciphers, we can make this problem a memory-hard problem such that it requires a lot of memory to efficiently solve it. Besides, we can independently adjust the required time complexity and memory complexity, according to requirements by target applications and progress of computational power.

The Proof of Stake (PoS) protocol is one of the consensus algorithms for blockchain, in which the integrity of a new block is validated according to voting by nodes called validators. However, due to validator-oriented voting, voting results are likely to be false when the number of validators with wrong votes increases. In the PoS protocol, validators are motivated to vote correctly by reward and penalty mechanisms. With such mechanisms, validators who contribute to correct consensuses are rewarded, while those who vote incorrectly are penalized. In this paper, we consider an incentivization mechanism based on the voting profile of a validator, which is estimated from the voting history of the validator. In this mechanism, the stake collected due to the penalties are redistributed to validators who vote correctly, improving the incentive of validators to contribute to the system. We evaluate the performance of the proposed mechanism by computer simulations, investigating the impacts of system parameters on the estimation accuracy of the validator profile and the amount of validator's stake. Numerical results show that the proposed mechanism can estimate the voting profile of a validator accurately even when the voting profile dynamically changes. It is also shown that the proposed mechanism gives more reward to validators who vote correctly with high voting profile.

A private decentralized e-health environment, empowered by blockchain technology, grants authorized healthcare entities to legitimately access the patient's medical data without relying on a centralized node. Every activity from authorized entities is recorded immutably in the blockchain transactions. In terms of privacy, the e-health system preserves a default privacy option as an initial state for every patient since the patients may frequently customize their medical data over time for several purposes. Moreover, adjustments in the patient's privacy contexts are often solely from the patient's initiative without any doctor or stakeholders' recommendation. Therefore, we design, implement, and evaluate user-defined data privacy utilizing nudge theory for decentralized e-health systems named PDPM to tackle these issues. Patients can determine the privacy of their medical records to be closed to certain parties. Data privacy management is dynamic, which can be executed on the blockchain via the smart contract feature. Tamper-proof user-defined data privacy can resolve the dispute between the e-health entities related to privacy management and adjustments. In short, the authorized entities cannot deny any changes since every activity is recorded in the ledgers. Meanwhile, the nudge theory technique supports providing the best patient privacy recommendations based on their behaviour activities even though the final decision rests on the patient. Finally, we demonstrate how to use PDPM to realize user-defined data privacy management in decentralized e-health environments.

After the work of Impagliazzo and Rudich (STOC, 1989), the black box framework has become one of the main research domain of cryptography. However black box techniques say nothing about non-black box techniques such as making use of zero-knowledge proofs. Brakerski et al. introduced a new black box framework named augmented black box framework, in which they gave a zero-knowledge proof oracle in addition to a base primitive oracle (TCC, 2011). They showed a construction of a non-interactive zero knowledge proof system based on a witness indistinguishable proof system oracle. They presented augmented black box construction of chosen ciphertext secure public key encryption scheme based on chosen plaintext secure public key encryption scheme and augmented black box separation between one-way function and key agreement. In this paper we simplify the work of Brakerski et al. by introducing a proof system oracle without witness indistinguishability, named coin-free proof system oracle, that aims to give the same construction and separation results of previous work. As a result, the augmented black box framework becomes easier to handle. Since our oracle is not witness indistinguishable, our result encompasses the result of previous work.

Distributed Denial of Service attacks against the application layer (L7 DDoS) are among the most difficult attacks to defend against because they mimic normal user behavior. Some mitigation techniques against L7 DDoS, e.g., IP blacklisting and load balancing using a content delivery network, have been proposed; unfortunately, these are symptomatic treatments rather than fundamental solutions. In this paper, we propose a novel technique to disincentivize attackers from launching a DDoS attack by increasing attack costs. Assuming financially motivated attackers seeking to gain profit via DDoS attacks, their primary goal is to maximize revenue. On the basis of this assumption, we also propose a mitigation solution that requires mining cryptocurrencies to access servers. To perform a DDoS attack, attackers must mine cryptocurrency as a proof-of-work (PoW), and the victims then obtain a solution to the PoW. Thus, relative to attackers, the attack cost increases, and, in terms of victims, the economic damage is compensated by the value of the mined coins. On the basis of this model, we evaluate attacker strategies in a game theory manner and demonstrate that the proposed solution provides only negative economic benefits to attackers. Moreover, we implement a prototype to evaluate performance, and we show that this prototype demonstrates practical performance.

Inspired by the efficient proof procedures discussed in Computability logic [3],[5],[6], we describe a heuristic proof procedure for first-order logic. This is a variant of Gentzen sequent system [2] and has the following features: (a) it views sequents as games between the machine and the environment, and (b) it views proofs as a winning strategy of the machine. From this game-based viewpoint, a poweful heuristic can be extracted and a fair degree of determinism in proof search can be obtained. This article proposes a new deductive system LKg with respect to first-order logic and proves its soundness and completeness.

In the obnoxious facility game, we design mechanisms that output a location of an undesirable facility based on the locations of players reported by themselves. The benefit of a player is defined to be the distance between her location and the facility. A player may try to manipulate the output of the mechanism by strategically misreporting her location. We wish to design a λ-group strategy-proof mechanism i.e., for every group of players, at least one player in the group cannot gain strictly more than λ times her primary benefit by having the entire group change their reports simultaneously. In this paper, we design a k-candidate λ-group strategy-proof mechanism for the obnoxious facility game in the metric defined by k half lines with a common endpoint such that each candidate is a point in each of the half-lines at the same distance to the common endpoint as other candidates. Then, we show that the benefit ratio of the mechanism is at most 1+2/(k-1)λ. Finally, we prove that the bound is nearly tight.

Kakuro is a popular logic puzzle, in which a player fills in all empty squares with digits from 1 to 9 so that the sum of digits in each (horizontal or vertical) line is equal to a given number, called a clue, and digits in each line are all different. In 2016, Bultel, Dreier, Dumas, and Lafourcade proposed a physical zero-knowledge proof protocol for Kakuro using a deck of cards; their proposed protocol enables a prover to convince a verifier that the prover knows the solution of a Kakuro puzzle without revealing any information about the solution. One possible drawback of their protocol would be that the protocol is not perfectly extractable, implying that a prover who does not know the solution can convince a verifier with a small probability; therefore, one has to repeat the protocol to make such an error become negligible. In this paper, to overcome this, we design zero-knowledge proof protocols for Kakuro having perfect extractability property. Our improvement relies on the ideas behind the copy protocols in the field of card-based cryptography. By executing our protocols with a real deck of physical playing cards, humans can practically perform an efficient zero-knowledge proof of knowledge for Kakuro.

Bilinear-type conversion is to translate a cryptographic scheme designed over symmetric bilinear groups into one that works over asymmetric bilinear groups with small overhead regarding the size of objects concerned in the target scheme. In this paper, we address scalability for converting complex cryptographic schemes. Our contribution is threefold. Investigating complexity of bilinear-type conversion. We show that there exists no polynomial-time algorithm for worst-case inputs under standard complexity assumption. It means that bilinear-type conversion in general is an inherently difficult problem. Presenting a new scalable conversion method. Nevertheless, we show that large-scale conversion is indeed possible in practice when the target schemes are built from smaller building blocks with some structure. We present a novel conversion method, called IPConv, that uses 0-1 Integer Programming instantiated with a widely available IP solver. It instantly converts schemes containing more than a thousand of variables and hundreds of pairings. Application to computer-aided design. Our conversion method is also useful in modular design of middle to large scale cryptographic applications; first construct over simpler symmetric bilinear groups and run over efficient asymmetric groups. Thus one can avoid complication of manually allocating variables over asymmetric bilinear groups. We demonstrate its usefulness by somewhat counter-intuitive examples where converted DLIN-based Groth-Sahai proofs are more compact than manually built SXDH-based proofs. Though the early purpose of bilinear-type conversion is to save existing schemes from attacks against symmetric bilinear groups, our new scalable conversion method will find more applications beyond the original goal. Indeed, the above computer-aided design can be seen as a step toward automated modular design of cryptographic schemes.

Recently, IoT compatible products have been popular, and various kinds of things are IoT compliant products. In these devices, cryptosystems and authentication are not treated properly, and security measures for IoT devices are not sufficient. Requirements of authentication for IoT devices are power saving and one-to-many communication. In this paper, we propose a zero-knowledge identification scheme using LDPC codes. In the proposed scheme, the zero-knowledge identification scheme that relies on the binary syndrome decoding problem is improved and the computational cost of identification is reduced by using the sparse parity-check matrix of the LDPC codes. In addition, the security level, computational cost and safety of the proposed scheme are discussed in detail.

The isomorphism of polynomials with two secret (IP2S) problem is one candidate of computational assumptions for post-quantum cryptography. The idea of identification scheme based on IP2S is firstly introduced in 1996 by Patarin. However, the scheme was not described concretely enough and no more details are provided on how to transcribe the idea into a real-world implementation. Moreover, the security of the scheme has not been formally proven and the originally proposed security parameters are no longer secure based on the most recent research. In this paper, we propose a concrete identification scheme based on IP2S with the idea of Patarin as the starting point. We provide formal security proof of the proposed scheme against impersonation under passive attack, sequential active attack, and concurrent active attack. We also propose techniques to reduce the implementation cost such that we are able to cut the storage cost and average communication cost to an extent that under parameters for the standard 80-bit security, the scheme is implementable even on the lightweight devices in the current market.