Search

Polynomial based secret sharing is the art of protecting information and a tool used in areas where a secret has to be distributed among multiple parties. In this method, secret is encrypted into noisy shares and transferred to participants in the group. Decoding of secret is possible only when sufficient number of authorized members in the group, stack their respective shares. In this article, polynomial based secret sharing for audio is proposed that computes a checksum to identify the dishonest participant and also the audio shares generated are of smaller dimension. To achieve this, a polynomial function is defined by considering amplitude values and random values as coefficients. Inclusion of random value as the coefficient of higher degree term in the polynomial makes the audio shares noisy and does not provide any information about the secret. This reduces the overhead of performing preprocessing on original audio before shares are generated. In addition, our proposed method can be used for multi secret sharing. Proposed scheme also facilitates identification of dishonest participant before reconstruction of secret through a trusted entity called combiner. [ABSTRACT FROM AUTHOR]

In this paper the discrete logarithm problem in matrix in finite fields is formulated, possible ways of solution are given.

We generalize our earlier works on computing short discrete logarithms with tradeoffs, and bridge them with Seifert's work on computing orders with tradeoffs, and with Shor's groundbreaking works on computing orders and general discrete logarithms. In particular, we enable tradeoffs when computing general discrete logarithms. Compared to Shor's algorithm, this yields a reduction by up to a factor of two in the number of group operations evaluated quantumly in each run, at the expense of having to perform multiple runs. Unlike Shor's algorithm, our algorithm does not require the group order to be known. It simultaneously computes both the order and the logarithm. We analyze the probability distributions induced by our algorithm, and by Shor's and Seifert's order-finding algorithms, describe how these algorithms may be simulated when the solution is known, and estimate the number of runs required for a given minimum success probability when making different tradeoffs.

Many public-key cryptosystems and, more generally, cryptographic protocols, use group exponentiations as important primitive operations. To expand the applicability of these solutions to computationally weaker devices, it has been advocated that a computationally weaker client (i.e., capable of performing a relatively small number of modular multiplications) delegates such primitive operations to a computationally stronger server. Important requirements for such delegation protocols include privacy of the client’s input exponent and security of the client’s output, in the sense of detecting, except for very small probability, any malicious server’s attempt to convince the client of an incorrect exponentiation result. Only recently, efficient protocols for the delegation of a fixed-based exponentiation, over cyclic and RSA-type groups with certain properties, have been presented and proved to satisfy both requirements.

Algorithms for interpolating a polynomial f from its evaluation points whose running time depends on the sparsity t of the polynomial when it is represented as a linear combination of t Chebyshev Polynomials of the First Kind with non-zero scalar coefficients are given by Lakshman and Saunders (1995) , Kaltofen and Lee (2003) and Arnold and Kaltofen (2015). The term degrees are computed from values of Chebyshev Polynomials of those degrees. We give an algorithm that computes those degrees in the manner of the Pohlig and Hellman algorithm (1978) for computing discrete logarithms modulo a prime number p when the factorization of p − 1 (or p + 1) has small prime factors, that is, when p − 1 (or p + 1) is smooth. Our algorithm can determine the Chebyshev degrees modulo such primes in bit complexity log ⁡ (p) O (1) times the squareroot of the largest prime factor of p − 1 (or p + 1). [ABSTRACT FROM AUTHOR]

We revisit the quantum algorithm for computing short discrete logarithms that was recently introduced by Ekerå and Håstad. By carefully analyzing the probability distribution induced by the algorithm, we show its success probability to be higher than previously reported. Inspired by our improved understanding of the distribution, we propose an improved post-processing algorithm that is considerably more efficient, enables better tradeoffs to be achieved, and requires fewer runs, than the original post-processing algorithm. To prove these claims, we construct a classical simulator for the quantum algorithm by sampling the probability distribution it induces for given logarithms. This simulator is in itself a key contribution. We use it to demonstrate that Ekerå–Håstad achieves an advantage over Shor, not only in each individual run, but also overall, when targeting cryptographically relevant instances of RSA and Diffie–Hellman with short exponents. [ABSTRACT FROM AUTHOR]

We study the security of individual bits in an RSA encrypted message EN(x). We show that given EN(x), predicting any single bit in x with only a nonnegligible advantage over the trivial guessing strategy, is (through a polynomial-time reduction) as hard as breaking RSA. Moreover, we prove that blocks of O(log log N) bits of x are computationally indistinguishable from random bits. The results carry over to the Rabin encryption scheme. Considering the discrete exponentiation function gx modulo p, with probability 1 -- o(1) over -random choices of the prime p, the analog results are demonstrated. The results do not rely on group representation, and therefore applies to general cyclic groups as well. Finally, we prove that the bits of ax + modulo p give hard core predicates for any one-way function f. All our results follow from a general result on the chosen multiplier hidden number problem: given an integer N, and access to an algorithm Px that on input a random a ∈ ZN, returns a guess of the i th bit of ax mod N, recover x. We show that for any i, if Px has at least a nonnegligible advantage in predicting the i th bit, we either recover x, or, obtain a nontrivial factor of N in polynomial time. The result also extends to prove the results about simultaneous security of blocks of O(log log N) bits. [ABSTRACT FROM AUTHOR]

The discrete logarithm over finite fields of small characteristic can be solved much more efficiently than previously thought. This algorithmic breakthrough is based on pinpointing relations among the factor base discrete logarithms. In this paper, we concentrate on the Kummer extension F q 2 ( q − 1 ) = F q 2 [ x ] / ( x q − 1 − A ) . It has been suggested that in this case, a small number of degenerate relations (from the Borel subgroup) are enough to solve the factor base discrete logarithms. We disprove the conjecture, and design a new heuristic algorithm with an improved bit complexity O ˜ ( q 1 + θ ) (or algebraic complexity O ˜ ( q θ ) ) to compute discrete logarithms of all the elements in the factor base { x + α | α ∈ F q 2 } , where θ < 2.38 is the matrix multiplication exponent over rings. Given additional time O ˜ ( q 4 ) , we can compute discrete logarithms of at least Ω ( q 3 ) many monic irreducible quadratic polynomials. We reduce the correctness of the algorithm to a conjecture concerning the determinant of a simple ( q + 1 ) -dimensional lattice, rather than to elusive smoothness assumptions. We verify the conjecture numerically for all prime powers q such that log 2 ⁡ ( q 2 ( q − 1 ) ) ≤ 5134 , and provide theoretical supporting evidences. [ABSTRACT FROM AUTHOR]

Public key cryptosystems are secure only when the authenticity of the public key is assured. Shao proposed a new scheme to overcome the problems of the existing schemes, which suffers from two major drawbacks. The first drawback is the availability of users' passwords in plaintext format in key server which are prone to attacks by ill-minded users. The second one is depending on the key server blindly for certificate generation, without further verification by the user. To overcome these severe drawbacks, we proposed an improved key authentication scheme based on Chinese remainder theorem and discrete logarithms. Our scheme allows the user to generate his/ her certificate without the help of any trusted third party. This scheme is intended for online services, military and defense applications to exchange keys securely. [ABSTRACT FROM AUTHOR]

In public key cryptosystem, the protecting of public keys against intruders is very important. Usually, key authentication schemes are required to preserve public keys. Most of the key authentication schemes require one or more authorities to authenticate public keys. Some other key authentication schemes require no authorities to authenticate public keys. The Zuhua Shao proposed a new scheme to overcome the drawbacks of existing schemes, but it has some vulnerabilities. This scheme relies only on key server for certificate generation. In a distributed network, the server can easily impersonate other legitimate users and listen the messages directed to them. Moreover, in this scheme, users’ passwords are stored in the form of plaintext. In this paper, slight modifications are pointed out to overcome these severe drawbacks. [ABSTRACT FROM AUTHOR]

Due to its use in cryptographic protocols such as the Diffie-Hellman key exchange, the discrete logarithm problem attracted a considerable amount of attention in the past 40 years. In this paper, we summarize the key technical ideas and their evolution for the case of discrete logarithms in small characteristic finite fields. This road leads from the original belief that this problem was hard enough for cryptographic purpose to the current state of the art where the algorithms are so efficient and practical that the problem can no longer be considered for cryptographic use. [ABSTRACT FROM AUTHOR]

ABSTRACT With the development of the Internet, multiplayer online games are rapidly replacing the traditional single-player games. The peer-to-peer architecture, which is suitable for massive multiplayer online games, is being considered as the replacement for traditional client-server architecture. Because the current solutions cannot prevent the cheating problems to gain unfair advantages in these games completely, we summarize the problems existing in some event signature protocols for peer-to-peer online games and propose a new secure event signature protocol. The security basis of the proposed protocol is the discrete logarithms and bilinear pairing. Our protocol provides higher security than some current protocols on secure event signature, although the efficiency of our protocol is lower than theirs. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

A strong designated verifier signature (SDVS) scheme only allows a designated verifier to validate signer's signatures for ensuring confidentiality. At the same time, the designated verifier can not transfer the signature to any third party, since he can also generate another computationally indistinguishable SDVS, which is referred to as non-transferability. A proxy signature scheme is a special type of digital signature schemes, which enables an authorized proxy signer to create a valid proxy signature on behalf of the original one. The resulted proxy signature is publicly verifiable by anyone. In this paper, we elaborate on the merits of SDVS schemes and proxy signature schemes to propose an efficient strong designated verifier proxy signature (SDVPS) scheme in which only a designated verifier can be convinced of the proxy signer's identity. The proposed scheme has crucial benefits in organizational operations and electronic commerce. Compared with related schemes, ours has not only shorter signature length, but also lower computational costs. Moreover, the security requirement of unforgeability against existential forgery under adaptive chosen-message attacks (EF-CMA) is proved in the random oracle model. [ABSTRACT FROM AUTHOR]

We present a method for constructing k-ary sequences over elliptic curves. Using the multiplicative character of order k of finite fields, we construct a family of k-ary pseudorandom elliptic curve sequences. The pseudorandom measures, such as the well-distribution measure, the correlation measure of order ℓ, and the linear complexity are estimated by using certain character sums. Such sequences share the same order of magnitude on the well-distribution measure, the correlation measure of order ℓ as the 'truly' random sequences. The method indicates that it is possible to construct 'good' pseudorandom sequences over elliptic curves widely used in public key cryptography. [ABSTRACT FROM AUTHOR]

Laih and Kuo developed two highly secure and efficient signature schemes based on factoring and discrete logarithms. Unfortunately, their schemes require many keys for signing document and verifying signature. Li, Tzeng, and Hwang improved one of their schemes and managed to reduce the number of keys, but unfortunately the improved scheme was shown to be insecure by Qian, Chao, and Bao. In this paper, a new modified scheme of Li-Tzeng-Hwang is presented with two main results: The modified scheme requires fewer keys than the scheme by Laih and Kuo, and it is able to withstand many attacks including the one mentioned by Qian, Chao and Bao. [ABSTRACT FROM PUBLISHER]

This paper presents a built-in self-test (BIST)-based scheme for fault diagnosis that can be used to identify permanent failures in embedded read-only memories. The proposed approach offers a simple test flow and does not require intensive interactions between a BIST controller and a tester. The scheme rests on partitioning of rows and columns of the memory array by employing low cost test logic. It is designed to meet requirements of at-speed test thus enabling detection of timing defects. Experimental results confirm high diagnostic accuracy of the proposed scheme and its time efficiency. [ABSTRACT FROM AUTHOR]

Embedded memories are increasingly identified as having potential for introducing new yield loss mechanisms at a rate, magnitude, and complexity large enough to demand major changes in fault diagnosis techniques. In particular, time-related or complex read faults that originate in the highest density areas of semiconductor designs require new methods to diagnose more complex faults affecting large groups of memory cells. This paper presents a built-in self-test (BIST)-based fault diagnosis scheme that can be used to identify a variety of failures in embedded random-access memory arrays. The proposed solution employs flexible test logic to record test responses at the system speed with no interruptions of a BIST session. It offers a simple test flow and enables detection of time-related faults. Furthermore, the way test responses are processed allows accurate and time-efficient reconstruction of error bitmaps. The proposed diagnostic algorithms use a number of techniques, including discrete logarithm-based counting with ring generators acting as very fast event counters and signature analyzers. Experimental results confirm high diagnostic accuracy of the proposed scheme and its time efficiency. [ABSTRACT FROM AUTHOR]

A convertible authenticated encryption scheme allows a designated receiver to retrieve an authenticated ciphertext and convert the authenticated ciphertext into an ordinary signature. The receiver can prove the dishonesty of the sender to anyone if the sender repudiates his/her signature. Recently, many researchers have proposed convertible authenticated encryption schemes based on cryptological algorithms. In this paper, the authors shall present a new convertible authenticated encryption scheme based on the ElGamal cryptosystem. The proposed scheme is more efficient than Wu-Hsu's scheme in terms of computational complexity. [ABSTRACT FROM AUTHOR]

Multi-proxy signature schemes allow the original signer to delegate his/her signing power to n proxy signers such that all proxy signers must corporately generate a valid proxy signature on behalf of the original signer. We first propose a multi-proxy signature scheme based on discrete logarithms and then adapt it to the elliptic curve cryptosystem. With the integration of self-certified public-key systems and the message recovery signature schemes, our proposed schemes have the following advantages: (1) They do not require the signing message to be transmitted, since the verifier can recover it from the signature; (2) The authentication of the public keys, verification of the signature, and recovery of the message can be simultaneously carried out in a single logical step; (3) No certificate is needed for validating the public keys. Further, the elliptic curve variant with short key lengths especially suits the cryptographic applications with limited computing power and storage space, e.g., smart cards. As compared with the previous work that was implemented with the certificate-based public-key systems, the proposed schemes give better performance in terms of communication bandwidth and computation efforts. [ABSTRACT FROM AUTHOR]