What is this parameter? in Lyubashevsky's ID-scheme

Rory

2/24/24, 10:53 AM

I am studying Lybashevsky's ID-scheme from the article Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures(https://www.iacr.org/archive/asiacrypt2009/59120596/59120596.pdf) by Vadim Lybashevsky.

I am trying to work trough the soundness and completness of the ID-scheme through the four steps offered in section 3.1. In step 1 it is claimed that the completness (probability that an honest verifier is accepted) is $1/e$, but the parameter $e$ is not introduced nor explained at any point in the article. Is this simply referring to the soundness error (the probability that a malicious prover is able to convince an honest verifier)?

Any clues on what this $e$ is referring to and how to go forward with these steps would be much appreciated :)

0 + 4

zero-knowledge-proofs

lattice-crypto

soundness

completeness

Daniel S

2/24/24, 12:46 PM

It's Euler's number $e\approx 2.71828...$.

Rory

2/24/24, 12:51 PM

@DanielS thank you for the response. Do you know why this would be Euler's number or if this is commonly used that way within cryptography?

Daniel S

2/24/24, 2:37 PM

It's a common proportion to crop up in parameter selection where you have $m$ criteria to meet and each criterion has an independent, roughly $1-1/m$ chance of being met.

Mark

2/24/24, 4:36 PM

perhaps to make the justification more obvious, one can show that $\lim_{m\to\infty}\left(1+\frac{k}{m}\right)^m = e^k$ for any $k$. In particular, for $k = -1$ and large enough $m$ you expect $\left(1-\frac{1}{m}\right)^m\approx e^{-1}$.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: What is this parameter? in Lyubashevsky's ID-scheme

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.