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 :)

  • 1
    $\begingroup$ It's Euler's number $e\approx 2.71828...$. $\endgroup$
    – Daniel S
    Commented Feb 24, 2023 at 12:46
  • $\begingroup$ @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? $\endgroup$
    – Rory
    Commented Feb 24, 2023 at 12:51
  • $\begingroup$ 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. $\endgroup$
    – Daniel S
    Commented Feb 24, 2023 at 14:37
  • 2
    $\begingroup$ 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}$. $\endgroup$
    – Mark Schultz-Wu
    Commented Feb 24, 2023 at 16:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.