Post-Quantum Cryptography (PQC) attempts to find cryptographic protocols resistant to attacks using Shor polynomial time algorithm for numerical field problems or Grover search algorithm. A mostly overlooked but valuable line of solutions is provided by non-commutative algebraic structures, specifically canonical protocols that rely on one-way trapdoor functions (OWTF). Here we develop an algebraic framework who could be applied to different asymmetric protocols like D-H KE (Diffie-Hellman key exchange), Public Key Encryption, Digital Signature, ZKP (zero-knowledge proof) authentication, Oblivious Transfer, Multi-Party Computing, and so on. The trapdoor one-way functions selected are (a) Triple decomposition Problem (TDP) developed by Kurt, where a known element is factored into a product of three unknown factors and (b) a new version of conjugacy search that we refer from now on as Blind Conjugacy Search Problem (BCSP). Our platform structure is the general linear group GL(d,F_p) d-square non-singular matrices of prime field values. We give support to the fact that this framework is cryptographically secure against classical attacks like linear algebra attacks, length-based attacks, side-channel attacks against square (or duplicate) and multiply (or sum) algorithm, high sensitivity to pseudo random deterministic generators, etc. At same time it is immune against quantum attacks (using Grover and Shor), if the size parameters are carefully selected. Semantic security and IND-CCA2 compliance for this framework is discussed.
In 2009, Gradwohl, Naor, Pinkas, and Rothblum proposed physical zero-knowledge proof protocols for Sudoku. That is, for a puzzle instance of Sudoku, their excellent protocols allow a prover to convince a verifier that there is a solution to the Sudoku puzzle and that he/she knows it, without revealing any information about the solution. The possible drawback is that the existing protocols have a soundness error with a non-zero probability or need special cards (such as scratch-off cards). Thus, in this study, we propose new protocols to perform zero-knowledge proof for Sudoku that use a normal deck of playing cards and have no soundness error. Our protocols can be easily implemented by humans with a reasonable number of playing cards.
Olivier Blazy, Philippe Gaborit, Julien Schrek, Nicolas Sendrier
In this paper we give the first blind signature protocol for code-based cryptography. Our approach is different from the classical original RSA based blind signature scheme, it is done in the spirit of the Fischlin approach [9] which is based on proofs of knowledge. To achieve our goal we consider a new tool for zero-knowledge (ZK) proofs, the Concatenated Stern ZK protocol, which permits to obtain an authentication protocol for concatenated matrices. A signature is then obtained from the usual Fiat-Shamir heuristic. We describe our blind signature protocol for cryptography based on Hamming metric and show how it can be extended to rank based cryptography. The security of our blind protocol is based on the security of a trapdoor function for the syndrome decoding problem: the CFS signature scheme for Hamming distance and on the more recent RankSign protocol for rank metric. We give proofs in the random oracle model (ROM) for our blind signature scheme, which rely on the Syndrome Decoding problem. The parameters we obtain for our protocol are practical for rank metric (200kBytes) for the signature length and 15kBytes for public key size) and a little less practical for Hamming distance.
Broadbent Anne, Zhengfeng Ji, Song Fang, Watrous John
Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum computations, these proof systems can be made secure against quantum attacks. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-knowledge proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive proof system that is zero-knowledge with respect to efficient quantum computations. Our QMA proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration. The proof system relies on a new variant of the QMA-complete local Hamiltonian problem in which the local terms are described by Clifford operations and standard basis measurements. We believe that the QMA-completeness of this problem may have other uses in quantum complexity.
A homomorphic public key crypto-scheme based on the Boolean Satisfiability Problem is proposed. The public key is a SAT formula satisfied by the private key. Probabilistic encryption generates functions implied to be false by the public key XOR the message bits. A zero-knowledge proof is used to provide signatures.
Authentication is a process by which an entity, which could be a person or intended computer, establishes its identity to another entity. In private and public computer networks including the Internet, authentication is commonly done through the use of logon passwords. Knowledge of the password is assumed to guarantee that the user is authentic. Internet business and many other transactions require a more stringent authentication process. The aim of this paper is to propose two authentication schemes based on general non-commutative rings. The key idea of the schemes is that for a given non-commutative ring; one can build polynomials on additive structure and takes them as underlying work structure. By doing so, one can implement authentication schemes, one of them being zero-knowledge interactive proofs of knowledge, on multiplicative structure of the ring. The security of the schemes is based on the intractability of the polynomial symmetrical decomposition problem over the given non-commutative ring.
In this paper we present a new 5-pass identification scheme with asymptotic\ncheating probability 1/2 based on the syndrome decoding problem. Our protocol\nis related to the Stern identification scheme but has a reduced communication\ncost compared to previous code-based zero-knowledge schemes, moreover our\nscheme permits to obtain a very low size of public key and secret key. The\ncontribution of this paper is twofold, first we propose a variation on the\nStern authentication scheme which permits to decrease asymptotically the\ncheating probability to 1/2 rather than 2/3 (and very close to 1/2 in practice)\nbut with less communication. Our solution is based on deriving new challenges\nfrom the secret key through cyclic shifts of the initial public key syndrome; a\nnew proof of soundness for this case is given Secondly we propose a new way to\ndeal with hashed commitments in zero-knowledge schemes based on Stern's scheme,\nso that in terms of communication, on the average, only one hash value is sent\nrather than two or three. Overall our new scheme has the good features of\nhaving a zero-knowledge security proof based on well known hard problem of\ncoding theory, a small size of secret and public key (a few hundred bits), a\nsmall calculation complexity, for an overall communication cost of 19kb for\nauthentication (for a $2^{16}$ security) and a signature of size of 93kb\n(11.5kB) (for security $2^{80}$), an improvement of 40% compared to previous\nschemes based on coding theory.\n
In this paper we present a new 5-pass identification scheme with asymptotic cheating probability 1/2 based on the syndrome decoding problem. Our protocol is related to the Stern identification scheme but has a reduced communication cost compared to previous code-based zero-knowledge schemes, moreover our scheme permits to obtain a very low size of public key and secret key. The contribution of this paper is twofold, first we propose a variation on the Stern authentication scheme which permits to decrease asymptotically the cheating probability to 1/2 rather than 2/3 (and very close to 1/2 in practice) but with less communication. Our solution is based on deriving new challenges from the secret key through cyclic shifts of the initial public key syndrome; a new proof of soundness for this case is given Secondly we propose a new way to deal with hashed commitments in zero-knowledge schemes based on Stern's scheme, so that in terms of communication, on the average, only one hash value is sent rather than two or three. Overall our new scheme has the good features of having a zero-knowledge security proof based on well known hard problem of coding theory, a small size of secret and public key (a few hundred bits), a small calculation complexity, for an overall communication cost of 19kb for authentication (for a $2^{16}$ security) and a signature of size of 93kb (11.5kB) (for security $2^{80}$), an improvement of 40% compared to previous schemes based on coding theory.
We use an idea of linear representations of the symmetric group to reduce the number of communication rounds in the verification protocol, proposed in Crypto 2005 by Peng et al., of a shuffling. We assume Paillier encryption scheme with which we can apply some known zero-knowledge proofs following the same line of approaches of Peng et al. Incidence matrices of 1-subsets and 2-subsets of a finite set is intensively used for the implementation, and the idea of <TEX>$\lambda$</TEX>-designs is employed for the improvement of the computational complexity.
Abstract. We show an efficient secure two-party protocol, based on Yao’s construction, which provides security against malicious adversaries. Yao’s original protocol is only secure in the presence of semi-honest adversaries. Security against malicious adversaries can be obtained by applying the compiler of Goldreich, Micali and Wigderson (the “GMW compiler”). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs. Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the ideal/real simulation paradigm, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running O(1) oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao’s protocol does not yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security. Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party com-putation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a sta-tistical security parameter. These two reductions are comparable to Kilian’s reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit [18]. 1
The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs. Triangular elimination is a specific combination of zero-lifting and Fourier-Motzkin elimination using the triangle inequality. We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.
Theoretical computer science has found fertile ground in many areas of mathematics. The approach has been to consider classical problems through the prism of computational complexity, where the number of basic computational steps taken to solve a problem is the crucial qualitative parameter. This new approach has led to a sequence of advances, in setting and solving new mathematical challenges as well as in harnessing discrete mathematics to the task of solving real-world problems. In this talk, I will survey the development of modern cryptography -- the mathematics behind secret communications and protocols -- in this light. I will describe the complexity theoretic foundations underlying the cryptographic tasks of encryption, pseudo-randomness number generators and functions, zero knowledge interactive proofs, and multi-party secure protocols. I will attempt to highlight the paradigms and proof techniques which unify these foundations, and which have made their way into the mainstream of complexity theory.
In this tutorial, selected topics of cryptology and of computational complexity theory are presented. We give a brief overview of the history and the foundations of classical cryptography, and then move on to modern public-key cryptography. Particular attention is paid to cryptographic protocols and the problem of constructing the key components of such protocols such as one-way functions. A function is one-way if it is easy to compute, but hard to invert. We discuss the notion of one-way functions both in a cryptographic and in a complexity-theoretic setting. We also consider interactive proof systems and present some interesting zero-knowledge protocols. In a zero-knowledge protocol one party can convince the other party of knowing some secret information without disclosing any bit of this information. Motivated by these protocols, we survey some complexity-theoretic results on interactive proof systems and related complexity classes.
<p>Let A and B be n x n matrices the entries of which are affine combinations of the variables a_1,... ,a_m,b_1,. .. ,b_m over GF(2). Suppose that, for each i, 1&lt;= i &lt;= m, the term a_i b_i is an element of the product matrix C = A € B. What is the maximum value that <em> m </em> can have as a function of <em> n </em>? This question arises from a recent technique for improving the communication complexity of zero-knowledge proofs.</p><p>The obvious upper bound of n^2 is improved to n^2 sqrt[3] 3 + O(n). Tighter bounds are obtained for smaller values of n. The bounds for n = 2, n = 3, and n = 4 are tight.</p>
Ruy de Queiroz, Luiz Carlos Pereira, Edward Hermann Hæusler
This volume contains the Proceedings of the 10th Workshop on Logic, Language, Information and Computation (WoLLIC'2003). The Workshop was held in Ouro Preto, Minas Gerais, Brazil from July 29 to August 1, 2003, in the Escola de Minas of the Universidade Federal de Ouro Preto ( UFOP ). WoLLIC is a series of workshops which started in 1994 with the aim of fostering interdisciplinary research in pure and applied logic . The idea is to provide a forum which is large enough in the number of possible interactions between logic and the sciences related to information and computation, and yet is small enough to allow for concrete and useful interaction among participants. Previous versions were held at: Recife (Pernambuco, Brazil) in 1994 and 1995; Salvador (Bahia, Brazil) in 1996; Fortaleza (Ceará, Brazil) in 1997; São Paulo (Brazil) in 1998; Itatiaia (Rio de Janeiro, Brazil) in 1999; Natal (Rio Grande do Norte) in 2000; Brasília (Distrito Federal, Brazil) in 2001; Rio de Janeiro (Brazil) in 2002. Scientific sponsorship comes from the Interest Group in Pure and Applied Logics ( IGPL ), the European Association for Logic, Language and Information ( FoLLI ), the Association for Symbolic Logic ( ASL ), European Association for Theoretical Computer Science ( EATCS ), the Sociedade Brasileira de Computação ( SBC ), and the Sociedade Brasileira de Lógica ( SBL ). Funding was kindly given by:(i) CNPq ( Conselho Nacional de Desenvolvimento Científico e Tecnológico , the scientific and technological development council of the Brazilian Ministério da Ciência e Tecnologia ) (grant 450709/2003-5);(ii) CAPES ( Fundação Coordenação de Apoio ao Aperfeiçoamento de Pessoal de Nível Superior , a Foundation for the Development of Higher-Education under the Brazilian Ministério da Educação e do Desporto ) (grant PAEP0565/03);(iii) FAPEMIG ( Fundação de Amparo à Pesquisa do Estado de Minas Gerais , the Minas Gerais state foundation for the support of scientific research);(iv) Escola de Minas da UFOP ( Universidade Federal de Ouro Preto ). Contributions were received in the form of short papers in all areas related to logic, language, information and computation, including:pure logical systems, proof theory, model theory, algebraic logic, type theory, category theory, constructive mathematics, lambda and combinatorial calculi, program logic and program semantics, logics and models of concurrency, logic and complexity theory, proof complexity, foundations of cryptography (zero-knowledge proofs), descriptive complexity, nonclassical logics, nonmonotonic logic, logic and language, discourse representation, logic and artificial intelligence, automated deduction, foundations of logic programming, logic and computation, and logic engineering. Apart from the contributed papers (15), and the invited talks (5), the programme includes 5 tutorial lectures: 1. Algorithmic Randomness and Derandomization by Eric Allender (Department of Computer Science, Rutgers, the State University of New Jersey, USA) 2. Generalized Quantifiers by Lauri Hella (Department of Mathematics, Statistics and Philosophy, University of Tampere, Finland) 3. Implicit computational complexity by Jean-Baptiste Joinet (Preuves-Programmes-Systèmes, Université Paris 7, France) 4. Proof search foundations for logic programming by Dale Miller (INRIA/Futurs/Saclay, and Laboratoire d'Informatique, École Polytechnique, France) 5. Iterated theory change by Hans Rott (Institut für Philosophie, Universität Regensburg, Germany) All papers in the volume were reviewed by the program committee consisting of Mauricio Ayala-Rinóon ( Departamento de Matemática, Universidade de Brasília, Brazil ) Argimiro Arratia ( Depto. Matematicas, Universidad Simon Bolivar, Venezuela ) Alessandra Carbone ( Institut des Hautes Études Scientifiques, and Université de Paris XII, France ) Marcelo Coniglio ( Centro de Lógica e Epistemologia, Universidade Estadual de Campinas, Brazil ) Gilles Dowek ( INRIA, France ) Arnaud Fleury ( Facoltà di Scienze, Università di Verona, Italy ) Dexter Kozen ( Cornell University, USA ) Maarten Marx ( ILLC, Faculty of Science, Universiteit Amsterdam, The Netherlands ) Anto˚nio Carlos da Rocha Costa ( Escola de Informática, Universidade Católica de Pelotas, Brazil ) Dieter Spreen ( Fachbereich Mathematik, Theoretische Informatik, Universität Siegen, Germany ) Luiz Carlos Pereira ( Departamento de Filosofia, PUC-Rio and UFRJ, Brazil ) Jouko Väänänen ( Department of Mathematics, University of Helsinki, Finland ) Renata Wassermann ( Departamento de Cie˚ncia da Computação, Instituto de Matemática e Estatística, Universidade de São Paulo, Brazil ) The organising committee consisted of Lucília Figueiredo ( Departamento de Computação, Universidade Federal de Ouro Preto, Brazil ) Fred Ulisses Maranhão ( Centro de Informática, Universidade Federal de Pernambuco, Brazil ) Anjolina Grisi de Oliveira ( Center of Informatics, Universidade Federal de Pernambuco, Brazil ) Elaine Pimentel ( Departamento de Matemática, Universidade Federal de Minas Gerais, Brazil ) (Co-Chair) Ruy de Queiroz ( Center of Informatics, Universidade Federal de Pernambuco, Brazil ) (Co-Chair) Maria Angela Weiss ( Departamento de Matemática, Universidade de São Paulo, Brazil ) The volume will be published as volume 84 in the series Electronic Notes in Theoretical Computer Science ( ENTCS ). This series is published electronically through the facilities of Elsevier B.V. and its auspices. The volumes in the ENTCS series can be accessed at the URL http://www.elsevier.nl/locate/entcs A printed version of the current volume has been distributed to the participants at the workshop in Ouro Preto. We are very grateful to the following persons, whose help has been crucial for the success of WoLLIC'2003: Mike Mislove, one of the Managing Editors of the ENTCS series, for his assistance with the use of the ENTCS style files; Thanks are also due to the Department of Mathematics of Universidade Federal de Minas Gerais and the Department of Computing of the Universidade Federal de Ouro Preto, which has provided the logistic support to the organising committee. August 2, 2003 Ruy de Queiroz, Elaine Pimentel, Lucilia Figueiredo