Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2011 | Book

A Signature Scheme with Efficient Proof of Validity Read chapter Read first chapter

Coding and Cryptology

Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings

Editors: Yeow Meng Chee, Zhenbo Guo, San Ling, Fengjing Shao, Yuansheng Tang, Huaxiong Wang, Chaoping Xing

Publisher: Springer Berlin Heidelberg

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This book constitutes the refereed proceedings of the Third International Workshop on Coding and Cryptology, IWCC 2011, held in Qingdao, China, May 30-June 3, 2011. The 19 revised full technical papers are contributed by the invited speakers of the workshop. The papers were carefully reviewed and cover a broad range of foundational and methodological as well as applicative issues in coding and cryptology, as well as related areas such as combinatorics.

Table of Contents

Frontmatter
A Signature Scheme with Efficient Proof of Validity
Abstract
A signature scheme is presented that, when combined with the Groth-Sahai proof system, can efficiently prove the validity of a committed signature to a message shown in the clear. Compared to the Boneh-Boyen signature scheme, the proposed scheme yields a shorter proof of validity and is based on a more desirable hardness assumption that achieves a better security bound when analyzed in the generic group model.
Masayuki Abe, Miyako Ohkubo
Secret-Sharing Schemes: A Survey
Abstract
A secret-sharing scheme is a method by which a dealer distributes shares to parties such that only authorized subsets of parties can reconstruct the secret. Secret-sharing schemes are an important tool in cryptography and they are used as a building box in many secure protocols, e.g., general protocol for multiparty computation, Byzantine agreement, threshold cryptography, access control, attribute-based encryption, and generalized oblivious transfer.
In this survey, we describe the most important constructions of secret-sharing schemes; in particular, we explain the connections between secret-sharing schemes and monotone formulae and monotone span programs. We then discuss the main problem with known secret-sharing schemes – the large share size, which is exponential in the number of parties. We conjecture that this is unavoidable. We present the known lower bounds on the share size. These lower bounds are fairly weak and there is a big gap between the lower and upper bounds. For linear secret-sharing schemes, which is a class of schemes based on linear algebra that contains most known schemes, super-polynomial lower bounds on the share size are known. We describe the proofs of these lower bounds. We also present two results connecting secret-sharing schemes for a Hamiltonian access structure to the NP vs. coNP problem and to a major open problem in cryptography – constructing oblivious-transfer protocols from one-way functions.
Amos Beimel
Lattice Codes for the Gaussian Wiretap Channel
Abstract
It has been shown recently that coding for the Gaussian Wiretap Channel can be done with nested lattices. A fine lattice intended to the legitimate user must be designed as a usual lattice code for the Gaussian Channel, while a coarse lattice is added to introduce confusion at the eavesdropper, whose theta series must be minimized. We study, here, the behavior of this invariant for a class of lattices.
Jean-Claude Belfiore, Frédérique Oggier, Patrick Solé
List Decoding for Binary Goppa Codes
Abstract
This paper presents a Patterson-style list-decoding algorithm for classical irreducible binary Goppa codes. The algorithm corrects, in polynomial time, approximately \(n-\sqrt{n(n-2t-2)}\) errors in a length-n classical irreducible degree-t binary Goppa code. Compared to the best previous polynomial-time list-decoding algorithms for the same codes, the new algorithm corrects approximately \(t^2\!/2n\) extra errors.
Daniel J. Bernstein
Faster 2-Regular Information-Set Decoding
Abstract
Fix positive integers B and w. Let C be a linear code over F 2 of length Bw. The 2-regular-decoding problem is to find a nonzero codeword consisting of w length-B blocks, each of which has Hamming weight 0 or 2. This problem appears in attacks on the FSB (fast syndrome-based) hash function and related proposals. This problem differs from the usual information-set-decoding problems in that (1) the target codeword is required to have a very regular structure and (2) the target weight can be rather high, so that there are many possible codewords of that weight.
Augot, Finiasz, and Sendrier, in the paper that introduced FSB, presented a variant of information-set decoding tuned for 2-regular decoding. This paper improves the Augot–Finiasz–Sendrier algorithm in a way that is analogous to Stern’s improvement upon basic information-set decoding. The resulting algorithm achieves an exponential speedup over the previous algorithm.
Daniel J. Bernstein, Tanja Lange, Christiane Peters, Peter Schwabe
Ideal Secret Sharing Schemes for Useful Multipartite Access Structures
Abstract
This paper is a survey of the main results and open problems in a line of work that was initiated shortly after secret sharing was introduced. Namely, the construction of ideal linear secret sharing schemes for access structures that are natural generalizations of the threshold ones and have interesting properties for the applications. Some of them have hierarchical properties, while other ones are suitable for situations requiring the agreement of several parties. These access structures are multipartite, that is, the participants are distributed into several parts and all participants in the same part play an equivalent role in the structure. This line of work has received an impulse from a recently discovered connection between ideal multipartite secret sharing schemes and integer polymatroids.
Oriol Farràs, Carles Padró
Loiss: A Byte-Oriented Stream Cipher
Abstract
This paper presents a byte-oriented stream cipher – Loiss, which takes a 128-bit initial key and a 128-bit initial vector as inputs, and outputs a keystream in bytes. The algorithm is based on a linear feedback shift register, and uses a structure called BOMM in the filter generator, which has good property on resisting algebraic attacks, linear distinguishing attacks and fast correlation attacks. In order for the BOMM to be balanced, the S-boxes in the BOMM must be orthomorphic permutations. To further improve the capability in resisting against those attacks, the S-boxes in the BOMM must also possess some good cryptographic properties, for example, high algebraic immunity, high nonlinearity, and so on. However current researches on orthomorphic permutations pay little attention on their cryptographic properties, and we believe that the proposal of Loiss will enrich the application of orthomorphic permutations in cryptography, and also motivate the research on a variety of cryptographic properties of orthomorphic permutations.
Dengguo Feng, Xiutao Feng, Wentao Zhang, Xiubin Fan, Chuankun Wu
Secure Message Transmission by Public Discussion: A Brief Survey
Abstract
In the problem of Secure Message Transmission in the public discussion model (SMT-PD), a Sender wants to send a message to a Receiver privately and reliably. Sender and Receiver are connected by n channels, up to t < n of which may be maliciously controlled by a computationally unbounded adversary, as well as one public channel, which is reliable but not private. The SMT-PD abstraction has been shown instrumental in achieving secure multi-party computation on sparse networks, where a subset of the nodes are able to realize a broadcast functionality, which plays the role of the public channel.
In this short survey paper, after formally defining the SMT-PD problem, we overview the basic constructions starting with the first, rather communication-inefficient solutions to the problem, and ending with the most efficient solutions known to-date—optimal private communication and sublinear public communication.
These complexities refer to resource use for a single execution of an SMT-PD protocol. We also review the amortized complexity of the problem, which would arise in natural use-case scenarios where \(\mathcal{S}\) and \(\mathcal{R}\) must send several messages back and forth, where later messages depend on earlier ones.
Juan Garay, Clint Givens, Rafail Ostrovsky
Variations on Encoding Circuits for Stabilizer Quantum Codes
Abstract
Quantum error-correcting codes (QECC) are an important component of any future quantum computing device. After a brief introduction to stabilizer quantum codes, we present two methods to efficiently compute encoding circuits for them.
Markus Grassl
Algorithms for the Shortest and Closest Lattice Vector Problems
Abstract
We present the state of the art solvers of the Shortest and Closest Lattice Vector Problems in the Euclidean norm. We recall the three main families of algorithms for these problems, namely the algorithm by Micciancio and Voulgaris based on the Voronoi cell [STOC’10], the Monte-Carlo algorithms derived from the Ajtai, Kumar and Sivakumar algorithm [STOC’01] and the enumeration algorithms originally elaborated by Kannan [STOC’83] and Fincke and Pohst [EUROCAL’83]. We concentrate on the theoretical worst-case complexity bounds, but also consider some practical facets of these algorithms.
Guillaume Hanrot, Xavier Pujol, Damien Stehlé
An Experiment of Number Field Sieve over GF(p) of Low Hamming Weight Characteristic
Abstract
The security of the digital signature algorithm (DSA) and Diffie-Hellman key exchange is based on the difficulty of the discrete logarithm problems (DLP) over prime field GF(p), and thus it is important to evaluate the difficulty of the DLP over GF(p) for discussing the security of these protocols. The number field sieve (NFS) is asymptotically the fastest algorithm to solve the DLP over GF(p). NFS was first proposed by Gordon and then it was improved by Schirokauer and Joux-Lercier. On the other hand, Schirokauer presented a new variant of NFS, which is particularly efficient for the characteristic p with low weight (p has a signed binary representation of low Hamming weight). In this paper, we implement the NFS proposed by Joux-Lercier and Schirokauer, and then we compare the running time of the NFS using the polynomials by Joux-Lercier and Schirokauer with respect to low weight primes of 100 bits or 110 bits.
Kenichiro Hayasaka, Tsuyoshi Takagi
The Minimum Distance of Graph Codes
Abstract
We study codes constructed from graphs where the code symbols are associated with the edges and the symbols connected to a given vertex are restricted to be codewords in a component code. In particular we treat such codes from bipartite expander graphs coming from Euclidean planes and other geometries. We give results on the minimum distances of the codes.
Tom Høholdt, Jørn Justesen
Local Duality and the Discrete Logarithm Problem
Abstract
It is shown that the computational complexity of Tate local duality is closely related to that of the discrete logarithm problem over finite fields. Local duality in the multiplicative case and the case of Jacobians of curves over p-adic local fields are considered. When the local field contains the necessary roots of unity, the case of curves over local fields is polynomial time reducible to the multiplicative case, and the multiplicative case is polynomial time equivalent to computing discrete logarithm in finite fields. When the local field dose not contains the necessary roots of unity, similar results can be obtained at the cost of going to an extension that does contain these roots of unity.
Ming-Deh Huang
On the Effects of Pirate Evolution on the Design of Digital Content Distribution Systems
Abstract
A cryptographic primitive that is widely deployed commercially for digital content distribution is the subset-difference (SD) method of Naor, Naor and Lotspiech that was introduced in Crypto 2001. This encryption mechanism, called a trace and revoke scheme, is part of the Advanced Access Content System (AACS), and is used for encrypting Blu-Ray movie disks and is based on an explicit combinatorial construction of an exclusive set system. At the time of its introduction the only attacks cryptographers considered against such schemes were against the revocation and tracing algorithms. The SD method defended against them successfully and provided a superior ciphertext length compared to other known techniques : the length of the ciphertext grew only linearly with the number of revocations r; in contrast, e.g., the simpler complete subtree (CS) method requires ciphertexts of length O(r·logN/r) where N is the total number of users.
In Crypto 2007 a new class of attacks was discovered against trace and revoke schemes called “pirate evolution.” Pirate evolution refers to the ability of the adversary to schedule the key material it possesses in such a way so that it can withstand a great number of rounds of tracing and revocation. With the introduction of pirate evolution, the reduction of the number of rounds of pirate evolution became a design consideration for trace and revoke schemes. In 2009, Jin and Lotspiech proposed a mechanism for defending against pirate evolution in the SD method that is a tradeoff between ciphertext size and the pirate evolution bound.
In this article we provide a review of all the above results. Moreover, we compare the modified SD scheme to the CS method (similarly modified to address pirate evolution) and find that for many choices of the parameters that are relevant to practice SD can be a less preferable choice. This fact highlights the importance of considering all relevant attack scenarios when applying a specific cryptographic primitive to a certain application domain.
Aggelos Kiayias
Arithmetic of Split Kummer Surfaces: Montgomery Endomorphism of Edwards Products
Abstract
Let E be an elliptic curve, \(\mathcal{K}_1\) its Kummer curve E/{±1}, E 2 its square product, and \(\mathcal{K}_2\) the split Kummer surface E 2/{±1}. The addition law on E 2 gives a large endomorphism ring, which induce endomorphisms of \(\mathcal{K}_2\). With a view to the practical applications to scalar multiplication on \(\mathcal{K}_1\), we study the explicit arithmetic of \(\mathcal{K}_2\).
David Kohel
A New Family of Quadriphase Sequences with Low Correlation
Abstract
For a positive integer n, a family of quadriphase sequences with period \(4\left(2^n-1\right)\) is proposed. The correlation values of the family and their distribution are completely determined. The maximum nontrivial correlation magnitude is \(4+2^{\frac{n+3}{2}}\) for odd n.
Jie Li, Xiangyong Zeng, Lei Hu
On the Link of Some Semi-bent Functions with Kloosterman Sums
Abstract
We extensively investigate the link between the semi- bentness property of some Boolean functions in polynomial forms and Kloosterman sums.
Sihem Mesnager, Gérard Cohen
Locally Decodable Codes: A Brief Survey
Abstract
Locally decodable codes are error correcting codes that simultaneously provide efficient random-access to encoded data and high noise resilience by allowing reliable reconstruction of an arbitrary data bit from looking at only a small number of randomly chosen codeword bits. Local decodability comes at the price of certain loss in terms of code efficiency. Specifically, locally decodable codes require longer codeword lengths than their classical counterparts. In this work we briefly survey the recent progress in constructions of locally decodable codes.
Sergey Yekhanin
On Relationship of Computational Diffie-Hellman Problem and Computational Square-Root Exponent Problem
Abstract
The Computational Square-Root Exponent Problem (CSREP), which is a problem to compute a value whose discrete logarithm is a square root of the discrete logarithm of a given value, was proposed in the literature to show the reduction between the discrete logarithm problem and the factoring problem. The CSREP was also used to construct certain cryptography systems. In this paper, we analyze the complexity of the CSREP, and show that under proper conditions the CSREP is polynomial-time equivalent to the Computational Diffie-Hellman Problem (CDHP). We also demonstrate that in group G with certain prime order p, the DLP, CDHP and CSREP may be polynomial time equivalent with respect to the computational reduction for the first time in the literature.
Fangguo Zhang, Ping Wang
Backmatter
Metadata
Title
Coding and Cryptology
Editors
Yeow Meng Chee
Zhenbo Guo
San Ling
Fengjing Shao
Yuansheng Tang
Huaxiong Wang
Chaoping Xing
Copyright Year
2011
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-20901-7
Print ISBN
978-3-642-20900-0
DOI
https://doi.org/10.1007/978-3-642-20901-7

Premium Partner

    Image Credits