Report on Present State ofESIGN Signature Evaluation(full evaluation)
January 28, 2002
Yasuyuki Sakai, Member
Public-Key Cryptography
Subcommittee
1

ESIGN signature(One of the signature schemes included in the guidelines
for electronic signature law)
• Category: Signature• Security basis:
It is difficult to solve n=p2q type factoring problems;AER (approximate e-th root) problems are difficult• Provable security:
ESIGN, which is included in the guidelines for electronic signature law, uses
the assumption that AER (approximate e-th root) problems are difficult. At
the present time there is no proof with this assumption that existential
forgeries are infeasible under adaptive chosen message attacks, even if arandom oracle hash function is used.

• Implementability characteristics :ESIGN’s signature generation is faster than that of RSA signatures.

• SW implementation information :Key generation: 610ms, signature generation: 1.04ms,signature verification: 0.70ms( |n|=1152, e=1024, SHA-1 used, Celeron 800MHz, included in self-evaluation)
2

ESIGN signature versions
ESIGN has been submitted or presented on seven occasions(the main ones are listed below).

Recommended parameter Encode
Guidelines for electronic
signature law|n| ≥ 1024, e ≥ 8CRYPTREC2001|n| ≥ 1152, e ≥ 1024

CRYPTREC2000|n| ≥ 960, e ≥ 8IEEE P1363a

No specifications (P1363 policy)

NESSIE(changes planned asshown on right)|n| ≥ 1152, e ≥ 1024

EMSA

Provable security
None (now evaluating todetermine whether there
is an efficient attackmethod)

No specifications (primitive proposal only)

EMSA5Yes (n=p2q type factoring
assumption, approximate e-throot assumption, random oracle
model, existential unforgeability
under adaptive chosen messageattacks)

3

Full evaluation policy• ESIGN is being evaluated from the following
perspectives– Primitive evaluation:
Difficulty of AER (approximate e-th root) problems– Scheme evaluation:
Recommended parameters in guidelines for electronic
signature law :Security of |n| ≥ 1024, e ≥ 8
Security of recommended parameters at otherstandardizing organizations– Other issues
4Evaluation comments:
AER (approximate e-th root) problems• If e=2:
AER problems can be solved using the method of Brickell et al[Crypto95] or the method of Vallee et al [Eurocrypt88](use LLL algorithm to solve for lower-degree modularpolynomials), as well as Coppersmith’s method [Eurocrypt96],
which is a refinement of the above.
• If e=3:
The above methods can be extended to apply to cases where e=3.
• If e ≥ 4:
The claim that there are no known efficient solutions to AER
problems is satisfactory.
5

Evaluation comments: Encoding (1/2)
ESIGN using EMSA Encoding (no provable security)(This ESIGN version is included in the guidelines for electronic signature law )• An external evaluator claims to have discovered a new attack method(forgery; the legitimacy of this claim has not been verified). If theevaluator’s claim is correct and the attack is used when the hash function
output is 160 bits (SHA-1), then forgeries would be successful with a nonnegligible probability in cases such as the following.
(1) |n|=1024 and e=4(2) |n|=2048 and e=7(3) |n|=2048 and e=8• The new attack discovered by this evaluator does not threaten security whene=1024 (according to the evaluator).
6

Evaluation comments: Encoding (2/2)
ESIGN using EMSA5 Encoding (provable security)(IEEE P1363a, NESSIE)

Under the assumption that AER (approximatee-th root) problems are difficult, satisfactory
proof is offered that existential forgeries areinfeasible (security in the strongest sense)
under adaptive chosen message attacks when arandom oracle is used.

7