---
_id: '1479'
abstract:
- lang: eng
text: "Most entropy notions H(.) like Shannon or min-entropy satisfy a chain rule
stating that for random variables X,Z, and A we have H(X|Z,A)≥H(X|Z)−|A|. That
is, by conditioning on A the entropy of X can decrease by at most the bitlength
|A| of A. Such chain rules are known to hold for some computational entropy notions
like Yao’s and unpredictability-entropy. For HILL entropy, the computational analogue
of min-entropy, the chain rule is of special interest and has found many applications,
including leakage-resilient cryptography, deterministic encryption, and memory
delegation. These applications rely on restricted special cases of the chain rule.
Whether the chain rule for conditional HILL entropy holds in general was an open
problem for which we give a strong negative answer: we construct joint distributions
(X,Z,A), where A is a distribution over a single bit, such that the HILL entropy
H HILL (X|Z) is large but H HILL (X|Z,A) is basically zero.\r\n\r\nOur counterexample
just makes the minimal assumption that NP⊈P/poly. Under the stronger assumption
that injective one-way function exist, we can make all the distributions efficiently
samplable.\r\n\r\nFinally, we show that some more sophisticated cryptographic
objects like lossy functions can be used to sample a distribution constituting
a counterexample to the chain rule making only a single invocation to the underlying
object."
acknowledgement: "This work was partly funded by the European Research Council under
ERC Starting Grant 259668-PSPC and ERC Advanced Grant 321310-PERCY.\r\n"
author:
- first_name: Stephan
full_name: Krenn, Stephan
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Akshay
full_name: Wadia, Akshay
last_name: Wadia
- first_name: Daniel
full_name: Wichs, Daniel
last_name: Wichs
citation:
ama: Krenn S, Pietrzak KZ, Wadia A, Wichs D. A counterexample to the chain rule
for conditional HILL entropy. Computational Complexity. 2016;25(3):567-605.
doi:10.1007/s00037-015-0120-9
apa: Krenn, S., Pietrzak, K. Z., Wadia, A., & Wichs, D. (2016). A counterexample
to the chain rule for conditional HILL entropy. Computational Complexity.
Springer. https://doi.org/10.1007/s00037-015-0120-9
chicago: Krenn, Stephan, Krzysztof Z Pietrzak, Akshay Wadia, and Daniel Wichs. “A
Counterexample to the Chain Rule for Conditional HILL Entropy.” Computational
Complexity. Springer, 2016. https://doi.org/10.1007/s00037-015-0120-9.
ieee: S. Krenn, K. Z. Pietrzak, A. Wadia, and D. Wichs, “A counterexample to the
chain rule for conditional HILL entropy,” Computational Complexity, vol.
25, no. 3. Springer, pp. 567–605, 2016.
ista: Krenn S, Pietrzak KZ, Wadia A, Wichs D. 2016. A counterexample to the chain
rule for conditional HILL entropy. Computational Complexity. 25(3), 567–605.
mla: Krenn, Stephan, et al. “A Counterexample to the Chain Rule for Conditional
HILL Entropy.” Computational Complexity, vol. 25, no. 3, Springer, 2016,
pp. 567–605, doi:10.1007/s00037-015-0120-9.
short: S. Krenn, K.Z. Pietrzak, A. Wadia, D. Wichs, Computational Complexity 25
(2016) 567–605.
date_created: 2018-12-11T11:52:16Z
date_published: 2016-09-01T00:00:00Z
date_updated: 2023-02-23T11:05:09Z
day: '01'
ddc:
- '004'
department:
- _id: KrPi
doi: 10.1007/s00037-015-0120-9
ec_funded: 1
file:
- access_level: open_access
checksum: 7659296174fa75f5f0364f31f46f4bcf
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:29Z
date_updated: 2020-07-14T12:44:56Z
file_id: '5012'
file_name: IST-2017-766-v1+1_678.pdf
file_size: 483258
relation: main_file
file_date_updated: 2020-07-14T12:44:56Z
has_accepted_license: '1'
intvolume: ' 25'
issue: '3'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Submitted Version
page: 567 - 605
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: Computational Complexity
publication_status: published
publisher: Springer
publist_id: '5715'
pubrep_id: '766'
quality_controlled: '1'
related_material:
record:
- id: '2940'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: A counterexample to the chain rule for conditional HILL entropy
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 25
year: '2016'
...
---
_id: '2259'
abstract:
- lang: eng
text: "The learning with rounding (LWR) problem, introduced by Banerjee, Peikert
and Rosen at EUROCRYPT ’12, is a variant of learning with errors (LWE), where
one replaces random errors with deterministic rounding. The LWR problem was shown
to be as hard as LWE for a setting of parameters where the modulus and modulus-to-error
ratio are super-polynomial. In this work we resolve the main open problem and
give a new reduction that works for a larger range of parameters, allowing for
a polynomial modulus and modulus-to-error ratio. In particular, a smaller modulus
gives us greater efficiency, and a smaller modulus-to-error ratio gives us greater
security, which now follows from the worst-case hardness of GapSVP with polynomial
(rather than super-polynomial) approximation factors.\r\n\r\nAs a tool in the
reduction, we show that there is a “lossy mode” for the LWR problem, in which
LWR samples only reveal partial information about the secret. This property gives
us several interesting new applications, including a proof that LWR remains secure
with weakly random secrets of sufficient min-entropy, and very simple constructions
of deterministic encryption, lossy trapdoor functions and reusable extractors.\r\n\r\nOur
approach is inspired by a technique of Goldwasser et al. from ICS ’10, which implicitly
showed the existence of a “lossy mode” for LWE. By refining this technique, we
also improve on the parameters of that work to only requiring a polynomial (instead
of super-polynomial) modulus and modulus-to-error ratio.\r\n"
alternative_title:
- LNCS
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Stephan
full_name: Krenn, Stephan
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Daniel
full_name: Wichs, Daniel
last_name: Wichs
citation:
ama: 'Alwen JF, Krenn S, Pietrzak KZ, Wichs D. Learning with rounding, revisited:
New reduction properties and applications. 2013;8042(1):57-74. doi:10.1007/978-3-642-40041-4_4'
apa: 'Alwen, J. F., Krenn, S., Pietrzak, K. Z., & Wichs, D. (2013). Learning
with rounding, revisited: New reduction properties and applications. Presented
at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United
States: Springer. https://doi.org/10.1007/978-3-642-40041-4_4'
chicago: 'Alwen, Joel F, Stephan Krenn, Krzysztof Z Pietrzak, and Daniel Wichs.
“Learning with Rounding, Revisited: New Reduction Properties and Applications.”
Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-40041-4_4.'
ieee: 'J. F. Alwen, S. Krenn, K. Z. Pietrzak, and D. Wichs, “Learning with rounding,
revisited: New reduction properties and applications,” vol. 8042, no. 1. Springer,
pp. 57–74, 2013.'
ista: 'Alwen JF, Krenn S, Pietrzak KZ, Wichs D. 2013. Learning with rounding, revisited:
New reduction properties and applications. 8042(1), 57–74.'
mla: 'Alwen, Joel F., et al. Learning with Rounding, Revisited: New Reduction
Properties and Applications. Vol. 8042, no. 1, Springer, 2013, pp. 57–74,
doi:10.1007/978-3-642-40041-4_4.'
short: J.F. Alwen, S. Krenn, K.Z. Pietrzak, D. Wichs, 8042 (2013) 57–74.
conference:
end_date: 2013-08-22
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2013-08-18
date_created: 2018-12-11T11:56:37Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T06:56:21Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: KrPi
doi: 10.1007/978-3-642-40041-4_4
ec_funded: 1
file:
- access_level: open_access
checksum: 16d428408a806b8e49eecc607deab115
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:55Z
date_updated: 2020-07-14T12:45:35Z
file_id: '4912'
file_name: IST-2016-684-v1+1_098.pdf
file_size: 587898
relation: main_file
file_date_updated: 2020-07-14T12:45:35Z
has_accepted_license: '1'
intvolume: ' 8042'
issue: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 57 - 74
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '4687'
pubrep_id: '684'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: 'Learning with rounding, revisited: New reduction properties and applications'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8042
year: '2013'
...
---
_id: '2940'
abstract:
- lang: eng
text: "A chain rule for an entropy notion H(.) states that the entropy H(X) of a
variable X decreases by at most l if conditioned on an l-bit string A, i.e., H(X|A)>=
H(X)-l. More generally, it satisfies a chain rule for conditional entropy if H(X|Y,A)>=
H(X|Y)-l.\r\n\r\nAll natural information theoretic entropy notions we are aware
of (like Shannon or min-entropy) satisfy some kind of chain rule for conditional
entropy. Moreover, many computational entropy notions (like Yao entropy, unpredictability
entropy and several variants of HILL entropy) satisfy the chain rule for conditional
entropy, though here not only the quantity decreases by l, but also the quality
of the entropy decreases exponentially in l. However, for \r\nthe standard notion
of conditional HILL entropy (the computational equivalent of min-entropy) the
existence of such a rule was unknown so far.\r\n\r\nIn this paper, we prove that
for conditional HILL entropy no meaningful chain rule exists, assuming the existence
of one-way permutations: there exist distributions X,Y,A, where A is a distribution
over a single bit, but $H(X|Y)>>H(X|Y,A)$, even if we simultaneously allow
for a massive degradation in the quality of the entropy.\r\n\r\nThe idea underlying
our construction is based on a surprising connection between the chain rule for
HILL entropy and deniable encryption. "
alternative_title:
- LNCS
author:
- first_name: Stephan
full_name: Krenn, Stephan
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Akshay
full_name: Wadia, Akshay
last_name: Wadia
citation:
ama: 'Krenn S, Pietrzak KZ, Wadia A. A counterexample to the chain rule for conditional
HILL entropy, and what deniable encryption has to do with it. In: Sahai A, ed.
Vol 7785. Springer; 2013:23-39. doi:10.1007/978-3-642-36594-2_2'
apa: 'Krenn, S., Pietrzak, K. Z., & Wadia, A. (2013). A counterexample to the
chain rule for conditional HILL entropy, and what deniable encryption has to do
with it. In A. Sahai (Ed.) (Vol. 7785, pp. 23–39). Presented at the TCC: Theory
of Cryptography Conference, Tokyo, Japan: Springer. https://doi.org/10.1007/978-3-642-36594-2_2'
chicago: Krenn, Stephan, Krzysztof Z Pietrzak, and Akshay Wadia. “A Counterexample
to the Chain Rule for Conditional HILL Entropy, and What Deniable Encryption Has
to Do with It.” edited by Amit Sahai, 7785:23–39. Springer, 2013. https://doi.org/10.1007/978-3-642-36594-2_2.
ieee: 'S. Krenn, K. Z. Pietrzak, and A. Wadia, “A counterexample to the chain rule
for conditional HILL entropy, and what deniable encryption has to do with it,”
presented at the TCC: Theory of Cryptography Conference, Tokyo, Japan, 2013, vol.
7785, pp. 23–39.'
ista: 'Krenn S, Pietrzak KZ, Wadia A. 2013. A counterexample to the chain rule for
conditional HILL entropy, and what deniable encryption has to do with it. TCC:
Theory of Cryptography Conference, LNCS, vol. 7785, 23–39.'
mla: Krenn, Stephan, et al. A Counterexample to the Chain Rule for Conditional
HILL Entropy, and What Deniable Encryption Has to Do with It. Edited by Amit
Sahai, vol. 7785, Springer, 2013, pp. 23–39, doi:10.1007/978-3-642-36594-2_2.
short: S. Krenn, K.Z. Pietrzak, A. Wadia, in:, A. Sahai (Ed.), Springer, 2013, pp.
23–39.
conference:
end_date: 2013-03-06
location: Tokyo, Japan
name: 'TCC: Theory of Cryptography Conference'
start_date: 2013-03-03
date_created: 2018-12-11T12:00:27Z
date_published: 2013-01-29T00:00:00Z
date_updated: 2023-02-23T10:00:43Z
day: '29'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.1007/978-3-642-36594-2_2
ec_funded: 1
editor:
- first_name: Amit
full_name: Sahai, Amit
last_name: Sahai
file:
- access_level: open_access
checksum: beb0cc1c0579da2d2e84394230a5da78
content_type: application/pdf
creator: dernst
date_created: 2019-01-22T14:11:11Z
date_updated: 2020-07-14T12:45:54Z
file_id: '5875'
file_name: 2013_LNCS_Krenn.pdf
file_size: 414823
relation: main_file
file_date_updated: 2020-07-14T12:45:54Z
has_accepted_license: '1'
intvolume: ' 7785'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 23 - 39
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '3795'
quality_controlled: '1'
related_material:
record:
- id: '1479'
relation: later_version
status: public
scopus_import: 1
status: public
title: A counterexample to the chain rule for conditional HILL entropy, and what deniable
encryption has to do with it
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7785
year: '2013'
...
---
_id: '2973'
abstract:
- lang: eng
text: "Efficient zero-knowledge proofs of knowledge (ZK-PoK) are basic building
blocks of many practical cryptographic applications such as identification schemes,
group signatures, and secure multiparty computation. Currently, first applications
that critically rely on ZK-PoKs are being deployed in the real world. The most
prominent example is Direct Anonymous Attestation (DAA), which was adopted by
the Trusted Computing Group (TCG) and implemented as one of the functionalities
of the cryptographic Trusted Platform Module (TPM) chip.\n\nImplementing systems
using ZK-PoK turns out to be challenging, since ZK-PoK are, loosely speaking,
significantly more complex than standard crypto primitives, such as encryption
and signature schemes. As a result, implementation cycles of ZK-PoK are time-consuming
and error-prone, in particular for developers with minor or no cryptographic skills.
\n\nIn this paper we report on our ongoing and future research vision with the
goal to bring ZK-PoK to practice by making them accessible to crypto and security
engineers. To this end we are developing compilers and related tools that support
and partially automate the design, implementation, verification and secure implementation
of ZK-PoK protocols."
acknowledgement: This work is being performed within the FP7 EU project CACE (Computer
Aided Cryptography Engineering).
alternative_title:
- LNCS
author:
- first_name: Endre
full_name: Bangerter, Endre
last_name: Bangerter
- first_name: Stefania
full_name: Barzan, Stefania
last_name: Barzan
- first_name: Stephan
full_name: Stephan Krenn
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Ahmad
full_name: Sadeghi, Ahmad-Reza
last_name: Sadeghi
- first_name: Thomas
full_name: Schneider, Thomas
last_name: Schneider
- first_name: Joe
full_name: Tsay, Joe-Kai
last_name: Tsay
citation:
ama: 'Bangerter E, Barzan S, Krenn S, Sadeghi A, Schneider T, Tsay J. Bringing Zero-Knowledge
Proofs of Knowledge to Practice. In: Christianson B, Malcolm J, Matyas V, Roe
M, eds. Vol 7028. Springer; 2013:51-62. doi:10.1007/978-3-642-36213-2_9'
apa: 'Bangerter, E., Barzan, S., Krenn, S., Sadeghi, A., Schneider, T., & Tsay,
J. (2013). Bringing Zero-Knowledge Proofs of Knowledge to Practice. In B. Christianson,
J. Malcolm, V. Matyas, & M. Roe (Eds.) (Vol. 7028, pp. 51–62). Presented at
the SPW: Security Protocols Workshop, Springer. https://doi.org/10.1007/978-3-642-36213-2_9'
chicago: Bangerter, Endre, Stefania Barzan, Stephan Krenn, Ahmad Sadeghi, Thomas
Schneider, and Joe Tsay. “Bringing Zero-Knowledge Proofs of Knowledge to Practice.”
edited by Bruce Christianson, James Malcolm, Vashek Matyas, and Michael Roe, 7028:51–62.
Springer, 2013. https://doi.org/10.1007/978-3-642-36213-2_9.
ieee: 'E. Bangerter, S. Barzan, S. Krenn, A. Sadeghi, T. Schneider, and J. Tsay,
“Bringing Zero-Knowledge Proofs of Knowledge to Practice,” presented at the SPW:
Security Protocols Workshop, 2013, vol. 7028, pp. 51–62.'
ista: 'Bangerter E, Barzan S, Krenn S, Sadeghi A, Schneider T, Tsay J. 2013. Bringing
Zero-Knowledge Proofs of Knowledge to Practice. SPW: Security Protocols Workshop,
LNCS, vol. 7028, 51–62.'
mla: Bangerter, Endre, et al. Bringing Zero-Knowledge Proofs of Knowledge to
Practice. Edited by Bruce Christianson et al., vol. 7028, Springer, 2013,
pp. 51–62, doi:10.1007/978-3-642-36213-2_9.
short: E. Bangerter, S. Barzan, S. Krenn, A. Sadeghi, T. Schneider, J. Tsay, in:,
B. Christianson, J. Malcolm, V. Matyas, M. Roe (Eds.), Springer, 2013, pp. 51–62.
conference:
name: 'SPW: Security Protocols Workshop'
date_created: 2018-12-11T12:00:38Z
date_published: 2013-01-08T00:00:00Z
date_updated: 2021-01-12T07:40:10Z
day: '08'
doi: 10.1007/978-3-642-36213-2_9
editor:
- first_name: Bruce
full_name: Christianson, Bruce
last_name: Christianson
- first_name: James
full_name: Malcolm, James A.
last_name: Malcolm
- first_name: Vashek
full_name: Matyas, Vashek
last_name: Matyas
- first_name: Michael
full_name: Roe, Michael
last_name: Roe
extern: 1
intvolume: ' 7028'
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2009/211.pdf
month: '01'
oa: 1
page: 51 - 62
publication_status: published
publisher: Springer
publist_id: '3732'
quality_controlled: 0
status: public
title: Bringing Zero-Knowledge Proofs of Knowledge to Practice
type: conference
volume: 7028
year: '2013'
...
---
_id: '2937'
abstract:
- lang: eng
text: Developers building cryptography into security-sensitive applications face
a daunting task. Not only must they understand the security guarantees delivered
by the constructions they choose, they must also implement and combine them correctly
and efficiently. Cryptographic compilers free developers from this task by turning
high-level specifications of security goals into efficient implementations. Yet,
trusting such tools is hard as they rely on complex mathematical machinery and
claim security properties that are subtle and difficult to verify. In this paper
we present ZKCrypt, an optimizing cryptographic compiler achieving an unprecedented
level of assurance without sacrificing practicality for a comprehensive class
of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline
of ZKCrypt integrates purpose-built verified compilers and verifying compilers
producing formal proofs in the CertiCrypt framework. By combining the guarantees
delivered by each stage, ZKCrypt provides assurance that the output implementation
securely realizes the abstract proof goal given as input. We report on the main
characteristics of ZKCrypt, highlight new definitions and concepts at its foundations,
and illustrate its applicability through a representative example of an anonymous
credential system.
acknowledgement: This work was partially funded by National Funds through the FCT
- Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and
Technology) within project ENI-AC/2224/2009, by ENIAC Joint Undertaking under grant
agreement number 120224, European Projects FP7-256980 NESSoS and FP7-229599 AMAROUT,
Spanish National project TIN2009-14599 DESAFIOS 10, and Madrid Regional project
S2009TIC-1465 PROMETIDOS.
author:
- first_name: José
full_name: Almeida, José
last_name: Almeida
- first_name: Manuel
full_name: Barbosa, Manuel
last_name: Barbosa
- first_name: Endre
full_name: Bangerter, Endre
last_name: Bangerter
- first_name: Gilles
full_name: Barthe, Gilles
last_name: Barthe
- first_name: Stephan
full_name: Krenn, Stephan
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Santiago
full_name: Béguelin, Santiago
last_name: Béguelin
citation:
ama: 'Almeida J, Barbosa M, Bangerter E, Barthe G, Krenn S, Béguelin S. Full proof
cryptography: Verifiable compilation of efficient zero-knowledge protocols. In:
Proceedings of the 2012 ACM Conference on Computer and Communications Security.
ACM; 2012:488-500. doi:10.1145/2382196.2382249'
apa: 'Almeida, J., Barbosa, M., Bangerter, E., Barthe, G., Krenn, S., & Béguelin,
S. (2012). Full proof cryptography: Verifiable compilation of efficient zero-knowledge
protocols. In Proceedings of the 2012 ACM conference on Computer and communications
security (pp. 488–500). Raleigh, NC, USA: ACM. https://doi.org/10.1145/2382196.2382249'
chicago: 'Almeida, José, Manuel Barbosa, Endre Bangerter, Gilles Barthe, Stephan
Krenn, and Santiago Béguelin. “Full Proof Cryptography: Verifiable Compilation
of Efficient Zero-Knowledge Protocols.” In Proceedings of the 2012 ACM Conference
on Computer and Communications Security, 488–500. ACM, 2012. https://doi.org/10.1145/2382196.2382249.'
ieee: 'J. Almeida, M. Barbosa, E. Bangerter, G. Barthe, S. Krenn, and S. Béguelin,
“Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols,”
in Proceedings of the 2012 ACM conference on Computer and communications security,
Raleigh, NC, USA, 2012, pp. 488–500.'
ista: 'Almeida J, Barbosa M, Bangerter E, Barthe G, Krenn S, Béguelin S. 2012. Full
proof cryptography: Verifiable compilation of efficient zero-knowledge protocols.
Proceedings of the 2012 ACM conference on Computer and communications security.
CCS: Computer and Communications Security, 488–500.'
mla: 'Almeida, José, et al. “Full Proof Cryptography: Verifiable Compilation of
Efficient Zero-Knowledge Protocols.” Proceedings of the 2012 ACM Conference
on Computer and Communications Security, ACM, 2012, pp. 488–500, doi:10.1145/2382196.2382249.'
short: J. Almeida, M. Barbosa, E. Bangerter, G. Barthe, S. Krenn, S. Béguelin, in:,
Proceedings of the 2012 ACM Conference on Computer and Communications Security,
ACM, 2012, pp. 488–500.
conference:
end_date: 2012-10-18
location: Raleigh, NC, USA
name: 'CCS: Computer and Communications Security'
start_date: 2012-10-16
date_created: 2018-12-11T12:00:26Z
date_published: 2012-10-01T00:00:00Z
date_updated: 2021-01-12T07:39:53Z
day: '01'
department:
- _id: KrPi
doi: 10.1145/2382196.2382249
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2012/258
month: '10'
oa: 1
oa_version: Submitted Version
page: 488 - 500
publication: Proceedings of the 2012 ACM conference on Computer and communications
security
publication_status: published
publisher: ACM
publist_id: '3798'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Full proof cryptography: Verifiable compilation of efficient zero-knowledge
protocols'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '2974'
abstract:
- lang: eng
text: "We construct a perfectly binding string commitment scheme whose security
is based on the learning parity with noise (LPN) assumption, or equivalently,
the hardness of decoding random linear codes. Our scheme not only allows for a
simple and efficient zero-knowledge proof of knowledge for committed values (essentially
a Σ-protocol), but also for such proofs showing any kind of relation amongst committed
values, i.e. proving that messages m_0,...,m_u, are such that m_0=C(m_1,...,m_u)
for any circuit C.\r\n\r\nTo get soundness which is exponentially small in a security
parameter t, and when the zero-knowledge property relies on the LPN problem with
secrets of length l, our 3 round protocol has communication complexity O(t|C|l
log(l)) and computational complexity of O(t|C|l) bit operations. The hidden constants
are small, and the computation consists mostly of computing inner products of
bit-vectors."
acknowledgement: "We are grateful to Petros Mol for helpful discussions on the reduction
for the hardness of the xLPN problem.\r\n"
alternative_title:
- LNCS
author:
- first_name: Abhishek
full_name: Jain, Abhishek
last_name: Jain
- first_name: Stephan
full_name: Krenn, Stephan
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Aris
full_name: Tentes, Aris
last_name: Tentes
citation:
ama: 'Jain A, Krenn S, Pietrzak KZ, Tentes A. Commitments and efficient zero knowledge
proofs from learning parity with noise. In: Wang X, Sako K, eds. Vol 7658. Springer;
2012:663-680. doi:10.1007/978-3-642-34961-4_40'
apa: 'Jain, A., Krenn, S., Pietrzak, K. Z., & Tentes, A. (2012). Commitments
and efficient zero knowledge proofs from learning parity with noise. In X. Wang
& K. Sako (Eds.) (Vol. 7658, pp. 663–680). Presented at the ASIACRYPT: Theory
and Application of Cryptology and Information Security, Beijing, China: Springer.
https://doi.org/10.1007/978-3-642-34961-4_40'
chicago: Jain, Abhishek, Stephan Krenn, Krzysztof Z Pietrzak, and Aris Tentes. “Commitments
and Efficient Zero Knowledge Proofs from Learning Parity with Noise.” edited by
Xiaoyun Wang and Kazue Sako, 7658:663–80. Springer, 2012. https://doi.org/10.1007/978-3-642-34961-4_40.
ieee: 'A. Jain, S. Krenn, K. Z. Pietrzak, and A. Tentes, “Commitments and efficient
zero knowledge proofs from learning parity with noise,” presented at the ASIACRYPT:
Theory and Application of Cryptology and Information Security, Beijing, China,
2012, vol. 7658, pp. 663–680.'
ista: 'Jain A, Krenn S, Pietrzak KZ, Tentes A. 2012. Commitments and efficient zero
knowledge proofs from learning parity with noise. ASIACRYPT: Theory and Application
of Cryptology and Information Security, LNCS, vol. 7658, 663–680.'
mla: Jain, Abhishek, et al. Commitments and Efficient Zero Knowledge Proofs from
Learning Parity with Noise. Edited by Xiaoyun Wang and Kazue Sako, vol. 7658,
Springer, 2012, pp. 663–80, doi:10.1007/978-3-642-34961-4_40.
short: A. Jain, S. Krenn, K.Z. Pietrzak, A. Tentes, in:, X. Wang, K. Sako (Eds.),
Springer, 2012, pp. 663–680.
conference:
end_date: 2012-12-06
location: Beijing, China
name: 'ASIACRYPT: Theory and Application of Cryptology and Information Security'
start_date: 2012-12-02
date_created: 2018-12-11T12:00:38Z
date_published: 2012-12-01T00:00:00Z
date_updated: 2021-01-12T07:40:11Z
day: '01'
ddc:
- '004'
- '005'
department:
- _id: KrPi
doi: 10.1007/978-3-642-34961-4_40
ec_funded: 1
editor:
- first_name: Xiaoyun
full_name: Wang, Xiaoyun
last_name: Wang
- first_name: Kazue
full_name: Sako, Kazue
last_name: Sako
file:
- access_level: open_access
checksum: ab879537385efc4cb4203e7ef0fea17b
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:00Z
date_updated: 2020-07-14T12:45:58Z
file_id: '5048'
file_name: IST-2016-721-v1+1_513.pdf
file_size: 482570
relation: main_file
file_date_updated: 2020-07-14T12:45:58Z
has_accepted_license: '1'
intvolume: ' 7658'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Submitted Version
page: 663 - 680
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '3730'
pubrep_id: '721'
scopus_import: 1
status: public
title: Commitments and efficient zero knowledge proofs from learning parity with noise
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7658
year: '2012'
...
---
_id: '2975'
abstract:
- lang: eng
text: "Zero-knowledge proofs of knowledge (ZK-PoK) for discrete logarithms and related
problems are indispensable for practical cryptographic protocols. Recently, Camenisch,
Kiayias, and Yung provided a specification language (the CKY-language) for such
protocols which allows for a modular design and protocol analysis: for every zero-knowledge
proof specified in this language, protocol designers are ensured that there exists
an efficient protocol which indeed proves the specified statement.\n\nHowever,
the protocols resulting from their compilation techniques only satisfy the classical
notion of ZK-PoK, which is not retained are when they used as building blocks
for higher-level applications or composed with other protocols.\nThis problem
can be tackled by moving to the Universal Composability (UC) framework, which
guarantees retention of security when composing protocols in arbitrary ways. \nWhile
there exist generic transformations from $\\Sigma$-protocols to UC-secure protocols,
these transformation are often too inefficient for practice.\n \nIn this paper
we introduce a specification language akin to the CKY-language and a compiler
such that the resulting protocols are UC-secure and efficient. \nTo this end,
we propose an extension of the UC-framework addressing the \nissue that UC-secure
zero-knowledge proofs are by definition proofs of knowledge, and state a special
composition theorem which allows one to use the weaker -- but more efficient and
often sufficient -- notion of proofs of membership in the UC-framework. \nWe
believe that our contributions enable the design of practically efficient protocols
that are UC-secure and thus themselves can be used as building blocks."
acknowledgement: This work was in part funded by the Swiss Hasler Foundation, and
the EU FP7 grants 216483 and 216499, as well as by the NSF grant CNS-0716690.
alternative_title:
- LNCS
author:
- first_name: Jan
full_name: Camenisch, Jan
last_name: Camenisch
- first_name: Stephan
full_name: Stephan Krenn
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Victor
full_name: Shoup, Victor
last_name: Shoup
citation:
ama: 'Camenisch J, Krenn S, Shoup V. A Framework for Practical Universally Composable
Zero-Knowledge Protocols. In: Lee D, Wang X, eds. Vol 7073. Springer; 2011:449-467.
doi:10.1007/978-3-642-25385-0'
apa: 'Camenisch, J., Krenn, S., & Shoup, V. (2011). A Framework for Practical
Universally Composable Zero-Knowledge Protocols. In D. Lee & X. Wang (Eds.)
(Vol. 7073, pp. 449–467). Presented at the ASIACRYPT: Theory and Application of
Cryptology and Information Security, Springer. https://doi.org/10.1007/978-3-642-25385-0'
chicago: Camenisch, Jan, Stephan Krenn, and Victor Shoup. “A Framework for Practical
Universally Composable Zero-Knowledge Protocols.” edited by Dong Lee and Xiaoyun
Wang, 7073:449–67. Springer, 2011. https://doi.org/10.1007/978-3-642-25385-0.
ieee: 'J. Camenisch, S. Krenn, and V. Shoup, “A Framework for Practical Universally
Composable Zero-Knowledge Protocols,” presented at the ASIACRYPT: Theory and Application
of Cryptology and Information Security, 2011, vol. 7073, pp. 449–467.'
ista: 'Camenisch J, Krenn S, Shoup V. 2011. A Framework for Practical Universally
Composable Zero-Knowledge Protocols. ASIACRYPT: Theory and Application of Cryptology
and Information Security, LNCS, vol. 7073, 449–467.'
mla: Camenisch, Jan, et al. A Framework for Practical Universally Composable
Zero-Knowledge Protocols. Edited by Dong Lee and Xiaoyun Wang, vol. 7073,
Springer, 2011, pp. 449–67, doi:10.1007/978-3-642-25385-0.
short: J. Camenisch, S. Krenn, V. Shoup, in:, D. Lee, X. Wang (Eds.), Springer,
2011, pp. 449–467.
conference:
name: 'ASIACRYPT: Theory and Application of Cryptology and Information Security'
date_created: 2018-12-11T12:00:39Z
date_published: 2011-11-21T00:00:00Z
date_updated: 2021-01-12T07:40:11Z
day: '21'
doi: 10.1007/978-3-642-25385-0
editor:
- first_name: Dong
full_name: Lee, Dong Hoon
last_name: Lee
- first_name: Xiaoyun
full_name: Wang, Xiaoyun
last_name: Wang
extern: 1
intvolume: ' 7073'
main_file_link:
- open_access: '0'
url: http://eprint.iacr.org/2011/228.pdf
month: '11'
page: 449 - 467
publication_status: published
publisher: Springer
publist_id: '3728'
quality_controlled: 0
status: public
title: A Framework for Practical Universally Composable Zero-Knowledge Protocols
type: conference
volume: 7073
year: '2011'
...
---
_id: '2977'
abstract:
- lang: eng
text: "Cryptographic two-party protocols are used ubiquitously in\n everyday
life. While some of these protocols are easy to\n understand and implement
(e.g., key exchange or transmission of\n encrypted data), many of them are
much more complex (e.g.,\n e-banking and e-voting applications, or anonymous
authentication\n and credential systems).\n\n For a software engineer without
appropriate cryptographic skills\n the implementation of such protocols is
often difficult, time\n consuming and error-prone. For this reason, a number
of compilers\n supporting programmers have been published in recent\n years.
However, they are either designed for very specific\n cryptographic primitives
(e.g., zero-knowledge proofs of\n knowledge), or they only offer a very low
level of abstraction and\n thus again demand substantial mathematical and cryptographic\n
\ skills from the programmer. Finally, some of the existing\n compilers do
not produce executable code, but only metacode which\n has to be instantiated
with mathematical libraries, encryption\n routines, etc. before it can actually
be used.\n \n In this paper we present a cryptographically aware compiler
which\n is equally useful to cryptographers who want to benchmark\n protocols
designed on paper, and to programmers who want to\n implement complex security
sensitive protocols without having to\n understand all subtleties. Our tool
offers a high level of\n abstraction and outputs well-structured and documented
Java\n code. We believe that our compiler can contribute to shortening\n the
development cycles of cryptographic applications and to\n reducing their error-proneness."
acknowledgement: This work was in part funded by the European Community’s Seventh
Framework Programme (FP7) under grant agreement no. 216499 and the Swiss Hasler
Foundation under projects no. 09037 and 10069.
author:
- first_name: Endre
full_name: Bangerter, Endre
last_name: Bangerter
- first_name: Stephan
full_name: Stephan Krenn
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Martial
full_name: Seifriz, Martial
last_name: Seifriz
- first_name: Ulrich
full_name: Ultes-Nitsche, Ulrich
last_name: Ultes Nitsche
citation:
ama: 'Bangerter E, Krenn S, Seifriz M, Ultes Nitsche U. cPLC - A Cryptographic Programming
Language and Compiler. In: Venter H, Coetzee M, Loock M, eds. IEEE; 2011. doi:10.1109/ISSA.2011.6027533'
apa: 'Bangerter, E., Krenn, S., Seifriz, M., & Ultes Nitsche, U. (2011). cPLC
- A Cryptographic Programming Language and Compiler. In H. Venter, M. Coetzee,
& M. Loock (Eds.). Presented at the ISSA: Information Security South Africa,
IEEE. https://doi.org/10.1109/ISSA.2011.6027533'
chicago: Bangerter, Endre, Stephan Krenn, Martial Seifriz, and Ulrich Ultes Nitsche.
“CPLC - A Cryptographic Programming Language and Compiler.” edited by Hein Venter,
Marijke Coetzee, and Marianne Loock. IEEE, 2011. https://doi.org/10.1109/ISSA.2011.6027533.
ieee: 'E. Bangerter, S. Krenn, M. Seifriz, and U. Ultes Nitsche, “cPLC - A Cryptographic
Programming Language and Compiler,” presented at the ISSA: Information Security
South Africa, 2011.'
ista: 'Bangerter E, Krenn S, Seifriz M, Ultes Nitsche U. 2011. cPLC - A Cryptographic
Programming Language and Compiler. ISSA: Information Security South Africa.'
mla: Bangerter, Endre, et al. CPLC - A Cryptographic Programming Language and
Compiler. Edited by Hein Venter et al., IEEE, 2011, doi:10.1109/ISSA.2011.6027533.
short: E. Bangerter, S. Krenn, M. Seifriz, U. Ultes Nitsche, in:, H. Venter, M.
Coetzee, M. Loock (Eds.), IEEE, 2011.
conference:
name: 'ISSA: Information Security South Africa'
date_created: 2018-12-11T12:00:39Z
date_published: 2011-08-01T00:00:00Z
date_updated: 2021-01-12T07:40:12Z
day: '01'
doi: 10.1109/ISSA.2011.6027533
editor:
- first_name: Hein
full_name: Venter, Hein S.
last_name: Venter
- first_name: Marijke
full_name: Coetzee, Marijke
last_name: Coetzee
- first_name: Marianne
full_name: Loock, Marianne
last_name: Loock
extern: 1
month: '08'
publication_status: published
publisher: IEEE
publist_id: '3726'
quality_controlled: 0
status: public
title: cPLC - A Cryptographic Programming Language and Compiler
type: conference
year: '2011'
...
---
_id: '2976'
abstract:
- lang: eng
text: |-
Side channel attacks on cryptographic systems exploit information
gained from physical implementations rather than theoretical
weaknesses of a scheme. In recent years, major achievements were made
for the class of so called access-driven cache attacks. Such attacks
exploit the leakage of the memory locations accessed by a victim
process.
In this paper we consider the AES block cipher and present an attack
which is capable of recovering the full secret key in almost realtime
for AES-128, requiring only a very limited number of observed
encryptions. Unlike previous attacks, we do not require any
information about the plaintext (such as its distribution, etc.).
Moreover, for the first time, we also show how the plaintext can be
recovered without having access to the ciphertext at all. It is the
first working attack on AES implementations using compressed
tables. There, no efficient techniques to identify the beginning
of AES rounds is known, which is the fundamental assumption underlying previous
attacks.
We have a fully working implementation of our attack which is able to
recover AES keys after observing as little as 100 encryptions. It
works against the OpenSSL 0.9.8n implementation of AES on Linux
systems. Our spy process does not require any special privileges
beyond those of a standard Linux user. A contribution of probably
independent interest is a denial of service attack on the task scheduler of
current Linux systems (CFS), which allows one to observe (on average)
every single memory access of a victim process.
acknowledgement: |-
This work was in part funded by the European Community’s Seventh Framework Programme (FP7) under grant agreement no. 216499 and the Swiss Hasler Foundation.
An extended abstract was also accepted for COSADE 2011.
author:
- first_name: David
full_name: Gullasch, David
last_name: Gullasch
- first_name: Endre
full_name: Bangerter, Endre
last_name: Bangerter
- first_name: Stephan
full_name: Stephan Krenn
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
citation:
ama: 'Gullasch D, Bangerter E, Krenn S. Cache Games - Bringing Access-Based Cache
Attacks on AES to Practice. In: IEEE; 2011:490-505. doi:10.1109/SP.2011.22'
apa: 'Gullasch, D., Bangerter, E., & Krenn, S. (2011). Cache Games - Bringing
Access-Based Cache Attacks on AES to Practice (pp. 490–505). Presented at the
S&P: IEEE Symposium on Security and Privacy, IEEE. https://doi.org/10.1109/SP.2011.22'
chicago: Gullasch, David, Endre Bangerter, and Stephan Krenn. “Cache Games - Bringing
Access-Based Cache Attacks on AES to Practice,” 490–505. IEEE, 2011. https://doi.org/10.1109/SP.2011.22.
ieee: 'D. Gullasch, E. Bangerter, and S. Krenn, “Cache Games - Bringing Access-Based
Cache Attacks on AES to Practice,” presented at the S&P: IEEE Symposium on
Security and Privacy, 2011, pp. 490–505.'
ista: 'Gullasch D, Bangerter E, Krenn S. 2011. Cache Games - Bringing Access-Based
Cache Attacks on AES to Practice. S&P: IEEE Symposium on Security and Privacy,
490–505.'
mla: Gullasch, David, et al. Cache Games - Bringing Access-Based Cache Attacks
on AES to Practice. IEEE, 2011, pp. 490–505, doi:10.1109/SP.2011.22.
short: D. Gullasch, E. Bangerter, S. Krenn, in:, IEEE, 2011, pp. 490–505.
conference:
name: 'S&P: IEEE Symposium on Security and Privacy'
date_created: 2018-12-11T12:00:39Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:40:11Z
day: '01'
doi: 10.1109/SP.2011.22
extern: 1
main_file_link:
- open_access: '0'
url: http://eprint.iacr.org/2010/594.pdf
month: '01'
page: 490 - 505
publication_status: published
publisher: IEEE
publist_id: '3727'
quality_controlled: 0
status: public
title: Cache Games - Bringing Access-Based Cache Attacks on AES to Practice
type: conference
year: '2011'
...
---
_id: '2979'
abstract:
- lang: eng
text: "Zero-knowledge proofs of knowledge (ZK-PoK) are important building blocks
for numerous cryptographic applications. Although ZK-PoK have a high potential
impact, their real world deployment is typically hindered by their significant
complexity compared to other (non-interactive) crypto primitives. Moreover, their
design and implementation are time-consuming and error-prone.\n\nWe contribute
to overcoming these challenges as follows: We present a comprehensive specification
language and a compiler for ZK-PoK protocols based on Σ-protocols. The compiler
allows the fully automatic translation of an abstract description of a proof goal
into an executable implementation. Moreover, the compiler overcomes various restrictions
of previous approaches, e.g., it supports the important class of exponentiation
homomorphisms with hidden-order co-domain, needed for privacy-preserving applications
such as DAA. Finally, our compiler is certifying, in the sense that it automatically
produces a formal proof of the soundness of the compiled protocol for a large
class of protocols using the Isabelle/HOL theorem prover. \n"
acknowledgement: |-
This work was in part funded by the European Community's Seventh Framework Programme (FP7) under grant agreement no. 216499.
A preliminary version of the compiler can be found at http://zkc.cace-project.eu.
alternative_title:
- LNCS
author:
- first_name: José
full_name: Almeida, José Bacelar
last_name: Almeida
- first_name: Endre
full_name: Bangerter, Endre
last_name: Bangerter
- first_name: Manuel
full_name: Barbosa, Manuel
last_name: Barbosa
- first_name: Stephan
full_name: Stephan Krenn
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Ahmad
full_name: Sadeghi, Ahmad-Reza
last_name: Sadeghi
- first_name: Thomas
full_name: Schneider, Thomas
last_name: Schneider
citation:
ama: 'Almeida J, Bangerter E, Barbosa M, Krenn S, Sadeghi A, Schneider T. A Certifying
Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols. In:
Gritzalis D, Preneel B, Theoharidou M, eds. Vol 6345. Springer; 2010:151-167.
doi:10.1007/978-3-642-15497-3'
apa: 'Almeida, J., Bangerter, E., Barbosa, M., Krenn, S., Sadeghi, A., & Schneider,
T. (2010). A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based
on Sigma-Protocols. In D. Gritzalis, B. Preneel, & M. Theoharidou (Eds.) (Vol.
6345, pp. 151–167). Presented at the ESORICS: European Symposium on Research in
Computer Security, Springer. https://doi.org/10.1007/978-3-642-15497-3'
chicago: Almeida, José, Endre Bangerter, Manuel Barbosa, Stephan Krenn, Ahmad Sadeghi,
and Thomas Schneider. “A Certifying Compiler for Zero-Knowledge Proofs of Knowledge
Based on Sigma-Protocols.” edited by Dimitris Gritzalis, Bart Preneel, and Marianthi
Theoharidou, 6345:151–67. Springer, 2010. https://doi.org/10.1007/978-3-642-15497-3.
ieee: 'J. Almeida, E. Bangerter, M. Barbosa, S. Krenn, A. Sadeghi, and T. Schneider,
“A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols,”
presented at the ESORICS: European Symposium on Research in Computer Security,
2010, vol. 6345, pp. 151–167.'
ista: 'Almeida J, Bangerter E, Barbosa M, Krenn S, Sadeghi A, Schneider T. 2010.
A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols.
ESORICS: European Symposium on Research in Computer Security, LNCS, vol. 6345,
151–167.'
mla: Almeida, José, et al. A Certifying Compiler for Zero-Knowledge Proofs of
Knowledge Based on Sigma-Protocols. Edited by Dimitris Gritzalis et al., vol.
6345, Springer, 2010, pp. 151–67, doi:10.1007/978-3-642-15497-3.
short: J. Almeida, E. Bangerter, M. Barbosa, S. Krenn, A. Sadeghi, T. Schneider,
in:, D. Gritzalis, B. Preneel, M. Theoharidou (Eds.), Springer, 2010, pp. 151–167.
conference:
name: 'ESORICS: European Symposium on Research in Computer Security'
date_created: 2018-12-11T12:00:40Z
date_published: 2010-08-30T00:00:00Z
date_updated: 2021-01-12T07:40:13Z
day: '30'
doi: 10.1007/978-3-642-15497-3
editor:
- first_name: Dimitris
full_name: Gritzalis, Dimitris
last_name: Gritzalis
- first_name: Bart
full_name: Preneel, Bart
last_name: Preneel
- first_name: Marianthi
full_name: Theoharidou, Marianthi
last_name: Theoharidou
extern: 1
intvolume: ' 6345'
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2010/339.pdf
month: '08'
oa: 1
page: 151 - 167
publication_status: published
publisher: Springer
publist_id: '3724'
quality_controlled: 0
status: public
title: A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols
type: conference
volume: 6345
year: '2010'
...
---
_id: '2980'
abstract:
- lang: eng
text: "Efficient zero-knowledge proofs of knowledge (ZK-PoK) are basic\n building
blocks of many practical cryptographic applications such as\n identification
schemes, group signatures, and secure multi-party\n computation (SMPC). Currently,
first applications that essentially\n rely on ZK-PoKs are being deployed in the
real world. The most\n prominent example is the Direct Anonymous Attestation
(DAA)\n protocol, which was adopted by the Trusted Computing Group (TCG) \n and
implemented as one of the functionalities of the cryptographic \n chip Trusted
Platform Module (TPM).\n\nImplementing systems using ZK-PoK turns out to be challenging,\n
\ since ZK-PoK are significantly more complex than standard crypto\n primitives
(e.g., encryption and signature schemes). As a result, \n the design-implementation
cycles of ZK-PoK are time-consuming\n and error-prone.\n\nTo overcome this, we
present a compiler with corresponding languages \n for the automatic generation
of sound and efficient ZK-PoK based on \n Σ-protocols. The protocol designer
using our compiler formulates \n the goal of a ZK-PoK proof in a high-level protocol
specification language,\n which abstracts away unnecessary technicalities from
the designer. The\n compiler then automatically generates the protocol implementation
in \n Java code; alternatively, the compiler can output a description of the
\n protocol in LaTeX which can be used for documentation or verification."
acknowledgement: This work was performed within the FP7 EU project CACE (Computer
Aided Cryptography Engineering).
alternative_title:
- LNCS
author:
- first_name: Endre
full_name: Bangerter, Endre
last_name: Bangerter
- first_name: Thomas
full_name: Briner, Thomas
last_name: Briner
- first_name: Wilko
full_name: Henecka, Wilko
last_name: Henecka
- first_name: Stephan
full_name: Stephan Krenn
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Ahmad
full_name: Sadeghi, Ahmad-Reza
last_name: Sadeghi
- first_name: Thomas
full_name: Schneider, Thomas
last_name: Schneider
citation:
ama: 'Bangerter E, Briner T, Henecka W, Krenn S, Sadeghi A, Schneider T. Automatic
Generation of Sigma-Protocols. In: Martinelli F, Preneel B, eds. Vol 6391. Springer;
2010:67-82. doi:10.1007/978-3-642-16441-5'
apa: 'Bangerter, E., Briner, T., Henecka, W., Krenn, S., Sadeghi, A., & Schneider,
T. (2010). Automatic Generation of Sigma-Protocols. In F. Martinelli & B.
Preneel (Eds.) (Vol. 6391, pp. 67–82). Presented at the EuroPKI: Public Key Infrastructures,
Services and Applications, Springer. https://doi.org/10.1007/978-3-642-16441-5'
chicago: Bangerter, Endre, Thomas Briner, Wilko Henecka, Stephan Krenn, Ahmad Sadeghi,
and Thomas Schneider. “Automatic Generation of Sigma-Protocols.” edited by Fabio
Martinelli and Bart Preneel, 6391:67–82. Springer, 2010. https://doi.org/10.1007/978-3-642-16441-5.
ieee: 'E. Bangerter, T. Briner, W. Henecka, S. Krenn, A. Sadeghi, and T. Schneider,
“Automatic Generation of Sigma-Protocols,” presented at the EuroPKI: Public Key
Infrastructures, Services and Applications, 2010, vol. 6391, pp. 67–82.'
ista: 'Bangerter E, Briner T, Henecka W, Krenn S, Sadeghi A, Schneider T. 2010.
Automatic Generation of Sigma-Protocols. EuroPKI: Public Key Infrastructures,
Services and Applications, LNCS, vol. 6391, 67–82.'
mla: Bangerter, Endre, et al. Automatic Generation of Sigma-Protocols. Edited
by Fabio Martinelli and Bart Preneel, vol. 6391, Springer, 2010, pp. 67–82, doi:10.1007/978-3-642-16441-5.
short: E. Bangerter, T. Briner, W. Henecka, S. Krenn, A. Sadeghi, T. Schneider,
in:, F. Martinelli, B. Preneel (Eds.), Springer, 2010, pp. 67–82.
conference:
name: 'EuroPKI: Public Key Infrastructures, Services and Applications'
date_created: 2018-12-11T12:00:40Z
date_published: 2010-10-25T00:00:00Z
date_updated: 2021-01-12T07:40:13Z
day: '25'
doi: 10.1007/978-3-642-16441-5
editor:
- first_name: Fabio
full_name: Martinelli, Fabio
last_name: Martinelli
- first_name: Bart
full_name: Preneel, Bart
last_name: Preneel
extern: 1
intvolume: ' 6391'
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2008/471.pdf
month: '10'
oa: 1
page: 67 - 82
publication_status: published
publisher: Springer
publist_id: '3723'
quality_controlled: 0
status: public
title: Automatic Generation of Sigma-Protocols
type: conference
volume: 6391
year: '2010'
...
---
_id: '2978'
abstract:
- lang: eng
text: |-
Efficient zero-knowledge proofs of knowledge for group homomorphisms are essential for numerous systems in applied cryptography. Especially, Σ-protocols for proving knowledge of discrete logarithms in known and hidden order groups are of prime importance. Yet, while these proofs can be performed very efficiently within groups of known order, for hidden order groups the respective proofs are far less efficient.
This paper shows strong evidence that this efficiency gap cannot be bridged. Namely, while there are efficient protocols allowing a prover to cheat only with negligibly small probability in the case of known order groups, we provide strong evidence that for hidden order groups this probability is bounded below by 1/2 for all efficient Σ-protocols not using common reference strings or the like.
We prove our results for a comprehensive class of Σ-protocols in the generic group model, and further strengthen them by investigating certain instantiations in the plain model.
alternative_title:
- LNCS
author:
- first_name: Endre
full_name: Bangerter, Endre
last_name: Bangerter
- first_name: Jan
full_name: Camenisch, Jan
last_name: Camenisch
- first_name: Stephan
full_name: Stephan Krenn
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
citation:
ama: 'Bangerter E, Camenisch J, Krenn S. Efficiency Limitations for Σ-Protocols
for Group Homomorphisms. In: Micciancio D, ed. Vol 5978. Springer; 2010:553-571.
doi:10.1007/978-3-642-11799-2'
apa: 'Bangerter, E., Camenisch, J., & Krenn, S. (2010). Efficiency Limitations
for Σ-Protocols for Group Homomorphisms. In D. Micciancio (Ed.) (Vol. 5978, pp.
553–571). Presented at the TCC: Theory of Cryptography Conference, Springer. https://doi.org/10.1007/978-3-642-11799-2'
chicago: Bangerter, Endre, Jan Camenisch, and Stephan Krenn. “Efficiency Limitations
for Σ-Protocols for Group Homomorphisms.” edited by Daniele Micciancio, 5978:553–71.
Springer, 2010. https://doi.org/10.1007/978-3-642-11799-2.
ieee: 'E. Bangerter, J. Camenisch, and S. Krenn, “Efficiency Limitations for Σ-Protocols
for Group Homomorphisms,” presented at the TCC: Theory of Cryptography Conference,
2010, vol. 5978, pp. 553–571.'
ista: 'Bangerter E, Camenisch J, Krenn S. 2010. Efficiency Limitations for Σ-Protocols
for Group Homomorphisms. TCC: Theory of Cryptography Conference, LNCS, vol. 5978,
553–571.'
mla: Bangerter, Endre, et al. Efficiency Limitations for Σ-Protocols for Group
Homomorphisms. Edited by Daniele Micciancio, vol. 5978, Springer, 2010, pp.
553–71, doi:10.1007/978-3-642-11799-2.
short: E. Bangerter, J. Camenisch, S. Krenn, in:, D. Micciancio (Ed.), Springer,
2010, pp. 553–571.
conference:
name: 'TCC: Theory of Cryptography Conference'
date_created: 2018-12-11T12:00:39Z
date_published: 2010-02-08T00:00:00Z
date_updated: 2021-01-12T07:40:12Z
day: '08'
doi: 10.1007/978-3-642-11799-2
editor:
- first_name: Daniele
full_name: Micciancio, Daniele
last_name: Micciancio
extern: 1
intvolume: ' 5978'
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2009/595.pdf
month: '02'
oa: 1
page: 553 - 571
publication_status: published
publisher: Springer
publist_id: '3725'
quality_controlled: 0
status: public
title: Efficiency Limitations for Σ-Protocols for Group Homomorphisms
type: conference
volume: 5978
year: '2010'
...