On Diophantine Complexity and Statistical Zero
Knowledge Arguments 1st edition by ISBN Helger
Lipmaa 3540205920 9783540205920 pdf download
https://ebookball.com/product/on-diophantine-complexity-and-
statistical-zero-knowledge-arguments-1st-edition-by-isbn-helger-
lipmaa-3540205920-9783540205920-9426/
Explore and download more ebooks or textbooks
at ebookball.com
, Get Your Digital Files Instantly: PDF, ePub, MOBI and More
Quick Digital Downloads: PDF, ePub, MOBI and Other Formats
Verifiable Homomorphic Oblivious Transfer and Private Equality Test
1st edition by Helger Lipmaa ISBN 3540205920 9783540205920
https://ebookball.com/product/verifiable-homomorphic-oblivious-
transfer-and-private-equality-test-1st-edition-by-helger-lipmaa-
isbn-3540205920-9783540205920-9424/
Non interactive Quantum Perfect and Statistical Zero Knowledge 1st
edition by Hirotada Kobayashi ISBN 3540245872 9783540245872
https://ebookball.com/product/non-interactive-quantum-perfect-
and-statistical-zero-knowledge-1st-edition-by-hirotada-kobayashi-
isbn-3540245872-9783540245872-9324/
LNCS 2729 Statistical Zero Knowledge Proofs with Efficient Provers
Lattice Problems and More 1st Edition by Daniele Micciancio, Salil
Vadhan ISBN 3540451463 9783540451464
https://ebookball.com/product/lncs-2729-statistical-zero-
knowledge-proofs-with-efficient-provers-lattice-problems-and-
more-1st-edition-by-daniele-micciancio-salil-vadhan-
isbn-3540451463-9783540451464-11432/
LNAI 2842 Signal Extraction and Knowledge Discovery Based on
Statistical Modeling 1st Edition by Genshiro Kitagawa ISBN
9783540200574 354020057X
https://ebookball.com/product/lnai-2842-signal-extraction-and-
knowledge-discovery-based-on-statistical-modeling-1st-edition-by-
genshiro-kitagawa-isbn-9783540200574-354020057x-10042/
,Efficient Group Signatures without Trapdoors 1st edition by Giuseppe
Ateniese, Breno de Medeiros ISBN 3540205920 9783540205920
https://ebookball.com/product/efficient-group-signatures-without-
trapdoors-1st-edition-by-giuseppe-ateniese-breno-de-medeiros-
isbn-3540205920-9783540205920-9868/
The AGM-X 0(N) Heegner Point Lifting Algorithm and Elliptic Curve
Point Counting 1st edition by David Kohel ISBN 3540205920
9783540205920
https://ebookball.com/product/the-agm-x-0-n-heegner-point-
lifting-algorithm-and-elliptic-curve-point-counting-1st-edition-
by-david-kohel-isbn-3540205920-9783540205920-11308/
Cryptanalysis of 3-Pass HAVAL 1st edition by Bart Van Rompay, Alex
Biryukov, Bart Preneel, Joos Vandewalle ISBN 3540205920 9783540205920
https://ebookball.com/product/cryptanalysis-of-3-pass-haval-1st-
edition-by-bart-van-rompay-alex-biryukov-bart-preneel-joos-
vandewalle-isbn-3540205920-9783540205920-13278/
Generalized Powering Functions and Their Application to Digital
Signatures 1st edition by Hisayoshi Sato, Tsuyoshi Takagi, Satoru
Tezuka, Kazuo Takaragi ISBN 3540205920 9783540205920
https://ebookball.com/product/generalized-powering-functions-and-
their-application-to-digital-signatures-1st-edition-by-hisayoshi-
sato-tsuyoshi-takagi-satoru-tezuka-kazuo-takaragi-
isbn-3540205920-9783540205920-9318/
A Simple Public Key Cryptosystem with a Double Trapdoor Decryption
Mechanism and Its Applications 1st edition by Emmanuel Bresson, Dario
Catalano, David Pointcheval ISBN 3540205920 9783540205920
https://ebookball.com/product/a-simple-public-key-cryptosystem-
with-a-double-trapdoor-decryption-mechanism-and-its-
applications-1st-edition-by-emmanuel-bresson-dario-catalano-
david-pointcheval-isbn-3540205920-9783540205920-10706/
, On Diophantine Complexity
and Statistical Zero-Knowledge Arguments
Helger Lipmaa
Laboratory for Theoretical CS
Department of CS&E, Helsinki University of Technology
P.O.Box 5400, FIN-02015 HUT, Espoo, Finland
Abstract. We show how to construct practical honest-verifier statisti-
cal zero-knowledge Diophantine arguments of knowledge (HVSZK AoK)
that a committed tuple of integers belongs to an arbitrary language in
bounded arithmetic. While doing this, we propose a new algorithm for
computing the Lagrange representation of nonnegative integers and a
new efficient representing polynomial for the exponential relation. We
apply our results by constructing the most efficient known HVSZK AoK
for non-negativity and the first constant-round practical HVSZK AoK
for exponential relation. Finally, we propose the outsourcing model for
cryptographic protocols and design communication-efficient versions of
the Damgård-Jurik multi-candidate voting scheme and of the Lipmaa-
Asokan-Niemi (b + 1)st-price auction scheme that work in this model.
Keywords: Arguments of knowledge, Diophantine complexity, integer
commitment scheme, statistical zero knowledge.
1 Introduction
A set S ⊂ ZZ n is called Diophantine [Mat93], if it has a representing polynomial
RS ∈ ZZ[X; Y ], X = (X1 , . . . , Xn ) and Y = (Y1 , . . . , Ym ), such that µ ∈ S
iff for some witness ω ∈ ZZ m , RS (µ; ω) = 0. A seminal result of Matiyasevich
from 1970 states that every recursively enumerable set is Diophantine. It has
?
been an open question since [AM76], whether D = NP, where D is the class
of sets S that have representing polynomials RS , such that µ ∈ S iff for some
polynomially long witness ω ∈ ZZ m , RS (µ; ω) = 0. One is also tempted to ask a
?
similar question PD = P about the “deterministic” version of class D, the class
PD that contains such languages for which the corresponding polynomially-long
witnesses can be found in polynomial time. The gap in our knowledge in such
questions is quite surprising; this is maybe best demonstrated by the recent proof
of Pollett that if D ⊆ co-NLOGTIME then D = NP [Pol03].
In this paper we take a more practice oriented approach. Namely, we are
interested in the sets S with sub-quadratic (i.e., with length, sub-quadratic in the
length of the inputs) witnesses. We propose representing polynomials with sub-
quadratic , polynomial-time computable, witnesses for a practically important,
C.S. Laih (Ed.): ASIACRYPT 2003, LNCS 2894, pp. 398–415, 2003.
c International Association for Cryptologic Research 2003
Knowledge Arguments 1st edition by ISBN Helger
Lipmaa 3540205920 9783540205920 pdf download
https://ebookball.com/product/on-diophantine-complexity-and-
statistical-zero-knowledge-arguments-1st-edition-by-isbn-helger-
lipmaa-3540205920-9783540205920-9426/
Explore and download more ebooks or textbooks
at ebookball.com
, Get Your Digital Files Instantly: PDF, ePub, MOBI and More
Quick Digital Downloads: PDF, ePub, MOBI and Other Formats
Verifiable Homomorphic Oblivious Transfer and Private Equality Test
1st edition by Helger Lipmaa ISBN 3540205920 9783540205920
https://ebookball.com/product/verifiable-homomorphic-oblivious-
transfer-and-private-equality-test-1st-edition-by-helger-lipmaa-
isbn-3540205920-9783540205920-9424/
Non interactive Quantum Perfect and Statistical Zero Knowledge 1st
edition by Hirotada Kobayashi ISBN 3540245872 9783540245872
https://ebookball.com/product/non-interactive-quantum-perfect-
and-statistical-zero-knowledge-1st-edition-by-hirotada-kobayashi-
isbn-3540245872-9783540245872-9324/
LNCS 2729 Statistical Zero Knowledge Proofs with Efficient Provers
Lattice Problems and More 1st Edition by Daniele Micciancio, Salil
Vadhan ISBN 3540451463 9783540451464
https://ebookball.com/product/lncs-2729-statistical-zero-
knowledge-proofs-with-efficient-provers-lattice-problems-and-
more-1st-edition-by-daniele-micciancio-salil-vadhan-
isbn-3540451463-9783540451464-11432/
LNAI 2842 Signal Extraction and Knowledge Discovery Based on
Statistical Modeling 1st Edition by Genshiro Kitagawa ISBN
9783540200574 354020057X
https://ebookball.com/product/lnai-2842-signal-extraction-and-
knowledge-discovery-based-on-statistical-modeling-1st-edition-by-
genshiro-kitagawa-isbn-9783540200574-354020057x-10042/
,Efficient Group Signatures without Trapdoors 1st edition by Giuseppe
Ateniese, Breno de Medeiros ISBN 3540205920 9783540205920
https://ebookball.com/product/efficient-group-signatures-without-
trapdoors-1st-edition-by-giuseppe-ateniese-breno-de-medeiros-
isbn-3540205920-9783540205920-9868/
The AGM-X 0(N) Heegner Point Lifting Algorithm and Elliptic Curve
Point Counting 1st edition by David Kohel ISBN 3540205920
9783540205920
https://ebookball.com/product/the-agm-x-0-n-heegner-point-
lifting-algorithm-and-elliptic-curve-point-counting-1st-edition-
by-david-kohel-isbn-3540205920-9783540205920-11308/
Cryptanalysis of 3-Pass HAVAL 1st edition by Bart Van Rompay, Alex
Biryukov, Bart Preneel, Joos Vandewalle ISBN 3540205920 9783540205920
https://ebookball.com/product/cryptanalysis-of-3-pass-haval-1st-
edition-by-bart-van-rompay-alex-biryukov-bart-preneel-joos-
vandewalle-isbn-3540205920-9783540205920-13278/
Generalized Powering Functions and Their Application to Digital
Signatures 1st edition by Hisayoshi Sato, Tsuyoshi Takagi, Satoru
Tezuka, Kazuo Takaragi ISBN 3540205920 9783540205920
https://ebookball.com/product/generalized-powering-functions-and-
their-application-to-digital-signatures-1st-edition-by-hisayoshi-
sato-tsuyoshi-takagi-satoru-tezuka-kazuo-takaragi-
isbn-3540205920-9783540205920-9318/
A Simple Public Key Cryptosystem with a Double Trapdoor Decryption
Mechanism and Its Applications 1st edition by Emmanuel Bresson, Dario
Catalano, David Pointcheval ISBN 3540205920 9783540205920
https://ebookball.com/product/a-simple-public-key-cryptosystem-
with-a-double-trapdoor-decryption-mechanism-and-its-
applications-1st-edition-by-emmanuel-bresson-dario-catalano-
david-pointcheval-isbn-3540205920-9783540205920-10706/
, On Diophantine Complexity
and Statistical Zero-Knowledge Arguments
Helger Lipmaa
Laboratory for Theoretical CS
Department of CS&E, Helsinki University of Technology
P.O.Box 5400, FIN-02015 HUT, Espoo, Finland
Abstract. We show how to construct practical honest-verifier statisti-
cal zero-knowledge Diophantine arguments of knowledge (HVSZK AoK)
that a committed tuple of integers belongs to an arbitrary language in
bounded arithmetic. While doing this, we propose a new algorithm for
computing the Lagrange representation of nonnegative integers and a
new efficient representing polynomial for the exponential relation. We
apply our results by constructing the most efficient known HVSZK AoK
for non-negativity and the first constant-round practical HVSZK AoK
for exponential relation. Finally, we propose the outsourcing model for
cryptographic protocols and design communication-efficient versions of
the Damgård-Jurik multi-candidate voting scheme and of the Lipmaa-
Asokan-Niemi (b + 1)st-price auction scheme that work in this model.
Keywords: Arguments of knowledge, Diophantine complexity, integer
commitment scheme, statistical zero knowledge.
1 Introduction
A set S ⊂ ZZ n is called Diophantine [Mat93], if it has a representing polynomial
RS ∈ ZZ[X; Y ], X = (X1 , . . . , Xn ) and Y = (Y1 , . . . , Ym ), such that µ ∈ S
iff for some witness ω ∈ ZZ m , RS (µ; ω) = 0. A seminal result of Matiyasevich
from 1970 states that every recursively enumerable set is Diophantine. It has
?
been an open question since [AM76], whether D = NP, where D is the class
of sets S that have representing polynomials RS , such that µ ∈ S iff for some
polynomially long witness ω ∈ ZZ m , RS (µ; ω) = 0. One is also tempted to ask a
?
similar question PD = P about the “deterministic” version of class D, the class
PD that contains such languages for which the corresponding polynomially-long
witnesses can be found in polynomial time. The gap in our knowledge in such
questions is quite surprising; this is maybe best demonstrated by the recent proof
of Pollett that if D ⊆ co-NLOGTIME then D = NP [Pol03].
In this paper we take a more practice oriented approach. Namely, we are
interested in the sets S with sub-quadratic (i.e., with length, sub-quadratic in the
length of the inputs) witnesses. We propose representing polynomials with sub-
quadratic , polynomial-time computable, witnesses for a practically important,
C.S. Laih (Ed.): ASIACRYPT 2003, LNCS 2894, pp. 398–415, 2003.
c International Association for Cryptologic Research 2003
