Search

Universal hash functions play a prominent role in the design of message authentication codes and the like. Whereas it is known how to build highly efficient sequential universal hash functions, parallel non-algebraic universal hash function designs are always built on top of a PRP. In such case, one employs a relatively strong primitive to obtain a function with a relatively weak security model. In this work, we present EliHash, a construction of a parallel universal hash function from non-compressing universal hash functions, and we back it up with supporting security analysis. We use this construction to design EliMAC, a message authentication code similar to LightMAC. We consider a heuristic instantiation of EliMAC with roundreduced AES, and argue that this instantiation of EliMAC is much more efficient than LightMAC, it is around 21% faster, and additionally allows for precomputation of the keys, albeit with a stronger assumption on the AES primitive than in LightMAC. These observations are backed up with an implementation of our scheme.

Flexible Ethernet (FlexE) over WDM transport is one of the key technologies for achieving high-speed next generation radio access network (NG-RAN). The security issue, such as optical fiber wiretap, becomes increasingly prominent. However, optical or electrical layer secure strategies cannot support higher rate and lower overhead transport, respectively. To this end, in this paper, we propose a cross-layer secure transport strategy in end-to-end FlexE over WDM networks, which leverages Universal Hashing based FlexE data block permutation and multiple parallel fiber transmission to achieve anti-eavesdropping. Different levels of attack ability are considered for measuring the impact on network security and resources utilization. Furthermore, the trade-off between efficient resources utilization and guarantee of higher level of transport security is also explored through building an integer linear programming (ILP) model. For the computation complexity of ILP model at large scale input conditions, a Security and resource-Efficiency-oriented Ant Colony optimization algorithm (SEAC) is proposed. Simulation results show that the cross-layer defense strategy is effective to struggle against intruders with different levels of attack ability, and the SEAC algorithm can achieve near-optimal performance and outperform the traditional first-fit algorithm.

Many concurrency platforms offer a processor oblivious model of computation, where the scheduler dynamically distributes work across threads. While this is convenient, it introduces non-determinism at runtime, which complicates debugging, because a program may have different outputs after each run. Leiserson et. al. [PPoPP ’12] persuaded Intel to modify its C/C++ compiler, which provided the Cilk Plus concurrency platform, to include a feature called pedigrees, which enables determinism by uniquely identifying strands with low overhead. They used pedigrees to design a DPRNG called DOTMIX, which hashes a pedigree, then mixes the result into a random number for a given strand. Improving the efficiency of DOTMIX by using a faster hash function is an open problem put forth by Leiserson et al. [PPoPP ’12]. We address this problem by introducing DOTMIX-Pro, which replaces the compression function used in DOTMIX with a faster universal hash function family called Square Hash due to Etzel et al. [CRYPTO ’99] and some of its variants, as well as other optimizations, which can be up to $$31\%$$ faster. Additionally, we introduce a generalization of Square Hash which works with arbitrary moduli.

The development of computer technology has determined the vector for the expansion of services based on the Internet and “G” technologies. The main requirements for modern services in the banking sector are security and reliability. At the same time, security is considered not only as ensuring the confidentiality and integrity of transactions, but also their authenticity. However, in the post-quantum period, US NIST specialists question the durability of modern means of providing basic security services based on symmetric and asymmetric cryptography algorithms. The increase in computing resources allows attackers to use modern threats in combination. Thus, there is a need to search for new and/or modify known algorithms for generating MAC (message authentication codes). In addition, the growth of services increases the amount of information that needs to be authenticated. Among the well-known hash algorithms, the hash functions of universal hashing are distinguished, which allow initially determining the number of collisions and their uniform distribution over the entire set of hash codes. Possibilities of modifying the cascade hashing algorithm UMAC (message authentication code based on universal hashing, universal MAC) based on the use of McEliece crypto-code construction on algebrogeometric (elliptic codes (EC), modified elliptic codes (MEC) and damaged codes (DC). This approach allows preserving the uniqueness property, in contrast to the classical UMAC scheme based on a block symmetric cipher (AES). The presented algorithms for evaluating the properties of universality and strict universality of hash codes make it possible to evaluate the security of the proposed hashing constructs based on universal hash functions, taking into account the preservation of the universality property

A description of an authenticated encryption with associated data (AEAD) block cypher mode, called XTSMAC, is presented. The results of the cryptanalysis, including the non-applicability of a new attack, based on differential properties of non-linear permutations, is also presented. The comparison with other AEAD modes and the results of practical software implementation on Intel’s CPU conclude the article.

We consider secret sharing where a dealer wants to share a secret with several participants such that predefined subsets of participants can reconstruct the secret and all other subsets of participants cannot learn any information about the secret. To this end, the dealer and the participants have access to samples of correlated random variables and a one-way (from the dealer to the participants), authenticated, public, and rate-limited communication channel. For this problem, we propose the first constructive and low-complexity coding scheme able to handle arbitrary access structures. Our construction relies on a vector quantization coupled with distribution approximations with polar codes to handle the reliability constraints, followed by universal hashing to handle the security constraints. We stress that our coding scheme does not require symmetry or degradation assumptions on the correlated random variables, and does not need a pre-shared secret among the participants and dealer. Our result is also optimal in the special case of rate-unlimited public communication when all the participants are needed to reconstruct the secret.

A quick generation method of k-wise independent uniformly distributed m-bit random variables with small randomness is proposed with applications to the Monte Carlo method.

As the device capacity of Dynamic Random Access Memory (DRAM) increases, refresh operation becomes a significant contributory factor toward total power consumption and memory throughput of the device. To reduce the problems associated with the refresh operation, a multi-rate refresh technique that changes the refresh period based on the retention time of DRAM cells has been proposed. Unfortunately, the multi-rate refresh technique has a scalability issue, because the additional storage and logic overhead on a memory controller increases as the device capacity increases. In this article, we propose a novel redundancy repair technique to increase the refresh period of DRAM by using a universal hashing technique. Our redundancy repair technique efficiently repairs both hard faults, which occur during the manufacturing process, and weak cells that have short retention time using the remaining spare elements after the process. Also, our technique solves the Variable Retention Time problem by repairing weak cells at boot time by exploiting the Built-in self-repair (BISR) technique and Error Correction Code. Our technique outperforms a conventional BISR redundancy repair with very little hardware overhead, and ensure reliability with more extended refresh period in the entire system. In particular, our experimental results show that our BISR technique achieves 100% repair rate at a 384ms refresh period in 1.0e-6 hard fault BER configuration, and reduces the refresh energy consumption by 83.9% compared to the 64ms refresh and 12% compared to the conventional multi-rate refresh technique for the state-of-the-art 4Gb device.

Досліджено шляхи підвищення імітостійкості сигналів попередження систем охорони НГУ на об’єктах критичної інфраструктури. Виконано аналіз автентичності повідомлень з конструктивними елементами MAC кодів на основі сімей хеш-функцій. Зроблений висновок, що практичні схеми хешування повинні включати класи хеш-функцій з великим коефіцієнтом стиснення для даних можливо дуже великого об՚єму. Наведені оцінки колізійної стійкості для схем універсального хешування за найкращими алгебраїчними кривими з великим числом точок і максимальними кривими., An important part of the combat activity of units of the National Guard of Ukraine is the physical protection of important state critical infrastructure facilities. The development of modern information technologies leads to the emergence of new threats to the security of such facilities, in particular, the number and power of cyber-attacks motivated by the interests of individual states, organizations and groups of people is growing. This determines the relevance of ensuring the confidentiality and integrity of messages exchanged between units of the National Guard of Ukraine through a warning system with potentially dangerous objects. To solve this problem, imitation-resistant data encoding is used, which makes it possible to check whether the data has been changed by a third party. The likelihood that the data has been changed serves as a measure of the resistance of the cipher.Ensuring the simulated resistance of data transmission systems is possible on the basis of solving an interconnected set of information protection tasks. The quality of solving security problems is largely determined by cryptographic algorithms for encryption, digital signature, hashing and generation of authentication codes used.A study of ways to increase the spoofing resistance of warning signals of the guard systems of the National Guard of Ukraine at critical infrastructure facilities was conducted.An analysis of the authenticity of messages with constructive elements of MAC codes based on hash function families is made. It is concluded that practical hashing schemes should include hash classes with a large compression ratio for data of very large volumes as possible. For these purposes, hash families on the basis of long algebraic geometric codes are of interest.An analysis of the general characteristics of algebraic-geometric codes showed that the best properties in terms of their code distance and computational complexity are the extended Reed-Solomon code, codes on Hermite curves, and codes on Suzuki curves. Collision stability estimates are presented for universal hashing schemes for the best algebraic curves with a large number of points and a maximum curve.The presented theory of universal hashing with Reed-Solomon algebraic-geometrical codes and codes on Hermite curves shows the ability to provide the necessary measure of the probability of collision of hash functions. Since a linear increase in collision probability for Reed-Solomon hashing limits the size of the hashed message, one of the ways to increase the simplicity of data transmission is to use codes on Hermite curves.

Quantum Key Distribution (QKD) is, nowadays, the dominant practical application in the quantum technologies field. Nevertheless, extracting secure keys from a physical implementation of a QKD system remains a complicated procedure. In this paper, post-processing algorithms were implemented to extract secret keys from a Continuous-Variable QKD (CV-QKD) system. The Discrete Modulated Four State CV-QKD protocol was considered due to lower complexity in the reconciliation procedure. The secret keys were extracted considering Maximum-Likelihood Estimators (MLEs) for parameter estimation, Iterative Low-Density Parity Check (LDPC) codes complemented with the Sum-Product Algorithm and error groups iterative reconciliation for information reconciliation, and the Toeplitz matrix as the universal hash function for privacy amplification. The post-processing algorithms were applied to extract secret keys from a simulated implementation of the Discrete Modulated Four State CV-QKD protocol, with double homodyne detection.

HalftimeHash is a new algorithm for hashing long strings. The goals are few collisions (different inputs that produce identical output hash values) and high performance.

Online cipher is an important primitive in many cryptographic schemes, such as authenticated encryption schemes. Considering performance and security, the Hash-ECB-Hash (HEH) structure provides a potential way to construct parallelizable and CCA secure online cipher. In this paper, we start from the online cipher POE which is the only instantiation of Hash-ECB-Hash structure in the literature. However, the AXU property of hash function in the hash layer cannot guarantee the security of POE. Then we propose a new concept of online universal hash function (OUHF) for the hash layer and prove that the Hash-ECB-Hash structure is CCA secure, if the hash layer is online almost universal (OAU) hash function and the underlying block cipher is CCA secure. We also give several concrete constructions of OAU.

This paper presents the first side-channel analysis (SCA) on polynomial-based message authentication code (MAC) schemes which is applicable to Poly1305. Typical SCAs (e.g., simple power analysis (SPA) and differential power analysis (DPA)) and conventional attacks on GCM/GMAC that focus on the first multiplication result in the universal hashing (i.e., polynomial evaluation) cannot be applied to Poly1305 owing to one-time keys and the structure of prime-field multiplication. On the other hand, the proposed attack retrieves the hash key from a single side-channel trace (e.g., a power/EM trace given by one execution) with a non-negligible probability and is applicable to polynomial-based MAC schemes implemented on an 8-bit micro-controller. The proposed attack allows the attacker to forge the authentication tag even if the hash key is a one-time key. The basic idea of the proposed attack is to exploit the addition in polynomial-based MAC schemes. Since the output or one input of the addition in these MAC schemes is known, we can efficiently estimate the unknown operands of addition, and then retrieve the hash key by the polynomial factorizations with the estimated candidates. This study also shows a cost-effective countermeasure for ChaCha20-Poly1305 using a combination of a lightweight masked Poly1305 and first-order mask conversion from Boolean to arithmetic.

Due to the reciprocity of wireless channels, the communication parties can directly extract the shared key from channel. This solution were verified through several schemes. However, in real situations, channel sampling of legitimate transceivers might be impacted by noises and other interferences, which makes the channel states obtained by initiator and responder might be obvious different. The efficiency and even availability of physical layer key generation are thus reduced. In this paper, we propose a lightweight and efficient physical layer key generation scheme, which extract shared secret keys from channel state information (CSI). To improve the key generation process, the discrete cosine transform (DCT) is employed to reduce differences of channel states of legitimate transceivers. Then, these outputs are quantified and encoded through multi-bit adaptive quantization(MAQ) quantizer and gray code to generate binary bit sequence, which can greatly reduce the bit error rate. Moreover, the low density parity check (LDPC) code and universal hashing functions are used to achieve information reconciliation and privacy amplifification. By adding preprocessing methods in the key generation process and using the rich information of CSI, the security of communications can be increased on the basis of improving the key generation rate. To evaluate this scheme, a number of experiments in various real environments are conducted. The experimental results show that the proposed scheme can effificiently generate shared secret keys for nodes and protect their communication.

With the traffic growth with different deterministic transport and isolation requirements in radio access networks (RAN), Flexible Ethernet (FlexE) over wavelength division multiplexing (WDM) network is as a candidate for next generation RAN transport, and the security issue in RAN transport is much more obvious, especially the eavesdropping attack in physical layer. Therefore, in this work, we put forward a cross-layer design for security enhancement through leveraging universal Hashing based FlexE data block permutation and multiple parallel fibre transmission for anti-eavesdropping in end-to-end FlexE over WDM network. Different levels of attack ability are considered for measuring the impact on network security and resource utilization. Furthermore, the trade-off problem between efficient resource utilization and guarantee of higher level of security is also explored. Numerical results demonstrate the cross-layer defense strategies are effective to struggle against intruders with different levels of attack ability.

Given a CNF formula F on n variables, the problem of model counting or #SAT is to compute the number of satisfying assignments of F . Model counting is a fundamental but hard problem in computer science with varied applications. Recent years have witnessed a surge of effort towards developing efficient algorithmic techniques that combine the classical 2-universal hashing with the remarkable progress in SAT solving over the past decade. These techniques augment the CNF formula F with random XOR constraints and invoke an NP oracle repeatedly on the resultant CNF-XOR formulas. In practice, calls to the NP oracle calls are replaced a SAT solver whose runtime performance is adversely affected by size of XOR constraints. The standard construction of 2-universal hash functions chooses every variable with probability p = 1/2 leading to XOR constraints of size n/2 in expectation. Consequently, the challenge is to design sparse hash functions where variables can be chosen with smaller probability and lead to smaller sized XOR constraints. In this paper, we address this challenge from theoretical and practical perspectives. First, we formalize a relaxation of universal hashing, called concentrated hashing and establish a novel and beautiful connection between concentration measures of these hash functions and isoperimetric inequalities on boolean hypercubes. This allows us to obtain (log m) tight bounds on variance and dispersion index and show that p = O( log(m)/m ) suffices for design of sparse hash functions from {0, 1}^n to {0, 1}^m. We then use sparse hash functions belonging to this concentrated hash family to develop new approximate counting algorithms. A comprehensive experimental evaluation of our algorithm on 1893 benchmarks demonstrates that usage of sparse hash functions can lead to significant speedups., Full version of paper accepted in LICS2020 conference

Many concurrency platforms offer a processor oblivious model of computation, where the scheduler dynamically distributes work across threads. While this is convenient, it introduces non\hyp determinism at runtime, which complicates debugging, since it precludes repeatability. Leiserson et al. [PPoPP '12] persuaded Intel to modify its C/C++ compiler, which provided the Cilk Plus concurrency platform, to include a feature called pedigrees, which enables determinism by uniquely identifying strands with low overhead. They used pedigrees to design a DPRNG called DOTMIX, which hashes a pedigree, then mixes the result into a random number for a given strand. Improving the efficiency of DOTMIX by using a faster hash function is an open problem put forth by Leiserson et al. [PPoPP '12]. We address this problem and improve the speed of the algorithm roughly by a factor of two, without sacrificing any statistical quality. Specifically, we replace the compression function used in DOTMIX with a faster universal hash function family due to Etzel et al. [CRYPTO '99] called Square Hash.

Tweakable block ciphers (TBCs) have been established as a valuable replacement for many applications of classical block ciphers. While several dedicated TBCs have been proposed in the previous years, generic constructions that build a TBC from a classical block cipher are still highly useful, for example, to reuse an existing implementation. However, most generic constructions need an additional call to either the block cipher or a universal hash function to process the tweak, which limited their efficiency. To address this deficit, Bao et al. proposed Tweak-aNd-Tweak (TNT) at EUROCRYPT’20. Their construction chains three calls to independent keyed permutations and adds the unmodified tweak to the state in between the calls. They further suggested an efficient instantiation TNT-AES that was based on round-reduced AES for each of the permutations. Their work could prove 2n/3-bit security for their construction, where n is the block size in bits. Though, in the absence of an upper bound, their analysis had to consider all possible attack vectors with up to 2n time, data, and memory. Still, closing the gap between both bounds remained a highly interesting research question. In this work, we show that a variant of Mennink’s distinguisher on CLRW2 with O(n23n/4) data and O(23n/2) time from TCC’18 also applies to TNT. We reduce its time complexity to O(n23n/4), show the existence of a second similar distinguisher, and demonstrate how to transform the distinguisher to a key-recovery attack on from an impossible differential. From a constructive point of view, we adapt the rigorous STPRP analysis of CLRW2 by Jha and Nandi to show O(23n/4) TPRP security for TNT. Thus, we move towards closing the gap between the previous proof and attacks for TNT as well as its proposed instance. Ministry of Education (MOE) Accepted version This research has been partially supported by Nanyang Technological University in Singapore under Grant 04INS000397C230, Singapore’s Ministry of Education under Grants RG18/19 and MOE2019-T2-1-060.

Multimodal hashing approaches have gained great success on large-scale cross-modal similarity search applications, due to their appealing computation and storage efficiency. However, it is still a challenge work to design binary codes to represent the original features with good performance in an unsupervised manner. We argue that there are some limitations that need to be further considered for unsupervised multimodal hashing: 1) most existing methods drop the discrete constraints to simplify the optimization, which will cause large quantization error; 2) many methods are sensitive to outliers and noises since they use $\ell _{2}$ -norm in their objective functions which can amplify the errors; and 3) the weight of each modality, which greatly influences the retrieval performance, is manually or empirically determined and may not fully fit the specific training set. The above limitations may significantly degrade the retrieval accuracy of unsupervised multimodal hashing methods. To address these problems, in this paper, a novel hashing model is proposed to efficiently learn robust discrete binary codes, which is referred as Robust and Flexible Discrete Hashing (RFDH). In the proposed RFDH model, binary codes are directly learned based on discrete matrix decomposition, so that the large quantization error caused by relaxation is avoided. Moreover, the $\ell _{2,1}$ -norm is used in the objective function to improve the robustness, such that the learned model is not sensitive to data outliers and noises. In addition, the weight of each modality is adaptively adjusted according to training data. Hence the important modality will get large weights during the hash learning procedure. Owing to above merits of RFDH, it can generate more effective hash codes. Besides, we introduce two kinds of hash function learning methods to project unseen instances into hash codes. Extensive experiments on several well-known large databases demonstrate superior performance of the proposed hash model over most state-of-the-art unsupervised multimodal hashing methods.

The hashing method maps similar data of various types to binary hashcodes with smaller hamming distance, and it has received broad attention due to its low-storage cost and fast retrieval speed. However, the existing limitations make the present algorithms difficult to deal with for large-scale data sets: 1) discrete constraints are involved in the learning of the hash function and 2) pairwise or triplet similarity is adopted to generate efficient hashcodes, resulting in both time and space complexity greater than $O(n^{2})$ . To address these issues, we propose a novel discrete supervised hash learning framework that can be scalable to large-scale data sets of various types. First, the discrete learning procedure is decomposed into a binary classifier learning scheme and binary codes learning scheme, which makes the learning procedure more efficient. Second, by adopting the asymmetric low-rank matrix factorization , we propose the fast clustering-based batch coordinate descent method, such that the time and space complexity are reduced to $O(n)$ . The proposed framework also provides a flexible paradigm to incorporate with arbitrary hash function, including deep neural networks and kernel methods, as well as any types of data to hash, including images and videos. Experiments on large-scale data sets demonstrate that the proposed method is superior or comparable with the state-of-the-art hashing algorithms.

In recent years, there has been increasing demand for social security and identity authentication, which leads to the booming of many biometrics involved large-scale problems such as recognition, retrieval, and identification. In this case, traditional models are infeasible due to the limited capability for handling large-scale data. Therefore, hashing technique is becoming prevalent due to its low storage cost and fast query speed. Recently, researchers have shown that supervised hashing can achieve higher accuracy than unsupervised hashing by incorporating tag or label information of data for learning hashing function. However, existing supervised methods treat all training examples equally, ignoring the different impacts of various training examples on the learning process. As a result, their performance is not satisfactory under some practical situations. As an improvement, this paper proposes a new method called “Supervised Hashing with Informative Set Selection” (SHISS), which assumes that different training examples have different influence on the learning process, and their usage should follow a logic way during optimization. In particular, we propose two criteria, certainty and diversity, to evaluate the informativeness of the subsets of training examples and encourage the more informative subsets to be learned ahead of the less informative ones. The experiments on two typical image retrieval datasets and one face dataset demonstrate that the proposed SHISS obtains higher mean average precision and shows faster convergence rate compared with the state-of-the-art hashing methods.

Universal hashing, discovered by Carter and Wegman in 1979, has many important applications in computer science. MMH$^*$, which was shown to be $\Delta$-universal by Halevi and Krawczyk in 1997, is a well-known universal hash function family. We introduce a variant of MMH$^*$, that we call GRDH, where we use an arbitrary integer $n>1$ instead of prime $p$ and let the keys $\mathbf{x}=\langle x_1, \ldots, x_k \rangle \in \mathbb{Z}_n^k$ satisfy the conditions $\gcd(x_i,n)=t_i$ ($1\leq i\leq k$), where $t_1,\ldots,t_k$ are given positive divisors of $n$. Then via connecting the universal hashing problem to the number of solutions of restricted linear congruences, we prove that the family GRDH is an $\varepsilon$-almost-$\Delta$-universal family of hash functions for some $\varepsilon, Comment: International Journal of Foundations of Computer Science, to appear

Indexing methods have been widely used for fast data retrieval on large scale datasets. When the data are represented by high dimensional vectors, hashing is often used as an efficient solution for approximate similarity search. When a retrieval task does not involve supervised training data, most hashing methods aim at preserving data similarity defined by a distance metric on the feature vectors. Hash codes generated by these approaches normally maintain the Hamming distance of the data in accordance with the similarity function, but ignore the local details of the distribution of data. This objective is not suitable for k-nearest neighbor search since the similarity to the nearest neighbors can vary significantly for different data samples. In this paper, we present a novel adaptive similarity measure which is consistent with k-nearest neighbor search, and prove that it leads to a valid kernel if the original similarity function is a kernel function. Next we propose a method which calculates hash codes using the kernel function. With a low-rank approximation, our hashing framework is more effective than existing methods that preserve similarity over an arbitrary kernel. The proposed similarity function, hashing framework, and their combination demonstrate significant improvement when compared with several alternative state-of-the-art methods.

Recent years have witnessed the promising efficacy and efficiency of hashing (also known as binary code learning) for retrieving nearest neighbor in large-scale data collections. Particularly, with supervision knowledge (e.g., semantic labels), we may further gain considerable performance boost. Nevertheless, most existing supervised hashing schemes suffer from the following limitations: (1) severe quantization error caused by continuous relaxation of binary codes; (2) disturbance of unreliable codes in subsequent hash function learning; and (3) erroneous guidance derived from imprecise and incomplete semantic labels. In this work, we propose a novel supervised hashing approach, termed as Robust Discrete Code Modeling (RDCM), which directly learns high-quality discrete binary codes and hash functions by effectively suppressing the influence of unreliable binary codes and potentially noisily-labeled samples. RDCM employs l2, p norm, which is capable of inducing sample-wise sparsity, to jointly perform code selection and noisy sample identification. Moreover, we preserve the discrete constraint in RDCM to eliminate the quantization error. An efficient algorithm is developed to solve the discrete optimization problem. Extensive experiments conducted on various real-life datasets show the superiority of the proposed RDCM approach as compared to several state-of-the-art hashing methods.