A linear network code is called k-secure if it is secure even if an adversary eavesdrops at most k edges. In this paper, we show an efficient deterministic construction algorithm of a linear transformation T that transforms an (insecure) linear network code to a k-secure one for any k, and extend this algorithm to strong k-security for any k . Our algorithms run in polynomial time if k is a constant, and these time complexities are explicitly presented. We also present a concrete size of $$|\mathsf{F}|$$ for strong k-security, where $$\mathsf{F}$$ is the underling finite field.

Consider a model of secret sharing schemes with cheaters. We say that a secret sharing scheme is error decodable if we can still recover the secretscorrectly from a noisy share vector (share1', ..., sharen'). In this paper, we first prove that a perfect secret sharing scheme is error decodable if and only if the adversary structure Γ satisfies a certain condition calledQ3. Next, for such Γ , we show a scheme such that the decoding algorithm runs in polynomial-time in |S| and the size of a linear secret sharing scheme which realizes Γ. We finally show an application to 1-round perfectly secure message transmission schemes (PSMT).

This paper shows that many independent pseudorandom permutations over {0,1}ncan be obtained from a single public random permutation and secret n bits. It is then proved that a slightly modified IAPM (an authenticated-encryption scheme) is secure even if the underlying block cipher F is publicly accessible (as a blackbox). A similar result is derived for OCB mode, too. The security proofs are based on our first result, and they are extremely simple. Finally, it is shown that our security bound is tight within a constant factor.

In the model of perfectly secure message transmission (PSMT) schemes, there are n channels between a sender and a receiver. An infinitely powerful adversary A may corrupt (observe and forge) the messages sent through t out of n channels. The sender wishes to send a secret s to the receiver perfectly privately and perfectly reliably without sharing any key with the receiver. In this paper, we show the first 2-round PSMT for n = 2t + 1 such that not only the transmission rate is O(n) but also the computational costs of the sender and the receiver are both polynomial in n. This means that we solve the open problem raised by Agarwal, Cramer, and de Haan at CRYPTO 2006. The main novelty of our approach is to introduce a notion of pseudobasis to the coding theory. It will be an independent interest for coding theory, too.

This paper shows the first practical semantically secure public-key encryption scheme such that its one-wayness is equivalent togeneralfactoring in thestandardmodel [in the sense of indistinguishability against chosen-plaintext attack (IND-CPA)]. Next our proof technique is applied to the Rabin-Paillier encryption scheme and a variant of the RSA-Paillier encryption scheme to prove their one-wayness under the factoring assumption via tight security reductions.

Consider the scenario where we are given an ideal functionality of oblivious transfer (OT), and we wish to construct a larger OT by invoking the above functionality as a black box. How many invocations of an ideal OT functionality are necessary? In tackling this problem, some lower bounds were derived using entropy previously. In this paper, we manage to achieve tighter lower bounds by employing a combinatorial approach. This new approach yields lower bounds which are two times larger than the existing bounds.

This paper proposes several new schemes which allow a sender to send encrypted messages to multiple recipients more efficiently (in terms of bandwidth and computation) than by using a standard encryption scheme. Most of the proposed schemes explore a new natural technique called randomness reuse. In order to analyze security of our constructions, we introduce a new notion of multirecipient encryption schemes (MRESs) and provide definitions of security for them. We finally show a way to avoid ad hoc analyses by providing a general test that can be applied to a standard encryption scheme to determine whether the associated randomness reusing MRES is secure. The results and applications cover both asymmetric and symmetric encryption.

Tompa and Woll introduced a problem of cheating in $(k,n)$ threshold secret sharing schemes. In this problem $k-1$ malicious participants aim to cheat an honest one by opening forged shares and causing the honest participant to reconstruct the wrong secret. We first derive a tight lower bound on the size of shares $|\cV_i|$ for secret sharing schemes that protect against this type of attack: $ |\cV_i| \geq (|\cS|-1)/\delta + 1 $, where $\cV_i$ denotes the set of shares of participant $P_i$, $\cS$ denotes the set of secrets, and $\delta$ denotes the cheating probability. We next present an optimum scheme, which meets the equality of our bound, by using "difference sets." A partial converse and some extensions are also shown.

Let$N(d,d^perp)$denote the minimum length$n$of a linear code$C$with$d$and$d^bot$, where$d$is the minimum Hamming distance of$C$and$d^bot$is the minimum Hamming distance of$C^bot$. In this correspondence, we show lower bounds and an upper bound on$N(d,d^perp)$. Further, for small values of$d$and$d^perp$, we determine$N(d,d^perp)$and give a generator matrix of the optimum linear code. This problem is directly related to the design method of cryptographic Boolean functions suggested by Kurosawa

In this paper, a new kind of adversarial goal called forge-and-impersonate in undeniable signature schemes is introduced. Note that forgeability does not necessarily imply impersonation ability. The security of the full-domain hash (FDH) variant of Chaum's undeniable signature scheme is then classified according to three dimensions, the goal of adversaries, the attacks, and the zero-knowledge (ZK) level of confirmation and disavowal protocols. Each security is then related to some well-known computational problem. In particular, the security of the FDH variant of Chaum's scheme with noninteractive zero-knowledge (NIZK) protocol confirmation and disavowal protocols is proven to be equivalent to the computational Diffie-Hellman (CDH) problem, as opposed to the gap Diffie-Hellman (GDH) problem as claimed by Okamoto and Pointcheval.

In this paper, we introduce a new covering radius of RM(r,n) from cryptography viewpoint. It is defined as the maximum distance between t-resilient functions and the rth order Reed-Muller code RM(r,n). We next derive its lower and upper bounds. We further present a table of numerical data of our bounds.

The propagation criterion, PC(/spl lscr/) of order k, is one of the most general cryptographic criteria of secure Boolean functions f. In this paper, we formalize its /spl epsiv/-almost version. The new definition requires that f(X)+f(X+/spl Delta/) is almost uniformly distributed while in the original definition, it must be strictly uniformly distributed. Better parameters are then obtained than the strict PC(/spl lscr/) of order k functions. To construct /spl epsiv/-almost PC(/spl lscr/) of order k functions, we introduce a notion of domain distance.

Linear complexity is an important cryptographic criterion of stream ciphers. The k-error linear complexity of a periodic sequence of period N is defined as the smallest linear complexity that can be obtained by changing k or fewer bits of the sequence per period. This article shows a relationship between the linear complexity and the minimum value k for which the k-error linear complexity is strictly less than the linear complexity.

For the problem of cheaters in secret-sharing schemes, we introduce d/sub cheat/ which is more appropriate than the minimum Hamming distance d/sub min/ of the related error-correcting code when it is needed only to recover the correct secret s (i.e., when it is not needed to identity the cheaters in the scheme). We then prove that d/sub min//spl les/d/sub cheat/=n-max/B/spl notin//spl Gamma/|B| where /spl Gamma/ denotes the access structure.

This article shows that /spl epsiv/-almost strongly universal classes of hash functions can yield better explicit constructions of identification codes via channels (ID codes) and identification plus transmission codes (IT codes) than the previous explicit constructions of Verdu and Wei (1993).

We show a necessary and sufficient condition for power complementary and linear phase filter banks. As a design example, a 3 channel such filter bank is presented.

One dimensional perfect reconstruction (PR) QMF banks have been studied extensively. It is attractive to use McClellan transform to obtain a two dimensional PR QMF bank. However, such an application of McClellan transform has not been studied in detail so far. This paper shows bad news and good news on the application of McClellan transform to 2D PR QMF banks. Let H/sub 0/(z/sub 1/, z/sub 2/) and H/sub 1/(z/sub 1/,z/sub 2/) be analysis filters obtained by McClellan transform. We prove that any such.>

One dimensional (1-D) perfect reconstruction (PR) QMF banks have been studied extensively. If all the analysis filters are linear phase in a PR QMF bank, we call it a 1-D linear phase PR QMF bank. Nguyen and Vaidyanathan showed a necessary condition for 1-D linear phase PRQMF banks [1989]. Recently, two dimensional (2-D) PR QMF banks have been studied. This paper shows a necessary condition for 2-D linear phase PR and MF banks. Our result is easily generalized to M dimensional linear phase PR QMF banks. In a 2-D system, subsampling is defined by a subsampling matrix D, where D is a 2*2 nonsingular matrix of integers. The sampling retains only samples at points m=(m/sub 1/,m/sub 2/)/sup T/ such that m=Dn, where n=(n/sub 1/,n/sub 2/)/sup T/ is an arbitrary integer vector. One out of every mod det(D) mod samples of the sequence is retained. A 2-D N channel analysis/synthesis filter bank is shown. We assume that all channels share the same subsampling matrix D such that mod det(D) mod =N (maximally decimated). For a matrix B, (B)/sub (i,j/) denotes the (i,j) element of B, diag(a/sub 0/,a/sub 1/,...,a/sub N-1/) denotes an N*/spl times/N diagonal matrix whose (i,i) element is a/sub i-1/.>

This paper presents a design method of linear phase PR QMF banks of the second approach. H/sub 1/(z) can be optimized not only in L/sub 2/-norm sense, but also in L/sub /spl infin//-norm sense (essentially, in any sense). Even in L/sub 2/-norm sense, the proposed method is more efficient than the Lagrange multiplier method. The proposed design method can be extended to M(>2)-channel systems immediately. Simulation results are shown for 2- and 3-channel systems, respectively.>

IIR type adaptive algorithms are classified into two categories according to their structures: series-parallel type and parallel type. Though parallel type algorithms show better convergence performance than series-parallel type, they present strong tendency to oscillate. Therefore, only Landau's method which is based on hyper-stability theory has been known as the parallel type. However, this method requires a lot of computation because it involves matrix operations. This paper proposes a new parallel type algorithm which utilizes the fast least squares method. Its computational complexity is much less than that of Landau's method. We also present by both analysis and computer simulation that the convergence performance of our method is better than that of the series-parallel type fast least squares method.