Fully homomorphic encryption (FHE) enables clients with small devices to securely delegate their computations to powerful servers. However, to delegate these computations, a client should generate and transmit several gigabytes of FHE keys to the server. Reducing the size of FHE keys without compromising efficiency is therefore highly desirable, particularly for applications involving mobile and IoT devices.

The CKKS Fully Homomorphic Encryption (FHE) scheme enables approximate arithmetic on encrypted complex numbers for a desired precision. Most implementations use RNS with carefully chosen parameters to balance precision, efficiency, and security. However, a key limitation in RNS-CKKS is the rigid coupling between the scale factor, which determines numerical precision, and the modulus, which ensures security. Since these parameters serve distinct roles—one governing arithmetic correctness and the other defining cryptographic structure—this dependency imposes design constraints, such as a lack of suitable NTT primes and limited precision flexibility, ultimately leading to inefficiencies.

Large language models (LLMs) offer personalized responses based on user interactions, but this use case raises serious privacy concerns. Homomorphic encryption (HE) is a cryptographic protocol supporting arithmetic computations in encrypted states and provides a potential solution for privacy-preserving machine learning (PPML). However, the computational intensity of transformers poses challenges for applying HE to LLMs. In this work, we propose a modified HE-friendly transformer architecture with an emphasis on inference following personalized (private) fine-tuning. Utilizing LoRA fine-tuning and Gaussian kernels, we achieve significant computational speedups---6.94$\times$ for fine-tuning and 2.3$\times$ for inference---while maintaining performance comparable to plaintext models. Our findings provide a viable proof of concept for offering privacy-preserving LLM services in areas where data protection is crucial. Our code is available on GitHub.

Secure Machine Learning as a Service (MLaaS) is a viable solution where clients seek secure ML computation delegation while protecting sensitive data. We propose an efficient method to securely evaluate deep standard convolutional neural networks based on residue number system variant of Cheon-Kim-Kim-Song (RNS-CKKS) scheme in the manner of batch inference. In particular, we introduce a packing method calledChannel-By-Channel Packingthat maximizes the slot compactness and Single-Instruction-Multiple-Data (SIMD) capabilities in ciphertexts. We also propose a new method for homomorphic convolution evaluation calledChannel-By-Channel Convolution, which minimizes the additional heavy operations during convolution layers. Simulation results show that our work has improvements in amortized runtime for inference, with a factor of 5.04 and 5.20 for ResNet-20 and ResNet-110, respectively, compared to the previous results. We note that our results almost simulate the original backbone models, with classification accuracy differing from the backbone within 0.02%p. Furthermore, we show that the client's rotation key size generated and transmitted can be reduced from 105.6 GB to 6.91 GB for ResNet models during an MLaaS scenario. Finally, we show that our method can be combined with previous methods, providing flexibility for selecting batch sizes for inference.

A recent security model for fully homomorphic encryption (FHE), called IND-CPAD security and introduced by Li and Micciancio [Eurocrypt'21], strengthens IND-CPA security by giving the attacker access to a decryption oracle for ciphertexts for which it should know the underlying plaintexts. This includes ciphertexts that it (honestly) encrypted and those obtained from the latter by evaluating circuits that it chose. Li and Micciancio singled out the CKKS FHE scheme for approximate data [Asiacrypt'17] by giving an IND-CPAD attack on it and claiming that IND-CPA security and IND-CPAD security coincide for exact FHE schemes.

Fully homomorphic encryption (FHE) is a promising cryptographic primitive for realizing private neural network inference (PI) services by allowing a client to fully offload the inference task to a cloud server while keeping the client data oblivious to the server. This work proposes NeuJeans, an FHE-based solution for the PI of deep convolutional neural networks (CNNs). NeuJeans tackles the critical problem of the enormous computational cost for the FHE evaluation of CNNs. We introduce a novel encoding method called Coefficients-in-Slot (CinS) encoding, which enables multiple convolutions in one HE multiplication without costly slot permutations. We further observe that CinS encoding is obtained by conducting the first several steps of the Discrete Fourier Transform (DFT) on a ciphertext in conventional Slot encoding. This property enables us to save the conversion between CinS and Slot encodings as bootstrapping a ciphertext starts with DFT. Exploiting this, we devise optimized execution flows for various two-dimensional convolution (conv2d) operations and apply them to end-to-end CNN implementations. NeuJeans accelerates the performance of conv2d-activation sequences by up to 5.68× compared to state-of-the-art FHE-based PI work and performs the PI of a CNN at the scale of ImageNet within a mere few seconds.

In privacy-preserving machine learning (PPML), homomorphic encryption (HE) has emerged as a significant primitive, allowing the use of machine learning (ML) models while protecting the confidentiality of input data. Although extensive research has been conducted on implementing PPML with HE by developing the efficient construction of private counterparts to ML models, the efficient HE implementation of embedding layers for token inputs such as words remains inadequately addressed. Thus, our study proposes an efficient algorithm for privacy-preserving embedding via look-up table evaluation with HE(HELUT) by developing an encrypted indicator function (EIF) that assures high precision with the use of the approximate HE scheme(CKKS). Based on the proposed EIF, we propose the CodedHELUT algorithm to facilitate an encrypted embedding layer for the first time. CodedHELUT leverages coded inputs to improve overall efficiency and optimize memory usage. Our comprehensive empirical analysis encompasses both synthetic tables and real-world largescale word embedding models. CodedHELUT algorithm achieves amortized evaluation time of 0.018-0.242s for GloVe6B50d, 0.104-01.298s for GloVe42300d, 0.262-3.283s for GPT-2 and BERT embedding layers while maintaining high precision (16 bits)

Statistical analysis of largescale data is useful as it enables the extraction of a large amount of information, despite its simplicity. Therefore, fusing and analyzing data from different security domains is an attractive and promising approach, unless it jeopardizes the privacy of the data in any security domain. In this study, we proposed the HEaaN-STAT toolkit that can efficiently fuse data from different domains to enable largescale statistical analysis while protecting data privacy. Moreover, we proposed an efficient inverse operation and a table lookup function for Cheon-Kim-Kim-Song (CKKS) encrypted data, as well as a data encoding method for counting encrypted data. Based on this, we proposed a method for generating a contingency table with a large number of cases and k-percentile for largescale data that is hundreds to thousands of times faster than the method proposed by Lu et al. in NDSS’17. The validity of the proposed toolkit was verified through practical use for business applications using real-world data.

Homomorphic Encryption (HE) schemes such as BGV, BFV, and CKKS consume some ciphertext modulus for each multiplication. Bootstrapping (BTS) restores the modulus and allows homomorphic computation to continue, but it is time-consuming and requires a significant amount of modulus. For these reasons, decreasing modulus consumption is crucial topic for BGV, BFV and CKKS, on which numerous studies have been conducted.

Making deep neural networks available as a service introduces privacy problems, for which homomorphic encryption of both model and user data potentially offers the solution at the highest privacy level. However, the difficulty of operating on homomorphically encrypted data has hitherto limited the range of operations available and the depth of networks. We introduce an extended CKKS scheme MatHEAAN to provide efficient matrix representations and operations together with improved noise control. Using the MatHEAAN we developed a deep sequential model with a gated recurrent unit called MatHEGRU. We evaluated the proposed model using sequence modeling, regression, and classification of images and genome sequences. We show that the hidden states of the encrypted model, as well as the results, are consistent with a plaintext model.

Bootstrapping, which enables the full homomorphic encryption scheme that can perform an infinite number of operations by restoring the modulus of the ciphertext with a small modulus, is an essential step in homomorphic encryption. However, bootstrapping is the most time and memory consuming of all homomorphic operations. As we increase the precision of bootstrapping, a large amount of computational resources is required. Specifically, for any of the previous bootstrap designs, the precision of bootstrapping is limited by rescaling precision.

Garam Lee, Minsoo Kim, Jai Hyun Park, Seung-won Hwang, Jung Hee Cheon. Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2022.

Homomorphic encryption (HE) is being widely used for privacy-preserving computation. Since HE schemes only support polynomial operations, it is prevalent to use polynomial approximations of non-polynomial functions. We cannot monitor the intermediate values during the homomorphic evaluation; as a consequence, we should utilize polynomial approximations with sufficiently large approximation intervals to prevent the failure of the evaluation. However, the large approximation interval potentially accompanies computational overheads, and it is a serious bottleneck of HE application on real-world data. In this work, we introduce domain extension polynomials (DEPs) that extend the domain interval of functions by a factor ofkwhile preserving the feature of the original function on its original domain interval. By repeatedly iterating the domainextension process with DEPs, we can extend withO(logK) operations the domain of a given function by a factor ofKwhile the feature of the original function is preserved in its original domain interval. By using DEPs, we can efficiently evaluate in an encrypted state a function that converges at infinities, i.e., limx→∞f(x)and limx→-∞f(x)exist in R. To uniformly approximate the function on [–R,R], our method exploitsO(logR) operations andO(1) memory. This is more efficient than the previous approach, the minimax approximation and Paterson-Stockmeyer algorithm, which uses Ω(√R) multiplications and Ω(√R) memory for the evaluation. As another application of DEPs, we also suggest a method to manage the risky outliers from a large interval [–R,R] by usingO(logR) additional multiplications. As a real-world application, we trained the logistic regression classifier on large public datasets in an encrypted state by using our method. We exploit our method to the evaluation of the logistic function on large intervals, e.g., [-7683, 7683].

Homomorphic Encryption (HE) [11] draws significant attention as a privacy-preserving way for cloud computing because it allows computation on encrypted messages called ciphertexts. Among numerous FHE schemes [2]–[4], [8], [9], HE for Arithmetic of Approximate Numbers (HEAAN [3]), which is also known as CKKS (Cheon-Kim-Kim-Song), is rapidly gaining popularity [10] as it supports computation on real numbers. A critical shortcoming of HE is the high computational complexity of ciphertext arithmetic, especially, HE multiplication (HE Mul). For example, the execution time for computation on encrypted data (ciphertext) increases from 100s to 10,000s of times compared to that on native, unen-crypted messages. However, a large body of HE acceleration studies, including ones exploiting GPUs and FPGAs, lack a rigorous analysis of computational complexity and data access patterns of HE Mul with large parameter sets on CPUs, the most popular computing platform.

In this study, we propose an efficient sorting method for encrypted data using fully homomorphic encryption (FHE). The proposed method extends the existing 2-way sorting method by applying the k-way sorting network for any prime k to reduce the depth in terms of comparison operation from O(log22n) to O(klogk2n), thereby improving performance for k slightly larger than 2, such as k=5. We apply this method to approximate FHE which is widely used due to its efficiency of homomorphic arithmetic operations. In order to build up the k-way sorting network, the k-sorter, which sorts k-numbers with a minimal comparison depth, is used as a building block. The approximate homomorphic comparison, which is the only type of comparison working on approximate FHE, cannot be used for the construction of the k-sorter as it is because the result of the comparison is not binary, unlike the comparison in conventional bit-wise FHEs. To overcome this problem, we propose an efficient k-sorter construction utilizing the features of approximate homomorphic comparison. Also, we propose an efficient construction of a k-way sorting network using cryptographic SIMD operations. To use the proposed method most efficiently, we propose an estimation formula that finds the appropriate k that is expected to reduce the total time cost when the parameters of the approximating comparisons and the performance of the operations provided by the approximate FHE are given. We also show the implementation results of the proposed method, and it shows that sorting 56= 15625 data using 5-way sorting network can be about 23.3% faster than sorting 214= 16384 data using 2-way.

In this paper we present a homomorphic computation algorithm that finds an optimal local alignment of a pair of encrypted sequences, based on the Smith-Waterman recurrence. Our algorithm also includes an efficient method of finding the location of an optimal local alignment, in order to avoid costly conditional branching in the backtracking. To reduce computation time, we use two level parallel computations: one for filling the entries of the dynamic programming recurrence, and the other for implementing the circuits. To the best of our knowledge, this is the first attempt to compute an optimal local alignment of homomorphically encrypted sequences. With the efficient location retrieval, parallel computations, and a proper HE scheme, our implementation shows good performances in the experiment so as to be useful in practice.

Homomorphic encryption (HE) is one of the most promising solutions to secure cloud computing. The number theoretic transform (NTT) that is widely used for convolution operations in HE requires a large amount of computation and has high parallelism, and therefore it has been a good candidate for hardware acceleration. Nevertheless, prior NTT hardware solutions for HE-based applications are impractical in most applications because they do not seriously consider the critical bootstrapping procedure that allows unlimited homomorphic operations on encrypted data. In this paper, we suggest practical bootstrappable parameters, specifically for an established residue number system (RNS)based HE scheme, and apply them to our NTT hardware design. In addition, to limit the size of internal memory for roots of unity increased by the bootstrappable parameters, only a few roots of unity are stored and others are generated on the fly. In our NTT hardware architecture, multiple NTT butterfly units (BUs) are efficiently deployed for high throughput and high resource utilization. In particular, several groups of BUs for respective moduli work in a parallel and pipelined manner, which is effective in an RNS-based HE scheme with a number of moduli. Our implementation on a Xilinx UltraScale FPGA with the bootstrappable parameters achieves a $118 \times$ faster processing speed than a software implementation, and it further provides various trade-off choices such as the number of DSP slices against BRAMs based on available FPGA resources.

Machine learning on (homomorphic) encrypted data is a cryptographic method for analyzing private and/or sensitive data while keeping privacy. In the training phase, it takes as input an encrypted training data and outputs an encrypted model without ever decrypting. In the prediction phase, it uses the encrypted model to predict results on new encrypted data. In each phase, no decryption key is needed, and thus the data privacy is ultimately guaranteed. It has many applications in various areas such as finance, education, genomics, and medical field that have sensitive private data. While several studies have been reported on the prediction phase, few studies have been conducted on the training phase.In this paper, we present an efficient algorithm for logistic regression on homomorphic encrypted data, and evaluate our algorithm on real financial data consisting of 422,108 samples over 200 features. Our experiment shows that an encrypted model with a sufficient Kolmogorov Smirnow statistic value can be obtained in ∼17 hours in a single machine. We also evaluate our algorithm on the public MNIST dataset, and it takes ∼2 hours to learn an encrypted model with 96.4% accuracy. Considering the inefficiency of homomorphic encryption, our result is encouraging and demonstrates the practical feasibility of the logistic regression training on large encrypted data, for the first time to the best of our knowledge.

In this paper, we describe a polynomial time cryptanalysis of the (approximate) multilinear map proposed by Coron, Lepoint, and Tibouchi in Crypto13 (CLT13). This scheme includes a zero-testing functionality that determines whether the message of a given encoding is zero or not. This functionality is useful for designing several of its applications, but it leaks unexpected values, such as linear combinations of the secret elements. By collecting the outputs of the zero-testing algorithm, we construct a matrix containing the hidden information as eigenvalues, and then recover all the secret elements of the CLT13 scheme via diagonalization of the matrix. In addition, we provide polynomial time algorithms to directly break the security assumptions of many applications based on the CLT13 scheme. These algorithms include solving subgroup membership, decision linear, and graded external Diffie–Hellman problems. These algorithms mainly rely on the computation of the determinants of the matrices and their greatest common divisor, instead of performing their diagonalization.

Private query processing on encrypted databases allows users to obtain data from encrypted databases in such a way that the users’ sensitive data will be protected from exposure. Given an encrypted database, users typically submit queries similar to the following examples: 1) How many employees in an organization make over U.S. $100000? 2) What is the average age of factory workers suffering from leukemia? Answering the questions requires one to search and then compute over the relevant encrypted data sets in sequence. In this paper, we are interested in efficiently processing queries that require both operations to be performed on fully encrypted databases. One immediate solution is to use several special-purpose encryption schemes simultaneously; however, this approach is associated with a high computational cost for maintaining multiple encryption contexts. Another solution is to use a privacy homomorphic scheme. However, no secure solutions have been developed that satisfy the efficiency requirements. In this paper, we construct a unified framework to efficiently and privately process queries with search and compute operations. For this purpose, the first part of our work involves devising several underlying circuits as primitives for queries on encrypted data. Second, we apply two optimization techniques to improve the efficiency of these circuit primitives. One technique involves exploiting single-instruction-multiple-data (SIMD) techniques to accelerate the basic circuit operations. Unlike general SIMD approaches, our SIMD implementation can be applied even to a single basic operation. The other technique is to use a large integer ring (e.g.,$\mathbb {Z}_{2^{t}}$) as a message space rather than a binary field. Even for an integer of$k$bits with$k>t$, addition can be performed using degree 1 circuits with lazy carry operations. Finally, we present various experiments performed by varying the considered parameters, such as the query type and the number of tuples.

In this paper, we revisit the private over-threshold data aggregation problem. We formally define the problem's security requirements as both data and user privacy goals. To achieve both goals, and to strike a balance between efficiency and functionality, we devise an efficient cryptographic construction and its proxy-based variant. Both schemes are provably secure in the semi-honest model. Our key idea for the constructions and their malicious variants is to compose two encryption functions tightly coupled in a way that the two functions are commutative and one public-key encryption has an additive homomorphism. We call that double encryption. We analyze the computational and communication complexities of our construction, and show that it is much more efficient than the existing protocols in the literature. Specifically, our protocol has linear complexity in computation and communication with respect to the number of users. Its round complexity is also linear in the number of users. Finally, we show that our basic protocol is efficiently transformed into a stronger protocol secure in the presence of malicious adversaries, and provide the resulting protocol's performance and security analysis.

Recently, the usage of GPU is not limited to the jobs associated with graphics and a wide variety of applications take advantage of the flexibility of GPUs to accelerate the computing performance. Among them, one of the most emerging applications is the fully homomorphic encryption (FHE) scheme, which enables arbitrary computations on encrypted data. Despite much research effort, it cannot be considered as practical due to the enormous amount of computations, especially in the bootstrapping procedure. In this paper, we accelerate the performance of the recently suggested fast bootstrapping method in FHEW scheme using GPUs, as a case study of a FHE scheme. In order to optimize, we explored the reference code and carried out profiling to find out candidates for performance acceleration. Based on the profiling results, combined with more flexible tradeoff method, we optimized the bootstrapping algorithm in FHEW using GPU and CUDA's programming model. The empirical result shows that the bootstrapping of FHEW ciphertext can be done in less than 0.11 second after optimization.

We introduce a hybrid homomorphic encryption that combines public-key encryption (PKE) and somewhat homomorphic encryption (SHE) to reduce the storage requirements of most somewhat or fully homomorphic encryption (FHE) applications. In this model, messages are encrypted with a PKE and computations on encrypted data are carried out using SHE or FHE after homomorphic decryption. To obtain efficient homomorphic decryption, our hybrid scheme combines IND-CPA PKE without complicated message padding with SHE with a large integer message space. Furthermore, if the underlying PKE is multiplicative, the proposed scheme has the advantage that polynomials of arbitrary degree can be evaluated without bootstrapping. We construct this scheme by concatenating the ElGamal and Goldwasser-Micali schemes over a ring ℤNfor a composite integer N whose message space is ℤN×. To accelerate the homomorphic evaluation of the PKE decryption, we introduce a method to reduce the degree of the exponentiation circuit at the cost of additional public keys. Using the same technique, we present an efficient partial solution to an open problem which is to evaluate mod q mod p arithmetic homomorphically for large p. As an independent interest, we also obtain a generic method for converting from private-key SHE to public-key SHE. Unlike the method described by Rothblum, we are free to choose the SHE message space.

We propose an efficient additive homomorphic encryption scheme. In our scheme, an encryption of a message is simply its noisy modular reduction by several different moduli. The security of our scheme relies on the hardness of a new problem, the co-Approximate Common Divisor problem. We analyze its hardness by applying all known attacks and devising dedicated attacks. These analyses are not complete, but give sufficiently plausible evidence for the hardness of this new problem.

The Tate pairing computation consists of two parts: Miller step and final exponentiation step. In this paper, we investigate the structure of the final exponentiation step. Consider an orderrsubgroup of an elliptic curve defined over Fqwith embedding degreek. The final exponentiation in the Tate pairing is an exponentiation of an element in Fqkby (qk-1)/r. The hardest part of this computation is to raise to the power λ:=Φk(q)/r, where Φk(·) denotes thekth cyclotomic polynomial. Write it as λ = λ0+λ1q+⋯+λφ(k)-1qφ(k)-1in theq-ary representation. The final exponentiation cost mostly depends on κ(λ), the size of the maximum of |λi|. In many parameterized pairing-friendly curves, the value κ is about (1-1/ρφ(k))log2qwhere ρ = log2q/log2r, while random curves will have κ ≈ log2q. We investigate how this small κ is obtained for parameterized pairing-friendly elliptic curves, and show that (1-1/ρφ(k))log2qis the lower bound for all known construction methods of parameterized pairing-friendly curves. In the second part of our paper, we propose a method to obtain a modified Tate pairing with small κ for any pairing-friendly elliptic curves including those not belonging to parameterized families. More precisely, our method finds an integermusing the lattice basis reduction such that κ(mλ)=(1-1/ρφ(k))log2q. Using this modified Tate pairing, we can reduce the number of squarings in the final exponentiation by a factor of (1-1/ρφ(k)) from the usual Tate pairing. We apply our method to several known pairing-friendly curves to verify the expected speedup.

We propose a new method to speed up discrete logarithm (DL)-based cryptosystems by considering a new variant of the DL problem, where the exponents are formed as e1+ e2for some fixed a and two integers e1, ae2with a low weight representation. We call this class of exponents split exponents, and we show that with certain choice of parameters the DL problem on split exponents is essentially as secure as the standard DL problem, while the exponentiation operation using exponents of this class is significantly faster than best exponentiation algorithms given for standard exponents. For example, the speed of scalar multiplication on the standard Koblitz curve K163 is estimated to be accelerated by up to 51.5 % and 23.5 % at the cost of memory for one precomputed point, compared to the TNAF and window TNAF methods, respectively. As for security, we show that the provable security of the DL problem using split exponents is only by a small constant, e.g., 1/4, worse than the security of the standard DL problem. Split exponents can be adopted to speed up various DL-based cryptosystems. We exemplify this on the recent CCA-secure public key encryption of Bellare, Kohno, and Shoup.

In this paper, we examine homomorphic signatures that can be used to protect the integrity of network coding. In particular, Yu et al. proposed an RSA-based homomorphic signature scheme recently for this purpose. We show that their scheme in fact does not satisfy the required homomorphic property, and further, even though it can be fixed easily, still it allows no-message forgery attacks.

Hoffstein and Silverman suggested the use of low Hamming weight product (LHWP) exponents to accelerate group exponentiation while maintaining the security level. With LHWP exponents, the computation costs onGF(2n) or Koblitz elliptic curves can be reduced significantly, where the cost of squaring and elliptic curve doubling is much lower than that of multiplication and elliptic curve addition, respectively. In this paper, we present a parameterized splitting system with an additional property, which is a refinement version of the system introduced in PKC'08. We show that it yields an algorithm for the discrete logarithm problem (DLP) with LHWP exponents with lower complexity than that of any previously known algorithms. To demonstrate its application, we attack the GPS identification scheme modified by Coron, Lefranc, and Poupard in CHES'05 and the DLP with Hoffstein and Silverman's (2,2,11)-exponent. The time complexity of our key recovery attack against the GPS scheme is261.82, which was expected to be278. Hoffstein and Silverman's (2,2,11)-exponent can be recovered with a time complexity of253.02, which is the lowest among the known attacks.

Multisignatures allow n signers to produce a short joint signature on a single message. Multisignatures were achieved in the plain model with a non-interactive protocol in groups with bilinear maps, by Boneh et al, and by a three-round protocol under the Discrete Logarithm (DL) assumption, by Bellare and Neven, with multisignature verification cost of, respectively, O(n) pairings or exponentiations. In addition, multisignatures with O(1) verification were shown in so-called Key Verification (KV) model, where each public key is accompanied by a short proof of well-formedness, again either with a non-interactive protocol using bilinear maps, by Ristenpart and Yilek, or with a three-round protocol under the Diffie-Hellman assumption, by Bagherzandi and Jarecki.

A timed-release cryptosystem allows a sender to encrypt a message so that only the intended recipient can read it only after a specified time. We formalize the concept of a secure timed-release public-key cryptosystem and show that, if a third party is relied upon to guarantee decryption after the specified date, this concept is equivalent to identity-based encryption; this explains the observation that all known constructions use identity-based encryption to achieve timed-release security. We then give several provably-secure constructions of timed-release encryption: a generic scheme based on any identity-based encryption scheme, and two more efficient schemes based on the existence of cryptographically admissible bilinear mappings. The first of these is essentially as efficient as the Boneh-Franklin Identity-Based encryption scheme, and is provably secure and authenticated in the random oracle model; the final scheme is not authenticated but is provably secure in the standard model (i.e., without random oracles).

We develop a couple of new methods to reduce transmission overheads in broadcast encryption. The methods are based on the idea of assigning one key per each partition using one-way key chains after partitioning the users. One method adoptsskippingchainson partitions containing up toprevoked users and the other adoptscascadechainson partitions with layer structure. The scheme using the former has the transmission overhead [(r)/(p+1)]+ [(N-r)/(c)], which is less thanr/pifr>p2N/c. The scheme using the latter keeps the same transmission overhead with the subset difference (SD) scheme whenrapproaches 0, whereris the number of revoked users. Combining the two schemes, we propose a new broadcast encryption scheme whose transmission overhead is the same with that of the SD scheme for smallrand becomes smaller than that of the SD asrgrows. The scheme using skipping chains possesses an advantage that any number of new users can join any time at no cost for current users. Finally, we show that the proposed key assignment scheme satisfieskey-indistinguishabilityassuming pseudorandom generators.

Modular exponentiation in an abelian group is one of the most frequently used mathematical primitives in modern cryptography. Batch verification is an algorithm for verifying many exponentiations simultaneously. We propose two fast batch verification algorithms. The first one makes use of exponents of small weight, called sparse exponents, and is asymptotically 10 times faster than individual verification and twice as fast as previous works at the same security level. The second one can only be applied to elliptic curves defined over small finite fields. Using sparse Frobenius expansion with small integer coefficients, we give a complex exponent test which is four times faster than the previous works. For example, each exponentiation in one batch asymptotically requires nine elliptic curve additions on some elliptic curves for 280security

Since broadcast encryption was first introduced in 1993 by Fiat and Naor, many broadcast encryption schemes have been developed. Among these, schemes based on tree structure and linear structure are notable. The subset difference (SD) scheme and layered subset difference (LSD) scheme based on tree structure have small user-key size and small transmission overhead when the number r of revoked users is very small. The punctured interval (PI) scheme based on linear (or circular) structure has better transmission overhead when r is not too small.In this paper, we propose a new broadcast encryption scheme, called the tree-based circle (TC) scheme, combining tree structure and circular structure. In this scheme, the transmission overhead is proportional to r like in the SD scheme for small r and becomes asymptotically same as that of the PI scheme when r grows, keeping the computation cost and the storage size small. The TC scheme also inherits the flexibility of the PI scheme. We further improve the transmission overhead of the TC scheme, when r is very small, by adopting the notion of cascade arc.

We give a novel relationship between the nonlinearity of rational functions over $\mathbb{F}_{2^n}$ and the number of points of the associated hyperelliptic curve. Using this, we obtain a lower bound on the nonlinearity for rational functions over $\mathbb{F}_{2^n}$. Compared to previous work that provides a lower bound on the nonlinearity only for monomials of special types, our result gives a general bound applicable to all rational functions defined over $\mathbb{F}_{2^n}$. By applying this result, we get a lower bound on the nonlinearity for various n × kn S-boxes.